Introducing „brainfuck“

Ist das etwa obszön?

Und ob das szön ist! Nein, „brainfuck“ ist eine sogenannte esoterische Programmiersprache mit nur 8 Befehlen.

Sie ist Turing-vollständig, was nichts weniger bedeutet als dass man mit dieser Sprache und der entsprechenden „Maschine“, die sie ausführt, alles berechnen kann, was sich berechnen lässt. Genügend Zeit und Speicherplatz vorausgesetzt. Man sollte „genügend“ aber im Zusammenhang mit Turing-Vollständigkeit geistig immer mit „beliebig viel“ hinterlegen! Insbesondere Zeit; stellt sich doch später heraus, das Speicher für die meisten „alltäglichen“ Sachen nicht größer als 20-100 Zellen sein muss. Um aber z.B. die Fakultät von 7 (7! = 2*3*4*5*6*7 = 5040) zu berechnen, braucht meine eigene Implementierung (siehe unten) mehr als 160000 ausgeführte Instruktionen. Aber nur 9 Speicherzellen.

Warum „brainfuck“?

Die Sprache wurde explizit mit dem Ziel entworfen, den kleinst-möglichen Compiler zu ermöglichen („imperativ minimal“). Gerüchten zufolge besteht der kleinste auf einer x86-Maschine ausführbare Compiler aus mageren 191 Bytes. Das zweite Ziel war die bereits angesprochene Turing-Vollständigkeit.

Der Name „brainfuck“ hat sich dann erst ergeben, nachdem man versucht hat, mit dieser Sprache tatsächlich etwas zu berechnen. Ich kann das nachvollziehen!

brainfac(7)before

brainfuck (16-Bit, unsigned, 20 Speicherzellen) vor, …

brainfac(7)while

… wärend und …

brainfac(7)after

… nach der Berechnung der Fakultät von 7.

(bevor jemand fragt: die Screenshots sind von meiner im Selbstbau befindlichen „brainfuck IDE„)

Architektur der Maschine

Brainfuck basiert im Gegensatz zu den meisten heutigen Rechnerarchitekturen (von-Neumann Architektur) auf der sogenannten Harvard-Architektur, die auch die ursprüngliche Turing-Maschine aufweist, obwohl dieser Begriff damals noch nicht geprägt war. Die Turingmaschine wurde von Alan Turing 1936 vorgestellt und die Harvard-Architektur datiert von ca. 1942/43, die erste physikalisch funktionierende Harvard-Maschine wurde 1944 in Betrieb genommen.

Von-Neumann-Maschinen halten die Daten und den Programmcode im gleichen Speicher, Harvard-Maschinen haben getrennte Speicher für Daten und Instruktionen. Heutige Rechner (PCs) sind (fast) ausschließlich von-Neumann-Maschinen, egal ob von Intel, AMD, Arm-Prozessoren oder was auch immer. Die Grafikkarten heutiger PCs sind allerdings (fast) allesamt Harvard-Maschinen, da sie physikalisch getrennte Speicher erstens für die Grafikinhalte und deren Berechnung und zweitens für die Shader-Programme haben.

Für die tägliche Praxis hat das aber wenig Bedeutung, außer man will selbstmodifizierenden Code, dann braucht man die von-Neumann-Architektur zwingend. Aber selbstmodifizierenden Code will man eigentlich nicht haben.

Speicher

Arbeitsspeicher

Der Speicher der urprünglichen Turingmaschine war ein unendlich langes Band aus Zellen in denen der Wert 0 oder 1 gespeichert werden konnte.  Der Speicher einer brainfuck-Maschine besteht prinzipiell ebenfalls aus beliebig vielen Speicherzellen, was man in der täglichen brainfuck-Praxis natürlich begrenzen muss.

Außerdem kann jede Speicherzelle nicht nur (aber auch) 1 Bit speichern sondern prinzipiell beliebig (aber begrenzt) viele. Die „üblichen“ Implementierungen benutzen ganzzahlige Werte (mit oder ohne Vorzeichen) mit 8, 16 oder 32 Bit.

Es gibt einen einzigen Zeiger in diesen Speicher. Der zeigt auf diejenige Zelle, die durch Instruktionen im Programmspeicher manipuliert werden kann.

Programmspeicher

Der Programmspeicher ist, wie gesagt, „physikalisch“ vom Datenspeicher getrennt. In ihm befindet sich der Programmtext, der sich während des Programmablaufs nicht verändern kann. Es gibt einen einzigen Zeiger, der auf die nächste auszuführende Instruktion der CPU (siehe unten) zeigt. Je nach Instruktion (und Inhalt der Zelle auf die der aktuelle Speicherzeiger zeigt) kann der Instruktions-Zeiger sich verändern.

CPU

Die CPU besteht aus dem Datenspeicher, dem Programmspeicher, zwei Registern (Datenzeiger und Befehlszeiger) und dem Rechenwerk (ALU). Der Datenspeicher ist beim „Systemstart“ mit Null initialisiert, der Datenzeiger (Memory Pointer, MP) zeigt auf Speicherzelle Null. Der Programmspeicher enthält das auszuführende Programm, der Befehlszeiger (Instruction Pointer, IP) steht ebenfalls auf Null, was in diesem Falle dem ersten Programmbefehl entspricht,

Befehlssatz (Instruction Set)

<>+-[].,

Ja, das war jetzt der komplette „Befehlssatz“ dieser Sprache. Im Einzelnen:

  1. „<„:
    Bewege den MP eine Position nach links.
  2. „>“:
    Bewege den MP eine Position nach rechts.
  3. „+“:
    Addiere 1 zu der Speicherzelle auf die der MP zeigt.
  4. „-„:
    Subtrahiere 1 von der Speicherzelle auf die der MP zeigt.
  5. „[„:
    Wenn der Wert der Speicherzelle auf die der MP zeigt, ungleich Null ist, erhöhe den IP um 1; ansonsten setze den IP auf die Stelle nach dem „passenden“ „]“.
    Man kann sich das als eine Art „if (*MP)“ vorstellen.
  6. „]“:
    Wenn der Wert, auf den der MP zeigt, Null ist, erhöhe den IP um 1, ansonsten setze den IP auf die Stelle nach dem passenden „[“ (rückwärts).
    Man kann sich das als eine Art „while (*MP)“ vorstellen.
  7. „.“ (Punkt):
    Wartet auf eine Eingabe (von der Tastatur, …) und schreibt den ASCII-Wert in die Speicherzelle, auf die der MP zeigt.
  8. „,“ (Komma):
    Gibt das ASCII-Zeichen entsprechend der Speicherzelle, auf die der MP zeigt, aus.

To be continued:

  • Der nächste Artikel befasst sich dann mit einfachen Algorithmen – ich nenne sie „Idiome“
  • Später werde ich genauer auf meine „brainfuck IDE“ eingehen.

Wer jetzt schonmal rumexperimentieren will, kann das hier:

http://fatiherikli.github.io/brainfuck-visualizer/#

, , , , , , , , , , , ,

  1. Introducing “brainfuck”: Idiome | Y371

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: