Die esoterische Programmiersprache Brainfuck

Entstehungsgeschichte

Mit der Programmiersprache Brainfuck wollte Urban Müller im Jahre 1993 eine Turing-vollständige Programmiersprache erschaffen, um dafür auf Amiga OS 2.0 den kleinsten Compiler der Welt zu schreiben. Das Ergebnis des Unterfangens, den Umfang der Programmiersprache bei gleichzeitigem Erhalt der Turing-Vollständigkeit möglichst gering zu halten, war eine Programmiersprache mit nur acht Befehlen.

In der Turing-Vollständigkeit und der vergleichsweise guten Lesbarkeit des Quellcodes unterscheidet sich Brainfuck von vielen anderen esoterischen Programmiersprachen.

Syntax und Semantik

Die einzigen Datenstrukturen in einer Brainfuck-Maschine sind ein Speicher mit sequentiellen Zellen und ein durch Brainfuck-Befehle verschiebbarer Zeiger, der auf eine Stelle im Speicher zeigt. Dieser Aufbau erinnert bereits an eine Turing-Maschine. Als Turing-vollständige Programmiersprache kann Brainfuck grundsätzlich jede Berechnungsaufgabe, die bei endlichem Speicherbedarf lösbar ist, mittels der folgenden acht Befehle durchführen:

+

Inkrementiert den Wert an der Stelle im Speicher, auf die der Zeiger verweist.

-

Dekrementiert den Wert an der Stelle im Speicher, auf die der Zeiger verweist.

<

Bewegt den Zeiger zum vorhergehenden Element des Speichers (dekrementiert den Zeiger).

>

Bewegt den Zeiger zum nächsten Element des Speichers (inkrementiert den Zeiger).

.

Gibt den Wert, auf den der Zeiger verweist, als ASCII-Zeichen aus.

,

Liest den ASCII-Code eines eingegebenen Zeichens in das Element des Speichers ein, auf das der Zeiger verweist.

[, ]

Wird verwendet wie eine while-Schleife. Die Ausführung wird abgebrochen, wenn der Wert an Stelle des Zeigers 0 ist.

[

Springt nach das übereinstimmende Blockende (]), wenn der Wert des Elements, auf das der Zeiger verweist, 0 ist.

]

