Brainfuck ist eine von Urban Müller entworfene esoterische Programmiersprache ¹⁾. Die Programmiersprache ist Turing-vollständig und verfügt über einen sehr geringen Sprachumfang von nur acht Zeichen. Brainfuck-Programme sind änlich aufgebaut wie eine Turingmaschine und können als eine ähnliche Maschine dargestellt werden.

Auf dieser Seite wird gezeigt, wie Brainfuck arbeitet und wie man mit Brainfuck programmieren kann. Alle Beispiele auf dieser Seite sind von mir mit Beef, dem in Debian verfügbaren Brainfuck-Interpreter, getestet worden.

Bevor es an die Praxis geht, wird in zwei kurzen Abschnitten etwas auf die Theorie rund um Brainfuck eingegangen.

Brainfuck hat einen sehr geringen Sprachumfang, es gibt lediglich acht Befehle, die jeweils aus nur einem Zeichen bestehen:

Alle anderen im Programm vorkommenden Zeichen (Buchstaben, Zahlen, Leereichen, Zeilenumbrüche, etc.) werden ignoriert und können so zur Kommentierung des Quelltextes verwendet werden.

Die Funktionsweise von Brainfuck kann man sich in etwa vorstellen wie die Funktionsweise einer Turingmaschine. Es gibt einen Schreib-/Lesekopf, der sich über einem unendlichen ²⁾ Band, auf dem sich Speicherzellen befinden, bewegt. In den einzelnen Speicherzellen werden ganze Zahlen („Integer“) gespeichert. Der Schreib-/Lesekopf kann in diesen Speicherzellen Werte speichern (schreiben), den Wert einer Speicherzelle auslesen und den Wert einer Zelle vergrößern (inkrementieren) oder verkleinern (dekrementieren). Eine Brainfuckmaschine würde also in etwas so aussehen:

In der Mehrzahl aller Bücher und Howtos über Programmierung wird mit einem klassischem „Hello World!“ begonnen - und so wird auch hier verfahren: Als erstes (und auch zweites) soll einfach ein „Hello World!“ auf der Konsole ausgegeben werden.

Als erstes soll einfach nur auf möglichst einfache Art und Weise ein „Hello World!“ ausgegeben werden. In Brainfuck könnte das so aussehen:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
+++++++++++++++++++++++++++++.
+++++++..
+++.
-------------------------------------------------------------------------------.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++.
++++++++++++++++++++++++.
+++.
------.
--------.
-------------------------------------------------------------------.
-----------------------.

Hier passiert noch gar nicht viel, es wird nur mit der ersten Speicherzelle gearbeitet. Als erstes wird eine 72 in die Speicherzelle geschrieben und anschließend ausgegeben; da die 72 im ASCII-Code für „H“ steht, erscheint ein H auf der Konsole. Als nächstes wird auf den Wert der Speicherzelle noch mal 29 aufaddiert, so dass diese nun den Wert 101 hat, was einem „e“ im ASCII-Code entspricht. Im folgenden setzt sich das Schema so fort, es wird in der Speicherzelle jeweils der ASCII-Wert des entsprechenden Zeichen abgelegt und dieses dann ausgegeben. Einzige Ausnahme ist das doppelte l, an dieser Stelle wird der Inhalte der Speicherzelle direkt zwei mal hintereinander ausgegeben. Das letzte Zeichen im Beispiel ist „LF“, ASCII-Code 10, was einen Zeilenumbruch auslöst ³⁾.

Zur Verdeutlichung ist hier das obrige Beispiel als C-Funktion implementiert:

void helloworld() {
  int c = 72; putchar(c);
  c += 29; putchar(c);
  c += 7; putchar(c); putchar(c);
  c += 3; putchar(c);
  c -= 79; putchar(c);
  c += 55; putchar(c);
  c += 24; putchar(c);
  c += 3; putchar(c);
  c -= 6; putchar(c);
  c -= 8; putchar(c);
  c -= 67; putchar(c);
  c -= 23; putchar(c);
}

Es folgt nun eine zweite Möglichkeit, wie ein „Hello World!“ ausgegeben werden kann. Diese zweite Version zeigt etwas deutlicher, wie Brainfuck funktioniert:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>++++++++++++++++++++++++++++++++
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>+++++++++++++++++++++++++++++++++
>++++++++++
<<<<<<<<<.
>.
>.
.
>.
>.
>.
<<.
>>>.
<<<<.
>>>>>.
>.
>.

In diesem kurzen Programm passiert schon etwas mehr, denn jetzt wird mit mehreren Speicherzellen gearbeitet. Als erstes wird in die erste Speicherzelle eine 72 gespeichert, dann wird der Schreib-/Lesekopf um eins nach rechts verschoben, so dass er sich über der zweiten Speicherzelle befindet. In der zweiten Zelle wird 101 gespeichert, danach wird der Schreib-/Lesekopf noch einen weiter nach rechts bewegt usw. . Dabei ist zu beachten, dass doppelte Zeichen (das l und das o, die mehrfach in Hello und World vorkommen) nicht doppelt gespeichert werden.
Sind alle ASCII-Codes gespeichert, so wird der Schreib-/Lesekopf wieder ganz an den Anfang des Bandes bewegt und es werden nacheinander die Zeichen ausgegeben, so dass „Hello World!“ erscheint. Dabei fällt auf, dass eben nicht alle Zeichen (bzw. die Inhalte der Zellen) nacheinander ausgegeben werden, sondern dass beim zweiten Auftreten des o der Schreib-/Lesekopf um zwei Speicherzellen nach links verschoben wird und anschließend wieder um drei Stellen nach rechts, zum nächsten Zeichen. Selbiges passiert beim dritten Auftreten des l.

In C ließe sich der oben gezeigte Code so ausdrücken:

void helloworld() {
  int c[10];
  int i = 0;
  c[i] = 72;
  c[++i] = 101;
  c[++i] = 108;
  c[++i] = 111;
  c[++i] = 32;
  c[++i] = 87;
  c[++i] = 114;
  c[++i] = 100;
  c[++i] = 33;
  c[++i] = 10;
  i = 0;
  putchar( c[i] );
  putchar( c[++i] );
  putchar( c[++i] );
  putchar( c[i] );
  putchar( c[++i] );
  putchar( c[++i] );
  putchar( c[++i] );
  putchar( c[i-=2] );
  putchar( c[i+=3] );
  putchar( c[i-=4] );
  putchar( c[i+=5] );
  putchar( c[++i] );
  putchar( c[++i] );
}

Nach den beiden „Hello World“-Beispielen geht es jetzt einen Schritt weiter, zu den Grundrechenarten. Die Umsetzung in Brainfuck ist gar nicht so schwer, wie die nun folgenden Beispiele Zeigen werden.

Eine Addition lässt sich einfach in Brainfuck ausführen, folgendes Beispiel zeigt es:

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

Die eigentliche Addition spielt sich hier in den Zeilen 1 – 3 ab, die letzten beiden Zeilen dienen nur der Ausgabe des Ergebnisses.
In der ersten Zeile wird in der ersten Zelle eine 5 gespeichert, in der zweiten Zeile wird der Schreib-/Lesekopf eins nach rechts, über die zweite Speicherzelle bewegt und in dieser Speicherzelle eine 3 gespeichert. In der dritten Zeile werden nun beide Zahlen addiert: Der Schreib-/Lesekopf wird einen Schritt nach links bewegt und der Wert der dortigen Speicherzelle wird um eins erhöht, dann bewegt sich der Schreib-/Lesekopf wieder zurück nach rechts und verringert den Wert der dortigen Speicherzelle um eins. Dieses Verfahren, durch die eckigen Klammern markiert, wird nun so lange wiederholt, bis der Wert der rechten Speicherzelle bei 0 angelangt ist. Folglich hat am Ende die linke Speicherzelle den Wert 8 (das Ergebnis der Addition) und die rechte Speicherzelle den Wert 0. Zur Verdeutlichung ist hier die Addition noch mal als Animation dargestellt:

In der vierten Zeile erfolgt die Ausgabe des Ergebnisses, dazu wird der Schreib-/Lesekopf zur linken Speicherzelle bewegt, ihr Wert wird um 48 erhöht (48 ist der ASCII-Code von 0) und dann ausgegeben. In der letzten Zeile wird der Schreib-/Lesekopf wieder nach rechts bewegt, über die Speicherzelle, die 0 enthält, ihr Wert wird auf 10 erhöht und so wird ein Zeilenumbruch ausgegeben.
Zu beachten ist hier, dass die Ausgabefunktion stark limitiert ist. Ist das Ergebnis der Addition größer als 9, so werden die im ASCII-Code folgenden Zeichen ausgegeben, an Stelle von 10, 11, etc. . Diese Limitierung betrifft jedoch nur die Ausgabe, die Addition selbst könnte auch größere Zahlen verarbeiten.

