Dieser Artikel existiert auch als Audiodatei.

Brainfuck

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 23. September 2022 um 13:48 Uhr durch imported>Y2kbug(217280) (x86...).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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 kann – 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
 + cell[ptr]++; inkrementiert den aktuellen Zellenwert
 − cell[ptr]--; dekrementiert den aktuellen Zellenwert
 . putchar (cell[ptr]); Gibt den aktuellen Zellenwert als ASCII-Zeichen auf der Standardausgabe aus
 , cell[ptr] = getchar(); Liest ein Zeichen von der Standardeingabe und speichert dessen ASCII-Wert in der aktuellen Zelle
 [ while (cell[ptr]) { 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.

Ähnliche Sprachen

Weiterhin existiert die Programmiersprache Brainfuck 2D, die das Brainfuck-Konzept in einen zweidimensionalen 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ölfmal aus (9+3=12). Der Befehl +0**** wird nicht interpretiert, da er gar nicht 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.[5]

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.[6]

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

  1. ↑ hugi.scene.org
  2. ↑ hevanet.com
  3. ↑ hevanet.com
  4. ↑ BF is Turing-complete. iwriteiam.nl
  5. ↑ Brainfuck 2D Referenz
  6. ↑ Flowbf-Projektseite auf GitHub
Abgerufen von „https://de.wikiup.org/index.php?title=Brainfuck&oldid=226409912“