Befunge

Befunge ist eine esoterische Programmiersprache von Chris Pressey, die ähnlich wie Forth Stack-orientiert ist. Die Programme basieren auf einem 2-dimensionalen Schema. Der Quelltext besteht aus ASCII-Zeichen in einer 80×25 Zeichen großen Anordnung. 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 den Quellcode zur Laufzeit dynamisch verändern kann.

Interessant ist Befunge für Forschung und Lehre, praktische Anwendungen dürfte es eher nicht geben. Für das Verständnis von selbstmodifizierendem Code ist Befunge gut zum Experimentieren geeignet, auch unkonventionelle Methoden zur Mehrfachverwendung von Programmcode lassen sich an Befunge gut darstellen.

Die Instruktionen in Befunge (93)

0-9Schiebe diese Ziffer auf den Stack
+Addition: Hole a und b, dann schiebe a+b auf den Stack
-Subtraktion: Hole a und b, dann schiebe ba auf den Stack
*Multiplikation: Hole a und b, dann schiebe a·b auf den Stack
/Ganzzahl-Division: Hole a und b, dann schiebe b/a (abgerundet) auf den Stack. Wenn a=0, frage den Benutzer nach dem Ergebnis.
%Modulo: Hole a und b, dann schiebe den Rest der Ganzzahl-Division von b/a auf den Stack. Wenn a=0, frage den Benutzer nach dem Ergebnis.
!Logisches NICHT: Hole den Wert; wenn Null, schiebe 1, sonst Null auf den Stack.
`Größer als: Hole a und b, dann schiebe 1 wenn b>a, sonst Null auf den Stack.
>Gehe nach rechts
<Gehe nach links
^Gehe nach oben
vGehe nach unten
?Gehe in zufällige Richtung
_Hole einen Wert vom Stack; gehe nach rechts, wenn Wert=0, sonst nach links.
|Hole einen Wert vom Stack; gehe nach unten, wenn Wert=0, sonst nach oben.
"Starte String-Modus: Schiebe den ASCII-Wert jedes Zeichens bis zum nächsten " nach oben.
:Dupliziere Wert auf der Spitze des Stacks.
\Vertausche zwei Werte auf der Spitze des Stacks.
$Hole einen Wert vom Stack.
.Hole einen Wert vom Stack und gib ihn als Ganzzahl aus.
,Hole einen Wert vom Stack und gib ihn als ASCII-Zeichen aus.
#Trampolin: Übergehe nächste Zelle.
gHole y und x vom Stack, dann schiebe den ASCII-Wert des Zeichens an der Position x/y im Programm auf den Stack.
pHole y, x und v vom Stack, dann ändere das Zeichen an der Position x/y im Programm zu dem Zeichen mit dem ASCII-Wert v.
&Frage den Benutzer nach einer Zahl und schiebe diese auf den Stack.
~Frage den Benutzer nach einem Zeichen und schiebe dessen ASCII-Wert auf den Stack.
@Beende Programm

Beispiele

Addition zweier Zahlen

4 3 + . @

Der Quellcode ähnelt einem Forth-Quellcode: 4 und 3 werden nacheinander auf dem Stack abgelegt, dann werden beide Zahlen vom Stack geholt, addiert und dann das Ergebnis wieder auf dem Stack abgelegt. Der Punkt . ist die Anweisung, die oberste Zahl des Stacks auszugeben. Mit dem At-Zeichen @ wird das Programm beendet. Kommazahlen werden nicht unterstützt. Sobald z. B. „0,12“ herauskommen würde, gibt das Programm „0“ aus.

Das Gleiche, nur mit Richtungsänderungen:

v   > . v

4   +   @

> 3 ^

Ganz kompakt, mit Füllzeichen:

v*>.v
4*+*@
>3^**

Hello World

0"!dlroW olleH" > v
                 ,
                 :
               ^ _ @

Das erste " signalisiert, dass es sich um ASCII-Code handelt. Dann wird in Umgekehrter Reihenfolge Hello World! zeichenweise in den Stack gelesen. Das letzte " schließt den ASCII-Strom ab. Dann kommt eine Schleife, bei denen >, v und ^ die Richtungspfeile für den Programmfluss darstellen, und das , (Komma) die Print-Anweisung für ein ASCII-Zeichen darstellt. Das _ (Unterstrich) stellt die While-Bedingung dar, die solange erfüllt ist, solange der letzte geholte Wert größer 0 ist.

Hello World ohne Schleife

"!dlroW olleH"v
 @,,,,,,,,,,,,<

Hier wird dasselbe gemacht wie oben, bloß wird statt einer Schleife die print-Funktion einfach mehrmals hintereinander ausgeführt, sodass der Stack am Ende leer ist.

Hello World Extended

91+70pv
v p173<        v  <
>"!dlroW olleH">,:|
     v:-1g17      <
^ p17_$70g,v
^_ #&@#p173<

Hier wird das Zeichen für einen Zeilenumbruch (ASCII-Code 10) auf den Stack geschrieben, ebenso ein Zähler mit dem Wert 3. Nun wird „Hello World!“ ausgegeben und der Counter um 1 verringert. Diese Ausgabe wiederholt sich so lange, bis der bei Counter 0 angelangt. Ist dies der Fall, so wird ein Zeilenumbruch ausgegeben, der Counter auf 3 zurückgesetzt und der Benutzer nach einer Zahl gefragt. Ist diese Zahl vom Benutzer 0, so wird das Programm beendet, ansonsten fängt das Programm wieder mit dem Ausgeben von „Hello World!“ an.

Fibonacci-Folge

Diese Programme geben die Fibonacci-Folge aus. Je nach Interpreter werden nur die Zahlen bis 233 ausgegeben.

0.1>:.:00p+00g\v
   ^           <

Zuerst wird die 0 auf den Stack gelegt und sofort ausgegeben. Danach wird eine 1 auf den Stack gelegt. Dann betritt das Programm die Endlosschleife: Stack verdoppeln, Wert ausgeben, wieder verdoppeln, oberstes Zeichen an Position 0/0 im Code speichern, oberste Werte addieren, Wert von Position 0/0 holen und die beiden obersten Werte vertauschen.

Das folgende Programm tut das gleiche, nur wurde es für genau eine Zeile geschrieben und ist daher etwas unübersichtlicher:

0.1> #<:#<.#<:#<0#<0#<p#<+#<0#<0#<g#<\# <

Hier nochmal in gekürzter Form:

0.1>:#\.#g:#00#00#+p# <

Hierbei gibt es Befehle für die Hinrichtung und für die Rückrichtung. Durch das Trampolin werden die Befehle aus der „falschen“ Richtung übersprungen.

Weitere Beispiele in Befunge

Conways Game of Life

Implementation des Game of Life von Dmitry M. Litvinov

v>>31g> ::51gg:2v++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
9p BXY|-+<v3*89<%+ *                                                      *   +
21 >98 *7^>+\-0|<+ *                                                     *    +
*5 ^:+ 1pg15\,:< + *                                                     ***  +
10^  <>$25*,51g1v+                                                            +
-^ p<| -*46p15:+<+                                                            +
> 31^> 151p>92*4v+                                                            +
 ^_ ".",   ^ vp1<+                                                            +
>v >41p      >0 v+                                                            +
:5! vg-1g15-1g14<+                                                            +
+1-+>+41g1-51gg+v+                                                            +
1p-1vg+1g15-1g14<+                                                            +
g61g>+41g51g1-g+v+                                                            +
14*1v4+g+1g15g14<+                           * *                              +
5>^4>1g1+51g1-g+v+                           * *                              +
^ _^v4+gg15+1g14<+                           ***                              +
>v! >1g1+51g1+g+v+                                                            +
g8-v14/*25-*4*88<+                                                            +
19+>g51gg" "- v  +                                                            +
4*5  v<   v-2:_3v+                                                            +
 >^   |!-3_$  v<-+                                                            +
^    < <      <|<+                                                         ***+
>g51gp ^ >51gp^>v+                                                            +
^14"+"<  ^g14"!"<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Ein kastriertes Schachprogramm

Beispiel für Eingabe: a2a3

**********>9"+  ",>,,1-:v  >:,,"@"  v>1+:4`!v>1~5v>01g1+802g-g:"a"`  v>+03g1+8v
*RNBQKBNR*,       ^"-+" _v "v:+1," "< v4-1~:_^v+5< >_"(: niw U">:#,_@#^!+`g40<0
*PPPPPPPP*+vp00:+1g  &lt;p  <  >:,"G"`!|p>4*%:7`v->$$^|!-"K":g-g408+1g30<>:"p"-7^4
*........*5>8`!55+,#v_9"+  ", v v5 $<^\0\_v#!<_^   >:"."-!#v_"a"`#v_#|^v"."p-g<
*........*5v9.-\9g00<#v!:-1,, < >5+, ^    v                ># $0 #<^#< >01g1+8v
*........* >"|",1-::!|>#v_"+-"^             v"q"+7gp90+"5"*"e"g<<v01p9p8pp-g20<
*........* ^,gg00-\9 <  >55^v      ,7 $$$ < > %00p09g"@"4*+:8%v9|<`8\9p00:+1g$<
*pppppppp*^                 < >  >                             ^>1-:::00g9*+\!|
*rnbqkbnr*>:"`"+,04g:"9"\-,p^    |-"P"_v#-"N":_v#-"K":_v#-"B"<1 ^p90+g90*gg00\<
**********^g30pg20g10"."+!+`g<   >2g1+v>$2v%2g$<       v< >gv:>+02p8/8%1+:01p0v
>01g:"`"+,02g:"9"\-,g:"P"-804^ v%2gp40<   >100g2/2%#v_v$| %2<|-"Q":_v#-"R":gg2<
^_"!niw I">:#,_@             v _g2/2%2*vv0_v#%2/4g00<\< >#^ #<     v>#$ <
 ^-"k"_$                 #v_  ^v:+g10-1<>\->\00g8/2%  v>g2/2%2*1-0v> g2/2%2*1-v