Springt direkt nach den übereinstimmenden Blockbeginn ([).

Alle anderen Zeichen im Brainfuck-Programm werden übersprungen und können für Kommentare genutzt werden. Auch die Brainfuck-Befehle selbst können als Kommentartext verwendet werden, wenn sie innerhalb einer garantiert nie betretenen Schleife ([…]) plaziert werden. Das ist etwa am Beginn des Brainfuck-Programms der Fall. Da der Wert des aktuellen Elements bei Ausführungsbeginn 0 ist, wird die Schleife übersprungen und die darin enthaltenen Befehlszeichen werden nicht ausgeführt. Der Trick mit dem Kommentar in der Schleife funktioniert auch an anderen Stellen im Brainfuck-Code, wenn der Zeiger beim Schleifenbeginn (Befehl [) auf ein Element mit Wert 0 zeigt.

Die Semantik der Befehle von Brainfuck kann leicht in Konstrukten der Programmiersprache C ausgedrückt werden. Folgende Liste führt die Entsprechungen der Befehle in C an und geht davon aus, daß p als char * (Zeiger auf char) definiert wurde:

Entsprechend der obenstehenden Äquivalenzliste ist es sehr einfach, einen Transcompiler zu schreiben, der Brainfuck-Programme in C-Quellcode übersetzt. Aus diesem Code kann anschließend mit einem C-Compiler ein ausführbares Programm erstellt werden.

Einfache Codebeispiele

Anders als bei vielen Programmiersprachen beginnen die einführenden Beispiele bei Brainfuck nicht mit dem Programm Hello World, sondern sie enden damit.

Umwandeln von Großbuchstaben in Kleinbuchstaben

Folgendes Listing zeigt ein Brainfuck-Programm zum Einlesen eines Großbuchstabens und der anschließenden Umwandlung und Ausgabe als Kleinbuchstabe. Zuerst wird das Zeichen mit dem Befehl , in das aktuelle Speicherelement eingelesen. Dann wird die Zahl 32 (erkennbar an den 32 +-Befehlen) zum ASCII-Code des Zeichens addiert. Abschließend erfolgt die Ausgabe des Ergebnisses über den Befehl .:

[Umwandeln von Grossbuchstaben in Kleinbuchstaben.]

Zeichen in #0 einlesen:
,

Die Zahl 32 zu #0 addieren:
++++++++++++++++++++++++++++++++

Wert von #0 ausgeben:
.

Multiplizieren zweier Zahlen

Dieses Beispiel zeigt, wie die Zahlen 8 und 4 multipliziert werden können. Im ersten Schritt wird 4 zum Inhalt des aktuellen Speicherelements addiert. Anschließend wird die Schleife betreten. Da der Wert des aktuellen Elements nicht 0 ist, werden die Befehle innerhalb der Schleife ausgeführt. Nachdem der Zeiger nach rechts auf ein leeres Element bewegt wurde, wird zu dessen Wert 8 addiert. Dann wird zum ersten Element zurückgegangen und dessen Wert dekrementiert. Die Schleife wird so lange ausgeführt, bis der Wert an der Stelle des Betretens 0 ist. Durch dieses Vorgehen wird die Zahl 8 insgesamt 4 Mal addiert:

[Multiplizieren von 8 und 4.]

++++          #0 = 4
[             Solange #0 nicht 0:

    Gehe zu #1 und addiere 8; dann gehe zurueck zu #0 und
    dekrementiere den dort gespeicherten Wert:
    >++++++++<-
]

Durch Einsatz dieser Technik kann das Programm zur Umwandlung von Großbuchstaben in Kleinbuchstaben weiter verkürzt werden. Der einzige Unterschied liegt im Bereich zwischen den Befehlen , und .. Während das erste Programm 35 Befehle lang war, umfaßt die folgende Implementierung nur noch 21 Befehle. Die Schleife in der Mitte des Quellcodes addiert 4 Mal die Zahl 8 zum Zeichen, was insgesamt eine Addition von 32 bedeutet:

[Umwandeln von Grossbuchstaben in Kleinbuchstaben.]

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

Ausgabe von „Hello World!

Im folgenden Listing wird der Quellcode eines Programms gezeigt, das die Zeichenfolge „Hello World!“ ausgibt. Die Vorgehensweise wird im Quellcode durch Kommentare erläutert:

[Schreibt "Hello World!" auf die Ausgabe.]

Berechne 2 * 6 = 12 in #0:
++            Zelle #0 auf 2 setzen
[             Solange #0 ungleich 0:
    >         Nach #1 gehen
    ++++++    #1 um 6 erhoehen
    <         Zurueck nach #1 gehen
    -         #0 erniedrigen
]
>             Nach #1 gehen (#1 = 12)

Berechne 12 * 6 = 72 ("H") in #0:
[             Solange #1 ungleich 0:
    <         Nach #0 gehen
    ++++++    #0 um 6 erhoehen
    >         Nach #1 gehen
    -         #1 um 1 erniedrigen
]
<             Nach #0 gehen
.             #0 als Zeichen ausgeben (#0 = 72 ("H"))

Die weiteren Zeichen werden nach dem selben Schema berechnet:
>             Nach #1 gehen
++++          #1 um 4 erhoehen
[
    >+++++<-
]
>
[
    <+++++>-
]
<+.+++++++..+++.>>+++++
[
    <++++++>-
]
<++.<<+++++++++++++++.>.+++.------.--------.>+.

Spracherweiterungen von Brainfuck

Wie die Beispiele zeigen, ist in Brainfuck-Programmen jegliche Ausgabe von Daten mit einem großen Aufwand für den Programmierer verbunden. Befehle zum direkten Einlesen und zur Ausgabe von Zahlen würden die Benutzbarkeit der Programmiersprache vereinfachen. Brainfuck besitzt zwar bereits Befehle zur Ein- und Ausgabe, allerdings steigt der Aufwand, wenn Zahlen größer als 9 ausgegeben werden sollen, die aus mehreren Zeichen bestehen. Deshalb kann die Programmiersprache um folgende drei Befehle erweitert werden:

'

Liest eine Ganzzahl in jenes Element des Speichers ein, auf das der Zeiger verweist.

:

Gibt den Wert des Elements, auf das der Zeiger verweist, als Ganzzahl aus.

@

Beendet die Ausführung an der aktuellen Position im Code. Der Befehl ist nützlich, um das Programm innerhalb von Schleifen vorzeitig beenden zu können.

Diese drei Befehle sind nicht Teil von Brainfuck und sollten nur mit Bedacht eingesetzt werden. Sie können zum Debugging bei der Programmierung in Brainfuck hilfreich sein.

Unklarheiten in der Sprachspezifikation

Mangels einer formalen Spezifikation der Programmiersprache Brainfuck weichen verschiedene Implementierungen von Compilern und Interpretern in wesentlichen Details voneinander ab. Brainfuck-Programme aus dem Web laufen daher oft nicht mit jedem Compiler oder Interpreter. Eventuell wird es in Zukunft eine allgemein akzeptierte Spezifikation für Brainfuck geben, anhand derer konforme Compiler, Interpreter und Quellcode entwickelt werden können.

Im Folgenden werden die wichtigsten Unterschiede in den Implementierungen infolge der fehlenden Spezifikation beschrieben:

Unspezifizierte Speichergröße

Mehrere Quellen sprechen von einem Standardwert von 30.000 Bytes. Die Größe des Speichers ist von Bedeutung um zu entscheiden, was passiert, wenn der Zeiger außerhalb des Speichers bewegt wird. Einige Implementierungen stürzen ab, andere hingegen berechnen den Index modulo der Gesamtzahl an Speicherelementen. Dieses Vorgehen kann wiederum zu unerwartetem Verhalten führen, wenn Quellcode für eine beliebige Speichergröße entwickelt wurde, der tatsächlich Speicher der Maschine aber eine geringere Größe aufweist.

Unspezifizierter Wertebereich der Speicherelemente

Die meisten Implementierungen benutzen ein Byte (Datentyp signed char) pro Element, manche arbeiten mit einem Array von vorzeichenbehafteten 32-Bit-Ganzzahlen (Datentyp signed int). Einige Brainfuck-Compiler und Interpreter bieten die Möglichkeit, einen Modulo-256-Modus zu aktivieren. Beim Datentyp signed char ist das automatisch der Fall; ein Zeichen kann durch Addition von 256 zum Zeichencode reproduziert werden. Ein- und Ausgaben beschränken sich in der Regel auf das ASCII-Zeichenrepertoire.

Implementierung eines Brainfuck-Interpreters in C

Bei dieser Implementierung des Brainfuck-Interpreters in C wurde darauf Rücksicht genommen, die wesentlichen Funktionsmerkmale anderer verfügbarer Compiler und Interpreter zu unterstützen. Zudem sollte der Interpreter zu möglichst vielen existierenden Codebeispielen kompatibel sein.

Der vorliegende Interpreter wurde 2023 mit Code::Blocks in C entwickelt und mittels der Testprogramme von Daniel B. Cristofani getestet. Brian Raiter gibt in Portable Brainfuck Hinweise zur Verbesserung der Interoperabilität verschiedener Brainfuck-Implementierungen, die ebenfalls berücksichtigt wurden.

Das Programm brainfuck kann über die Befehlszeile aufgerufen werden:

Usage: brainfuck [-<options>] [--mem:<size>] [--stack:<size>] <filename>
  <options>:  c  Validate the program before running it.
                 When combined with o, the optimized program gets validated.
              d  Enables the debug command `#`.
              e  Enables additional commands `@`, `'`, and `:`.
              m  Memory cells are calculated modulo 256.
              n  Treat newline as character code 10.
              o  Optimize program before running it.
              v  Ask for user input in a verbose way and print a line feed
                 after the end of the program output.
  --mem:<size>   Memory size (default: 30,000).
  --stack:<size> Loop stack size (default: 100).

Ohne die angeführten Zusatzoptionen wurden folgende Voreinstellungen bzw. Umsetzungsentscheidungen getroffen:

Fehlende Funktionen und Limitierungen:

Downloads

Brainfuck-Interpreter (Brainfuck.zip)

C-Projekt für Code::Blocks.

Weiterführende Informationen

Chris Pressey: The current Brainfuck home page (Cat’s Eye Technologies)

Die originalen Implementierungen des Compilers und Interpreters.

Daniel B. Cristofani: some brainfuck fluff by daniel b cristofani

Außergewöhnliche Codebeispiele und Informationen zur Standardisierung der Programmiersprache Brainfuck.

Panu Kalliokoski: The Brainfuck archive

Sammlung von Compilern, Interpretern, Präprozessoren und Brainfuck-Quellcode.

Frans Faase: Frans Faase’s web page on Brainfuck

Anleitungen, ein in Java entwickelten Interpreter für Brainfuck und einen Interpreter, der in Brainfuck geschrieben wurde.

Brian Raiter: The Brainfuck Programming Language

Verschiedene Brainfuck-Implementierungen.

Simon Howard: BrainFuck.Net

Ein in Python geschriebenen Compiler, der Brainfuck-Quellcode nach MSIL übersetzt.