Brainfuck

Brainfuck (dt.: „Hirnfick“) ist eine esoterische Programmiersprache, die der Aminet-Gründer, der Schweizer Urban Müller, im Jahre 1993 entwarf. Die Sprache wird auch als Brainf*ck, Brainf*** oder BF bezeichnet.

Brainfuck ist für den produktiven Einsatz viel zu umständlich und zu ineffizient, aber geeignet, um die Methodik von Softwareentwicklung zu schulen. Speziell zeichnet sich Brainfuck durch ein extrem einfaches Sprachkonzept und hochkompakte Realisierung des Compilers aus, gleichzeitig wurde aber die (im berechenbarkeitstheoretischen Sinne) 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. Es gelang ihm schließlich, die zweite Version seines Compilers für den Commodore-Amiga in lediglich 240 Byte zu schreiben. Brian Raiter konnte dies 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.

Befehlssatz

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

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

Anmerkungen

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 endlicher Größe[2] und für ein endlich großes Feld aus Zellen unendlicher Größe[3] durch Daniel B. Cristofani.
Für ein unendlich großes Feld aus Zellen unendlicher Größe durch Frans Faase.[4]

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 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 Interpreter 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 zu programmieren. 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 einmal 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 zwei 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 zweite 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. Daher 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.

Literatur

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

Weblinks

Esolang: Übersicht, Beispiele und Einordnung der Programmiersprache
Brainfuck On-line-Interpreter in JavaScript mit einer umfangreichen Bibliothek von Programmen.
awib – in Brainfuck geschriebener Brainfuck-Compiler

Einzelnachweise

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] ugi.scene.org

[2] vanet.com

[3] vanet.com

[4] BF is Turing-complete. iwriteiam.nl

[5] Brainfuck 2D Referenz

[6] Flowbf-Projektseite auf GitHub