Brainfuck

Brainfuck ⓘ
Paradigma	Esoterisch, imperativ, strukturiert
Entworfen von	Urban Müller
Erstmals erschienen	September 1993
Disziplin des Tippens	Typlose
Dateinamen-Erweiterungen	.b, .bf
Beeinflusst durch
	P′′, FALSE
Beeinflusst
	Malbolge

Brainfuck ist eine esoterische Programmiersprache, die 1993 von Urban Müller entwickelt wurde. ⓘ

Die Sprache zeichnet sich durch ihren extremen Minimalismus aus: Sie besteht aus nur acht einfachen Befehlen, einem Datenzeiger und einem Befehlszeiger. Obwohl sie vollständig Turing-kompatibel ist, ist sie nicht für den praktischen Gebrauch gedacht, sondern um Programmierer herauszufordern und zu unterhalten. Brainfuck verlangt, dass man Befehle in mikroskopisch kleine Schritte zerlegt. ⓘ

Der Name der Sprache ist eine Anspielung auf den Slangbegriff Brainfuck, der sich auf Dinge bezieht, die so kompliziert oder ungewöhnlich sind, dass sie die Grenzen des eigenen Verständnisses überschreiten. ⓘ

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. ⓘ

Geschichte

Im Jahr 1992 übernahm Urban Müller, ein Schweizer Physikstudent, ein kleines Online-Archiv für Amiga-Software. Das Archiv wurde immer beliebter und wurde bald in der ganzen Welt gespiegelt. Heute ist es das größte Amiga-Archiv der Welt, bekannt als Aminet. ⓘ

Müller entwarf Brainfuck mit dem Ziel, den kleinstmöglichen Compiler zu implementieren, inspiriert von dem 1024-Byte-Compiler für die Programmiersprache FALSE. Müllers ursprünglicher Compiler war in Maschinensprache implementiert und wurde zu einer Binärdatei mit einer Größe von 296 Byte kompiliert. Er lud den ersten Brainfuck-Compiler 1993 ins Aminet hoch. Dem Programm lag eine "Readme"-Datei bei, die die Sprache kurz beschrieb und den Leser herausforderte: "Wer kann damit etwas Sinnvolles programmieren? :)". Müller fügte auch einen Interpreter und einige recht ausführliche Beispiele bei. Eine zweite Version des Compilers benötigte nur 240 Bytes. Derzeit gibt es viele Brainfuck-Compiler im Web. ⓘ

Als Aminet wuchs, wurde der Compiler in der Amiga-Gemeinde populär, und mit der Zeit wurde er auch für andere Plattformen implementiert. ⓘ

P′′: Brainfucks formale "Muttersprache"

Abgesehen von den beiden E/A-Befehlen ist Brainfuck eine kleine Variation der von Corrado Böhm 1964 entwickelten formalen Programmiersprache P′′, die wiederum ausdrücklich auf der Turing-Maschine basiert. Unter Verwendung von sechs Symbolen, die den jeweiligen Brainfuck-Befehlen +, -, <, >, [, ] entsprechen, lieferte Böhm ein explizites Programm für jede der Grundfunktionen, die zusammen zur Berechnung jeder berechenbaren Funktion dienen. Die ersten "Brainfuck"-Programme erscheinen also in Böhms Arbeit von 1964 - und sie reichten aus, um die Turing-Vollständigkeit zu beweisen. ⓘ

Der Unendliche Abakus: Brainfucks "Großeltern"-Sprache

Eine Version mit expliziter Speicheradressierung - anstelle von relativen Bewegungen auf einem Stapel - und einem bedingten Sprung - anstelle von Schleifen - wurde 1961 von Joachim Lambek unter dem Namen Infinite Abacus eingeführt, bestehend aus einer unendlichen Anzahl von Zellen und zwei Anweisungen:

X+ (Zelle X inkrementieren)
X- sonst Sprung T (Dekrementieren von X, wenn es positiv ist, sonst Sprung zu T)

Er beweist, dass der Unendliche Abakus jede berechenbare rekursive Funktion berechnen kann, indem er die Kleene-Menge der grundlegenden μ-rekursiven Funktion programmiert. ⓘ

