Lambda-Krokodile

Einleitung

Bret Victor hat sich ein Spiel ausgedacht, bei dem die Regeln des Lambda-Kalküls durch Alligatoren realisiert werden, die sich gegenseitig fressen. Ich habe dieses System mal in Haskell und mit Krokodilen implementiert. Um es auszuprobieren, einfach diese Datei herunterladen und ghci kroko.hs ausführen.

Im Folgenden beschreibe ich die Spielregeln und die Benutzung des Programms und stelle anschließend einige Sachen vor, die man mit Krokodilkalkül anstellen kann. Das Spiel besteht darin, diese Sachen selber rauszufinden, daher: Spoiler-Alarm!

Und so geht's

Das Programm zeigt die Krokodilfamilien als ASCII-Graphiken an. Das hier ist ein hungriges Krokodil, dass sein Ei bewacht:

-+-°<
 O

Um es zu erzeugen, habe ich Kroko[Ei 0] am ghci-Prompt eingegeben.

Hier ist ein hungriges Krokodil, das seine etwas komplexere Familie bewacht (Die Eier sind mit den Krokodilen verbunden, zu denen sie gehören):

----+----°<
-+--|-°<
 O  O

Für diese Krokodilfamilie musste ich Kroko[Kroko[Ei 0, Ei 1]] eingeben. Das bedeutet: Ein hungriges Krokodil, dass ein hungriges Krokodil bewacht, dass zwei Eier bewacht, wobei das erste Ei zu dem hungrigen Krokodil direkt darüber gehört (0 hungrige Krokodile dazwischen), während sich zwischen dem zweiten Ei und seiner Mutter ein hungriges Krokodil befindet (Daher die 1 hinter dem zweiten Ei).

Ein altes Krokodil hat keine eigenen Eier, frisst nichts und bewacht nur seine Familie. Wenn ich Alt[Kroko[Kroko[Ei 0, Ei 1]], Kroko[Ei 0, Ei 0]] eingebe, bekomme ich folgende Graphik:

=====================
----+----°< -+--+-°< 
-+--|-°<     O  O    
 O  O

Fressen und Schlüpfen

Wenn sich mehrere Krokodile hintereinander in derselben Familie befinden, dann frisst das linkeste Krokodil (vorausgesetzt es ist hungrig) seinen Nachfolger inklusive Familie:

=====================
----+----°< -+--+-°< 
-+--|-°<     O  O   
 O  O

Anschließend stirbt es an Überfressung und verschwindet. Aber aus jedem seiner Eier (hier nur eins) schlüpft – oh Wunder des Lebens – eine ganze Familie, die mit der soeben gefressenen identisch ist:

===============
-+----------°< 
 O -+--+-°<    
    O  O       

Das alte Krokodil hat nun seinen Daseinszweck erfüllt, weil seine Familie jetzt für sich selbst sorgen kann (Sie besteht auf oberster Ebene nur noch aus einem einzigen Krokodil), und stirbt. Übrig bleibt:

-+----------°< 
 O -+--+-°<  
    O  O      

Mit dem Haskell-Programm kann man diese Regeln automatisiert anwenden. Die Eingabe

sim 3 [Kroko[Kroko[Ei 0, Ei 1]], Kroko[Ei 0, Ei 0]]

simuliert drei Schritte (Fressen und Schlüpfen, oder das Sterben alter Krokodile) und erzeugt die Ausgabe

=====================
----+----°< -+--+-°< 
-+--|-°<     O  O    
 O  O                

===============
-+----------°< 
 O -+--+-°<    
    O  O       

-+----------°< 
 O -+--+-°<    
    O  O       

Das alte Krokodil wurde automatisch hinzugefügt, da der zweite Parameter von sim eine Liste von Familien ist, die für die Simulation zu einer einzigen Familie zusammengefasst werden müssen.

Datentypen

Man kann nun verschiedene Datentypen durch Krokodilfamilien darstellen. Natürlich sind alle Krokodilfamilien Funktionen, wobei fressen als Argument nehmen bedeutet und die Eier die Parameter darstellen. Alte Krokodile sind Klammern. Aber man kann im Prinzip jeden Datentyp als Funktion/Krokodilfamilie kodieren.

Wahrheitswerte

Am einfachsten sind die Wahrheitswerte true und false als Funktionen zu kodieren. Sie bestehen jeweils aus zwei Krokodilen, die zwei andere Krokodilfamilien fressen. Dabei bleibt am Ende bei true nur die erste gefressene Familie übrig, bei false dagegen die zweite. Dementsprechend sehen die Familien aus:

true:

-+----°< 
-|-°<    
 O   

false:

------°< 
-+-°<    
 O     

