Introducing „brainfuck“: Idiome

(Dieser Artikel ist die Fortsetzung von Introducing „brainfuck“)

Idiome

„Idiome“ im Sinne (meiner Implementierung) von „brainfuck“ sind kurze, immer wiederkehrende Code-Sequenzen, die man tausende Male am Tag braucht, wenn man produktiv mit brainfuck arbeiten will. Was kein Mensch will, der noch einigermaßen bei Verstand ist.

Die „Hardware“

Meine „brainfuck“ (bf) Maschine besteht aus 20 Speicherzellen die jeweils eine 16-Bit-Zahl ohne Vorzeichen beinhalten (0x0000 bis 0xFFFF). Inkrementiert man (2^16)-1 bekommt man eine Null. Dekrementiert man die Null, erhält man (2^16)-1 (0xFFFF). Prinzipiell kann ich jeden ganzzahligen Datentyp benutzen („generic brainfuck“), aber 16-Bit unsigned hat sich als guter Kompromiss herausgestellt zwischen Laufzeiten für simples Löschen u.Ä. und dem, was man berechnen kann, ohne gleich Multi-„Byte“ Datentypen zu implementieren. Oder gar float.

Wenn ich mich mal so richtig scheiße fühle und Bock auf Alpträume habe, fange ich vielleicht mal eine floating-point Addition an …

Fehlerzustände oder gar -Meldungen gibt es keine.

Ein bf-Programm wird so lange ausgeführt, bis eine der folgenden Bedingungen zutrifft:

  • Der Speicherzeiger wird über die Grenzen des vorhandenen Speichers hinaus verschoben.
  • Der Befehlszeiger wird über die Grenzen des vorhandenen Programms hinaus verschoben. Üblicherweise bedeutet das, dass das Programm am Ende angekommen ist.
  • Nicht bekannte Instruktionen (bis auf eine Ausnahme, siehe unten) werden einfach ignoriert und der IP (Befehlszeiger) einfach eine Position weiter geschaltet.
  • Der „Interpreter“ trifft auf den Befehl „!“. Das ist eine von mir eingeführte Erweiterung der Sprache. Es repräsentiert einen Breakpoint. Meine Maschine wird angehalten und man kann sich alle Speicherinhalte usw. in Ruhe angucken. Danach kann man die Maschine weiter laufen lassen.

Programmier-Philosophie/-Modell

Ich habe mich (nach reiflichen Überlegungen) dazu entschlossen, ein Stack-basiertes Programmiermodell zu realisieren, weil ich anderweitig nicht so richtig klar kam.

Das bedeutet, dass ein bf-Idiom immer davon ausgeht, dass die Werte mit denen es arbeitet links vom aktuellen Speicherzeiger (MP) liegen und rechts davon „alles frei“ ist. „Alles frei“ kann verschiedenes bedeuten:

  1. Man geht davon aus, dass alle Zellen rechts von „uns“ auf Null stehen.
    Dafür muss alles in einer Art und Weise implementiert werden, dass nicht mehr zu benutzende Zellen während der Berechnung bis auf Null heruntergezählt werden.
  2. Man löscht jede Zelle „rechts von uns“ bevor man sie benutzt.

Die Standard-Annahme ist bei meiner Maschine der Punkt 2. Die Standard-Implementierung versuche ich laut Punkt 1 zu realisieren. Damit kann man den „Overhead“, den es zum Löschen einzelner Zellen braucht, ganz gut managen.

Erste Schritte

Kommentare

Als netter „Trick“, Programme (egal welcher Programmiersprache) les-, interpretier- und wartbar zu machen, gelten Kommentare im Quelltext des Programms. Netterweise ignoriert brainfuck jede in der Sprache nicht vorhandene Instruktion, so dass man ohne weiteres

+++++> ; Add 5 to top of stack (ToS/*MP)

schreiben kann. Aber wehe, es befinden sich gültige brainfuck-Befehle im Kommentar, die werden gnadenlos ausgeführt; in meiner Implementierung auch die Breakpoints (‚!‘). Weiß man aber, dass die aktuelle Speicherzelle (*MP) Null ist, kann man zwischen ‚[‚ und ‚]‘ jeden beliebigen Text unterbringen, weil er nicht interpretiert wird:

[ - Push the number 5 onto the stack, then move the MP one place to the right (*MP++)!
    + <xmlTag>name = "....bl+.[]ah"</>:
    + Code is: "+++++>"
    (das war jetzt albern. Aber es geht um's Prinzip!)
]
+++++>

Es gibt eine Einschränkung: die Anzahl der ‚[‚ im Kommentar muss derjenigen der ‚]‘ entsprechen. Nach einem ‚;‘ als Kommentareinleitung würde solcher Text ohne die „[…]“ – Konstruktion ziemlichen Bruch anrichten.

*MP = 0 (Nullsetzen der aktuellen Speicherzelle)

Brainfuck kann bedingt durch seinen begrenzten Befehlssatz nicht einfach eine Speicherzelle löschen oder gar einen bestimmten Wert hinein schreiben. Also muss man anders vorgehen.

Durch die eben erwähnte Standard-Annahme (2) (löschen der Zelle bevor man sie benutzt) ergibt sich mein 1. Idiom. Es benutzt die bf-Instruktionen „[“ (if), „“ (Dekrement) und „]“ (while). Umgangssprachlich bleibt einem bei bf nichts anderes übrig, als solange 1 von der Speicherzelle abzuziehen (oder zu addieren), bis sie Null ist. Man will also zuerst wissen, ob die Speicherzelle auf die der MP zeigt nicht schon Null ist:

[„:

  • ist die Zelle bereits Null, wird im Programmtext vorwärts die passende „]“ Klammer gesucht und der IP dahinter gesetzt. Falls nicht, wird der IP auf den nächsten Befehl gesetzt:

„:

  • von der Zelle auf die der MP zeigt, wird 1 subtrahiert. Der IP wird auf den nächsten Befehl gesetzt:

]„:

  • ist der Inhalt der Zelle auf die der MP zeigt Null, wird der IP um eins erhöht und dieses „Idiom“ ist zuende. Falls nicht, wird rückwärts die passende „[“ Klammer gesucht und der IP dahinter gesetzt, es wird also weiter dekrementiert.

Hinweis: wärend dieses ganzen Ablaufs hat sich der MP nicht verändert, er zeigt die ganze Zeit auf die zu löschende Zelle!

Zusammengefasst: (*MP = 0) lautet in bf „[-]“ (ohne die „“). Die maximale Laufzeit ist direkt proportional zur maximal darstellbaren Zahl der implementierten Maschine, d.h. eine 16-Bit bf-Maschine braucht maximal 256-mal so lange eine Zahl zu löschen, wie eine 8-Bit Maschine braucht.

*MP = X (Konstanten, numerisch)

  1. +
  2. ++
  3. +++
  4. … usw.

Das soll für diesmal genügen.

Im nächsten Artikel geht es dann um konkrete Idiome, die Daten nicht nur verändern, sondern geziehlt bewegen oder vervielfältigen.

, , ,

  1. Hinterlasse einen Kommentar

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: