偉そうな事を書いている割にまだ全然 Joy の世界を理解していないので、実装を通してゆっくり考えてみる。まず、再帰を書くのに使う linrec 。これは例えば、階乗 (1 * 2 * 3 * ..) をこのように書くのに使う。何とクォーテーションが四つもある。恐ろしい。。。
DEFINE factorial == [null] [succ] [dup pred] [*] linrec.
Joy を Haskell のポイントフリー版と考えると分かりやすいと以前分かったので http://d.hatena.ne.jp/propella/20070518/p1 、これも Haskell で考える。Haskell で階乗を素直に書くとこんな感じだろうか。
f1 x = if (x == 0) then 1 else x * f1 (x - 1)
中置演算子の無い Joy にあわせて、前置式に変換する。pred は引数を一つ引く関数。
f2 x = if (x == 0) then 1 else (*) x (f2 (pred x))
ここまで来たら出来たも同然。まず Joy 版の [null] は (x == 0) に対応する終了条件だと分かる。次に [succ] は (const 1) これはトリッキーだが終了条件の際の初期値。わざわざ succ を使っているのはスタックをクリアするためで pop 1 の省略だろう。次は難しいが、[dup pred] と (pred) これで再帰的に渡す引数 f (x - 1) を表現する。最後に [*] (*) で答えを出す。こんなの良く考えたなー。
linrec p t r1 r2 x = if (p x) then (t x) else (r2 x (linrec p t r1 r2 (r1 x))) f3 = linrec (== 0) (const 1) (pred) (*)