Diese beiden Krokodilfamilien sind im Programm unter den Namen true und false vordefiniert.

Warum sind das die Wahrheitswerte? Weil man damit ganz einfach eine if-Funktion implementieren kann: Die Anwendung des Wahrheitswertes auf zwei Werte ist die if-Funktion! Wenn man einem Wahrheitswert zwei Alternativen verfüttert, so ist das Ergebnis die erste Alternative, wenn der Wahrheitswert true war, und die zweite Alternative, wenn er false war.

Natürliche Zahlen

Natürliche Zahlen werden nach Art der Church-Numerale kodiert. Eine Krokodilfamilie, die eine Natürliche Zahl n kodiert, frisst dabei eine Familie f und Familie o. Übrig bleibt eine Situation, in der die Familie f n mal hintereinander auf o angewendet wird. Man kann o als Startwert und f als Nachfolgerfunktion auffassen. Alternativ kann man die Zahl n, kodiert als Funktion, interpretieren als eine Funktion höherer Ordnung, die eine einzige Funktion f als Argument nimmt und als Ergebnis eine Funktion zurückgibt, die der n-maligen Hintereinanderausführung der Funktion f entspricht, also bei n=5 das Ergebnis f⁵=f∘f∘f∘f∘f.

So sehen die Krokodilfamilien für die Zahlen von 0 bis 4 aus:

------°< 
-+-°<    
 O    
 
-+-------°< 
-|--+-°<    
 O  O  

-+--+-------°< 
-|--|--+-°<    
 O =|==|=      
    O  O  

-+--+--+-------°< 
-|--|--|--+-°<    
 O =|==|==|=      
    O =|==|=      
       O  O      

-+--+--+--+-------°< 
-|--|--|--|--+-°<    
 O =|==|==|==|=      
    O =|==|==|=      
       O =|==|=      
          O  O    

Im Programm kann man Zahl-Krokodilfamilien mit der Funktion zahl aus gewöhnlichen Haskell-Integers erzeugen.

Rechenoperationen

Addition ist eine recht einfache Rechenoperation, ist aber komplizierter als Multiplikation und Potenzrechnung, wenn man mit Krokodilen rechnet. Hier ist die Krokodilfamilie für die Addition, im Programm verfügbar unter dem Namen plus:

-+----------------------°< 
-|-----+-------------°<    
-|--+--|--+-------°<       
-|--|--|--|--+-°<          
 O  O =|==|==|=            
       O  O  O    

Was bedeutet das? Im wesentlichen folgendes: Friss zwei Zahlen, eine Nachfolgerfunktion und einen Startwert. Dann lass die eine Zahl die Nachfolgerfunktion und den Startwert fressen. Dann lass die andere Zahl die Nachfolgerfunktion fressen und das Ergebnis der vorigen Fresserei.

Da die letzten beiden Argumente der Additionsfunktion als Nachfolgerfunktion und Startwert interpretiert werden, ist das Ergebnis nach dem Fressen der ersten beiden Argumente bereits eine Zahl-Krokodilfamilie, die dann die letzten beiden Argumente frisst. Somit kann man plus als eine Funktion mit zwei Parametern auffassen, die als Ergebnis eine Zahl liefert. plus ist also ein binärer Präfixoperator.

Die Infixoperator-Version der Addition ist einfach die Funktion, die aus einer natürlichen Zahl ihren Nachfolger macht:

----+-------------°< 
-+--|--+-------°<    
-|--|--|--+-°<       
 O =|==|==|=         
    O  O  O   

Wenn man diese Krokodilfamilie und eine Zahl-Familie m an eine Zahl-Familie n verfüttert, dann wird diese (+1)-Funktion n mal auf m angewendet, man erhält also m+n.

Infix-minus geht (mit Einschränkungen) ganz ähnlich, nur dass man dann die Funktion nimmt, die aus jeder natürlichen Zahl ihren Vorgänger macht (und aus der Null wieder die Null). Diese lautet als Krokodilfamilie:

-+----------------------------------°< 
-|--------+----------------------°<    
-|--------|--------+----------°<       
 O ----+--|----°< -|-°< -+-°<          
   -+--|--|-°<     O     O             
    O =|==|=                           
       O  O                            

Die Einschränkungen dabei sind:

1. Man kommt nicht in den negativen Zahlenbereich. Stattdessen ist das Ergebnis 0. Negative Zahlen lassen sich mit einfachen Church-Numeralen auch gar nicht darstellen.
2. Die Reihenfolge der Operanden ist gegenüber dem gewöhnlichen Minus vertauscht. Darum heißt diese Krokodilfamilie im Programm sunim.

