Zum Inhalt springen

Brainfuck

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 27. April 2005 um 09:24 Uhr durch 84.167.196.11 (Diskussion) (→Weiteres). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Brainfuck ist eine minimalistische Programmiersprache, entworfen vom Schweizer Urban Müller um 1993. Die Sprache wird manchmal auch Brainf*ck, Brainf*** oder BF genannt.

Allgemeines

Müllers Ziel war es, eine einfache turingvollständige Sprache zu entwerfen, welche mit einem möglichst kleinem Compiler implementiert werden konnte - inspiriert wurde er dabei durch False, eine andere esoterische Programmiersprache, deren Compiler nur 1024 Byte groß war. Er schaffte es schließlich, die zweite Version seines Compilers für den Amiga in nur lediglich 240 Byte zu schreiben. Brian Raiter gelang es, dies zu unterbieten, indem er - unter Verwendung von nur 171 Bytes - einen BF Compiler für x86 Linux schrieb.

Sprachdesign

Ein BF-Programm ähnelt stark der formalen Definition einer Turing-maschine, statt eines Lese-/Schreibkopfes auf einem Band, Zuständen sowie einem frei definierbarem Alphabet werden jedoch im Sinne einer iterativen Programmiersprache ein Zeiger auf ein Datenfeld, Schleifenkonstrukte und eine rudimentäre ALU verwendet. Der Programmcode wird dabei separat vom Datenfeld abgelagert. (siehe Harvard-Architektur)

Befehlssatz

Brainfuck besitzt acht Befehle, jeweils bestehend aus einem einzigen Zeichen:

Zeichen C Equivalent Semantik
> ++ptr; inkrementiert den Zeiger
< --ptr; dekrementiert den Zeiger
+ ++*ptr; inkrementiert den aktuellen Zellenwert
- --*ptr; dekrementiert den aktuellen Zellenwert
. putchar(*ptr); Gibt den aktuellen Zellenwert als ASCII-Zeichen auf der Standardausgabe aus
, *ptr = getchar(); Liest ein Zeichen von der Standardeingabe und speichert dessen ASCII-Wert in der aktuellen Zelle
[ while (*ptr) { Springt nach vorne, hinter den passenden ]-Befehl, wenn der aktuelle Zellenwert null ist
] } Springt zurück, hinter den passenden [-Befehl, wenn der aktuelle Zellenwert verschieden von null ist

Anmerkung: Es gibt verschiedene semantisch äquivalente Varianten der letzten beiden Befehle, die hier angegebenen sind jedoch implementationstechnisch betrachtet die effizientesten.

Turing-Vollständigkeit

Für verschiedene BF-Umgebungen wurde Turing-Vollständigkeit bewiesen:

  • Für ein unendlich großes Feld aus Zellen unendlicher Größe ([1]) durch Frans Faase
  • Für ein unendlich großes Feld aus Zellen endlicher Größe ([2]) durch Daniel B. Cristofani
  • Für ein endlich großes Feld aus Zellen unendlicher Größe ([3]) durch Daniel B. Cristofani

Bei einer BF-Variante mit endlicher Zellgröße sowie endlicher Feldgröße (z.B. BFmin) handelt es sich um einen endlichen Automaten; sie kann somit nicht turingvollständig sein.

Grundlagen der Programmierung in Brainfuck

Anmerkung: Obwohl die Zeichen // wie die aus anderen Programmiersprachen bekannten Kommentare aussehen, sind es keine. Deshalb wird das Pluszeichen in n+1 als ein Inkrementierbefehl ausgewertet. Die unten angegebenen Beispiele funktionieren daher nur, wenn man die Kommentare aus dem Programmtext löscht.

Schleifen

Schleifen beginnen mit [ und enden mit ]. Die Schleife wird solange ausgeführt, wie der Wert der aktuellen Zelle ungleich Null ist. Die einfachste Form ist die Nullschleife, die die aktuelle Zelle dekrementiert, bis diese Null ist: 

 [-]

Rechenoperationen

 [>+<-]
  • Kopieren eines Wertes erfolgt durch das verschieben in 2 Folgezellen und anschließendes Zurückverschieben:
 >[-]>[-]            // nur notwendig wenn die beiden Variablen nicht leer sind
 <<[>+>+<<-]         // verschiebe Inhalt von Zelle n nach Zellen n+1 und n+2
 >>[<<+>>-]          // verschiebe Inhalt von Zelle n+2 nach Zelle n
 <<                  // gehe wieder auf Zelle n
  • Addition. p[1] = p[1] + p[0]; Nebeneffekt: p[0] = 0
 [>+<-]

 [>-<-]
  • Multiplikation mit einer Konstanten: p[1] = p[0] * 5; Nebeneffekt: p[0] = 0

Es wird eine normale Verschiebung durchgeführt, wobei die Zielzelle nicht jeweils um eins, sondern um den entsprechenden Faktor erhöht wird. 

 [>+++++<-]
  • Multiplikation mit einem Zellenwert: Hier wird der 2. Faktor wiederholt zum Produkt mittels obiger Kopierfunktion addiert:
 p[2] = p[0] * p[1]; Nebeneffekt: p[0] = p[3] = 0
 [>[>+>+<<-]>>[<<+>>-]<<<-]
  • Potenzieren: Eine Zahl mit +++ in eine Zelle zu schreiben, wird spätestens ab zweistelligen Zahlen mehr als aufwändig. Also behilft man sich mittels Potenzen:
 p[2] = 5^3 = 125; Nebeneffekt: p[0] = p[1] = 0
 +++++[>+++++[>+++++<-]<-]
  • Division funktioniert am einfachsten als restlose Division, alles andere resultiert in dem Fall in einer Endlosschleife. Die Idee ist ansonsten dieselbe wie bei der Multiplikation:
 p[1] = p[0] / 5; Nebeneffekt: p[0] = 0
 [>+<-----]
  • Restbehaftete Division in Brainfuck ist hingegen etwas komplizierter:
 // Der C-Code zum nachfolgenden Brainfuck-Programm
 while(p[0]--) {
   p[1]--; 
   p[2]++;
   if(p[1] == 0) {
     p[3]++;
     p[1] = p[2];
     p[2] = 0;
   }
 }

 // p[2] = p[0] % p[1]
 // p[3] = p[0] / p[1]
 // Nebeneffekt: p[0] = 0; p[1] = p[1] - p[0] % p[1]
 >>[-]>[-]>[-]>[-]<<<<<[->>+<-[>>>]>[[<+>-]>+>>]<<<<<]

Weiteres

Weiterhin existiert die Programmiersprache Brainfuck2D, die das Brainfuck-Konzept in einen 2-dimensionalen Zeichenraum portiert. Dabei wird mit Textzeichen eine Schnur gebildet, ihre Richtung gibt den entsprechenden Brainfuck-Befehl an wobei die länge unbedeuten für die Anzahl der aufrufe ist. Ein Befehl wird entsprechend der Summe aller Zahlen auf seinem Abschnitt wiederholt. So ist +********* der gleiche Befehl wie +** , +93*** führt den Befehl jedoch 12 mal aus (9+3=12). der Befehl +0**** wird nicht interpretiert, da er 0 mal ausgeführt wird. So kann man sich Platz für seine Schnur verschaffen, sollte dieser einmal nicht reichen. Ist der Verlauf der Schnur für den Interpreter nicht eindeutig erkennbar oder endet die Schnur wird das Programm beendet.

Brainfuck

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Brainfuck&oldid=5579574“