00 Was ist Befunge?

Befunge – Wikipedia

Befunge ist eine esoterische Programmiersprache von Chris Pressey.

Chris Pressey erfand Befunge 1993 mit dem Ziel, eine möglichst schwer kompilierbare Sprache zu definieren. Eine Schwierigkeit für Compiler stellt beispielsweise das p-Kommando dar, welches das Programm zur Laufzeit dynamisch verändern kann.

Das Programm besteht aus ASCII-Zeichen in einer 80×25 Zeichen großen Anordnung. Alle Funktionen werden auf einem Stapel (Stack) ausgeführt.

Die Grundlagen von Befunge-93

Das wohl einzigartigste Element der Befunge-93-Programmierung ist der Programmzähler (PC). In fast allen Computerprogrammiersprachen bewegt sich der Programmzähler kontinuierlich vorwärts durch das Programm, wobei er gelegentlich zu einer anderen Stelle im Code springt (aber trotzdem weiterläuft).

Für den PC in Befunge-93 gelten jedoch andere Regeln. Er kann sich vorwärts, rückwärts, links oder rechts bewegen. Ein Befunge-93-Programm wird wie ein 80×25 Torus (eine Seite, die an den Rändern umläuft) aus ASCII-Text behandelt. Bestimmte Befehle ändern die Richtung des Fortschritts des PCs. Standardmäßig zeigt der PC auf die obere linke Ecke des Programms und ist so ausgerichtet, dass er sich von links nach rechts bewegt.

Jeder Befehl in Befunge-93 ist ein einzelnes Zeichen, ebenso wie die größte Dateneinheit, die im Quelltext des Programms angegeben werden kann; Befunge-93-Programme haben eine maximale Größe von insgesamt 80×25 Befehlen und Datenbytes. Es gibt keine Laufzeitvariablen, sondern nur einen einzigen Laufzeitstapel. Befunge-93-Programme können selbst modifiziert werden. Aufgrund der 2-dimensionalen Natur des PCs erlauben sie auch einige extrem skurrile Codes.

Der Stapel

Ähnlich wie Forth und PostScript unterstützt Befunge-93 einen LIFO, Reverse Polish Notation (RPN oder Postfix) Stack aus vorzeichenbehafteten Long-Integer-Zahlen (d.h. jede Zelle des Stacks kann so viel wie ein vorzeichenbehafteter Long-Int in der Sprache C auf der gleichen Plattform enthalten).

Der Vorgang, einen Wert auf den Stapel zu legen, wird “Push” genannt, und der Vorgang, einen Wert vom Stapel zu nehmen, wird “Pop” genannt.

Die Ziffern von 0 bis 9 sind gültige Befunge-93-Befehle, die ihre jeweiligen Werte auf den Stack schieben. Ein doppeltes Anführungszeichen ” schaltet den Zeichenkettenmodus um, und während der Zeichenkettenmodus aktiv ist, wird der ASCII-Wert aller Zeichenzellen auf den Stapel geschoben, bis ein weiteres ” gefunden wird.

Es gibt ein paar grundlegende Rechenbefehle:

+Addition
Subtraktion
/Ganzzahlige Division
*Multiplikation
%Modulo
!logische Negation

Diese werden im Abschnitt Befehle näher erläutert.

Um eine Zahl größer als 9 auf den Stack zu schieben, müssen Berechnungen mit Zahlen kleiner oder gleich 9 durchgeführt werden. In jeder anderen Sprache wäre dies ein Problem. In Befunge-93 ist es eine Freude. Um zum Beispiel ‘123’ auf den Stapel zu schieben, könnte man 9 schieben, dann 9, dann multiplizieren (so dass 81 übrig bleibt), dann 7 schieben, dann 6, dann multiplizieren (so dass 81 und 42 übrig bleiben), dann addieren (so dass 123 übrig bleibt.): 9976+

Dies setzt natürlich voraus, dass der PC bei oder vor der ersten 9 beginnt und nach rechts arbeitet. Wenn dieser Ausschnitt ein komplettes Befunge-93-Programm darstellt, ist diese Annahme richtig: Der PC beginnt oben links im Torus und ist zunächst nach rechts ausgerichtet.

Wenn der Stack leer ist, wenn Sie etwas aus dem Stack herausnehmen, sollten Sie sich darüber im Klaren sein, dass dies nicht zu einem Unterlauf führen wird! Es wird einfach ein Wert von 0 auf den Stack geschoben.

Der Programmzähler im Detail

Es gibt 5 Befehle, die bedingungslos die Richtung des PC steuern:

>Bewege den PC nach rechts
<Bewege den PC nach links
vBewege den PC nach unten
^Bewege den PC nach oben
?Bewege den PC in eine zufällige Richtung

Sollte der PC auf den “Rand” des Programms stoßen, wird einfach auf der anderen Seite weitergemacht.

Verzweigungen

Die Standard-‘if’-Anweisung in Befunge-93 ist entweder _ oder |, je nachdem, wie Sie verzweigen wollen. Bei beiden Anweisungen wird ein Wert vom Stapel genommen und geprüft, ob er wahr (ungleich Null) ist, und die Richtung des PCs entsprechend geändert:

