Yコンビネータ

CS Lisp

ついでだからSchemeにおいて*1再帰を使ってしまった似非Y combinatorを導くところも示そう（昨日の話の前段階に当たる）．
まず普通に再帰で書いた階乗関数facとその使用例は次の通り：

(define fac
  (lambda (n)
    (if (> n 1)
        (* n (fac (- n 1)))
        1)))

(fac 10)

「これはfacという名前に頼って再帰を行っているのがけしからん！ たとえfacの定義本体をなすλ式だけを取り出そうとも機能するようにせよ」というのがコンビネータ理論の要求（？）なわけだ．
そこでfacという名前に頼って「自分」を参照している部分をlambda抽象して外から与えてやるような設計にする((昨日Yを完全なコンビネータに書き換えたときも同じことをやったが，つまりはイディオムと言える．))：

(define pre-fac
  (lambda (fac)
    (lambda (n)
      (if (> n 1)
          (* n (fac (- n 1)))
          1))))

このpre-facは本物の（出来合いの）階乗関数を引数に与えて評価してやると本物の階乗関数を返す．例えばさっき定義したfacを借りてくればよい：

(define fac/cheating (pre-fac fac))

(fac/cheating 10)

じゃあ借り物でない階乗関数を自前で用意するには？ pre-facの返り値は階乗関数になるように設計されてるんだから，いくらか頭をひねればできそうではないか．facをpre-facの返り値で置き換える方向で悩んでみよう：

(define fac/trying (pre-fac (pre-fac fac)))

動くには動くけど，まだfacが残ってるからダメじゃん...

(define fac/trying-nth (pre-fac (pre-fac (pre-fac (pre-fac (pre-fac ... ))))))

うぎゃ．このままnaiveに悩んでも見込みは薄いということか．
ここで一転，魔法のオペレータを導入しよう．pre-facを与えると，な〜んと上で捜し求めていた階乗関数をあっけなく与えてくれるようなオペレータだ．これをYと呼ぶのが慣習：

(define fac/Y (Y pre-fac))

(fac/Y 10) ; => Yが実在するなら答が出る

さてこのままではしょうがないので，魔法を科学で置換したい．どうやってYをSchemeで実装するか？ ここで思い出すべきポイントは2つ：

  1. pre-facに階乗関数を与えると階乗関数が得られる（これはpre-facの設計からして当然）
  2. Yにpre-facを与えると階乗関数が得られる（解き明かすべき「魔法」）

やってることは似ている．Yを実装するのに1. を利用しない手はない．
とりあえず雛形を書いて落ち着こう：

(define Y
  (lambda (pre-fac_)
    ... ))

Yの引数にはpre-facが来ることが決まってるので，それを思い出しやすい仮引数名としてpre-fac_を付けた．さてこうなるとY内部ではわざわざやって来たpre-facを利用しない手はないように思えてくる．Yが返すはずの階乗関数（これを生成するにはlambdaを使う）は，pre-facで実装してしまおう：

(define Y
  (lambda (pre-fac_)
    (lambda (n)
      ((pre-fac_ 階乗関数をここに与えさえすればOK) n))))

そしてここがひどいトリックなのだが，pre-fac_の引数に与える階乗関数はどこから調達しようかと言うと，Yを再帰的に評価してしまうことにする．Yにpre-facを与えると階乗関数が得られるのだった（そういう風にYを実装しようとしている）．

(define Y
  (lambda (pre-fac_)
    (lambda (n)
      ((pre-fac_ (Y pre-fac_)) n))))

さて，とりあえず構文的に誤りはないっぽい．んで，実際にこれをScheme処理系に与えると... 動いちゃうんだなこれが．評価順序や型を全く考慮してこなかったのですごくインチキ臭い導出だけど，ちゃんと機能してしまうんだからしょうがない．最後にお好みで，仮引数pre-fac_を，階乗関数に限らないような名前fに付け替えて((今できあがったYはいわゆるY combinatorと同一の機能を有することが分かっているから．))，完成である：

(define pre-fac
  (lambda (fac)
    (lambda (n)
      (if (> n 1)
          (* n (fac (- n 1)))
          1))))

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

(define fac/Y (Y pre-fac))

(fac/Y 10)

上のYをcombinatorにする話は昨日すでに書いた．
Y combinatorの汎用性を示すために，fibonacci数列（もちろん再帰版）での利用例も載せておこう：

(define pre-fib
  (lambda (fib)
    (lambda (n)
      (if (> n 1)
          (+ (fib (- n 1))
             (fib (- n 2)))
          1))))

(define fib/Y (Y pre-fib))

(fib/Y 10)

昨日の話と合わせれば（つまり再帰版似非Yを経由する方式を採用したことにより），ネットで見た中で一番分かりやすいYコンビネータの導出が書けたと自負しているが，まぁ自分で書いたことなのだから分かりやすく思えて当然だよなぁ．
Acknowledgement: Plasterさんの日記にインスパイヤされました．
それにしてももう1週間早く書いてUTMCの駒場祭部誌に寄稿すりゃよかった．id:nyaasan，ごめんよ...

*1:というか動的型，静的スコープ，正格評価の関数型言語において．