Last active
March 19, 2026 22:06
-
-
Save halotukozak/84549e0491b629d42885dcf60ec73a08 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //> using scala "3.8.2" | |
| //> using jvm 21 | |
| //> using dep "io.github.halotukozak::alpaca:0.1.0" | |
| //> using option -experimental | |
| //> using option -Yretain-trees | |
| import alpaca.* | |
| import scala.collection.mutable | |
| case class BrainLexContext(var brackets: Int = 0, var squareBrackets: Int = 0) extends LexerCtx | |
| val BrainLexer = lexer[BrainLexContext]: | |
| case ">" => Token["next"] | |
| case "<" => Token["prev"] | |
| case "\\+" => Token["inc"] | |
| case "-" => Token["dec"] | |
| case "\\." => Token["print"] | |
| case "," => Token["read"] | |
| case "\\[" => | |
| ctx.squareBrackets += 1 | |
| Token["jumpForward"] | |
| case "\\]" => | |
| require(ctx.squareBrackets > 0, "Mismatched brackets") | |
| ctx.squareBrackets -= 1 | |
| Token["jumpBack"] | |
| case name@"[A-Za-z]+" => | |
| Token["functionName"](name) | |
| case "\\(" => | |
| ctx.brackets += 1 | |
| Token["functionOpen"] | |
| case "\\)" => | |
| require(ctx.brackets > 0, "Mismatched brackets") | |
| ctx.brackets -= 1 | |
| Token["functionClose"] | |
| case "!" => Token["functionCall"] | |
| case "." => Token.Ignored | |
| case "\n" => Token.Ignored | |
| class Memory( | |
| val underlying: Array[Int] = new Array(256), | |
| var pointer: Int = 0, | |
| val functions: mutable.Map[String, List[BrainAST]] = mutable.Map.empty, | |
| ) | |
| enum BrainAST: | |
| case Root(ops: List[BrainAST]) | |
| case While(ops: List[BrainAST]) | |
| case FunctionDef(name: String, ops: List[BrainAST]) | |
| case FunctionCall(name: String) | |
| case Next, Prev, Inc, Dec, Print, Read | |
| def eval(mem: Memory): Unit = this match | |
| case BrainAST.Root(ops) => ops.foreach(_.eval(mem)) | |
| case BrainAST.Next => mem.pointer = (mem.pointer + 1) & 0xff | |
| case BrainAST.Prev => mem.pointer = (mem.pointer - 1) & 0xff | |
| case BrainAST.Inc => mem.underlying(mem.pointer) = (mem.underlying(mem.pointer) + 1) & 0xff | |
| case BrainAST.Dec => mem.underlying(mem.pointer) = (mem.underlying(mem.pointer) - 1) & 0xff | |
| case BrainAST.Print => print(mem.underlying(mem.pointer).toChar) | |
| case BrainAST.Read => mem.underlying(mem.pointer) = scala.io.StdIn.readChar() & 0xff | |
| case BrainAST.While(ops) => while mem.underlying(mem.pointer) != 0 do ops.foreach(_.eval(mem)) | |
| case BrainAST.FunctionDef(name, ops) => mem.functions += (name -> ops) | |
| case BrainAST.FunctionCall(name) => mem.functions(name).foreach(_.eval(mem)) | |
| case class BrainParserCtx(functions: mutable.Set[String] = mutable.Set.empty) extends ParserCtx | |
| object BrainParser extends Parser[BrainParserCtx]: | |
| val root: Rule[BrainAST] = rule: | |
| case Operation.List(stmts) => BrainAST.Root(stmts) | |
| val While: Rule[BrainAST] = rule: | |
| case (BrainLexer.jumpForward(_), Operation.List(stmts), BrainLexer.jumpBack(_)) => BrainAST.While(stmts) | |
| val FunctionDef: Rule[BrainAST] = rule { | |
| case (BrainLexer.functionName(name), BrainLexer.functionOpen(_), Operation.List(ops), BrainLexer.functionClose(_)) => | |
| require(ctx.functions.add(name.value), s"Function ${name.value} is already defined") | |
| BrainAST.FunctionDef(name.value, ops) | |
| } | |
| val FunctionCall: Rule[BrainAST] = rule { case (BrainLexer.functionName(name), BrainLexer.functionCall(_)) => | |
| require(ctx.functions.contains(name.value), s"Function ${name.value} is not defined") | |
| BrainAST.FunctionCall(name.value) | |
| } | |
| val Operation: Rule[BrainAST] = rule( | |
| { case BrainLexer.next(_) => BrainAST.Next }, | |
| { case BrainLexer.prev(_) => BrainAST.Prev }, | |
| { case BrainLexer.inc(_) => BrainAST.Inc }, | |
| { case BrainLexer.dec(_) => BrainAST.Dec }, | |
| { case BrainLexer.print(_) => BrainAST.Print }, | |
| { case BrainLexer.read(_) => BrainAST.Read }, | |
| { case While(whl) => whl }, | |
| { case FunctionDef(fdef) => fdef }, | |
| { case FunctionCall(call) => call }, | |
| ) | |
| @main | |
| def main(): Unit = | |
| // Undefined function is now caught at parse time | |
| try | |
| val (_, badTokens) = BrainLexer.tokenize("bar!") | |
| BrainParser.parse(badTokens) | |
| catch case e: IllegalArgumentException => | |
| println(s"Caught at parse time: ${e.getMessage}") | |
| println("---") | |
| // Duplicate definition is also caught | |
| try | |
| val (_, dupTokens) = BrainLexer.tokenize("foo(+)foo(++)") | |
| BrainParser.parse(dupTokens) | |
| catch case e: IllegalArgumentException => | |
| println(s"Caught at parse time: ${e.getMessage}") | |
| println("---") | |
| // Hello World still works | |
| val (ctx, result) = BrainLexer.tokenize( | |
| "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.", | |
| ) | |
| require(ctx.squareBrackets == 0, "Mismatched brackets") | |
| val (_, ast) = BrainParser.parse(result) | |
| ast.nn.eval(new Memory()) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //> using scala "3.8.2" | |
| //> using jvm 21 | |
| //> using dep "io.github.halotukozak::alpaca:0.1.0" | |
| //> using dep "org.scalameta::munit:1.2.4" | |
| //> using option -experimental | |
| //> using option -Yretain-trees | |
| import alpaca.parse | |
| class LexerTest extends munit.FunSuite: | |
| private def tokenize(input: String) = | |
| val (ctx, tokens) = BrainLexer.tokenize(input) | |
| require(ctx.brackets == 0 && ctx.squareBrackets == 0, "Mismatched brackets") | |
| (ctx, tokens) | |
| test("tokenize basic operators") { | |
| val (_, tokens) = tokenize("><+-.,") | |
| assert(tokens.map(_.name) == List("next", "prev", "inc", "dec", "print", "read")) | |
| } | |
| test("tokenize brackets") { | |
| val (ctx, tokens) = tokenize("[>+<-]") | |
| assert(ctx.squareBrackets == 0) | |
| assert(tokens.map(_.name) == List("jumpForward", "next", "inc", "prev", "dec", "jumpBack")) | |
| } | |
| test("mismatched closing bracket") { | |
| intercept[IllegalArgumentException] { | |
| tokenize("]") | |
| } | |
| } | |
| test("tokenize function syntax") { | |
| val (ctx, tokens) = tokenize("foo(++)") | |
| assert(ctx.brackets == 0) | |
| assert(tokens.map(_.name) == List("functionName", "functionOpen", "inc", "inc", "functionClose")) | |
| } | |
| test("tokenize function call") { | |
| val (_, tokens) = tokenize("foo!") | |
| assert(tokens.map(_.name) == List("functionName", "functionCall")) | |
| } | |
| test("ignore whitespace and unknown chars") { | |
| val (_, tokens) = tokenize("+ +\n+") | |
| assert(tokens.map(_.name) == List("inc", "inc", "inc")) | |
| } | |
| class ParserTest extends munit.FunSuite: | |
| private def parse(input: String): BrainAST = | |
| val (_, tokens) = BrainLexer.tokenize(input) | |
| val (_, ast) = BrainParser.parse(tokens) | |
| ast.nn | |
| test("parse basic operations") { | |
| val ast = parse("><+-.,") | |
| assert(ast == BrainAST.Root(List(BrainAST.Next, BrainAST.Prev, BrainAST.Inc, BrainAST.Dec, BrainAST.Print, BrainAST.Read))) | |
| } | |
| test("parse empty program") { | |
| val ast = parse("") | |
| assert(ast == BrainAST.Root(List.empty)) | |
| } | |
| test("parse while loop") { | |
| val ast = parse("[>+<-]") | |
| assert(ast == BrainAST.Root(List(BrainAST.While(List(BrainAST.Next, BrainAST.Inc, BrainAST.Prev, BrainAST.Dec))))) | |
| } | |
| test("parse nested loops") { | |
| val ast = parse("[>[+]-]") | |
| assert(ast == BrainAST.Root(List(BrainAST.While(List(BrainAST.Next, BrainAST.While(List(BrainAST.Inc)), BrainAST.Dec))))) | |
| } | |
| test("parse function definition") { | |
| val ast = parse("foo(++)") | |
| assert(ast == BrainAST.Root(List(BrainAST.FunctionDef("foo", List(BrainAST.Inc, BrainAST.Inc))))) | |
| } | |
| test("parse function definition and call") { | |
| val ast = parse("foo(++)foo!") | |
| assert( | |
| ast == | |
| BrainAST.Root(List(BrainAST.FunctionDef("foo", List(BrainAST.Inc, BrainAST.Inc)), BrainAST.FunctionCall("foo"))), | |
| ) | |
| } | |
| class EvalTest extends munit.FunSuite: | |
| private def run(input: String): Memory = | |
| val (_, tokens) = BrainLexer.tokenize(input) | |
| val (_, ast) = BrainParser.parse(tokens) | |
| val mem = new Memory() | |
| ast.nn.eval(mem) | |
| mem | |
| test("increment") { | |
| val mem = run("+++") | |
| assert(mem.underlying(0) == 3) | |
| } | |
| test("decrement") { | |
| val mem = run("+++-") | |
| assert(mem.underlying(0) == 2) | |
| } | |
| test("move pointer") { | |
| val mem = run("+++>++>+") | |
| assert(mem.underlying(0) == 3) | |
| assert(mem.underlying(1) == 2) | |
| assert(mem.underlying(2) == 1) | |
| assert(mem.pointer == 2) | |
| } | |
| test("move pointer back") { | |
| val mem = run(">+++<++") | |
| assert(mem.underlying(0) == 2) | |
| assert(mem.underlying(1) == 3) | |
| assert(mem.pointer == 0) | |
| } | |
| test("simple loop - clear cell") { | |
| val mem = run("+++++[-]") | |
| assert(mem.underlying(0) == 0) | |
| } | |
| test("loop - multiply") { | |
| val mem = run("+++++[>+++<-]") | |
| assert(mem.underlying(0) == 0) | |
| assert(mem.underlying(1) == 15) | |
| } | |
| test("nested loops") { | |
| val mem = run("++[>++[>+++<-]<-]") | |
| assert(mem.underlying(2) == 12) | |
| } | |
| private def runAndCapture(input: String): (Memory, String) = | |
| val (_, tokens) = BrainLexer.tokenize(input) | |
| val (_, ast) = BrainParser.parse(tokens) | |
| val mem = new Memory() | |
| val out = new java.io.ByteArrayOutputStream() | |
| Console.withOut(out) { ast.nn.eval(mem) } | |
| (mem, out.toString) | |
| test("print character") { | |
| val (_, output) = runAndCapture("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.") | |
| assert(output == "H") | |
| } | |
| test("hello world") { | |
| val (_, output) = runAndCapture( | |
| "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.", | |
| ) | |
| assert(output == "Hello World!\n") | |
| } | |
| test("function definition registers in memory") { | |
| val mem = run("foo(+++)") | |
| assert(mem.functions.contains("foo")) | |
| } | |
| test("function call executes body") { | |
| val mem = run("foo(+++)foo!") | |
| assert(mem.underlying(0) == 3) | |
| } | |
| test("function call multiple times") { | |
| val mem = run("foo(+++)foo!foo!") | |
| assert(mem.underlying(0) == 6) | |
| } | |
| test("function with pointer movement") { | |
| val mem = run("foo(>+++)foo!foo!") | |
| assert(mem.underlying(1) == 3) | |
| assert(mem.underlying(2) == 3) | |
| assert(mem.pointer == 2) | |
| } | |
| test("undefined function call fails at parse time") { | |
| intercept[IllegalArgumentException] { | |
| run("bar!") | |
| } | |
| } | |
| test("duplicate function definition fails at parse time") { | |
| intercept[IllegalArgumentException] { | |
| run("foo(+)foo(++)") | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment