Y コンビネータの作り方
Lazy K プログラマたる者、Y コンビネータの一つも自力で作れるようになりたいものである、ということで作り方を考えてみた。
みんな大好き Y コンビネータは、
Yx=x(Yx)
であるという所から出発する。
1
Y が複数のコンビネータの組み合わせからできているとする。
Y=ab
a コンビネータは b と x を引数に取ると、x(abx) を返すコンビネータとなる。b から a を作る必要があるのだが、b=a とすると簡単だろう、ということで Y が
Y=aa
という形をしていると仮定する。すると、
aax=x(aax) =SI(aa)x =SI(SIIa)x =S(K(SI))(SII)ax
なので、
a=S(K(SI))(SII)
とすればよい。なので、
Y=aa =SIIa =SII(S(K(SI))(SII))
とか、
Y=aa =S(K(SI))(SII)(S(K(SI))(SII)) =S(S(K(SI)))(S(K(SI)))(SII) =SSI(S(K(SI)))(SII)
とか、
Y=aa =S(K(SI))(SII)(S(K(SI))(SII)) =SI(SII(S(K(SI))(SII))) =SI(SI(S(K(SI)))(SII))
となる。
2
上のコンビネータは Lazy K の prelude.scm に載っている
(lazy-def '(Y f) '((lambda (x) (x x)) (lambda (self) (f (self self)) )))
から得られる
SS(S(S(KS)K))(K(SII))
とは違っている。
こちらを導くには、Yx が複数のコンビネータの組み合わせからできていると考え、
Yx=cd =x(cd)
c コンビネータは d を引数に取ると、x(cd) を返すコンビネータとなる。d から c を作る必要があるのだが、c=d とすると簡単だろう、ということで Yx=cc とする。この c は中に x を含んでいるのだが x は引数なので、c=ex のように書けるはず、ということで、
Yx=ex(ex)
の形をしていると仮定する。すると、
ex(ex)=x(ex(ex)) =x(SII(ex)) =S(Kx)(SII)(ex) =S(KS)Kx(SII)(ex) =S(S(KS)K)(K(SII))x(ex)
なので、
e=S(S(KS)K)(K(SII))
とすればよい。なので
Yx=ex(ex) =Seex =SSIex Y=SSIe =SSI(S(S(KS)K)(K(SII)))
とか、
Yx=ex(ex) =SII(ex) =S(K(SII))ex Y=S(K(SII))e =S(K(SII))(S(S(KS)K)(K(SII))) =SS(S(S(KS)K))(K(SII))
となる。