Die esoterische Programmiersprache Brainfuck

Einführung in die Programmiersprache Brainfuck mit Codebeispielen und einem in C geschriebenen Interpreter.

Inhaltsverzeichnis

• Entstehungsgeschichte
• Syntax und Semantik
• Einfache Codebeispiele
  • Umwandeln von Großbuchstaben in Kleinbuchstaben
  • Multiplizieren zweier Zahlen
  • Ausgabe von „Hello World!“
• Spracherweiterungen von Brainfuck
• Unklarheiten in der Sprachspezifikation
  • Unspezifizierte Speichergröße
  • Unspezifizierter Wertebereich der Speicherelemente
• Implementierung eines Brainfuck-Interpreters in C
  • Voreinstellungen und Entwurfsentscheidungen
  • Fehlende Funktionen und Limitierungen
• Downloads
• Weiterführende Informationen

Entstehungsgeschichte

Mit der Programmiersprache Brainfuck verfolgte Urban Müller 1993 das Ziel, eine turing-vollständige Sprache mit einem minimalen Compiler für AmigaOS 2.0 zu entwickeln. Das Resultat dieses Unterfangens war eine Sprache, die mit gerade einmal acht Befehlen auskommt und dennoch die theoretische Turing-Vollständigkeit wahrt.

Während Brainfuck diese universelle Berechenbarkeit mit anderen esoterischen Programmiersprachen teilt, unterscheidet es sich von ihnen vor allem durch die extreme Einfachheit seines Befehlssatzes.

Syntax und Semantik

Eine Brainfuck-Maschine besitzt als einzige Datenstrukturen einen Speicher aus sequentiellen Zellen sowie einen frei verschiebbaren Zeiger, der auf eine dieser Zellen verweist. Dieser minimalistische Aufbau gleicht dem einer Turing-Maschine. Als turing-vollständige Programmiersprache ist Brainfuck theoretisch imstande, jede bei endlichem Speicherbedarf lösbare Berechnungsaufgabe mithilfe der folgenden acht Befehle zu bewältigen:

