Steuern Sie einen Lagerkran per Code und stapeln Sie farbige Kisten um, unter einem Befehlslimit, das so knapp ist, dass es Rekursion verlangt.
Bauen Sie aus Kranbefehlen (nach links und rechts fahren, greifen, ablegen und Farbbedingungen) ein Programm, das die Kistenbehälter in den Zielstapel umordnet. Das Befehlslimit ist absichtlich knapp, sodass Sie auf den Befehl Call angewiesen sind, der Ihr ganzes Programm von vorn erneut ausführt; eine Bedingung, die nicht erfüllt ist, wird zum Basisfall, der die Rekursion beendet. Es gibt zehn von Hand gebaute Level, von einer einzelnen roten Kiste bis zu einem Turm aus sechs Kisten, und acht davon lassen sich ohne Call nicht lösen.
Turm aus drei: Drei rote Kisten stehen in Behälter 1 und müssen in Behälter 2 landen, und Sie dürfen nur sechs Befehle verwenden. Ausgeschrieben braucht jede Kiste Grab, Right, Drop und Left, also elf Befehle für drei Kisten, selbst wenn man das letzte Left weglässt. Sechs reichen nicht.
Schreiben Sie also eine einzige Fahrt und lassen Sie sie wiederholen: Grab, If-held rot, Right, Drop, Left, Call. Das sind sechs Befehle. Der Kran greift eine Kiste, prüft, ob er Rot hält, bringt sie hinüber, setzt sie ab, fährt zurück und ruft das ganze Programm erneut auf. Beim vierten Aufruf ist Behälter 1 leer, Grab greift nichts, die Prüfung If-held rot schlägt fehl, und das Programm hält an. Diese fehlschlagende Prüfung ist der Basisfall.
Ändern Sie If-held rot in If-held blau, und dieselben sechs Befehle lösen auch das Level mit vier Kisten und den Turm aus sechs Kisten, denn die Routine zählt nie Kisten; sie macht weiter, bis keine mehr übrig sind. Darum geht es bei der Rekursion: Das Programm beschreibt einen Schritt und eine Abbruchregel, und die Eingabe entscheidet, wie oft es läuft.
Claw Compiler vermittelt Rekursion mithilfe eines Kistenstapelkrans und eines strengen Zugbudgets und macht so eine schwierige Idee greifbar.
Kranbefehle – nach links und rechts fahren, greifen, ablegen und Bedingungen zur Farbe – sind eine minimale Assemblersprache mit einem physischen Körper.
Programmieren mit einem kleinen Roboter in einer kleinen Welt zu lehren, geht auf Karel the Robot zurück, die Anfängersprache, die Richard Pattis 1981 in einem Buch vorstellte und in seinen Kursen in Stanford einsetzte. Spiele griffen die Idee auf: Lightbot vermittelt Schleifen und Prozeduren, indem man einen Roboter durch ein Labyrinth programmiert, und der nächste Vorfahr von Claw Compiler ist Cargo-Bot, ein iPad-Rätselspiel von 2012, in dem man einem Roboter beibringt, Kisten zu bewegen. Two Lives Left entwickelte es gemeinsam mit Rui Viana aus dessen Prototyp in ihrer iPad-Programmier-App Codea und bewarb es als das erste vollständig auf einem iPad programmierte Spiel.
Die Aufgabe, Kistenbehälter in einen Zielstapel umzuordnen, ist Sortieren durch eine Maschine, die genau ein Ding auf einmal halten kann. Diese Beschränkung auf einen einzigen Greifer ist eine Lektion für sich. Es ist dieselbe Einschränkung, die ein Register auferlegt, und sie ist der Grund, warum echtes Sortieren einen Ablageplatz braucht – zu entdecken, dass man einen freien Behälter benötigt, heißt, die Idee des Zwischenspeichers zu entdecken.
Da Call immer der letzte Befehl ist, ist jedes Programm hier endrekursiv: Der Selbstaufruf ist das Letzte, was es tut. Viele Sprachimplementierungen wandeln einen Endaufruf in einen einfachen Sprung zurück an den Anfang um, weshalb sich dasselbe Programm sowohl als Rekursion als auch als Schleife lesen lässt. Zu erkennen, dass beides ein und dieselbe Idee ist, macht einen großen Teil des Verständnisses von Rekursion aus.
Claw Compiler ist ein originelles, kostenloses Browserspiel, entwickelt für PlayPendium: eine Kransprache mit sieben Befehlen, zehn Level, deren Limits Rekursion notwendig statt optional machen, ein gemeinsames Tageslevel und ein Übungsmodus, der die übrigen austeilt.