1. Herfried K. Wagner’s VB.Any
  2. Diverses
  3. Artikel

Die esoterische Programmiersprache Brainf*ck

Entstehungsgeschichte

Die Programmiersprache Brainf*ck wurde von Urban Müller mit dem Ziel erschaffen, eine Turing-vollständige Programmiersprache zu entwickeln, um dafür auf Amiga OS 2.0 den kleinsten Compiler der Welt zu schreiben. Sein Compiler war 240 Bytes groß, aktuelle Versionen erreichen Größen von weniger als 200 Bytes. Das Ergebnis des Unterfangens, den Umfang der Programmiersprache bei gleichzeitigem Erhalt der Turing-Vollständigkeit möglichst gering zu halten, war eine Programmiersprache mit acht Befehlen. In der Turing-Vollständigkeit und der guten Lesbarkeit des Quellcodes unterscheidet sich Brainf*ck von vielen anderen esoterischen Programmiersprachen.

(Hinweis: Da der Begriff „Brainfuck“ unhöflich ist, sieht man stattdessen in Publikationen oft Schreibweisen wie „Brainf*ck“, „Brainf***“, „Brainfork“ und „BF“.)

Syntax und Semantik

Die einzigen Datenstrukturen in einer Brainf*ck-Maschine sind ein Array fester Größe und ein Zeiger. Dies erinnert bereits an den Aufbau einer Turing-Maschine. Brainf*ck ist daher in der Lage, jede Berechnungsaufgabe, die bei endlichem Speicherbedarf lösbar ist, durchzuführen. Die Befehle der Programmiersprache sind +, -, <, >, [, ], , und ..

+

Inkrementiert den Wert an der Stelle im Array, auf das der Zeiger verweist.

-

Dekrementiert den Wert an der Stelle im Array, auf das der Zeiger verweist.

<

Bewegt den Zeiger zum nächstniedrigen Index des Arrays (dekrementiert den Zeiger).

>

Bewegt den Zeiger zum nächsthöheren Index des Arrays (inkrementiert den Zeiger).

.

Zeigt das ASCII-Zeichen, welches dem Wert, auf den der Zeiger zeigt, entspricht, an.

,

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

[, ]

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

[

Springt nach die übereinstimmende ], wenn der Wert des Arrayelements, auf das der Zeiger verweist, null ist.

]

Springt zur übereinstimmenden [.

Alle anderen Zeichen werden als Kommentare interpretiert.

Die Semantik der Befehle von Brainf*ck kann leicht in Konstrukten der Programmiersprache C ausgedrückt werden. Folgende Liste führt die Entsprechungen der Befehle in C an, wobei davon ausgegangen wird, daß p als char *) definiert wurde:

Entsprechend der obenstehenden Äquivalenzliste ist es sehr einfach, ein Programm zu schreiben, das Brainf*ck-Quellcode nach C übersetzt.

Einfache Codebeispiele

Anders als bei anderen Programmiersprachen beginnen die einführenden Beispiele nicht mit einem „Hello World!“-Programm, sondern sie enden damit.

Umwandlung von Großbuchstaben in Kleinbuchstaben

Folgendes Listing zeigt den Quellcode, der Einlesen eines Großbuchstabens und der anschließenden Umwandlung und Ausgabe als Kleinbuchstabe erforderlich ist. Zuerst wird das Zeichen mit , in das Arrayelement, auf das der Zeiger verweist, eingelesen. Dann wird 32 (die 32 +-Befehle) zum ASCII-Wert des Zeichens addiert. Schließlich erfolgt die Ausgabe des Ergebnisses über .:

;
; Umwandlung und Ausgabe eines eingelesenen Großbuchstabens
; in einen Kleinbuchstaben_
;

; Einlesen eines Zeichens in #0_
,
; Addiere 32 zu #0_ 
++++++++++++++++++++++++++++++++
; Gib #0 zurück_
.

Multiplizieren zweier Zahlen

Dieses Beispiel zeigt, wie die Zahlen 8 und 4 multipliziert werden können. Im ersten Schritt wird 4 zum Inhalt des Arrayelements addiert. Anschließend wird die Schleife betreten. Da der Wert des aktuellen Arrayelements nicht null ist, werden die in der Schleife enthaltenen Befehle ausgeführt. Nachdem der Zeiger nach rechts auf ein leeres Arrayelement bewegt wurde, wird zu dessen Wert 8 addiert. Dann wird zum ersten Arrayelement zurückgegangen und dessen Wert dekrementiert. Die Schleife wird so lange ausgeführt, bis der Wert an der Stelle des Betretens null ist. Es ist offensichtlich, daß auf diese Weise die Zahl 8 vier Mal addiert wird:

;
; Multiplizieren von 8 und 4_
;

; #0 = 4_
++++
; Solange #0 nicht 0_
[
	; Gehe zu #1 und addiere 8~ dann gehe zurück zu #0 und
	; dekrementiere den dort gespeicherten Wert_
	>++++++++<-
]

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

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

Ausgabe von „Hello World!