^_   0^`"a":_v#-".":gg40g3<  1 >:03p0`\04gg"a"  vv0_v#<v-1*2%2/4g0<v_v#%2/4g00<
 ^ !p80:+1g8$<>04g0`*904g`*^ >g:03p04gg"."-! v  `>\->0vv           <\<>4pg8/8%v
              ^*`g309`0g3  <  v*%2/2g00!-3g40_v<*v0+g1<>05p06p1g03p2g0^  v_v#:<
Chess program on Befunge'93  > 3g04g1+:04pgv  3 !>3p02gv v!p30:+g50g30-1 < >v
"Hungry dragon" v1.1         |<  vp3_v#-"."<  p|< vp40+<v_03g04g06g+:04pg"."-!|
by mtve at frox25.dhs.org  ^ <   <   <        <<  <    $<                   < <

BefBef

BefBef ist ein Befunge-Interpreter, geschrieben in Befunge, von Wim Rijnders.

028p038p108p018pv
     vp91+56p900<       v_v#!-+1"!":<                 >:"<"-!#v_:"^"-!#v_  v
     >"*"09g:19g\19gg29p p 29g28g  #^_ :" "-!#v_:"v"-#^_    v
     ^p91+g91g81p90+g90g 8 0pg91g90g92$       <    <
                          >:         >38g7p38g1+38p^p811p800<
                        >28g!28p                   ^p810p80-10<         <
                                                   ^p81-10p800         <
                                                   ^p810p801<     _v#!-">":<
                                     ^  -"0":_v#`\+1"9":_v#` -1"0":<    #
                                              >    #     >:"!"1+-!#v_v
#######################>19g+\48gp                  ^      p #82!g82<
0"!dlroW olleH">v     #              ^               g7-1g83_v#!-":":<
               ,:     #     >$,                    ^ <      #>:"p"-!#v_v
               ^_25*,@#   v_^#-4:_v#-3:_v#-1:_v#-2:\g7p83:-1_v#:g83<2<
#######################   >:5-#v_v$                ^ #    0 #<
                       ^  _v#-6< > $6      v  >$09g+48p1  >>       ^
                                        >$0>         #             ^     <
                                 v_                         ^

                           >*                        ^     ^3_v#!-"_": <
                                                              >:","-#v_4 ^
                                                          ^5_v#!-"*":<

                                 >                          #@          ^

Literatur

  • Oliver Lau: Hexenwerk – Ein Plädoyer für esoterische Programmiersprachen. c’t 22/07, S. 192–199.

Weblinks