Die Multiplikationsfunktion ist einfacher aufgebaut als die vorigen Operatoren:

-+-------------°< 
-|--+-------°<    
-|--|--+-°<       
 O =|==|=         
    O  O    

Man versteht sie am besten, wenn man die Zahlen als Funktionen höherer Ordnung interpretiert, die eine ihnen übergebene Funktion entsprechend oft iterieren. Die Multiplikations-Familie frisst also drei Familien: Eine Zahl m, eine Zahl n und eine Funktion f. Die Funktion wird an n verfüttert und somit n-fach iteriert, also fⁿ. Dieses Ergebnis wird anschließend an m übergeben und m-fach iteriert: (fⁿ)^m = f^n·m. Die Multiplikationsfunktion ist unter dem Namen mal verfügbar.

Am allereinfachsten aufgebaut ist die Potenzfunktion, im Programm verfügbar unter dem Name hoch:

----+----°< 
-+--|-°<    
 O  O    

Sie frisst einfach zwei Zahl-Familien und verfüttert die erste (b für Basis) an die zweite (e für Exponent). Um sie zu verstehen, sollte man sich vorstellen, was das Ergebnis mit einer Funktion f macht. Diese Funktion f spielt für e die Rolle des Startwerts, während b die Rolle der Nachfolgerfunktion übernimmt. b einmal angewendet auf f ist f^b, also f, b-fach iteriert. b zweimal angewendet auf f ist (f^b)^b=f^b2. e wendet b aber e mal auf f an, also bekommen wir f^be. Das Ergebnis von hoch (zahl b) (zahl e) ist also die Zahl-Krokodilfamilie für b^e. Außer wenn e=0 ist, dann funktioniert es nicht.

Tupel

Tupel (a, b, c, ...) lassen sich allgemein so als Funktion/Krokodilfamilie darstellen:

-+---------------°<
 O  a  b  c  ...

Ein n-Tupel frisst also eine Funktion mit n Parametern und wendet sie auf seine Elemente an. Um ein Tupel auszulesen, muss man ihm also die Aktion übergeben, die man mit seinen Elementen durchführen möchte. Um zum Beispiel das erste Element eines Paares zu bekommen, übergibt man ihm true, und für das zweite Element false. Eine Krokodilfamilie, die aus zwei Argumenten ein Paar konstruiert, ist im Programm unter dem Namen paar verfügbar.

Alternativen

Ein Element einer disjunkten Vereinigung von Datentypen T und U ist entweder ein Element von t von T oder ein Element u von U, zusammen mit der Information, welches von beiden. Als Krokodilfamilie lässt sich das so darstellen:

-+-------°<    
-|----°<       
 O  t   

---------°<    
-+----°<       
 O  u   

Solchen Familien verfüttert man also zwei Funktionen: Die erste für den Fall dass es ein Element von T ist und die zweite für den Fall dass es ein Element von U ist. Im Programm gibt es dafür die vordefinierten Krokodilfamilien links und rechts, die jeweils einen Wert fressen und ihn als Element von T bzw. U verpacken.

Rekursive Funktionen

Das ist die Krokodilfamilie mit dem Namen unverdaulich:

-+-----------+----------°< 
-|--+--+-°< -|--+--+-°<    
 O =|==|=    O =|==|=      
    O  O        O  O   

Wenn man ihr eine Krokodilfamilie f verfüttert, bekommt man etwas, das von f unverändert wieder herausgelassen wird: (unverdaulich f) = (f (unverdaulich f)) = (f (f (unverdaulich f)))...

Es handelt sich um einen sogenannten Fixpunkt-Kombinator. Mit seiner Hilfe lassen sich rekursive Funktionen definieren, zum Beispiel die Fakultätsfunktion:

========================================================
unverdaulich ----------------------------+------------°<
             --------+----------------+--|--------+-°<
             isZero  O  (zahl 1) =====|==|========|=
                                 mal  O =|========|=
                                         O =======|=
                                           sunim  O

wobei isZero definiert ist als

-+----------------------°< 
 O ---------°< -+----°<    
   ------°<    -|-°<       
   -+-°<        O          
    O  

f ist in diesem Fall die Familie, die an unverdaulich verfüttert wird. unverdaulich verfüttert anschließend (unverdaulich f) an f, somit steht (unverdaulich f), was ja die Fakultätsfunktion ist, für die Auswertung von f zur Verfügung: Rekursion!

Mit meinem Programm auf diese Weise so etwas einfaches wie 3! auszurechnen, dauert aber sehr lange. Das liegt daran, dass die Reihenfolge der Fressschritte ungünstig gewählt wird und so riesige Zwischenergebnisse entstehen.