Im folgenden Listing wird der Quellcode eines Programms wiedergegeben, das die Zeichenfolge „Hello World!“ ausgibt. Auf eine nähere Beschreibung wird hier verzichtet, da die Kommentare im Quellcode zum Verständnis ausreichend sein sollten:

;
; Schreibt "Hello World!" auf die Ausgabe_
;

; Zelle #0 auf 2 setzen_
++
; Solange #0 ungleich 0_
[
	; Nach #1 gehen_
	>
	; #1 um 6 erhöhen_
	++++++
	; Zurück nach #1 gehen_
	<
	; #0 erniedrigen_
	-
]
; Nach #1 gehen (#1 = 12)_
>
; Solange #1 ungleich 0 (wir wollen nun 12 * 6 = 72 = ASCII=
; Code von "H" in #0 berechnen)_
[
	; Nach #0 gehen_
	<
	; #0 um 6 erhöhen_
	++++++
	; Nach #1 gehen_
	>
	; #1 um 1 erniedrigen_
	-
]
; Nach #0 gehen_
<
; #0 als Zeichen ausgeben (#0 = 72)_
.
; Nach #1 gehen_
>
; #1 um 4 erhöhen_
++++
; Nachfolgende Zeichen werden nach dem selben Schema berechnet_
[
	>+++++<-
]
>
[
	<+++++>-
]
<+.+++++++..+++.>>+++++
[
	<++++++>-
]
<++.<<+++++++++++++++.>.+++.------.--------.>+.

Spracherweiterungen

Wie aus den Beispielen ersichtlich ist, ist jegliche Ausgabe von Daten mit einem großen Aufwand für den Entwickler verbunden. Funktionen zum Einlesen und zur Ausgabe von Zahlen würden die Benutzbarkeit der Programmiersprache erhöhen. Brainf*ck besitzt zwar bereits Befehle zur Ein- und Ausgabe, allerdings steigt der Aufwand, wenn Zahlen größer als 9 ausgegeben werden sollen. Deshalb kann die Programmiersprache um die drei Befehle ', : und @ erweitert werden:

'

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

:

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

@

Beendet die Ausführung an der aktuellen Position im Code. Dies ist nützlich, um das Programm in Schleifen zu beenden.

Es gilt zu beachten, daß diese drei Befehle nicht Teil von Brainf*ck sind und daher nicht unbedacht eingesetzt werden sollen. Zudem sind die Befehle redundant und stehen einer möglichen Standardisierung der Programmiersprache im Wege.

Annahmen für die Implementierung

Beispielcode in Brainf*ck, den man im Web findet, läuft oft nicht mit jedem Compiler oder Interpreter. Die Ursachen dafür liegen in der in vielen Punkten offenen Spezifikation der Programmiersprache. Im Folgenden werden die wichtigsten Unterschiede in den Implementierungen beschrieben:

Es bleibt zu hoffen, daß es in Zukunft einen Standard für Brainf*ck geben wird, sodaß man Compiler, Interpreter und Quellcode mit der Bezeichnung „Plain Brainf*ck 1.0 compliant“ versehen kann. Bei der Implementierung der hier angebotenen Interpreter wurde darauf Rücksicht genommen, die besten Funktionsmerkmale, die in den anderen verfügbaren Compilern und Interpretern enthalten sind, zu unterstützen.

Downloads

Interpreter und Beispiele (brainfuck.zip)

Projekte für Interpreter in Visual C# 2002 und Visual Basic 6.0 sowie Quellcodebeispiele in Brainf*ck.

Weiterführende Literatur

Im Folgenden werden einige Ressourcen mit Bezug auf die Programmiersprache Brainf*ck genannt:

The current Brainf*ck home page (Cat’s Eye Technologies)

Dieses Angebot wird als Teil der Website von Cat’s Eye Technologies von Chris Pressey betreut. Hier können die originalen Implementierungen des Compilers und Interpeters heruntergeladen werden.

The Brainfuck archive

Panu Kalliokoski betreut eine Sammlung von allen Dingen mit Bezug zu Brainf*ck: Compiler, Interpreter, Präprozessoren und jede Menge Brainf*ck-Quellcode.

Frans Faase’s web page on Brainfuck

Auf dieser Website gibt es Anleitungen, einen in Java entwickelten Interpeter für Brainf*ck und einen Interpeter, der direkt in Brainf*ck geschrieben wurde.

Frédéric van der Plancke’s Esoteric programming web page

Hier finden sich ein in Thue geschriebener Brainf*ck-Interpeter und ein in Python geschriebener Interpeter für BFM (Brainf*ck with Macros). Diese Website sticht unter den Websites zu esoterischer Programmierung durch die hohe Qualität der gebotenen Inhalte hervor.

The Brainfuck Programming Language

Eine kleine Website über Brainf*ck mit einigen netten Brainf*ck-Implementierungen.

BrainFuck.Net

Website von Simon Howard über einen in Python geschriebenen Compiler, der Brainf*ck-Quellcode nach MSIL übersetzt.

some brainfuck fluff by daniel b cristofani

Auf dieser Website werden einige großartige Quellcodes und Informationen zu Brainf*ck präsentiert und es wird auf Bestrebungen zur Standardisierung der Programmiersprache eingegangen.