Seine Maschine wurde von Melzacs Maschine simuliert, die die Berechnung durch Ari^thmetik (und nicht durch binäre Logik) nachahmt, indem sie einen menschlichen Bediener nachahmt, der Kieselsteine auf einem Abakus bewegt, daher die Anforderung, dass alle Zahlen positiv sein müssen. Melzac, dessen Ein-Befehl-Mengen-Computer einem unendlichen Abakus entspricht, gibt Programme für Multiplikation, gcd, die n-te Primzahl, die Darstellung zur Basis b, die Sortierung nach Größenordnung und zeigt, wie man eine beliebige Turing-Maschine simuliert. ⓘ

Aufbau der Sprache

Die Sprache besteht aus acht Befehlen, die unten aufgeführt sind. Ein Brainfuck-Programm ist eine Abfolge dieser Befehle, eventuell durchsetzt mit anderen Zeichen (die ignoriert werden). Die Befehle werden sequentiell ausgeführt, mit einigen Ausnahmen: Ein Befehlszeiger beginnt beim ersten Befehl, und jeder Befehl, auf den er zeigt, wird ausgeführt, danach geht es normalerweise weiter zum nächsten Befehl. Das Programm wird beendet, wenn der Befehlszeiger den letzten Befehl hinter sich gelassen hat. ⓘ

Die Brainfuck-Sprache verwendet ein einfaches Maschinenmodell, das aus dem Programm und dem Befehlszeiger sowie einem eindimensionalen Array von mindestens 30.000 Byte-Zellen besteht, die auf Null initialisiert werden; einem beweglichen Datenzeiger (der so initialisiert wird, dass er auf das am weitesten links stehende Byte des Arrays zeigt) und zwei Byteströmen für die Ein- und Ausgabe (die meist mit einer Tastatur bzw. einem Monitor verbunden sind und die ASCII-Zeichenkodierung verwenden). ⓘ

Befehle

Die acht Sprachbefehle bestehen jeweils aus einem einzigen Zeichen:

Zeichen	Bedeutung ⓘ
`>`	Erhöhen des Datenzeigers (um auf die nächste Zelle auf der rechten Seite zu zeigen).
`<`	Dekrementieren des Datenzeigers (um auf die nächste Zelle nach links zu zeigen).
`+`	Inkrementieren (um eins erhöhen) des Bytes am Datenzeiger.
`-`	Dekrementieren (Verringern um eins) des Bytes am Datenzeiger.
`.`	Ausgabe des Bytes am Datenzeiger.
`,`	Akzeptiere ein Byte der Eingabe und speichere dessen Wert in dem Byte am Datenzeiger.
`[`	Wenn das Byte am Datenzeiger Null ist, wird der Befehlszeiger nicht zum nächsten Befehl weitergeschoben, sondern springt zum Befehl nach dem passenden `]` Befehl.
`]`	Ist das Byte am Datenzeiger ungleich Null, dann wird der Befehlszeiger nicht zum nächsten Befehl vorwärts bewegt, sondern springt zurück zum Befehl nach dem passenden `[`-Befehl.

(Alternativ kann der ]-Befehl auch als unbedingter Sprung zum entsprechenden [-Befehl übersetzt werden oder umgekehrt; Programme verhalten sich dann gleich, laufen aber aufgrund der unnötigen doppelten Suche langsamer). ⓘ

