Y Combinater
そういや昔Y Combinaterについて瞬間最大風速的にいろんな人が言及していたことがあったけど、あのときは興味もないしよくわからないしでスルーしていたんですが、Schemeの勉強を始めたんだし、まじめに考えてみようと思いました。
結果的にわかったような気分ですが、なんか一番大事なキモを置き忘れているようで微妙にモヤモヤが。あと、再帰と高階関数になじんでいないときついですね、これ。
とりあえずまとめておく。間違っていたら誰か教えて欲しい...
参考にしたサイト
何がしたいか
定番ですが階乗を再帰で書くと次のようになります。
(define (fact i) (if (= i 1) i (* (fact - i 1))))
しかしこれはfactの定義の中にfactが出ているという自己言及の構造になっているので、λ計算で表現することができない。じゃあどうやって自分の名前を使わずに再帰関数を定義しようかというのが、問題です。
継続渡しで
うーん、とりあえず定義の中からfactをなくすということで、継続渡しスタイルにしてみよう。
(define (fact i proc) (if (= i 1) i (* i (proc (- i 1) proc))))
呼び出し側はこれでも良いけど、
(fact 4 fact)
一応適当な関数を作って、くくりだしておこう。
(define (l proc) (lambda (i) (proc i proc))) (print ((l fact) 4)) => 24
やった！ 計算できた！
fact-makerを使って
で終わるとY Combinatorの出番がなくなってしまうので、参考にしたサイトに従って、factが次に呼び出す関数procを引数に、factを生成する高階関数fact-makerを定義する。
(define (fact-maker proc) (lambda (i) (if (= i 1) i (* i (proc (- i 1))))))
このfact-makerを使うと、factは次のように定義できる。
(define fact (lambda ()fact-maker fact))
(lambdaで囲っているのは、fact定義時に(fact-maker fact)が評価されると無限ループに陥るため)
つまり
fact = (fact-maker fact)
これを無限に展開し続けると
fact = (fact-maker (fact-maker fact)) = (fact-maker (fact-maker (fact-maker fact))) = ... = (fact-maker (fact-maker (fact-maker (fact-maker .......)))) = ...
という形の再帰構造になる。でもこのままだと、factの定義からfactを消すためには、fact-makerを自身に無限に適用し続けないといけない。
ここでもし、関数を引数にとり、(Y p) = (p (Y p))となる関数Yがあるとする。するとこのYをfact-makerに適用すると、
(Y fact-maker) = (fact-maker (Y fact-maker)) = (fact-maker (fact-maker (Y fact-maker))) = ... = (fact-maker (fact-maker (fact-maker (fact-maker ......))))
というように展開される。
これは、上記のfactの定義と同じになる！
つまり
fact = (fact-maker (Y fact-maker)) = (Y fact-maker)
となる。
この関数を引数にとる再帰的な関数YをY Combinatorと呼ぶらしい。
Y Combinatorの導出
さて、では(Y p) = (p (Y p))という関数はなんだろう。というのをこの定義から導き出す方法がわかんなかったので、参考サイトを参考に作ってみよう。
factも面倒くさいので、単純に無限に自分を呼び出し続ける関数recを考える。評価すると無限ループします。試していないけど、末尾最適化されるので、永遠にループし続けるはず。
(define (rec i) (rec i)) (rec 10) ;=> 無限ループになるはず ;1.fact-makerと同じスタイルにする。 (define (rec-maker proc) (lambda (i) ((proc proc) i))) ((rec-maker rec-maker) 10) ;=> 無限ループになるはず ;2.(proc proc) => (lambda (arg) ((proc proc) arg))に変形。 (define (rec-maker proc) (lambda (i) ((lambda (arg) ((proc proc) arg)) i)) ((rec-maker rec-maker) 10) ;=> 無限ループになるはず ;3.(lambda (arg) ((proc proc) arg)) を fact0の外にくくり出す。 ;元のrec-makerをrec0に変名。 (define (rec0 proc) (lambda (i) (proc i)) (define (rec-maker proc) (rec0 (lambda (arg) ((proc proc) arg)))) ;4.(rec-maker rec-maker) は次のように展開される。 ((lambda (proc) (rec0 (lambda (arg) ((proc proc) arg)))) (lambda (proc) (rec0 (lambda (arg) ((proc proc) arg))))) ;5.proc と rec0をくくりだして名前をつける。 (define Y (lambda (f) ((lambda (proc) (f (lambda (arg) ((proc proc) arg)))) ((lambda (proc) (f (lambda (arg) ((proc proc) arg)))))))) ((Y rec) 10) ;=> 無限ループになるはず
実行しても無限ループになるから試していません！ 括弧の対応も間違っているかも。素直にfactでやればよかった。
わかりやすいようにしてみる。（これは意味的には変わらないですが、実行順序の関係で無限ループになる）
(define (Y f) ((lambda (p) (f (p p))) (lambda (p) (f (p p)))))
展開すると、たしかに(Y p) = (p (Y p))となる。
(Y f) => ((lambda (p) (f (p p))) (lambda (p) (f (p p))))) => (f ((lambda (p) (f (p p))))) (lambda (p) (f (p p))))))) => (f (Y f))
(p p)がキモですね。こいつが自分自身を複製するおかげで、無限に展開し続けられます。
任意の長さの引数をつけるように、applyをつかうようにしておく。
(define (Y proc) ((lambda (p) (proc (lambda args (apply (p p) args)))) (lambda (p) (proc (lambda args (apply (p p) args))))))
使用例
factばかり計算させるのもY Combinatorに申し訳ないので、foldを定義してみる。
(define (my-fold proc init lst) ((Y (lambda (self) (lambda (proc init lst) (if (null? lst) init (self proc (proc (car lst) init) (cdr lst)))))) proc init lst)) (print (my-fold + 0 '(1 2 3 4))) ;=> 10
おー、動いてる動いてる。というわけで好きな再帰関数が自分の名前を使わずに定義できるようになりました。
まだ調べていないけどletrecのマクロ定義とかも似たようなことしているんじゃないかと思ってます。
感想
実用的にはあんまり必要ないんでしょうけど、なかなか頭の体操になって面白かったです。正確な理解かどうかは自信はないですが。高階関数はなかなか面白いですね。本当は学生時代に勉強したはずなんですけどね... ちゃんと理解していなかったから試験終了と同時に忘れたんだろうなあ。
というわけで学生時代にざるですくってほとんどこぼれていった知識を、気が向いたらまた掬い直したいなあと思いました。
