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)
}
}
![日経ソフトウエア 2011年 06月号 [雑誌]](http://ecx.images-amazon.com/images/I/61HeZFMnexL._SL160_.jpg "日経ソフトウエア 2011年 06月号 [雑誌]")
![Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)](http://ecx.images-amazon.com/images/I/41nFY0KbnfL._SL160_.jpg "Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)")
