Yコンビネータを理解したい

Scheme手習いの9章にYコンビネータが出てきます。

Y combinator - /var/log/messages

を読んで、もう一度しっかり取り組んでみようかと思いました。

前回読んだときの感想で最後に「すっきり」と書いておきながら再度9章読むとやっぱり理解出来てなかったかも。

頑張って「λ計算入門」でググって基礎文法最速マスターを読んだり、どこかの大学の講義のpdfな資料を読んだり、Yコンビネータでググって資料を読んだり。(本はScheme手習い以外読んでないです*^q^*

少しだけ分かった気がするのでエントリにまとめておきます。

Yに渡す関数

リストの長さを求める関数、とりあえずFとでも名付けましょう。

(define F
(lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l))))))))

Fは長さを計算する関数lengthを取り関数を返す。

listを取って空なら0を、それ以外の場合lのcdrの長さをlengthで求めそれに1を加えて返す関数。

Yコンビネータ

(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))

中身の2つの関数、別々に見てみる。

最初の関数

(lambda (f) (f f))

関数fを引数に取り、fにfを適用する。(この時点でちょっと???な感じww)

2番目の関数B

(lambda (f)
(le (lambda (x) ((f f) x))))

引数で直接(le (f f))という風に渡すと、先に引数を評価してからleを呼び出すので、leを呼び出す前に(f f)の部分で延々と再帰します。

なのでlambdaで包んで評価を遅らせてますね(p173)

FにYを適用するとどうなるのか

とりあえずScheme手習いで出て来るYコンビネータをFに適用する

(Y F)

Yの定義のlambdaに置き換え。

((lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x))))))
F)

leの部分をFで置き換えてこんな感じになる。

((lambda (f) (f f))
(lambda (f)
(F (lambda (x) ((f f) x)))))

fの部分を置き換えて

((lambda (f)
(F (lambda (x) ((f f) x))))
(lambda (f)
(F (lambda (x) ((f f) x)))))

こうなる。

よく見るYコンビネータの中身と同じになりましたね。

で、こうなると、(lambda (f) ...)で取っているのは自分自身

Fに渡す無名関数

(lambda (x) ((f f) x))

の中で使われてるfは

(lambda (f)
(F (lambda (x) ((f f) x))))

に束縛されてるのかな。

無名関数にFを適用する

さて、帰って来る(F (lambda (x) ((f f) x)))のFを置き換えてみると

((lambda (length)
(lambda (l)
(cond ((null? l) 0)
(else (+ 1 (length (cdr l)))))))
(lambda (x) ((f f) x)))

lengthを引数で置き換えて

(lambda (l)
(cond ((null? l) 0)
(else (+ 1 ((lambda (x) ((f f) x)) (cdr l))))))

こんな関数が帰って来る、と。これがlengthか。

その関数に'()を与えると、0を。そうでない場合に+1して

((lambda (x) ((f f) x)) (cdr l))

が呼び出されています。

(f f)が何をしてるか

このfには

(lambda (f)
(F (lambda (x) ((f f) x))))

が入っています。なのでこれにfを与える、つまり

((lambda (f)
(F (lambda (x) ((f f) x))))
(lambda (f)
(F (lambda (x) ((f f) x)))))

となる。

で、これさっき見たよね。

(f f)を呼び出すだけで再帰が出来とる!!w

YじゃなくてZコンビネータらしい

(lambda (x) ((f f) x))

でlambdaでくるんでるのは(f f)が引数の方が先に評価されてしまうから。評価順序云々が絡んでるみたいです。先行評価。

で、実はλで遅延させてるのはZコンビネータらしい。

普通のYコンビネータはこう。

λf.(λx.f(xx))(λx.f(xx))

Zはこう。

λf.(λx.f(λy.xxy))(λx.f(λy.xxy))

Zの一部をη変換するとYと同じになる、という理解。

Yコンビネータの話

Y = λf.(λx.f(xx))(λx.f(xx))

MにYを適用してみると

YM = λf.(λx.f(xx))(λx.f(xx))M
= (λx.M(xx))(λx.M(xx))
= M(λx.M(xx)(λx.M(xx)))

最終的にこんな形に。3行目の引数が2行目と同じになるので

YM=M(YM)

Zだと

Z = λf.(λx.f(λy.xxy))(λx.f(λy.xxy))
ZM = (λf.(λx.f(λy.xxy))(λx.f(λy.xxy)))M
= (λx.M(λy.xxy))(λx.M(λy.xxy))
= M(λy.(λx.M(λy.xxy))(λx.M(λy.xxy))y)

Mの引数で渡してるのはλ、ここで1回評価を遅らせてる感じなのだろうか

最後の形の引数をη変換すると

(λx.M(λy.xxy))(λx.M(λy.xxy))

となって、ZMを簡約してる途中で出てきたのと同じ形になる

つまり、M(ZM) = ZM

ってことなのかな

(Y Y)はどうなるの

YFするとF(YF)が帰って来る。ここでFの場合はYFをlengthとして受け取った後に、(lambda (l) …)な関数を戻しているのでそこで計算が止まる。

YYするとY(YY)が帰って来る。Y(YY)はYYを返す。でYYはY(YY)を返す。でYYは…と無限ループする。

という理解でいいのかな。