Brainfuck in Scala


Heute habe ich irgendwie keine Lust auf etwas ernsthaftes, also habe ich meinen kleinen Brainfuck-Interpreter ausgebuddelt. Brainfuck ist nichts schweinisches, sondern eine minimalistische turing-komplette Programmiersprache. Allerdings kostet es ganz schon Gehirnschmalz, darin etwas Vernünftiges zu progammieren – ich denke, ein Interpreter dafür ist leichter zu schreiben.

Meine Implementierung sollte möglichst flexibel sein, also z.B. sollte man einfach von einem „Band“ mit Bytes auf eines mit Ints umsteigen können. Das Band sollte (im Gegensatz zur Original-Definition) in beide Richtungen unendlich lang sein. Und natürlich alles wieder ohne veränderliche Datenstrukturen. Klingt schwierig, ist es aber nicht. Zuerst die Operationen, die man auf dem Band ausführen können muss:

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

trait 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) }
}

Alles sehr elementar, wie man sieht. Nun das Band selber, das schwieriger aussieht, als es eigentlich ist. Die Grundidee ist, das Band mit dem aktuellen Wert und zwei Listen zu repräsentieren. Angenomme, das Band sieht so aus:
1 2 3 4 [5] 6 7 8
Dann ist meine aktuelle Zelle 5, alles davor wird „rückwärts“ durch List(4,3,2,1) repräsentiert, alles danach durch List(6,7,8). Um einen Schritt zurückzugehen, füge ich meinen Wert 5 als Kopf der zweiten Liste an und mache den Kopf der ersten Liste zu meinem aktuellen Wert:
1 2 3 [4] 5 6 7 8. Komme ich ans Ende einer der Listen, liefere ich einfach Nullen.

class Tape[T](val cell:T, private val left:List[T], private val right:List[T], val func:Func[T]) {
    
    def inc = new Tape(func.inc(cell),left, right, func )
    def dec = new Tape(func.dec(cell),left, right, func)
    def goLeft = left match {
        case Nil => new Tape(func.zero,Nil, cell :: right, func)
        case head :: tail => new Tape(head, tail, cell :: right, func )
    }
    def goRight = right match {
        case Nil => new Tape(func.zero, cell:: left, Nil, func)
        case head :: tail => new Tape(head, cell :: left, tail, func)
    }
    def output = {
         func.out(cell)
         this
    }
    def input() = new Tape(func.in, left, right, func)
    def isZero = cell == func.zero
}

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

Voila, ein unendliches Band! Natürlich wird bei jeder Operation ein neues Band zurückgeliefert, aber das ist nicht so schlimm, wie es klingt: Da alle Datenstrukturen unveränderlich sind, können auch alle ihre Bestandteile wiederverwendet werden.

object Brainfuck {
   def execute(prog: String) {
       println("---running---")
       execute(prog.replaceAll("[^\\+\\-\\[\\]\\.\\,\\>\\<&#93;", ""), 0, Tape(new ByteFunc{}))
   }

    def execute(prog: String, pos:Int, tape:Tape&#91;Byte&#93;) {

        def closedBracePos(bPos:Int, count:Int):Int =
           if (count < 0 || bPos == prog.length)
              error ("Unbalanced braces")
           else prog.charAt(bPos) match {
               case '&#91;' => closedBracePos(bPos + 1, count + 1)
               case ']' =>  if (count == 0) bPos
                            else closedBracePos(bPos + 1, count - 1)
               case _ =>  closedBracePos(bPos + 1, count)
           }

        def openBracePos(bPos:Int, count:Int):Int =
           if (count < 0 || bPos < 0)
              error ("Unbalanced braces")
           else prog.charAt(bPos) match {
               case '&#93;' => openBracePos(bPos - 1, count + 1)
               case '[' =>  if (count == 0) bPos
                            else openBracePos(bPos - 1, count - 1)
               case _ =>  openBracePos(bPos - 1, count)
           }

        if(pos < prog.length) prog.charAt(pos) match {
          case '+' => execute(prog, pos + 1, tape.inc)
          case '-' => execute(prog, pos + 1, tape.dec)
          case '>' => execute(prog, pos + 1, tape.goRight)
          case '<' => execute(prog, pos + 1, tape.goLeft)
          case '.' => execute(prog, pos + 1, tape.output)
          case ',' => execute(prog, pos + 1, tape.input)
          case '[' => if (tape.isZero) execute(prog, closedBracePos(pos + 1, 0) + 1, tape)
                      else execute(prog, pos + 1, tape)
          case ']' => if (! tape.isZero) execute(prog, openBracePos(pos - 1, 0), tape)
                      else execute(prog, pos + 1, tape)
        } else {
          println("\n---done---")
        }
    }

