Okt 17

Brainfuck – Ein kurzer Blick auf eine esoterische Programmiersprache

Mittwoch, 17. Oktober 2007 12:05

Durch einen kurzen Artikel in der aktuellen c’t (Ausgabe 22/2007) bin ich über die esoterische Programmiersprache “Brainfuck” gestolpert. Esoterische Programmiersprachen haben häufig keinen sonderlich großen praktischen Nutzen, dienen entweder humoristischen Zielen oder verkörpern ganz eng abgegrenzte Philosophien der Informatik oder anderer Programmiersprachen. Einige davon verfolgen die Realisierung einer sog. “Turing-Maschine” also einem idealen Computer, der in der Lage ist sämtliche mathematischen Ein- und Ausgaben und Problemstellungen korrekt zu verarbeiten. Als Modell dafür dient ein endloses Magnetband, das beliebig vor und zurückgespult werden kann und beliebig beschrieben und gelesen werden kann. (Zum besseren Verständnis einer Turing-Maschine empfehle ich den Artikel bei Wikipedia.)

Um die Turing-Bedingungen zu erfüllen benötigt Brainfuck nur 8 Befehle:

< Den Speicherpointer um den Wert 1 dekrementieren (“Sprung” nach links )

> Den Speicherpointer um den Wert 1 inkrementieren (“Sprung” nach rechts)

+ Den Wert an der aktuellen Speicherstelle um 1 inkrementieren

- Den Wert an der aktuellen Speicherstelle um 1 dekrementieren

[ und ] Mit diesen Zeichen wird eine Schleife eingeleitet, die so lange ausgeführt wird, wie der Inhalt der aktuellen Speicherzelle ungleich 0 ist.

, liest ein Zeichen von STDIN und schreibt es an die aktuelle Speicherstelle

. Gibt das Zeichen an der aktuellen Speicherstelle aus.

[Da Brainfuck als Ein- und Ausgabe nur ASCII-Codes interpretieren kann muss im Fall des letzten Befehls "." an der entsprechenden Speicherstelle der ASCII-Code stehen, der das gewünschte Zeichen repräsentiert, bspw. "51" für die Zahl 3]

In der Referenzimplementierung sind tatsächlich nur diese 8 Befehle vorhanden. Das “Magnetband” auf dem man sich bewegt ist auch nur 30.000 8-Bit große Zeichen “lang”. Je nach verwendetem Interpreter (Ich verwende “beef” unter Linux) können auch noch Debugging-Befehle dazukommen. So unwahrscheinlich wie es auf den ersten Eindruck scheint kann man mit Brainfuck tatsächlich funktionierende Programme schreiben. (Was nicht bei jeder esotherischen Programmiersprache das erklärte Ziel ist…)

Brainfuck-Tutorials gibt es im Internet mehr als genug, aus diesem Grund will ich mich auch an dieser Stelle nur auf ein paar Beispiele beschränken. Wer sich wirklich ernsthaft mit BF beschäftigen will, dem empfehle ich die Links am Ende dieses Artikels. Brainfuck-Programme schreibt man am besten mit einem reinen Texteditor, es werden vom Interpreter ausschließlich die 8 Brainfuck-Befehle verarbeitet, alles andere wird als Kommentar im Quelltext ignoriert. Auch die Formatierung ist nicht relevant. Quelltext sollte als Plaintext mit der Endung “.b” gespeichert werden.

Zum besseren Verständnis vom Brainfuck und den Befehlen hier ein einfaches Beispiel. Wenn ein Programm von einem Interpreter ausgeführt wird sind zunächst alle Speicherstellen auf “0″ gesetzt und er Speicherpointer steht auf dem ersten Byte (unterstrichen):

|0| |0| |0| |0| …

Das denkbar einfachste Programm in Brainfuck besteht aus genau einem Zeichen:

Der Inhalt der Speicherzellen sieht dann folgendermaßen aus:

|1| |0| |0| |0| …

Eine Programm dieser Form

+++

führt demnach zu folgendem Ergebnis:

|3| |0| |0| |0| …

usw. usw.

Nun möchte man sicher auch mal eine andere Speicherstelle als die erste verändern. Das folgende Beispiel füllt die ersten 3 Speicherstellen mit den Werten “1″ “2″ und “3″

+>++>+++

|1| |2| |3| |0| …

Um nun ein Programm zu schreiben, welches ein bestimmtes ASCII-Zeichen ausgibt muss eine Speicherstelle mit dem dezimalen ASCII-Wert des Zeichens “gefüllt” werden. (Als Beispiel die Zahl “2″ entspricht in ASCII: DEC 050) Das Listing dazu sieht folgendermaßen aus:

>+++++[<++++++++++>-]<.

Dieses kurze Programm macht in Worten nichts anderes als: “Zähle 5 mal bis 10 und addiere die bei jedem Durchlauf.”

Der Ablauf im Detail in Worten sieht folgendermaßen aus (farblich hervorgehoben):

“Springe zur 2. Stelle, schreibe an diese Stelle den Wert “5″. Springe dann wieder zur ersten Stelle, schreibe dort den Wert 10. Spring wieder zur 2. Stelle und verringere den dort stehenden Wert um 1. Alles was in eckigen Klammern steht machst Du 5 Mal (So lange bis die 2. Speicherstelle 0 ist]. Springe dann wieder an die erste Speicherstelle und gib das ASCII-Zeichen zum Wert “50″ aus”

Einfache Probleme – einfach gelöst… (Oder komplizierter, je nach Sichtweise… *gg*)

Ich will an dieser Stelle auch nicht weiter auf Brainfuck eingehen, ich denke, dass etablierte Tutorials das besser können als ich. Wer sich eingehender damit beschäftigen möchte dem seien folgende Internetseiten zum Thema empfohlen:

http://neworder.box.sk/newsread.php?newsid=13065 Gutes Tutorial

http://de.wikipedia.org/wiki/Brainfuck Wiki-Eintrag zum Thema Brainfuck

http://de.wikipedia.org/wiki/Turingmaschine Was ist eine Turingmaschine?

Thema: Funstuff, Linux | Kommentare (0) | Autor: Nicolas Dorwig