Brainfuck

Brainfuck ist eine so genannte esoterische Programmiersprache, entworfen vom Schweizer Urban Müller um 1993. Die Sprache wird manchmal auch Brainf*ck, Brainf*** oder BF genannt.

Brainfuck ist zwar für den ernsthaften Einsatz zu umständlich und ineffizient, aber gut geeignet, um Grundlagen der Computertechnik zu lernen. Speziell zeichnet sich Brainfuck durch ein extrem einfaches Sprachkonzept und hochkompakte Realisierung des Compilers aus, gleichzeitig wurde aber die (prinzipielle) universelle Einsetzbarkeit nicht eingeschränkt.

Allgemeines

Müllers Ziel war es, eine einfache Turing-vollständige Sprache zu entwerfen, welche mit einem möglichst kleinen Compiler übersetzt werden konnte – inspiriert wurde er dabei durch False, eine andere esoterische Programmiersprache, deren Compiler nur 1024 Byte groß war. Er schaffte es schließlich, die zweite Version seines Compilers für den Amiga in lediglich 240 Byte zu schreiben. Brian Raiter gelang es, dies zu unterbieten, indem er – unter Verwendung von nur 171 Bytes – einen Brainfuck-Compiler für x86 Linux schrieb. Für MS-DOS gibt es einen Brainfuck-Interpreter von Bertram Felgenhauer mit einer Größe von nur 98 Bytes.^[1]

Sprachdesign

Ein Brainfuck-Programm ähnelt stark der formalen Definition einer Turingmaschine. Statt eines Lese-/Schreibkopfes auf einem Band, Zuständen, sowie einem frei definierbaren Alphabet werden jedoch im Sinne einer iterativen Programmiersprache ein Zeiger auf ein Datenfeld, Schleifenkonstrukte und eine rudimentäre ALU verwendet. Der Programmcode wird dabei separat vom Datenfeld gespeichert (siehe Harvard-Architektur).

Befehlssatz

Brainfuck besitzt acht Befehle, jeweils bestehend aus einem einzigen Zeichen:

