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:
>
entspricht++p;
<
entspricht--p;
+
entspricht++*p;
-
entspricht--*p;
.
entsprichtputchar(*p);
,
entspricht*p = getchar();
[
entsprichtwhile (*p) {
]
entspricht}
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 .
:
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:
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:
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:
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:
Ohne die angeführten Zusatzoptionen wurden folgende Voreinstellungen bzw. Umsetzungsentscheidungen getroffen:
Der Speicher ist standardmäßig 30.000 Bytes groß, die Größe kann alternativ frei gewählt werden.
Das Programm kann wahlweise mit Speicherelementen des Typs
char
oderint
kompiliert werden.Mittels der Option
m
werden Berechnungen modulo 256 durchgeführt (standardmäßig der Fall, wenn das Programm fürchar
kompiliert wurde).Ohne aktivierte Option
c
werden auch ungültige Programme solange ausgeführt, bis ein Fehler auftritt. Das kann dazu führen, dass Ein- und Ausgaben erfolgen, bevor der Interpreter das Programm aufgrund eines Fehlers abbricht. Bei der Validierung wird lediglich geprüft, ob alle Schleifen korrekt geschlossen sind.Der Schleifenstapel bietet standardmäßig Platz für 100 Elemente, die Größe kann alternativ frei gewählt werden. Die Verwendung eines Stapels verbessert die Performanz, indem der Beginn einer Schleife zum Zurückspringen in konstanter Zeit ermittelt werden kann.
Die Optimierung besteht darin, den Code von allen Kommentaren zu befreien und so die Ausführungsgeschwindigkeit zu verbessern. Optimierungen wie das Erkennen und Entfernen unerreichbaren Codes wurden nicht vorgenommen.
Zeigern wurde gegenüber Arrays bei der Implementierung der Vorzug gegeben.
Fehlende Funktionen und Limitierungen:
Der Interpreter besitzt keinen interaktiven Modus, in dem sowohl Brainfuck-Befehle als auch Eingaben interaktiv erfolgen können.
Der Zeiger zeigt beim Programmstart auf die erste Zelle, ein
<
-Befehl würde daher fehlschlagen. Die Zeigerposition beim Start ist nicht einstellbar.Der Speicher ist nicht als Ringspeicher implementiert, also besitzt einen Anfang und ein Ende.
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.