Brainf*ck decorder

BrainfuckDecorder.scala

// 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(">,[>,]<<[<]>[.>]")

BrainFu*kプログラム評価器の簡潔な実装。

ParseResult[T]を抽象構文木と位置づけ、木の走査(Visitorパターン)はmap(^^), flatMap(>>)側で記述。

Parser[T]モナドを用いることでパースと実行の独立性を適度に保って全体をコンパクトに纏め上げることに成功しており、OOPではパースと構文木と走査がそれぞれ異なるドメインとして実装され見通しが悪かった点が改善されている。

ただし、ループに関してはパースと走査の両方の性質を持つために明確に分離して記述する訳にはいかず、少々実装が複雑になってしまった感がある。