コードで倉庫のクレーンを動かし、再帰が欠かせないほど厳しい命令数の制限の下で色付きの木箱を積み直そう。
クレーンの命令（左右の移動、つかむ、落とす、色の条件）でプログラムを組み、容器の木箱を目標の積み方に並べ替えます。命令数の制限は意図的に厳しくしてあるので、プログラム全体を先頭から再実行する Call コマンドに頼ることになります。失敗した条件が、再帰を止める基本ケースになります。手作りのレベルは10あり、赤い木箱1つから6個の木箱の塔までそろっていて、そのうち8つは Call なしでは解けません。
Tower of Three（3段の塔）: 容器1に赤い木箱が3つあり、それを容器2に移さなければなりませんが、使える命令は6つだけです。愚直に書き出すと、木箱1つごとに Grab、Right、Drop、Left が必要で、最後の Left を省いても木箱3つで11命令になります。6つでは足りません。
そこで1往復分を書いて繰り返させます。Grab、If-held 赤、Right、Drop、Left、Call。これで6命令です。クレーンは木箱をつかみ、赤を持っていることを確かめ、運んで下ろし、戻ってきてプログラム全体をもう一度呼び出します。4回目の呼び出しでは容器1は空なので、Grab は何もつかめず、If-held 赤のチェックが失敗してプログラムが止まります。この失敗するチェックこそが基本ケースです。
If-held 赤を If-held 青に変えれば、同じ6命令で木箱4つのレベルも6個の塔もクリアできます。このルーチンは木箱を数えることがなく、なくなるまで続けるだけだからです。これが再帰の要点です。プログラムは1つのステップと停止の規則を記述し、何回実行するかは入力が決めるのです。
Claw Compiler は、木箱を積み上げるクレーンと厳密な移動予算を通じて再帰を教え、難しいアイデアを具体化します。
クレーンへの命令、つまり左右への移動、つかむ、離す、そして色による条件は、物理的な体を持った最小限のアセンブリ言語である。
小さな世界の小さなロボットを通じてプログラミングを教える手法は、カレル・ザ・ロボットにさかのぼる。リチャード・パティスが1981年の本で紹介し、スタンフォード大学の授業で使った初心者向けの言語である。ゲームもこの発想を取り入れた。Lightbotは迷路の中でロボットをプログラムすることでループと手続きを教え、Claw Compiler に最も近い祖先はCargo-Botである。ロボットに木箱の動かし方を教える2012年のiPad用パズルだ。Two Lives Left は、Rui Viana が同社のiPad用コーディングアプリCodeaで作ったプロトタイプをもとに彼と共にこのゲームを開発し、iPadだけでプログラムされた最初のゲームとうたった。
課題は、箱の入った容器を目標の積み方に並べ替えることであり、一度にちょうど一つのものしか持てない機械が行う並べ替えである。アームが一つしかないという制限は、それ自体が一つの教訓である。それはレジスタが課すのと同じ制約であり、本当の並べ替えにどこか物を置いておく場所が必要な理由でもある。予備の容器が必要だと気づくことは、一時記憶という考え方を発見することなのである。
Call は常に最後の命令なので、ここでのプログラムはすべて末尾再帰である。自分自身の呼び出しが最後に行う処理なのだ。多くの言語処理系は末尾呼び出しを先頭への単なるジャンプに変換する。同じプログラムを再帰としてもループとしても読めるのはそのためである。この二つが同じ考え方だと分かることが、再帰を理解することの大きな部分を占める。
Claw Compiler は、PlayPendiumのために作られたオリジナルの無料ブラウザゲームです。7つの命令からなるクレーン言語、制限によって再帰が任意ではなく必須となる10のレベル、全員共通のデイリーレベル、そしてほかのレベルを出題する練習モードを備えています。