名前付き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)