Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BrainF**k interpreter by Scala (confirmed by 2.10.2)
import scala.annotation.tailrec
object BF {
class Parser(val str: String) {
val cmap = Map(
">" -> 'pinc,
"<" -> 'pdec,
"+" -> 'inc,
"-" -> 'dec,
"." -> 'out,
"," -> 'inp,
"[" -> 'jmp,
"]" -> 'ret)
val parser = s"""[${cmap.keys.map(s => "\\" + s).mkString("|")}]""".r
def parse: List[Symbol] = {
parser.findAllIn(str).map(s => cmap.getOrElse(s, 'err)).toList
}
}
class Machine(val coms: List[Symbol]) {
val commands = coms.zipWithIndex.map(c => (c._2, c._1)) // e.g. (1, 'inc), (2, 'inc), ...
val comMap = commands.toMap // e.g. (1 -> 'inc, 2 -> 'inc, ...)
val jumpMap = parseJump(commands) // e.g. (9 -> 41, 41 -> 9)
def execute: String = {
stepExecute(1, 0, 0, Map(), "")
}
private def parseJump(coms: List[(Int, Symbol)]): Map[Int, Int] = {
val sj = coms.collect { case (c, 'jmp) => c }
val ej = coms.collect { case (c, 'ret) => c }.reverse
if (sj.length != ej.length) throw new Exception("jump couples invalid")
sj.zip(ej).toMap ++ ej.zip(sj).toMap
}
@tailrec
private def stepExecute(
step: Int, // step index (for debug)
cindex: Int, // command index
pindex: Int, // pointer index
buf: Map[Int, Int], // value buffer
result: String): String = {
comMap.getOrElse(cindex, 'fin) match {
case 'fin => result
case 'pinc => stepExecute(step + 1, cindex + 1, pindex + 1, buf, result)
case 'pdec => stepExecute(step + 1, cindex + 1, pindex - 1, buf, result)
case 'inc => stepExecute(step + 1, cindex + 1, pindex, increment(pindex, buf), result)
case 'dec => stepExecute(step + 1, cindex + 1, pindex, decrement(pindex, buf), result)
case 'out => stepExecute(step + 1, cindex + 1, pindex, buf, result + output(pindex, buf))
case 'inp => stepExecute(step + 1, cindex + 1, pindex, buf, result) // skip
case 'jmp => stepExecute(step + 1, jumpTo(cindex, pindex, buf), pindex, buf, result)
case 'ret => stepExecute(step + 1, returnTo(cindex, pindex, buf), pindex, buf, result)
case _ => throw new Exception("execute error")
}
}
private def bufValue(pindex: Int, buf: Map[Int, Int]): Int = {
buf.getOrElse(pindex, 0)
}
private def increment(pindex: Int, buf: Map[Int, Int]): Map[Int, Int] = {
buf + (pindex -> (bufValue(pindex, buf) + 1))
}
private def decrement(pindex: Int, buf: Map[Int, Int]): Map[Int, Int] = {
buf + (pindex -> (bufValue(pindex, buf) - 1))
}
private def output(pindex: Int, buf: Map[Int, Int]): String = {
bufValue(pindex, buf).toChar.toString
}
private def jumpTo(cindex: Int, pindex: Int, buf: Map[Int, Int]): Int = {
val bv = bufValue(pindex, buf)
jumpMap.get(cindex) match {
case Some(i) if bv == 0 => i
case Some(i) => cindex + 1
case None => throw new Exception("jump index error")
}
}
private def returnTo(cindex: Int, pindex: Int, buf: Map[Int, Int]): Int = {
val bv = bufValue(pindex, buf)
jumpMap.get(cindex) match {
case Some(i) if bv != 0 => i
case Some(i) => cindex + 1
case None => throw new Exception("jump index error")
}
}
}
def execute(str: String): String = {
val coms = new Parser(str).parse
val machine = new Machine(coms)
machine.execute
}
def main(args: Array[String]) = {
val hello = """+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+."""
val source = if (args.isEmpty) hello else args(0)
println(execute(source)) // => "Hello, world!"
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment