Brainf*ck

Brainfuck ist eine sogenannte 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 ineffektiv, 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 BF-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 BF-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 BF-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 durch Daniel B. Cristofani^[3]
• Für ein endlich großes Feld aus Zellen unendlicher Größe durch Daniel B. Cristofani^[4]

Bei einer BF-Variante mit endlicher Zellgröße sowie endlicher Feldgröße (z. B. BFmin) handelt es sich − wie bei jedem nicht vernetzten realen Computer − um einen endlichen Automaten; sie kann somit nicht turingvollständig sein.

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'
>+.                     // '!'
>.                      // Zeilenumbruch

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 der 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: Obwohl die Zeichen // wie die aus anderen Programmiersprachen bekannten Kommentare aussehen, sind es keine. Deshalb wird ein Pluszeichen z. B. in n+1 als ein Inkrementierbefehl ausgewertet, im unten angegebenen Beispiel steht aus diesem Grund n plus 1.

Schleifen

Schleifen beginnen mit [ und enden mit ]. Die Schleife wird solange ausgeführt, bis die aktuelle Zelle 0 ist. Die einfachste sinnvolle Form ist die Nullschleife, die die aktuelle Zelle dekrementiert, bis diese Null ist:

 [-]

Einfache Schleife

 ,[.,]

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

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 und 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 aufwendig. 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]

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

Ä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.

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. Da die meisten Brainfuckprogramme auf Unix-Umgebungen ausgelegt sind, werden im Folgenden die Implementierungen als „kompatibel“ bezeichnet, die diese Programme ausführen können. „Inkompatible“ Implementierungen sind dagegen auf Windows festgelegt und können die meisten Brainfuckprogramme, darunter auch die von Urban Müller, nicht korrekt übersetzen.

Literatur

• Oliver Lau, Hexenwerk - Ein Plädoyer für esoterische Programmiersprachen, c’t 22/07, S. 192-199.

Quellen

1. ↑ http://www.hugi.scene.org/compo/compoold.htm#compo6
2. ↑ BF is Turing-complete
3. ↑ http://www.hevanet.com/cristofd/brainfuck/utm.b
4. ↑ http://www.hevanet.com/cristofd/brainfuck/urmutm.b

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 Developer, eine Brainfuck-IDE für Windows
• Brainfuck Palm-OS Engine u. IDE von Rudolf Seitz