+

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 ([).

Sämtliche anderen Zeichen innerhalb eines Brainfuck-Programms werden ignoriert und lassen sich somit für Kommentare nutzen. Selbst die eigentlichen Brainfuck-Befehle können als Kommentartext dienen, sofern man sie innerhalb einer garantiert nie betretenen Schleife ([…]) plaziert. Dies ist beispielsweise zu Beginn des Programms der Fall: Da der Wert der aktuellen Speicherzelle bei Ausführungsbeginn 0 beträgt, wird die Schleife übersprungen, sodaß die darin enthaltenen Befehle unausgeführt bleiben. Dieser Kniff funktioniert ebenso an beliebigen anderen Stellen im Code.

Die Semantik der Brainfuck-Befehle läßt sich auf einfache Weise in Konstrukten der Programmiersprache C ausdrücken. Die folgende Übersicht stellt die Befehle ihren C-Entsprechungen gegenüber und setzt voraus, daß p zuvor als char * (Zeiger auf char) deklariert wurde:

• > entspricht ++p;
• < entspricht --p;
• + entspricht ++*p;
• - entspricht --*p;
• . entspricht putchar(*p);
• , entspricht *p = getchar();
• [ entspricht while (*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.

Auf Grundlage dieser Äquivalenzliste läßt sich unschwer ein Transcompiler entwickeln, der Brainfuck-Programme in C-Quellcode übersetzt. Aus diesem Quelltext generiert anschließend ein gängiger C-Compiler ein direkt ausführbares Programm.

Einfache Codebeispiele

Im Gegensatz zu den meisten Programmiersprachen beginnen die einführenden Beispiele bei Brainfuck nicht mit dem klassischen Hello-World-Programm, sondern sie enden damit.

Umwandeln von Großbuchstaben in Kleinbuchstaben

Das folgende Listing zeigt ein Brainfuck-Programm, welches einen Großbuchstaben einliest, diesen in den entsprechenden Kleinbuchstaben umwandelt und anschließend ausgibt. Zunächst wird das Zeichen mittels des Befehls , in die aktuelle Speicherzelle eingelesen. Danach addiert das Programm den Wert 32 – dargestellt durch 32 aufeinanderfolgende +-Befehle – zum ASCII-Code des Zeichens. Abschließend erfolgt die Ausgabe des resultierenden Kleinbuchstabens ü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 veranschaulicht die Multiplikation der Zahlen 8 und 4. Im ersten Schritt wird der Wert 4 in die aktuelle Speicherzelle addiert. Anschließend beginnt die Schleife: Da der Wert der Zelle ungleich 0 ist, werden die darin enthaltenen Befehle ausgeführt. Hierbei bewegt sich der Zeiger zunächst nach rechts auf eine leere Zelle, um deren Wert um 8 zu erhöhen. Danach kehrt das Programm zur Ausgangszelle zurück und dekrementiert deren Wert. Diese Schleife wird so lange wiederholt, bis der Wert der initialen Zelle 0 erreicht. Durch dieses Verfahren wird die Zahl 8 insgesamt viermal 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 den Einsatz dieser Technik läßt sich das Programm zur Umwandlung von Großbuchstaben in Kleinbuchstaben weiter verkürzen. Der einzige Unterschied betrifft den Abschnitt zwischen den Befehlen , und .. Während die erste Variante eine Länge von 35 Befehlen aufwies, umfaßt die folgende Implementierung lediglich 21 Befehle. Die Schleife in der Mitte des Quellcodes addiert viermal die Zahl 8 zum eingelesenen Zeichen, was im Ergebnis der benötigten Addition von 32 entspricht:

[Umwandeln von Grossbuchstaben in Kleinbuchstaben.]

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

Ausgabe von „Hello World!“

Das folgende Listing zeigt den Quellcode eines Programms, welches die Zeichenfolge „Hello World!“ ausgibt. Die genaue Funktionsweise wird direkt im Quelltext durch Kommentare erläutert:

[Ausgeben von "Hello World!".]

Berechne 2 * 6 = 12 in #0:
++            Zelle #0 auf 2 setzen
[             Solange #0 ungleich 0:
    >         Nach #1 gehen
    ++++++    #1 um 6 erhoehen
    <         Zurueck nach #0 gehen
    -         #0 um 1 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 verdeutlichen, ist in Brainfuck-Programmen jede Datenausgabe mit erheblichem Aufwand für den Programmierer verbunden. Befehle zum direkten Einlesen sowie zur Ausgabe numerischer Werte würden die Handhabung der Programmiersprache spürbar erleichtern. Zwar verfügt Brainfuck bereits über Instruktionen zur Ein- und Ausgabe, jedoch steigt der Programmieraufwand drastisch, sobald Zahlen ab einem Wert von 10 auszugeben sind, die sich aus mehreren Ziffern zusammensetzen. Aus diesem Grund läßt sich die Programmiersprache sinnvoll um die folgenden drei Befehle erweitern:

'

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 kein offizieller Bestandteil von Brainfuck und sollten daher nur mit Bedacht eingesetzt werden. Für die Fehlersuche (das sogenannte Debugging) während der Programmierung in Brainfuck können sie jedoch eine wertvolle Hilfe darstellen.

Unklarheiten in der Sprachspezifikation

Mangels einer formalen Spezifikation der Programmiersprache Brainfuck weichen die verschiedenen Compiler- und Interpreter-Implementierungen in wesentlichen Details voneinander ab. Im Internet zu findende Brainfuck-Programme sind daher oft nicht ohne weiteres mit jedem System kompatibel. Möglicherweise wird es in Zukunft eine allgemein anerkannte Spezifikation für Brainfuck geben, auf deren Grundlage konforme Compiler, Interpreter sowie standardisierter Quellcode entwickelt werden können.

Im Folgenden werden die signifikantesten Unterschiede beschrieben, die sich aus dieser fehlenden Spezifikation für die Implementierungen ergeben:

Unspezifizierte Speichergröße

Mehrere Quellen nennen einen Standardwert von 30.000 Byte. Die Größe des Speichers ist insbesondere dann von Bedeutung, wenn der Zeiger über dessen Grenzen hinaus bewegt wird. Einige Implementierungen stürzen in diesem Fall ab oder beenden die Ausführung des Brainfuck-Programms mit einer Fehlermeldung; andere hingegen berechnen den Index modulo der Gesamtzahl an Speicherzellen. Dieses Vorgehen kann wiederum zu unerwartetem Verhalten führen, wenn der Quelltext für eine beliebig große Speicherkapazität entwickelt wurde, die tatsächliche Maschine jedoch über weniger Speicher verfügt.

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.

Die meisten Implementierungen verwenden ein Byte (Datentyp unsigned char oder signed char) pro Speicherzelle; manche arbeiten hingegen mit einem Feld vorzeichenbehafteter 32-Bit-Ganzzahlen (Datentyp signed int). Einige Brainfuck-Compiler und -Interpreter bieten die Möglichkeit, einen Modulo-256-Modus zu aktivieren. Beim Datentyp unsigned char (mit einer Breite von 8 Bit) ist dies ohnehin automatisch der Fall, da ein Zeichenwert durch Überlauf oder das Addieren von 256 zyklisch reproduziert wird. Die Ein- und Ausgabe beschränkt sich in der Regel auf das ASCII-Zeichenrepertoire.

Implementierung eines Brainfuck-Interpreters in C

Bei dieser Implementierung des Brainfuck-Interpreters in C wurde darauf geachtet, die wesentlichen Funktionsmerkmale anderer verfügbarer Compiler und Interpreter zu unterstützen. Zudem sollte das System 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).

Voreinstellungen und Entwurfsentscheidungen

• Der Speicher umfaßt standardmäßig 30.000 Byte, wobei sich die Größe alternativ frei wählen läßt.

• Das Programm kann wahlweise mit Speicherzellen des Typs char oder int kompiliert werden.

• Mittels der Option m werden Berechnungen modulo 256 durchgeführt (was standardmäßig der Fall ist, wenn das Programm für den Typ char kompiliert wurde).

• Ohne aktivierte Option c werden selbst ungültige Programme so lange ausgeführt, bis ein Fehler auftritt. Dies kann dazu führen, daß Ein- und Ausgaben erfolgen, bevor der Interpreter das Programm aufgrund eines Fehlers abbricht. Bei der Validierung wird lediglich geprüft, ob sämtliche Schleifen korrekt geschlossen sind.

• Der Schleifenstapel bietet standardmäßig Platz für 100 Elemente, wobei die Kapazität alternativ frei gewählt werden kann. Die Verwendung eines solchen Stapels steigert die Performanz, da sich der Beginn einer Schleife zum Zurückspringen in konstanter Zeit ermitteln läßt.

• Die Optimierung beschränkt sich darauf, den Code von allen Kommentaren zu befreien und so die Ausführungsgeschwindigkeit zu erhöhen. Weitergehende Optimierungen, wie das Erkennen und Entfernen unerreichbaren Codes, wurden nicht vorgenommen.

• Bei der Implementierung wurde Zeigern gegenüber Arrays der Vorzug gegeben.

Fehlende Funktionen und Limitierungen

• Der Interpreter verfügt über keinen interaktiven Modus, welcher es erlauben würde, sowohl vom Brainfuck-Programm angeforderte Eingaben zu tätigen als auch Brainfuck-Befehle zur Laufzeit einzugeben.

• Der Zeiger verweist beim Programmstart auf die erste Zelle, sodaß ein <-Befehl fehlschlagen würde. Die initiale Zeigerposition ist nicht konfigurierbar.

• Der Speicher ist nicht als Ringspeicher konzipiert, besitzt folglich einen festen Anfang sowie ein definiertes Ende. Ein „Überlaufen“ zum entgegengesetzten Ende des Speichers bei Überschreiten der Grenzen ließe sich jedoch einfach implementieren.

Downloads

Weiterführende Informationen

Aminet – dev/lang/brainfuck-2.lha

Die Originalimplementierung des Brainfuck-Compilers für AmigaOS 2.0 von Urban Müller.

Daniel B. Cristofani: some brainfuck fluff

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: Brainf***

Anleitungen, ein in Java entwickelter Interpreter für Brainfuck und ein Brainfuck-Interpreter, der in Brainfuck geschrieben wurde.

Brian Raiter: The Brainfuck Programming Language

Verschiedene Brainfuck-Implementierungen.

Simon Howard: BrainFuck.Net

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