[ und ] passen wie Klammern: jedes [ passt genau zu einem ] und umgekehrt, das [ kommt zuerst, und es kann kein unpassendes [ oder ] zwischen den beiden stehen. ⓘ

Brainfuck-Programme können mit den folgenden Substitutionen in C übersetzt werden, vorausgesetzt, ptr ist vom Typ char* und wurde so initialisiert, dass es auf ein Array von nullten Bytes zeigt:

Brainfuck-Befehl	C-Äquivalent ⓘ
(Programmstart)	`char array[30000] = {0}; char *ptr = array;`
`>`	`++ptr;`
`<`	`--ptr;`
`+`	`++*ptr;`
`-`	`--*ptr;`
`.`	`putchar(*ptr);`
`,`	`*ptr = getchar();`
`[`	`while (*ptr) {`
`]`	`}`

Wie der Name schon sagt, sind Brainfuck-Programme in der Regel schwer zu verstehen. Das liegt zum einen daran, dass jede halbwegs komplexe Aufgabe eine lange Folge von Befehlen erfordert, und zum anderen daran, dass der Programmtext keine direkten Hinweise auf den Zustand des Programms gibt. Dies sowie die Ineffizienz von Brainfuck und seine begrenzten Ein- und Ausgabemöglichkeiten sind einige der Gründe, warum es nicht für ernsthafte Programmierung verwendet wird. Nichtsdestotrotz ist Brainfuck, wie jede vollständige Turing-Sprache, theoretisch in der Lage, jede berechenbare Funktion zu berechnen oder jedes andere Rechenmodell zu simulieren, wenn man Zugang zu einer unbegrenzten Menge an Speicher hat. Es wurde eine Vielzahl von Brainfuck-Programmen geschrieben. Obwohl Brainfuck-Programme, insbesondere komplizierte, schwierig zu schreiben sind, ist es aufgrund ihrer Einfachheit recht trivial, einen Interpreter für Brainfuck in einer typischeren Sprache wie C zu schreiben. Es gibt sogar Brainfuck-Interpreter, die in der Brainfuck-Sprache selbst geschrieben sind. ⓘ

Brainfuck ist ein Beispiel für ein sogenanntes Turing-Tarpit: Man kann damit jedes beliebige Programm schreiben, aber es ist nicht praktisch, weil Brainfuck so wenig Abstraktion bietet, dass die Programme sehr lang oder kompliziert werden. ⓘ

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. ⓘ

Beispiele

Addieren von zwei Werten

Als erstes, einfaches Beispiel soll der folgende Codeschnipsel den Wert der aktuellen Zelle zur nächsten Zelle addieren: Bei jeder Ausführung der Schleife wird die aktuelle Zelle dekrementiert, der Datenzeiger wandert nach rechts, die nächste Zelle wird inkrementiert, und der Datenzeiger wandert wieder nach links. Diese Abfolge wird so lange wiederholt, bis die Startzelle 0 ist. ⓘ

[->+<] <span title="Aus: Englische Wikipedia, Abschnitt &quot;Adding two values&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Adding_two_values <span style="color:#dddddd">ⓘ</span>]</span>

Dies kann wie folgt in ein einfaches Additionsprogramm eingebaut werden:

++ Zelle c0 = 2
> +++++ Zelle c1 = 5 <span title="Aus: Englische Wikipedia, Abschnitt &quot;Adding two values&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Adding_two_values <span style="color:#dddddd">ⓘ</span>]</span>

[Beginnen Sie Ihre Schleifen mit dem Zellenzeiger auf dem Schleifenzähler (in unserem Fall c1)
< + Addiere 1 zu c0
> - Subtrahiere 1 von c1
]        Beenden Sie Ihre Schleifen mit dem Zellenzeiger auf dem Schleifenzähler <span title="Aus: Englische Wikipedia, Abschnitt &quot;Adding two values&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Adding_two_values <span style="color:#dddddd">ⓘ</span>]</span>

An dieser Stelle hat unser Programm 5 zu 2 addiert, was 7 in c0 und 0 in c1 ergibt
aber wir können diesen Wert nicht auf dem Terminal ausgeben, da er nicht ASCII-kodiert ist. <span title="Aus: Englische Wikipedia, Abschnitt &quot;Adding two values&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Adding_two_values <span style="color:#dddddd">ⓘ</span>]</span>

Um das ASCII-Zeichen "7" anzuzeigen, müssen wir 48 zu dem Wert 7 addieren.
Wir verwenden eine Schleife, um 48 = 6 * 8 zu berechnen. <span title="Aus: Englische Wikipedia, Abschnitt &quot;Adding two values&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Adding_two_values <span style="color:#dddddd">ⓘ</span>]</span>

++++ ++++ c1 = 8 und dies wird wieder unser Schleifenzähler sein
[
< +++ +++ Addiere 6 zu c0
> - Subtrahiere 1 von c1
]
< Geben Sie c0 aus, das den Wert 55 hat, was "7" entspricht!

ⓘ

Hallo Welt!

Das folgende Programm gibt "Hello World!" und einen Zeilenumbruch auf dem Bildschirm aus:

[ Dieses Programm gibt "Hello World!" und einen Zeilenumbruch auf dem Bildschirm aus, seine
  Länge beträgt 106 aktive Befehlszeichen. [Es ist nicht das kürzeste.] <span title="Aus: Englische Wikipedia, Abschnitt &quot;Hello World!&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Hello_World! <span style="color:#dddddd">ⓘ</span>]</span>

  Diese Schleife ist eine "anfängliche Kommentarschleife", eine einfache Art, einen Kommentar
  Kommentar zu einem BF-Programm hinzuzufügen, so dass man sich nicht um irgendwelche Befehlszeichen
  Zeichen. Alle ".", ",", "+", "-", "<" und ">" Zeichen werden einfach
  ignoriert, die Zeichen "[" und "]" müssen lediglich ausgeglichen werden. Diese
  Schleife und die darin enthaltenen Befehle werden ignoriert, weil die aktuelle Zelle
  standardmäßig den Wert 0 hat; der Wert 0 bewirkt, dass diese Schleife übersprungen wird.
]
++++++++ Zelle #0 auf 8 setzen
[
    >++++ Addieren Sie 4 zu Zelle 1; dadurch wird Zelle 1 immer auf 4 gesetzt
    [ da die Zelle durch die Schleife gelöscht wird
        >++ Addiere 2 zu Zelle #2
        >+++ Hinzufügen von 3 zu Zelle #3
        >+++ Hinzufügen von 3 zu Zelle #4
        >+ Hinzufügen von 1 zu Zelle #5
        <<<<- Dekrementieren des Schleifenzählers in Zelle 1
    ]                   Schleife, bis Zelle 1 Null ist; Anzahl der Iterationen ist 4
    >+ Addiere 1 zu Zelle #2
    >+ Addiere 1 zu Zelle #3
    >- Subtrahiere 1 von Zelle #4
    >+ Addiere 1 zu Zelle #6
    [Gehen Sie zurück zur ersten Nullzelle, die Sie finden; dies wird
                        Dies ist die Zelle 1, die in der vorherigen Schleife gelöscht wurde.
    <- Dekrementieren Sie den Schleifenzähler in Zelle #0
]                       Schleife, bis Zelle #0 Null ist; Anzahl der Iterationen ist 8 <span title="Aus: Englische Wikipedia, Abschnitt &quot;Hello World!&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Hello_World! <span style="color:#dddddd">ⓘ</span>]</span>

Das Ergebnis dieser Schleife ist:
Zelle Nr : 0 1 2 3 4 5 6
Inhalt:   0 0 72 104 88 32 8
Zeiger :   ^ <span title="Aus: Englische Wikipedia, Abschnitt &quot;Hello World!&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Hello_World! <span style="color:#dddddd">ⓘ</span>]</span>

>>.                     Zelle Nr. 2 hat den Wert 72, der 'H' ist.
>---.                   Subtrahiere 3 von Zelle #3, um 101 zu erhalten, was 'e' ist
+++++++..+++.           Das Gleiche gilt für 'llo' aus Zelle #3
>>.                     Zelle #5 ist 32 für das Leerzeichen
<-.                     Subtrahiere 1 von Zelle #4 für 87, um ein 'W' zu erhalten.
<. Zelle #3 wurde auf 'o' vom Ende von 'Hello' gesetzt
+++.------.--------.    Zelle #3 für 'rl' und 'd'
>>+.                    Addiere 1 zu Zelle #5 und wir erhalten ein Ausrufezeichen
>++.                    Und schließlich ein Zeilenumbruch in Zelle #6

ⓘ

Zur "Lesbarkeit" wurde dieser Code auf viele Zeilen verteilt und mit Leerzeichen und Kommentaren versehen. Brainfuck ignoriert alle Zeichen außer den acht Befehlen +-<>[],. daher ist keine spezielle Syntax für Kommentare erforderlich (solange die Kommentare nicht die Befehlszeichen enthalten). Der Code hätte genauso gut wie folgt geschrieben werden können:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. <span title="Aus: Englische Wikipedia, Abschnitt &quot;Hello World!&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#Hello_World! <span style="color:#dddddd">ⓘ</span>]</span>

Eine genauere Beschreibung des Hallo-Welt-Codes finden Sie hier. ⓘ

ROT13

Dieses Programm verschlüsselt seine Eingabe mit der ROT13-Chiffre. Dazu muss es die Zeichen A-M (ASCII 65-77) auf N-Z (78-90) abbilden, und umgekehrt. Außerdem muss es a-m (97-109) auf n-z (110-122) und umgekehrt abbilden. Es muss alle anderen Zeichen auf sich selbst abbilden; es liest ein Zeichen nach dem anderen und gibt ihre verschlüsselten Entsprechungen aus, bis es ein EOF liest (hier wird angenommen, dass es entweder als -1 oder "keine Änderung" dargestellt wird), woraufhin das Programm beendet wird. ⓘ

Der grundlegende Ansatz ist wie folgt. Aufrufen des Eingabezeichens x, Dividieren von x-1 durch 32, Behalten des Quotienten und des Rests. Wenn der Quotient nicht 2 oder 3 ist, wird x einfach ausgegeben, nachdem eine Kopie davon während der Division behalten wurde. Ist der Quotient 2 oder 3, wird der Rest ((x-1) modulo 32) durch 13 geteilt; ist der Quotient hier 0, wird x+13 ausgegeben; ist er 1, wird x-13 ausgegeben; ist er 2, wird x ausgegeben. ⓘ

Was den Divisionsalgorithmus betrifft, so gibt es bei der Division von y durch z, um einen Quotienten q und einen Rest r zu erhalten, eine äußere Schleife, die q und r zunächst auf den Quotienten und den Rest von 1/z, dann auf den von 2/z usw. setzt; nachdem sie y-mal ausgeführt wurde, endet diese äußere Schleife und lässt q und r auf den Quotienten und den Rest von y/z gesetzt. (Die Dividende y wird als abnehmender Zähler verwendet, der steuert, wie oft diese Schleife ausgeführt wird.) Innerhalb der Schleife gibt es Code zum Inkrementieren von r und Dekrementieren von y, was in der Regel ausreicht; allerdings muss bei jedem z-ten Durchlauf durch die äußere Schleife r auf Null gesetzt und q inkrementiert werden. Dies geschieht mit einem Verkleinerungszähler, der auf den Divisor z gesetzt wird; bei jedem Durchlauf durch die äußere Schleife wird dieser Zähler dekrementiert, und wenn er Null erreicht, wird er wieder aufgefüllt, indem der Wert von r zurück in ihn verschoben wird. ⓘ

-,+[ Erstes Zeichen lesen und äußere Zeichenleseschleife starten
    -[ Vorwärts springen, wenn Zeichen 0 ist
        >>++++[>++++++++<-] Einstellen des Divisors (32) für die Divisionsschleife
                               (SPEICHERAUFBAU: Dividende Kopie Rest Divisor Quotient Null Null)
        <+<-[ Dividende einrichten (x minus 1) und Divisionsschleife einleiten
            >+>+>-[>>>] Kopie und Rest erhöhen / Divisor verringern / Normalfall: vorwärts springen
            <[[>+<-]>>+>]    Sonderfall: Rest zurück zum Divisor verschieben und Quotient erhöhen
            <<<<<- Dividende vermindern
        ]                    Divisionsschleife beenden
    >>>>[-]+ Ende der Überspringungsschleife; ehemaliger Divisor auf Null setzen und Platz für ein Flag wiederverwenden
    >--[-[<->+++[-]]]<[ Dieses Flag auf Null setzen, es sei denn, der Quotient war 2 oder 3; Quotient auf Null setzen; Flag prüfen
        ++++++++++++<[ Wenn Flag, dann Divisor (13) für zweite Divisionsschleife einrichten
                               (SPEICHERLAYOUT: Null Kopie Dividende Divisor Rest Quotient Null Null)
            >-[>+>>] Divisor verkleinern; Normalfall: Rest erhöhen
            >[+[<+>-]>+>>]   Sonderfall: Rest erhöhen / zum Divisor zurückschieben / Quotient erhöhen
            <<<<<- Dividende vermindern
        ]                    Divisionsschleife beenden
        >>[<+>-] Rest wieder zum Divisor addieren, um eine sinnvolle 13 zu erhalten
        >[ Vorwärts springen, wenn Quotient 0 war
            -[ Quotient dekrementieren und vorwärts springen, wenn der Quotient 1 war
                -<<[-]>> Quotient und Divisor auf Null setzen, wenn der Quotient 2 war
            <<[<<->>-]>> Divisor auf Null setzen und 13 von der Kopie subtrahieren, wenn der Quotient 1 war
        <<[<<+>>-] Divisor auf Null setzen und 13 zur Kopie addieren, wenn der Quotient 0 war
    ]                        Äußere Sprungschleife beenden (hierher springen, wenn ((Zeichen minus 1)/32) nicht 2 oder 3 war)
    <[-] Rest der ersten Division löschen, wenn die zweite Division übersprungen wurde
    <.[-] ROT13-Zeichen aus der Kopie ausgeben und löschen
    <-,+ Nächstes Zeichen lesen
]                            Zeichenleseschleife beenden <span title="Aus: Englische Wikipedia, Abschnitt &quot;ROT13&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Brainfuck#ROT13 <span style="color:#dddddd">ⓘ</span>]</span>

Probleme der Übertragbarkeit

Teilweise weil Urban Müller keine gründliche Sprachspezifikation geschrieben hat, haben die vielen nachfolgenden Brainfuck-Interpreter und -Compiler leicht unterschiedliche Dialekte von Brainfuck implementiert. ⓘ

Größe der Zellen

In der klassischen Distribution haben die Zellen eine Größe von 8 Bit (Zellen sind Bytes), und dies ist immer noch die gängigste Größe. Um jedoch nicht-textuelle Daten zu lesen, muss ein Brainfuck-Programm unter Umständen eine End-of-File-Bedingung von jedem möglichen Byte-Wert unterscheiden; daher wurden auch 16-Bit-Zellen verwendet. Einige Implementierungen haben 32-Bit-Zellen, 64-Bit-Zellen oder Bignum-Zellen mit theoretisch unbegrenztem Bereich verwendet, aber Programme, die diesen zusätzlichen Bereich nutzen, sind wahrscheinlich langsam, da das Speichern des Wertes $n$ in einer Zelle erfordert $O(n)$ Zeit benötigt, da der Wert einer Zelle nur durch Inkrementieren und Dekrementieren geändert werden kann. ⓘ

In all diesen Varianten lesen und schreiben die Befehle , und . weiterhin Daten in Bytes. In den meisten dieser Varianten sind die Zellen umlaufend, d. h. das Inkrementieren einer Zelle, die ihren Maximalwert enthält (mit dem Befehl +), bringt sie auf ihren Minimalwert und umgekehrt. Ausnahmen sind Implementierungen, die weit von der zugrunde liegenden Hardware entfernt sind, Implementierungen, die Bignums verwenden, und Implementierungen, die versuchen, Portabilität zu erzwingen. ⓘ

Normalerweise ist es einfach, Brainfuck-Programme zu schreiben, die niemals einen Integer-Wraparound oder Überlauf verursachen und daher nicht von der Zellengröße abhängen. Im Allgemeinen bedeutet dies, dass eine Erhöhung von +255 (vorzeichenloser 8-Bit-Wraparound) oder ein Überschreiten der Grenzen von [-128, +127] (vorzeichenbehafteter 8-Bit-Wraparound) vermieden wird (da es keine Vergleichsoperatoren gibt, kann ein Programm nicht zwischen einer vorzeichenbehafteten und vorzeichenlosen Zweierkomplement-Zelle mit fester Bitgröße unterscheiden, und die Negativität von Zahlen ist eine Frage der Interpretation). Weitere Einzelheiten zum Integer-Wraparound finden Sie im Artikel Integer-Überlauf. ⓘ

Array-Größe

In der klassischen Verteilung hat das Array 30.000 Zellen, und der Zeiger beginnt in der Zelle ganz links. Es werden sogar noch mehr Zellen benötigt, um Dinge wie die millionste Fibonacci-Zahl zu speichern, und der einfachste Weg, die Sprache Turing-komplett zu machen, ist, das Array auf der rechten Seite unbegrenzt zu machen. ⓘ

Einige wenige Implementierungen erweitern das Array auch nach links; dies ist ein ungewöhnliches Merkmal, und daher sind portable Brainfuck-Programme nicht darauf angewiesen. ⓘ

Wenn sich der Zeiger außerhalb der Grenzen des Arrays bewegt, geben einige Implementierungen eine Fehlermeldung aus, andere versuchen, das Array dynamisch zu erweitern, wieder andere bemerken das nicht und erzeugen ein undefiniertes Verhalten, und wieder andere verschieben den Zeiger an das andere Ende des Arrays. Dabei gibt es einige Kompromisse: Das dynamische Erweitern des Arrays nach rechts ist der benutzerfreundlichste Ansatz und eignet sich gut für speicherhungrige Programme, geht aber zu Lasten der Geschwindigkeit. Wenn ein Array mit fester Größe verwendet wird, ist es hilfreich, es sehr groß zu machen, oder noch besser, den Benutzer die Größe festlegen zu lassen. Die Ausgabe einer Fehlermeldung bei Grenzwertverletzungen ist sehr nützlich für die Fehlersuche, aber auch das bringt einen Geschwindigkeitsverlust mit sich, es sei denn, die Speicherschutzfunktionen des Betriebssystems können dies verhindern. ⓘ

Code am Ende der Zeile

Verschiedene Betriebssysteme (und manchmal auch verschiedene Programmierumgebungen) verwenden leicht unterschiedliche Versionen von ASCII. Der wichtigste Unterschied liegt in dem Code, der für das Ende einer Textzeile verwendet wird. MS-DOS und Microsoft Windows verwenden in den meisten Kontexten ein CRLF, d. h. eine 13 gefolgt von einer 10. UNIX und seine Nachfahren (einschließlich Linux und macOS) sowie Amigas verwenden nur eine 10, und ältere Macs nur eine 13. Es wäre schwierig, wenn Brainfuck-Programme für verschiedene Betriebssysteme umgeschrieben werden müssten. Ein einheitlicher Standard war jedoch leicht zu schaffen. Urban Müllers Compiler und seine Beispielprogramme verwenden 10, sowohl bei der Eingabe als auch bei der Ausgabe; so auch die große Mehrheit der existierenden brainfuck-Programme; und 10 ist auch bequemer zu verwenden als CRLF. Daher sollten Brainfuck-Implementierungen sicherstellen, dass Brainfuck-Programme, die newline = 10 voraussetzen, korrekt laufen; viele tun dies, aber einige nicht. ⓘ

Diese Annahme stimmt auch mit den meisten Beispielcodes für C und andere Sprachen überein, da sie "\n" oder 10 für Zeilenumbrüche verwenden. Auf Systemen, die CRLF-Zeilenenden verwenden, setzt die C-Standardbibliothek "\n" bei der Ausgabe transparent auf "\r\n" und "\r\n" bei der Eingabe auf "\n" um, wenn die Datenströme nicht im Binärmodus geöffnet sind. ⓘ

Verhalten am Ende der Datei

Das Verhalten des Befehls , beim Auftreten einer Dateiende-Bedingung ist unterschiedlich. Einige Implementierungen setzen die Zelle am Zeiger auf 0, einige setzen sie auf die C-Konstante EOF (in der Praxis ist das normalerweise -1), einige lassen den Wert der Zelle unverändert. Es gibt keinen wirklichen Konsens; die Argumente für die drei Verhaltensweisen sind wie folgt. ⓘ

Das Setzen der Zelle auf 0 vermeidet die Verwendung negativer Zahlen und macht es geringfügig übersichtlicher, eine Schleife zu schreiben, die Zeichen liest, bis EOF auftritt. Dies ist eine Spracherweiterung, die von Panu Kalliokoski entwickelt wurde. ⓘ

Das Setzen der Zelle auf -1 erlaubt es, EOF von jedem Byte-Wert zu unterscheiden (wenn die Zellen größer als Bytes sind), was für das Lesen von nicht-textuellen Daten notwendig ist; außerdem ist es das Verhalten der C-Übersetzung von , die in Müllers Readme-Datei angegeben ist. Es ist jedoch nicht offensichtlich, dass diese C-Übersetzungen als normativ zu betrachten sind. ⓘ

Den Wert der Zelle unverändert zu lassen ist das Verhalten von Urban Müllers Brainfuck-Compiler. Dieses Verhalten kann leicht mit einem der beiden anderen koexistieren; zum Beispiel kann ein Programm, das EOF = 0 annimmt, die Zelle vor jedem ,-Befehl auf 0 setzen und wird dann bei Implementierungen, die entweder EOF = 0 oder EOF = "keine Änderung" verwenden, korrekt funktionieren. Es ist so einfach, das "no change"-Verhalten zu berücksichtigen, dass jeder Programmierer, der an Portabilität interessiert ist, dies tun sollte. ⓘ

Implementierungen

Obwohl es trivial ist, einen naiven Brainfuck-Interpreter zu erstellen, wird das Schreiben eines optimierenden Compilers oder Interpreters zu einer größeren Herausforderung und zu einem Vergnügen, ähnlich wie es das Schreiben von Programmen in Brainfuck selbst ist: Um einigermaßen schnelle Ergebnisse zu erzielen, muss der Compiler die fragmentarischen Anweisungen, die durch die Sprache erzwungen werden, zusammensetzen. Mögliche Optimierungen reichen von einfachen Lauflängen-Peephole-Optimierungen für wiederholte Befehle und häufige Schleifenmuster wie [-]bis hin zu komplizierteren Optimierungen wie der Eliminierung von totem Code und der Konstantenfaltung. ⓘ

Neben der Optimierung sind auch andere Arten von ungewöhnlichen Brainfuck-Interpretern geschrieben worden. Mehrere Brainfuck-Compiler wurden auf eine Größe von weniger als 200 Byte gebracht - einer davon ist nur 100 Byte in x86-Maschinencode. ⓘ

Ableitungen

Viele Leute haben brainfuck-Äquivalente (Sprachen mit Befehlen, die direkt auf brainfuck abgebildet werden) oder brainfuck-Derivate (Sprachen, die das Verhalten von brainfuck erweitern oder seine Semantik verändern) entwickelt. ⓘ

Einige Beispiele:

Pi, das brainfuck auf Fehler in einzelnen Ziffern von Pi abbildet.
VerboseFuck, das wie eine herkömmliche Programmiersprache aussieht, nur dass das, was als Parameter oder Ausdrücke erscheint, in Wirklichkeit Teile längerer Befehle sind, die nicht geändert werden können.
DerpPlusPlus, bei dem die Befehle durch Wörter wie "HERP", "DERP", "GIGITY" usw. ersetzt werden.
Ook!, das die acht Befehle von brainfuck auf Zwei-Wort-Kombinationen von "Ook.", "Ook?" und "Ook!" abbildet, die nach Angaben ihres Schöpfers scherzhaft so konzipiert sind, dass sie "von Orang-Utans geschrieben und gelesen werden können", eine Anspielung auf den Orang-Utan Librarian in den Romanen von Terry Pratchett.
Ternary, ein ähnliches Konzept wie Ook!, das jedoch aus Permutationen der ASCII-Zeichen 0, 1 und 2 besteht.
BodyFuck, eine BrainFuck-Implementierung, die auf einem gestengesteuerten System basiert, bei dem die Bewegungen des Programmierers von einer Videokamera erfasst und in die 8 möglichen Zeichen umgewandelt werden.
OooWee, Befehle sind Variationen von OooWee (z.B. ooo,ooe,wee etc.). Inspiriert von der Rick and Morty Figur Mr. PoopyButthole.
I Use Arch btw, das Brainfuck den Wörtern in der Phrase "I Use Arch btw" zuordnet. Inspiriert von einer Phrase, die von der Arch-Linux-Gemeinschaft geprägt wurde.
Brainfunk, bildet brainfuck auf Sprachsamples ab, die in einem Tanzstück verwendet werden, dessen Worte ein brainfuck-Programm kodieren.
DNA# ist ein Superset, das auf DNA-Molekülen basiert, wobei die Befehle durch Nucleobase ersetzt werden. Eine Form verwendet die Helix-Darstellung des DNA-Moleküls. ⓘ

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. ⓘ

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 und für ein endlich großes Feld aus Zellen unendlicher Größe durch Daniel B. Cristofani.
Für ein unendlich großes Feld aus Zellen unendlicher Größe durch Frans Faase. ⓘ

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. ⓘ

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

Einfache Schleife

  ,[.,] <span title="Aus: Deutsche Wikipedia, Abschnitt &quot;Einfache Schleife&quot;" class="plainlinks">[https://de.wikipedia.org/wiki/Brainfuck#Einfache_Schleife <span style="color:#dddddd">ⓘ</span>]</span>

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. ⓘ