Zeichen	C-Äquivalent	Semantik
>	++ptr;	inkrementiert den Zeiger
<	--ptr;	dekrementiert den Zeiger
+	++*ptr;	inkrementiert den aktuellen Zellenwert
-	--*ptr;	dekrementiert den aktuellen Zellenwert
.	putchar(*ptr);	Gibt den aktuellen Zellenwert als ASCII-Zeichen auf der Standardausgabe aus
,	*ptr = getchar();	Liest ein Zeichen von der Standardeingabe und speichert dessen ASCII-Wert in der aktuellen Zelle
[	while (*ptr) {	Springt nach vorne, hinter den passenden ]-Befehl, wenn der aktuelle Zellenwert null ist
]	}	Springt zurück, hinter den passenden [-Befehl, wenn der aktuelle Zellenwert verschieden von null ist

Anmerkung: Es gibt verschiedene semantisch äquivalente Varianten der letzten beiden Befehle, die hier angegebenen lassen sich jedoch am effizientesten implementieren.

Andere im Quelltext vorkommende Zeichen (z. B. Buchstaben, Zahlen, Leerzeichen, Zeilenumbrüche) werden in der Regel ignoriert und können so als Quelltextkommentar verwendet werden.

Turing-Vollständigkeit

Für verschiedene Brainfuck-Umgebungen wurde Turing-Vollständigkeit bewiesen:

• Für ein unendlich großes Feld aus Zellen unendlicher Größe durch Frans Faase.^[2]
• Für ein unendlich großes Feld aus Zellen endlicher Größe^[3] und für ein endlich großes Feld aus Zellen unendlicher Größe^[4] durch Daniel B. Cristofani.

Bei einer Brainfuck-Variante mit endlicher Zellgröße sowie endlicher Feldgröße (z. B. BFmin) handelt es sich – wie bei jedem realen Computer – um einen endlichen Automaten.

Beispielprogramme in Brainfuck

Hello World!

Das folgende Programm gibt „Hello World!“ und einen Zeilenumbruch aus.

 ++++++++++
 [
  >+++++++>++++++++++>+++>+<<<<-
 ]                       Schleife zur Vorbereitung der Textausgabe
 >++.                    Ausgabe von 'H'
 >+.                     Ausgabe von 'e'
 +++++++.                'l'
 .                       'l'
 +++.                    'o'
 >++.                    Leerzeichen
 <<+++++++++++++++.      'W'
 >.                      'o'
 +++.                    'r'
 ------.                 'l'
 --------.               'd'
 >+.                     '!'
 >.                      Zeilenvorschub
 +++.                    Wagenrücklauf

Zur besseren Lesbarkeit ist dieser Brainfuckcode auf mehrere Zeilen verteilt und kommentiert worden. Brainfuck ignoriert alle Zeichen, die keine Brainfuckbefehle sind. Alle Zeichen mit Ausnahme von +-<>[],. können deswegen zur Kommentierung des Quellcodes genutzt werden.

Zunächst wird die erste (die „nullte“) Zelle des Datenfelds auf den Wert 10 gesetzt (a[0] = 10). Die Schleife am Anfang des Programms errechnet dann mit Hilfe dieser Zelle weitere Werte für die zweite, dritte, vierte und fünfte Zelle. Für die zweite Zelle wird der Wert 70 errechnet, welcher nahe dem ASCII-Wert des Buchstaben 'H' (ASCII-Wert 72) liegt. Die dritte Zelle erhält den Wert 100, nahe dem Buchstaben 'e' (ASCII-Wert 101), die vierte den Wert 30 nahe dem Wert für Leerzeichen (ASCII-Wert 32), die fünfte den Wert 10, welches dem ASCII-Zeichen „Line Feed“ entspricht und als Zeilenumbruch interpretiert wird (oder werden sollte, siehe dazu den Abschnitt „Implementierungen“).

Die Schleife errechnet die Werte, indem einfach auf die zu anfangs mit 0 initialisierten Zellen 10-mal 7, 10, 3 und 1 addiert wird. Nach jedem Schleifendurchlauf wird a[0] dabei um eins verringert, bis es den Wert 0 hat und die Schleife dadurch beendet wird.

Am Ende der Schleife hat das Datenfeld dann folgende Werte: a[0] = 0; a[1] = 70; a[2] = 100; a[3] = 30; a[4] = 10;

Als nächstes wird der Zeiger auf die zweite Zelle des Datenfelds (a[1]) positioniert und der Wert der Zelle um zwei erhöht. Damit hat es den Wert 72, welches dem ASCII-Wert des Zeichens 'H' entspricht. Dieses wird daraufhin ausgegeben. Nach demselben Schema werden die weiteren auszugebenden Buchstaben mit Hilfe der durch die Schleife initialisierten Werte, sowie der bereits verwendeten Werte, errechnet.

Grundlagen der Programmierung in Brainfuck

Anmerkung: Alle Zeichen außerhalb des Brainfuck-Befehlssatzes werden vom Compiler ignoriert. Sie werden somit als Kommentar interpretiert. Da beispielsweise Pluszeichen nicht als Kommentar verstanden werden, sondern als ein Inkrementierbefehl ausgewertet werden, steht im unten angegebenen Beispiel aus diesem Grund im Kommentar n plus 1.

Schleifen

Schleifen beginnen mit dem Zeichen '[' und enden mit dem zugehörigen ']'. Die Schleife wird solange ausgeführt, bis der Wert der aktuellen Zelle Null ist. Die einfachste sinnvolle Form ist die Nullschleife, die den Wert der aktuellen Zelle dekrementiert, bis dieser Null ist:

  [-]

Einfache Schleife

  ,[.,]

Einfaches Echo-Programm. Zeichen werden von der Standardeingabe gelesen und wieder auf die Standardausgabe ausgegeben.

Geschachtelte Schleifen

In der Definition der beiden Schleifen-Befehle ist auch die Möglichkeit enthalten, geschachtelte Schleifen programmieren zu können. Im Quellcode mehrerer Rechenoperationen (s.u.) sind entsprechende Beispiele zu finden.

Bedingungen

• x ungleich y (wird durch Subtraktion der beiden Zahlen erreicht)

Wichtig ist, dass Zelle 0 auf 0 gesetzt ist, ansonsten kann es dazu kommen, dass der Bedingungsblock mehrmals aufgerufen wird.

  >+++++           addiere 5 zu Zelle 1
  >++++            addiere 4 zu Zelle 2
  [<->-]           subtrahiere Zelle 2 von Zelle 1
  <                gehe zu Zelle 1
 
  [                wird aufgerufen wenn Zelle 1 ungleich 0 ist
  <                gehe zu Zelle 0 (somit wird die Schleife nur ein mal durchlaufen)
  ]

Rechenoperationen

Verschieben des Wertes einer Zelle in die nächste (zuerst Nullsetzung der Folgezelle, dann in einer Schleife Inkrementierung der Folgezelle, gleichzeitige Dekrementierung der aktuellen):

  >[-]<[>+<-]

Kopieren eines Wertes erfolgt durch das Verschieben in 2 Folgezellen und anschließendes Zurückverschieben:

 >[-]>[-]<<          nur notwendig wenn die beiden Variablen nicht leer sind
 [>+>+<<-]           verschiebe Inhalt von Zelle n nach Zellen n plus 1 und n plus 2
 >>[<<+>>-]          verschiebe Inhalt von Zelle n plus 2 nach Zelle n
 <<                  gehe wieder auf Zelle n

Addition: p[1] = p[1] + p[0]; Nebeneffekt: p[0] = 0

  [>+<-]

Subtraktion: p[1] = p[1] - p[0]; Nebeneffekt: p[0] = 0

  [>-<-]

Multiplikation mit einer Konstanten: p[1] = p[0] * 5; Nebeneffekt: p[0] = 0 Es wird eine normale Verschiebung durchgeführt, wobei die Zielzelle nicht jeweils um eins, sondern um den entsprechenden Faktor erhöht wird.

  [>+++++<-]

Multiplikation mit einem Zellenwert: Hier wird der 2. Faktor wiederholt zum Produkt mittels obiger Kopierfunktion addiert: p[2] = p[0] * p[1]; Nebeneffekt: p[0] = p[3] = 0

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

Potenzieren: Eine Zahl mit +++ in eine Zelle zu schreiben wird spätestens ab zweistelligen Zahlen mehr als aufwändig. Also behilft man sich mittels Potenzen: p[2] = 5^3 = 125; Nebeneffekt: p[0] = p[1] = 0

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

Division funktioniert am einfachsten als restlose Division, alles andere resultiert in dem Fall in einer Endlosschleife. Die Idee ist ansonsten dieselbe wie bei der Multiplikation: p[1] = p[0] / 5; Nebeneffekt: p[0] = 0

  [>+<-----]

Restbehaftete Division in Brainfuck ist hingegen etwas komplizierter.

Der C-Code zum nachfolgenden Brainfuck-Programm:

while(p[0]--) {
  p[1]--;
  p[2]++;
  if(p[1] == 0) {
   p[3]++;
   p[1] = p[2];
   p[2] = 0;
  }
 }
 p[2] = p[0] % p[1];
 p[3] = p[0] / p[1];

Nebeneffekt: p[0] = 0; p[4] = 0; p[5] = 0; p[1] = p[1] - p[0] % p[1]

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

Konvertierung

Der nachfolgende Code gibt eine Zahl in dezimaler Form aus

 ++++++++[>++++++++<-]>[-<++>]<-----     schreibt die Zahl 123 in die erste Zelle
 >[-]++++++++[>[-]<[->+<]>-]<<<<<<<<<    löschen der nächsten Zellen
 [->+<]>[>+<-<+>]>[>>>>>[->+<]>+<<<<<    der eigentliche Code
 ++++++++++<[->>+<-[>>>]>[[<+>-]>+>>]
 <<<<<]>[-]>[-<<+>>]>[-<<+>>]<<]>>>>>
 [<<<<+++++++[-<+++++++>]<-[<+>-]<.[-
 ]>>>>>>[-<+>]<-]<<<<<<<

Implementierungen

Da Brainfuck keine standardisierte Programmiersprache ist, kann es zu Inkompatibilitäten kommen. Diese betreffen am häufigsten die verschiedenen Zeilenumbruchformate der Betriebssysteme Windows und Unix, sowie deren unterschiedliche Zeichencodes für die Eingabetaste. Die meisten Brainfuckprogramme, darunter auch die von Urban Müller, sind auf Unix-Umgebungen ausgelegt und können daher mit Implementierungen, die von Windows-Zeichencodes ausgehen, nicht korrekt übersetzt werden.

Ähnliche Sprachen

Weiterhin existiert die Programmiersprache Brainfuck 2D, die das Brainfuck-Konzept in einen 2-dimensionalen Zeichenraum portiert. Dabei wird mit Textzeichen eine Schnur gebildet, deren Richtung den entsprechenden Brainfuck-Befehl angibt, wobei die Länge unbedeutend für die Anzahl der Aufrufe ist. Ein Befehl wird entsprechend der Summe aller Ziffern auf seinem Abschnitt wiederholt. So ist +********* der gleiche Befehl wie +; +93*** führt den Befehl jedoch zwölf Mal aus (9+3=12). Der Befehl +0**** wird nicht interpretiert, da er null Mal ausgeführt wird. Auf diese Weise kann man sich Platz für seine Schnur verschaffen, sollte dieser einmal nicht reichen. Ist der Verlauf der Schnur für den Interpreter nicht eindeutig erkennbar oder endet die Schnur, wird das Programm beendet.

Eine weitere, nicht ganz ernst gemeinte Variante von Brainfuck ist Ook!.

Eine andere 2D Variante ist Path, welches es ermöglicht / und \ als Spiegel einzusetzen. Der Programmfluss stellt dann quasi einen Lichtstrahl dar. In Flow, welches Path recht ähnlich ist, verläuft der Programmfluss wie Wasser, das heißt bei Verzweigungen teilt er sich, und ermöglicht damit (Pseudo-)Threads.^[5]

Literatur

• Oliver Lau: Hexenwerk – Ein Plädoyer für esoterische Programmiersprachen. In: c’t 22/2007, S. 192–199.

Weblinks

• Brainfuck – An Eight-Instruction Turing-Complete Programming Language von Brian Raiter
• Brainfuck Archive bei Panu Kalliokoski
• Brainfuck Interpreter, Brainfuck Code im Browser testen.
• Brainfuck in Javascript, Implementierung von Brainfuck in nur 139 Zeichen
• Brainfuck Developer, eine Brainfuck-IDE für Windows
• Brainfuck Palm-OS Engine und IDE von Rudolf Seitz
• awib, in Brainfuck geschriebener Brainfuck Compiler
• brainfuck.p ein Brainfuck Interpreter für den ZX81 mit Doku in Deutsch und Englisch

Einzelnachweise

1. ↑ hugi.scene.org
2. ↑ BF is Turing-complete
3. ↑ http://www.hevanet.com/cristofd/brainfuck/utm.b
4. ↑ http://www.hevanet.com/cristofd/brainfuck/urmutm.b
5. ↑ Flowbf-Projektseite auf Berlios