Y combinatorへもう一歩

CS Lisp

本物のY combinatorにはあと一歩，自明な書き換えを行うだけである．整理すると現状は次の通り((私の好みに従って少々名前を変えた．fixよりYが好き．))：

(define pre-fact
  (lambda (fact)
    (lambda (n)
      (if (< n 1)
          1
          (* (fact (- n 1)) n)))))

(define Y
  (lambda (f)
    (lambda (n)
      ((f (Y f)) n))))

((Y pre-fact) 10)

ここではYの定義内でYを使ってるので，これを外部から提供してやるためにlambda抽象を行う：

(define Y
  (lambda (Y_)
    (lambda (f)
      (lambda (n)
        ((f (Y_ f)) n))))

このままでは無論「使う部分」 (Y pre-fact)がおかしくなるのでYを(Y Y)に書き換える((ここはサラっと書いてはみたが，とても微妙なところだ．もちろん先に行ったlambda抽象では「Yそのものを外部から（引数として）提供してやる」ことを目的としていたのだから，その意味ではこの書き換えは当然なんだが... 覚えてないとできないのではないかな？))：

(((Y Y) pre-fact) 10)

（id:nucくんの指摘に基づいてこの段落を挿入） Yを使ってるのはここだけではない．Yの定義本体内において，Y_はYそのものを与えることを意図した仮引数なので，Y_を使っている部分でも同様の書き換えが必要：

(define Y
  (lambda (Y_)
    (lambda (f)
      (lambda (n)
        ((f ((Y_ Y_) f)) n))))

これで 糸冬 了 なんだけど，やはりYを「使う部分」でYがダブってるのが審美的にイマイチ．そこで現状のYをpre-Yとして，ダブってる部分を新Yに任せると，結局 次のようになる：

(define pre-fact
  (lambda (fact)
    (lambda (n)
      (if (< n 1)
          1
          (* (fact (- n 1)) n)))))

(define pre-Y
  (lambda (Y_)
    (lambda (f)
      (lambda (n)
        ((f ((Y_ Y_) f)) n))))

(define Y
  (lambda (f)
    ((pre-Y pre-Y) f)))

(define fact/Y (Y pre-fact))

(fact/Y 10)

これですっきりした．もちろんうるさく言えば現状のYは依然としてcombinatorではないが，その中のpre-Yの出現をpre-Yの定義内容で置換してやることで http://www.loveruby.net/ja/misc/ycombinator.html に載っているものと同じものができる．

何だかんだ言っても，私は自分の頭を動かしてY combinatorを書こうと思ったことはなかった．書くことがあるとすれば，資料から丸写しか，もしくはそれを繰り返すうちに暗記するに至るかのどっちかだろうと思っていた．やはり理情生は違うなぁ，というのが感想．