2006/10/10

名前付きletをlambda式にしたい。

SICPの第4章では、Schemeの式の評価機をSchemeで書く。こう書くとやたらに抽象的で深遠でカッコよさげに聞こえるけど、まずはプロシージャをいくつかのスペシャルフォームによる表現に均さないといけないからandやorをletをlambdaにするとか、そういうどちらかというとバタ臭い作業が続く。
で、ex.4.8では、名前付きletをlambda式にしろとある。letrecがないので、たぶん正解はinternal defineを使う方法。でも、そろそろ式の表現を変換するだけの作業には飽きてきたので、不必要に解答をややこしくしてみる。つまり、要するに関数を再帰させる話だと解釈して、こういう問題設定にする。

再帰的なプロシージャを抽象化したい。

答えは分かっている。Yコンビネータだ。というわけで、以下はYコンビネータのおさらい。"The Little Schemer"の第9章の翻案ともいう。

まず、再帰を含む関数を用意する。たとえばex. 4.8のフィボナッチ名前付きlet版。
(define (fib n)
(let fib-iter ((a 1) (b 0) (count n))
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))

count≠0 のときに再帰しているので、 count > 0 のときに適当に答えを出してくれる fib-iter-1 というプロシージャが世界のどこかでよろしく定義されていると妄想する。
(define (fib n)
((lambda (a b count)
(if (= count 0)
b
(fib-iter-1 (+ a b) a (- count 1))))
1 0 n))

再帰しないですむようになったので、もうletに名前はいらない。それで、ついでにletをlambda式にしておいた。もちろん、実際には fib-iter-1 なんていう都合のいいプロシージャはないし、もしあっても fib-iter-1 の中にはきっと再帰があるだろう。fib-iter-1 の再帰を片付けるのに fib-iter-2 を妄想し、さらに fib-iter-2 の再帰を片付けるのに fib-iter-3 を妄想し、……嘘をつき続けなければならない。

そこで発想を飛ばして、「fib-iter-1を妄想する」ことを抽象化してみよう。ちょっと分かりにくいけど、妄想したいものを受け取ってfibの中身のlambdaを返してくれるようなプロシージャを作ればいい。つまりこんな感じ。
(lambda (fib-iter)
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))

ただし現実には「妄想の果て」が必要になる。また妄想なんだけど、とりあえず果てに行き付いたので無理矢理納得することにする。妄想の果てを fib-iter-omega とすると、
(define (fib n)
(((lambda (fib-iter)
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))
fib-iter-omega)
1 0 n))


ここで再び発想を飛ばして、今度は「妄想の果て」を抽象化する。それには、妄想を受け取って妄想を返し続けるようなプロシージャを作ればいい。こんな禅問答のようなプロシージャが考えられる。
(lambda (fib-iter) (fib-iter fib-iter))

これってつまり「関数を自分にぶちこむ」ってことなので、「再帰する」ことを抽象化しているとも考えられる。

ところが、実はこれだけだと果てしなく続く妄想だけになっちゃて、妄想の仕様が何も分からない。仕様がないものは使いようがない。そこで、まずは妄想を整形してやって、それを「果てしなく続く妄想」に渡すようにしてやりたい。いま考えているfib-iterでは3つの引数(a,b,const)を使っているので、この「妄想の果て」も3つの引数をとるプロシージャを返すようにしないといけない。
(lambda (delusion)
((lambda (fib-iter) (fib-iter fib-iter))
(lambda (f) (delusion (lambda (x y z) ((f f) x y z))))))

妄想delusionを受け取って、それを3引数を取るプロシージャの形にして、後はひたすら妄想を続けるというノリ。これがYコンビネータ。だからYコンビネータは、妄想を使えるものにするための、どっちかっていうとテクニカルな細工なんだと思う。

以上をfibに取り込むと、こうなる。
(define (fib n)
(((lambda (delusion)
((lambda (fib-iter) (fib-iter fib-iter))
(lambda (f) (delusion (lambda (x y z) ((f f) x y z))))))
(lambda (fib-iter)
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))))
1 0 n))


もうすっかり妄想が抽象化されつくしたので、これはフィボナッチ数列のn項を求めるプロシージャとしてちゃんと評価される。

gosh> (map fib (iota 20))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

0 件のコメント: