ScalaでBrainf*ckインタープリタを実装してみた

ScalaでBrainf*ckのインタプリタを書いてみたよ - 都元ダイスケ IT-PRESS
Scalaを頑張っておるようなので、私もBrainf*ckのインタープリタをなんとなく実装してみた。

BrainfuckRuntimeと、Expression系のクラスが関数型らしくないのでなんとかしたいな...。
ソースはgithubにあげてます。ツッコミ or フォーク歓迎 https://github.com/j5ik2o/brainfuck-scala
とりあえず、nullチェックとか、例外処理は適当です。

package com.github.j5ik2o.brainfuck

object BrainfuckApplication {

  def main(args: Array[String]) =
    try {
      new BrainfuckRuntime(new BrainfuckParser).execute(args(0))
    } catch {
      case BrainfuckException(msg) => println(msg)
    }

}

以下のように実行するとHello World!が表示されるはず。

$ scala com.github.j5ik2o.brainfuck.BrainfuckApplication "++++++++++[>++++++++++<-]>++++.+++++++.--------.--."

以下、パーサーとランタイムのソース。

package com.github.j5ik2o.brainfuck

case class BrainfuckException(msg:String) extends RuntimeException

class BrainfuckRuntime(parser: BrainfuckParser, size: Int) {
  require(size > 0)

  val memory = Array.fill(size)(0)

  var pointer = 0

  var counter = 0

  val evaluator = new Evaluator()

  def this(parser: BrainfuckParser) = this (parser, 3000)

  // Brainfuckのスクリプトを実行する
  def execute(script: String) {
    val parseResult = parser.parse(script)
    if (parseResult.successful) {
      evaluateExpressions(parseResult.get)
      println
    } else {
      throw new BrainfuckException("parse error")
    }
  }

  // ASTを評価するビジター
  class Evaluator extends ExpressionVisitor {

    override def visit(expression: Expression): Unit = expression match {
      case IncrementPointerExpression() => incrementPointer
      case DecrementPointerExpression() => decrementPointer
      case IncrementMemoryAtPointerExpression() => incrementMemoryAtPointer
      case DecrementMemoryAtPointerExpression() => decrementMemoryAtPointer
      case OutputMemoryAtPointerExpression() => outputMemoryAtPointer
      case LoopExpression(expressions: List[Expression]) => loop(expressions)
    }

  }

  // 以下、ランタイムが持つAPI

  private def validateRange =
    if (counter > size) throw new BrainfuckException("limit over")

  private def readMemory = {
    validateRange
    memory(pointer)
  }

  private def writeMemory(b: Int) = {
    validateRange
    memory(pointer) = b
  }


  private def incrementPointer {
    validateRange
    pointer += 1
    counter += 1
  }

  private def decrementPointer {
    validateRange
    pointer -= 1
    counter += 1
  }

  private def incrementMemoryAtPointer {
    writeMemory(readMemory + 1)
  }

  private def decrementMemoryAtPointer {
    writeMemory(readMemory - 1)
  }

  private def outputMemoryAtPointer {
    print(readMemory.toChar)
  }

  private def loop(expressions: List[Expression]) {
    while (readMemory != 0) {
      evaluateExpressions(expressions)
    }
  }

  private def evaluateExpressions(expressions: List[Expression]) {
    expressions.foreach(_.accept(evaluator))
  }


}

Scalaのパーサコンビネータを使って実装しているので、以下のURLを読むとコードを理解しやすいと思います。
http://www.coins.tsukuba.ac.jp/~i021216/Scala-parser-combinator.pdf

package com.github.j5ik2o.brainfuck

import util.parsing.combinator._

// 式を訪問するビジター
trait ExpressionVisitor {
  def visit(e: Expression): Unit
}

// 式を表すトレイト
trait Expression {
  def accept(visitor: ExpressionVisitor): Unit = {
    visitor.visit(this)
  }
}

// 式の実装 これを使ってASTを構築する
case class IncrementPointerExpression extends Expression
case class DecrementPointerExpression extends Expression
case class IncrementMemoryAtPointerExpression extends Expression
case class DecrementMemoryAtPointerExpression extends Expression
case class OutputMemoryAtPointerExpression extends Expression
case class LoopExpression(expressions:List[Expression]) extends Expression

// Brainfuckパーサ
class BrainfuckParser extends JavaTokenParsers {

  def parse(source:String) = parseAll(brainfuck, source)

  def brainfuck: Parser[List[Expression]] = rep(instruction)

  def instruction: Parser[Expression] = loop | token

  def token: Parser[Expression] = incrementPointer ||| decrementPointer |||
    incrementMemoryAtPointer ||| decrementMemoryAtPointer ||| outputMemoryAtPointer

  def incrementPointer: Parser[Expression] = ">" ^^ {
    case ops => IncrementPointerExpression()
  }

  def decrementPointer: Parser[Expression] = "<" ^^ {
    case ops => DecrementPointerExpression()
  }

  def incrementMemoryAtPointer: Parser[Expression] = "+" ^^ {
    case ops => IncrementMemoryAtPointerExpression()
  }

  def decrementMemoryAtPointer: Parser[Expression] = "-" ^^ {
    case ops => DecrementMemoryAtPointerExpression()
  }

  def outputMemoryAtPointer: Parser[Expression] = "." ^^ {
    case ops => OutputMemoryAtPointerExpression()
  }

  def loop: Parser[Expression] = "["~>brainfuck<~"]" ^^ {
    case exprs => LoopExpression(exprs)
  }

}