_verhält sich wie <, wenn der Wert wahr ist, oder >, wenn er falsch ist
|verhält sich wie ^, wenn der Wert wahr ist, oder wie v, wenn er falsch ist

While”-Schleifen können durch Einfügen eines “if” in eine Endlosschleife erstellt werden. Zum Beispiel _@

Dieses Programmfragment löscht alle Nicht-Null-Werte vom Stapel und den ersten Null-Wert und beendet sich dann [@ ist der Exit-Befehl]

Eingabe

&holt einen numerischen Wert (dezimal) von der Standardeingabe und schiebt ihn auf den Stapel
~holt das nächste ASCII-Zeichen von der Standardeingabe und schiebt es auf den Stack.

Zum Beispiel,

&, gibt “A” aus, wenn der Benutzer “65” eingibt, und…

~. gibt “65 ” aus, wenn der Benutzer “A” eingibt.

Ausgabe

.nimmt einen Wert vom Stapel und gibt ihn als dezimale Ganzzahl aus, gefolgt von einem Leerzeichen
,holt einen Wert vom Stapel, interpretiert ihn als ASCII-Wert eines Zeichens und gibt dieses Zeichen aus ohne nachfolgendes Leerzeichen

Zum Beispiel,

665+*1-, gibt ASCII 65 (“A”.) aus, und…

665+*1-. druckt “65” aus.

Besondere Befehle

#ist der ‘Brücken’-Befehl… er bewirkt, dass der nächste Befehl, der normalerweise ausgeführt werden würde, übersprungen und nicht ausgeführt wird.

Zum Beispiel,

123…@ würde “3 2 1” ausgeben, aber

123#…@ würde “3 2″ ausgeben, wobei eines der ‘.”s übersprungen wird. Ein geschickter Einsatz von # kann für sehr interessanten Code sorgen!

:ist der Befehl zur Vervielfältigung. Er erstellt eine Kopie des obersten Elements des Stapels.
$holt einen Wert vom Stapel, macht aber nichts damit. Beispiel,

123.$.@ ergibt “3 1”.

\tauscht die beiden obersten Elemente des Stapels aus. Also,

123...@ ergibt “2 3 1”.

`ist der “Größer-als”-Befehl. Er vergleicht die beiden obersten Werte auf dem Stapel und gibt “1” zurück, wenn der erste Wert größer ist als der zweite. Zum Beispiel,

65`. gibt eine “1” aus und…

25`. gibt “0” aus.

Selbstmodifikation

Die letzten beiden Befehle, die erklärt werden müssen, sind diejenigen, die es ermöglichen, den Inhalt des Torus, in dem das Programm gespeichert ist, zu untersuchen und zu verändern. Dieses “Spielfeld” kann als Hilfsspeicher verwendet werden, wenn der Stack allein nicht ausreicht. Aber aufpassen, der Torus enthält auch das laufende Programm.

gDer Befehl g prüft den Inhalt des Spielfelds. Er holt eine y-Koordinate vom Stapel, dann eine x-Koordinate. Er schiebt den an (x, y) gefundenen Wert auf den Stapel. Wenn es sich bei (x, y) um einen Befunge-93-Befehl handelt, ist der Wert, der auf den Stapel geschoben wird, der ASCII-Wert dieses Zeichens. Vom Standpunkt des Programmtextes aus betrachtet, bestimmt x die Spalte und y die Zeile; (0, 0) bezieht sich auf die erste (ganz linke) Spalte und die erste (oberste) Zeile der Programmquelle.
pDer Befehl p ändert den Inhalt des Spielfelds. Er holt eine y-Koordinate vom Stapel, dann eine x-Koordinate und dann einen Wert. Der Wert wird in den Torus bei (x, y) eingefügt. Wenn das Programm zu einem späteren Zeitpunkt den Befehl an (x, y) ausführt, wird er im ASCII-Zeichensatz als Befunge-Befehl mit demselben Wert interpretiert, der mit dem p-Befehl dort abgelegt wurde.

Befehlsübersicht

BefehlStack – aufsteigendStack (Resultat)
+add<Wert1> <Wert2><Wert1 + Wert2>
sub<Wert1> <Wert2><Wert1 – Wert2>
*mult<Wert1> <Wert2><Wert1 * Wert2>
/div<Wert1> <Wert2><Wert1 / Wert2>
%mod<Wert1> <Wert2><Wert1 mod Wert2>
!nicht<Wert><0 wenn Wert <> 0, sonst 1>
größer<Wert1> <Wert2><1 wenn Wert1 > Wert2, sonst 0>
>rechts
<links
^auf
vab
?zufällig
_horizontal verzweigen <Wert> <>
|vertikal verzweigen <Wert> <>
zeichenmodus
:dub <Wert> <Wert1> <Wert1>
\tausche <Wert1> <Wert2> <Wert2> <Wert1>
$abwerfen <Wert> <>
.ausgabe zahl <Wert> gibt <Wert> als Zahl aus
,ausgabe zeichen <Wert> gibt <Wert> als Zeichen aus
#auslassen
gget <x> <y> <Wert von (x,y)>
pput <Wert> <x> <y>legt Wert bei (x,y) ab
&eingabe zahl<Wert>
~eingabe zeichen<ASCII-Wert>
@ende