Brainfuck und der implizite Schweinezyklus


Mit etwas mehr Scala-Erfahrung habe ich meinen kleinen Brainfuck-Interpreter nochmal nachbearbeitet, und habe dabei eine einfache, aber interessante Beobachtung gemacht. Ich hatte ja schon im ersten Artikel geschrieben, dass ich den Typ des Speicher-Bands flexibel lassen will. Alle dafür benötigten Operationen stecken im Trait Func:

trait Func[T] {
    val zero: T
    def inc(t: T): T
    def dec(t: T): T
    def in: T
    def out(t: T): Unit
}

Wenn das Band wie im „Brainfuck-Sprachstandard“ mit Bytes gefüllt sein soll, kann man das Trait so implementieren:

object ByteFunc extends Func[Byte] {
  override val zero: Byte = 0
  override def inc(t: Byte) = ((t + 1) & 0xFF).toByte
  override def dec(t: Byte) = ((t - 1) & 0xFF).toByte
  override def in: Byte = readByte
  override def out(t: Byte) { print(t.toChar) }
}

Nun muss man dem Band so eine Implementierung irgendwie mitgeben. In meiner alten Version wurde das über einen ganz normalen Parameter erledigt, diesmal entschied ich mich für einen impliziten Parameter:

case class Tape[T](left: List[T], cell: T, right: List[T])(implicit func: Func[T]) {
  private def headOf(list:List[T]) = if (list.isEmpty) func.zero else list.head
  private def tailOf(list:List[T]) = if (list.isEmpty) Nil else list.tail
  def isZero = cell == func.zero
  def execute(ch: Char) = ch match {
   case '+' => copy(cell = func.inc(cell))
   case '-' => copy(cell = func.dec(cell))
   case '<' => Tape(tailOf(left), headOf(left), cell :: right)
   case '>' => Tape(cell :: left, headOf(right), tailOf(right))
   case '.' => func.out(cell); this
   case ',' => copy(cell = func.in)
   case '[' | ']' => this
   case _ => error("Unexpected token: " + ch)
  }
}

object Tape {
  def empty[T](func: Func[T]) = Tape(Nil, func.zero, Nil)(func)
}

In der empty-Methode des Tape-Objekts gebe ich den impliziten Parameter „func“ explizit mit. Der Witz ist jetzt, dass sich dieser implizite Parameter sozusagen automatisch „weitervererbt“: Wenn ich in der Fallklasse Tape ein neues Tape erzeuge, brauche ich func nicht zu erwähnen, der implizite Konstruktor-Parameter der aktuellen Klasse fungiert wie ein implizites Objekt, wird also vom Konstruktor des zu erzeugenden Objekts gefunden. Bisher ist mir dieses Verhalten noch nicht aufgefallen.
Die neue Implementierung „hört“ in der Methode execute direkt auf Chars, statt für alle Operationen eigene Methoden bereitzustellen. Als Konsequenz schrumpelt der Interpreter auf ein paar Zeilen zusammen:

import scala.annotation._

class Brainfuck[T](func:Func[T]) {

  def execute(p: String) {
    val prog = p.replaceAll("[^\\+\\-\\[\\]\\.\\,\\>\\<]", "")

    @tailrec def braceMatcher(pos: Int, stack: List[Int], o2c: Map[Int, Int]): Map[Int,Int] =
      if(pos == prog.length) o2c else (prog(pos): @switch) match {
        case '[' => braceMatcher(pos + 1, pos :: stack, o2c)
        case ']' => braceMatcher(pos + 1, stack.tail, o2c + (stack.head -> pos))
        case _ => braceMatcher(pos + 1, stack, o2c)
      }

    val open2close = braceMatcher(0, Nil, Map())
    val close2open = open2close.map(_.swap)

    @tailrec def ex(pos:Int, tape:Tape[T]):Unit = 
      if(pos < prog.length) ex((prog(pos): @switch) match {
          case '[' if tape.isZero => open2close(pos)
          case ']' if ! tape.isZero => close2open(pos)
          case _ => pos + 1
        }, tape.execute(prog(pos)))

    println("---running---")
    ex(0, Tape.empty(func))
    println("\n---done---")
  }
}

Anzumerken ist, dass ich in der alten Version das Finden zugehöriger Klammern absolut umständlich gelöst hatte. In der neuen Version scannt der Interpreter vor der Ausführung einmal durch das ganze Programm und merkt sich alle Klammerpaare in zwei Maps (von der öffnenden zur schließenden und umgekehrt), was nicht nur einfacher, sondern vor allem viel effizienter ist. Die Hauptschleife ist dank dieser Idee und der besseren Zusammenarbeit mit Tape auf gerade mal sechs Zeilen zusammengeschrumpft.

Fehlt nur noch das obligatorische „Hello World“:

    val bf = new Brainfuck(ByteFunc)
    bf.execute(""">+++++++++[<++++++++>-]<.>+++++++[<++
                  ++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]
                  <.#>+++++++++++[<+++++>-]<.>++++++++[<++
                  +>-]<.+++.------.--------.[-]>++++++++[<++++>
                  -]<+.[-]++++++++++.""")
//--> ---running---
//--> Hello World!
//-->
//--> ---done---

Ich finde, die neue Implementierung besitzt eine gewisse Eleganz und ist leichter zu verstehen als die alte. Oder zumindest einfacher als das „Hello World“ in Brainfuck…

Nachtrag
Ich fühle mich geehrt, dass mein kleiner Schnipsel als ein Code-Beispiel für die offizielle Scala-Seite angenommen wurde.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s