   def main(args:Array[String]) {
       if (args.length == 1) execute(args(0))
       else println("First parameter must be a Brainfuck program")
   }
}

Der Interpreter ist ziemlich einfach: Das Brainfuck-Programm wird als String geladen. Zuerst werden alle Kommentare entfernt – Brainfuck betrachtet alle Zeichen, denen kein Befehl zugeordnet ist, als Kommentar. Danach wird mit einem neuen, leeren Band gestartet. Die schwierigste Aufgabe ist, die richtige öffnende Klammer zu einer schließenden Klammer zu finden (und umgekehrt), denn natürlich dürfen diese geschachtelt werden. Eckige Klammern dienen übrigens als Schleifenkonstrukt von Brainfuck.

Bleibt bloß noch, das Programm einmal auszuprobieren. Hier ein paar Anregungen:

//Hello World
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++
[<++++>-]<.#>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------. [-]>++++++++[<++++>-]<+.[-]++++++++++.""") //Die Zahlen von 9 bis 0 ++++++++++++++++++++++++++++++++[>+>+<<-] >>+++++++++++++++++++++++++<<++++++++++[>>.-<.<-] //ein Brainfuck-Quine //siehe http://de.wikipedia.org/wiki/Quine_(Computerprogramm) ->+>+++>>+>++>+>+++>>+>++>>>+>+>+>++>+>>>>+++>+>>++>+>+++
>>++>++>>+>>+>++>++>+>>>>+++>+>>>>++>++>>>>+>>++>+>+++>>>
++>>++++++>>+>>++>+>>>>+++>>+++++>>+>+++>>>++>>++>>+>>++>
+>+++>>>++>>+++++++++++++>>+>>++>+>+++>+>+++>>>++>>++++>>
+>>++>+>>>>+++>>+++++>>>>++>>>>+>+>++>>+++>+>>>>+++>+>>>>
+++>+>>>>+++>>++>++>+>+++>+>++>++>>>>>>++>+>+++>>>>>+++>>
>++>+>+++>+>+>++>>>>>>++>>>+>>>++>+>>>>+++>+>>>+>>++>+>++
++++++++++++++++>>>>+>+>>>+>>++>+>+++>>>++>>++++++++>>+>>
++>+>>>>+++>>++++++>>>+>++>>+++>+>+>++>+>+++>>>>>+++>>>+>
+>>++>+>+++>>>++>>++++++++>>+>>++>+>>>>+++>>++++>>+>+++>>
>>>>++>+>+++>>+>++>>>>+>+>++>+>>>>+++>>+++>>>+[[->>+<<]<+]+ ++++[->+++++++++<]>.[+]>>[<<+++++++[->+++++++++<]>-.———–
——–>-[-<.<+>>]<[+]<+>>>]<<<[-[-[-[>>+<++++++[->+++++<]]>++++
++++++++++<]>+++<]++++++[->+++++++<]>+<<<-[->>>++<<<]>[->>.<<]<<] [/sourcecode] Na dann, viel Spaß mit Brainfuck!

Advertisements

3 Gedanken zu “Brainfuck in Scala

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