Die Subtraktion ist, wie das folgende Beispiel zeigt, sehr ähnlich aufgebaut wie die Addition:

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

Im direkten Vergleich zur Addition fallen zwei Veränderungen auf. Zum einen natürlich die Rechnung selbst: Statt dass der Wert der linken Speicherzelle erhöht wird, wird er nun verringert, ansonsten ist das Verfahren genau gleich. Zum Schluss beinhaltet die linke Speicherzelle eine 2 (das Ergebnis der Subtraktion) und die rechte Speicherzelle eine 0. Zum anderen fällt eine Änderung in der letzten Zeile auf: hier wird nicht mehr der Schreib-/Lesekopf nach rechts bewegt, sondern es wird der Inhalt der linken Zelle auf 0 gesetzt (der Inhalt der Speicherzelle wird so lange um eins verringert, bis die 0 erreicht ist), dann wird eine 10 addiert und so ein Zeilenumbruch ausgegeben.
Beachtet werden muss auch hier die limitierte Ausgabefunktion, die nur die Zahlen 0 bis 9 korrekt ausgeben kann. Außerdem birgt die Subtraktion die Gefahr, dass das Ergebnis negativ, also kleiner als 0, werden kann. In Brainfuck ist dieser Fall so eigentlich nicht vorgesehen und kann Probleme verursachen, da die Werte der Speicherzellen größer-gleich 0 sein sollten. Negative Werte gilt es also zu vermeiden, sonst kann unter Umständen der Brainfuck-Interpreter hängen bleiben.

Für die Multiplikation ist, wie im folgenden Beispiel gezeigt, schon etwas mehr Aufwand nötig:

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

Im gezeigten Beispiel werden 3 und 2 miteinander multipliziert, die Ein- und Ausgabe in den ersten bzw. letzten beiden Zeilen ist bereits (mitsamt ihren Limitierungen) bekannt und werden nicht weiter erklärt. Da Brainfuck die Multiplikation nicht direkt unterstützt, muss sie auf die Addition zurückgeführt werden. So wird in Brainfuck nicht 3 * 2 , sondern 2 + 2 + 2 gerechnet. Im oben angegebenen Quelltext passiert diese mehrfache Addition in Zeile 4.
Als erstes wird eine äußere Schleife erzeugt, die auf der ersten Speicherzelle (1. Faktor bzw. jetzt Anzahl der Summanden) ausgeführt wird. In dieser äußeren Schleife gibt es zwei innere Schleifen. Die erste innere Schleife stellt dabei eine Kopierfunktion dar, die den Wert der zweiten Speicherzelle (2. Faktor bzw. jetzt die Summanden) auf die dritte (das Zwischen- bzw. Endergebnis) und vierte Speicherzelle (temporärer Speicher) aufaddiert. Gleichzeitig verringert sich der Wert der zweiten Speicherzelle zur 0. In der zweiten inneren Schleife wird der in der vierten Speicherzelle gespeicherte Wert wieder zurück in die zweite Speicherzelle verschoben. Dieses Verfahren wird so lange angewendet, bis der Wert der ersten Speicherzelle 0 erreicht hat; dann befindet sich in der dritten Speicherzelle das Endergebnis.
Grafisch veranschaulicht läuft das oben erwähnte Beispiel so ab:

Wird fortgesetzt…

In Brainfuck werden immer wieder die ASCII-Codes gebraucht, deshalb hier eine Übersicht über die wichtigsten ASCII-Codes:

Bedeutung der Abkürzungen:

• LF: line feed - Zeilenvorschub (bewirkt Zeilenumbruch)
• VT: vertical tabulation - Tabulator
• CR: carriage return - Wagenrücklauf
• SP: space - Leerzeichen
• DEL: delete - Löschen

Das Internet bietet noch mehr Informationen zu Brainfuck - diese Seiten kann ich empfehlen:

• Brainfuck - Der Wikipedia-Artikel über Brainfuck
• kiyuko.org: Beef - Der Brainfuck-Interpreter, den ich benutze
• brainfuck.tk - Ein Online-Interpreter für Brainfuck