Created
July 13, 2012 03:09
-
-
Save tonosaman/3102437 to your computer and use it in GitHub Desktop.
Brainf*ck decorder
This file contains 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
// Brainf*ck decorder | |
// usage: | |
// $ scala <thisfile> | |
object BrainfuckDecorder extends util.parsing.combinator.RegexParsers { | |
val memory = collection.mutable.Map.empty[Int, Int].withDefaultValue(0) | |
var pointer = 0 | |
def read = memory(pointer) | |
def write(x: Int) = memory(pointer) = x | |
override val whiteSpace = """[^><+-.,\[\]]+""".r | |
def exec(in: String): ParseResult[Unit] = parseAll(exprs, in) | |
def exprs: Parser[Unit] = (incPtr | decPtr | incMem | decMem | output | input | loop).* ^^ { _ => } | |
def incPtr = ">" ^^ { _ => pointer += 1 } | |
def decPtr = "<" ^^ { _ => pointer -= 1 } | |
def incMem = "+" ^^ { _ => write(read + 1) } | |
def decMem = "-" ^^ { _ => write(read - 1) } | |
def output = "." ^^ { _ => print(read.toChar) } | |
def input = "," ^^ { _ => | |
if (!Console.in.ready) print("Brainf*ck (Ctrl-D to end): ") | |
Console.in.read.toChar match { | |
case '\u0004' => write(0); println | |
case c => write(c) | |
} | |
} | |
def loop = "[" ~> LoopParser <~ "]" | |
object LoopParser extends Parser[Unit] { | |
@scala.annotation.tailrec | |
def apply(in: Input): ParseResult[Unit] = | |
if (memory(pointer) == 0) | |
seekLoopEnd(in) match { | |
case Right(offset) => Success(Unit, in.drop(offset - in.offset)) | |
case Left(offset) => Failure("] expected", in.drop(offset - in.offset)) | |
} | |
else | |
exprs(in) match { | |
case ns: NoSuccess => ns | |
case Success(_, _) => apply(in) | |
} | |
@scala.annotation.tailrec | |
def seekLoopEnd(in: Input, depth: Int=1): Either[Int, Int] = | |
(depth + Map('[' -> 1, ']' -> -1).getOrElse(in.first, 0)) match { | |
case 0 => Right(in.offset) | |
case depth => if (in.atEnd) Left(in.offset) else seekLoopEnd(in.rest, depth) | |
} | |
} | |
} | |
def encode_brainfuck_echo(s: String, rep: Int) = | |
s.flatMap("+" * _.toInt + ">") + "+" * rep + "[" + "<" * s.length + ".>" * s.length + "-]" | |
BrainfuckDecorder.exec(encode_brainfuck_echo("hoge\n", 3)) | |
// Brainfuck echo back program | |
BrainfuckDecorder.exec(">,[>,]<<[<]>[.>]") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
BrainFu*kプログラム評価器の簡潔な実装。
ParseResult[T]を抽象構文木と位置づけ、木の走査(Visitorパターン)はmap(^^), flatMap(>>)側で記述。
Parser[T]モナドを用いることでパースと実行の独立性を適度に保って全体をコンパクトに纏め上げることに成功しており、OOPではパースと構文木と走査がそれぞれ異なるドメインとして実装され見通しが悪かった点が改善されている。
ただし、ループに関してはパースと走査の両方の性質を持つために明確に分離して記述する訳にはいかず、少々実装が複雑になってしまった感がある。