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))

となる。