Yコンビネータを読み解こう
Y コンビネータって何？ - IT戦記で話題になってるYコンビネータがイマイチわからない。
良記事発見したので、Y CombinatorのYコンビネータを読み解いて行きたいと思います。英語版も必見デス。
相当長いです。
Yコンビネータとはナニモノ!?
そういや、再帰って、名前が無いと再帰出来ないのかなぁ・・・全ての式がλで書けるなら、再帰関数もλで書けるはずだ。名前イラナイ!!という時、困っちゃうのが再帰関数の定義。僕の少ない頭では定義出来ませんでした。
「再帰をλで書きたい」
と、思ったときに登場するのが「Yコンビネータ」らしい。追っていく。
階乗ってなんだっけ
まずは復習。とりあえず階乗を書きます。
(define (fact n) (if (zero? n) 1 (* n (fact (- n 1))))) (fact 10) ; 3628800
式をを分解すると、
(* 10 (* 9 (* 8 (* 7 (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1)))))))))) ; 3628800
こんな感じ。
階乗の定義を分解すると、
(fact 10)は10と(fact 9)を掛けたもの。 (fact 9)は9と(fact 8)を掛けたもの。 (fact 8)は8と(fact 7)を掛けたもの。 ... (fact 0)は1。
(fact 0)まで降りて,だだぁっと掛け算。10まできたら終わる。答えは3628800になる。
再帰には、
- nが0の時の定義
- 1
- nの時の定義
- nと(fact (- n 1))を掛けたもの
が必要だった。再帰には終端(脱出口)と繰り返し部分がある。終端(脱出口)が無いと無限ループになっちゃう。
おっけ!!
再帰ってなんだろう
階乗の定義はこうだ。
(define (fact n) (if (zero? n) 1 (* n (fact (- n 1)))))
階乗の定義。nにn - 1を掛けたもの。nが0なら1。これが階乗の定義。
んじゃ、「再帰の定義」ってなんだろう。
自分に自分を作用させて、自分に自分を作用させて、自分に自分を作用させて、・・・
「自分に自分を作用させて」これが再帰っぽい。再帰の定義も再帰だ。
でもだ、でもだ、再帰には「脱出口」が必要だった。「脱出口」について考える。
nの階乗を考えよう
(* n ... (* 10 (* 9 (* 8 (* 7 (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1))))))))))
!!
そうだ。再帰の脱出口は「nの時が何か」って事。
イメージ的にこんな感じ。
(f (g (g (g (g ... )))))
初期関数fと繰り返し関数gが必要。脱出口というよりは、はじめのの一歩といった感じ。
はじめの一歩目を定義して、自分自身で自分自身を定義する。終わりを知ってるのは関数の中にあるかもしれない。無いかもしれない。再帰関数にとっては、はじめのめの一歩が脱出口。
何かが足りない気がするが、なんとなくわかってきた。
なんとなくわかってきたので、コーディングだ!!
まずは、理想形を考える。
理想形を考えよう。
とりあえず階乗の関数を作り出したい。
(define fact-maker (lambda (何か) (lambda (n) (if (zero? n) 1 (* n (何か (- n 1)))))))
空白部分を埋めるのが今回のミッションだ。何かとは何かを考える。
何かとは、
そうそう、再帰は自分に自分を与えたもの。だから、引数は自分。
fact-makerと置いておこう。self = fact-makerという意味。
(define fact-maker (lambda (self) (lambda (n) (if (zero? n) 1 (* n ((self self) (- n 1)))))))
(self self)は自分で、自分を作用させたもの。ついでに引数に自分を取る。次の自分だ。
評価すると、中の関数(lambda (n) ...)が出てくる。10だと、(self self)を呼んでるから、 評価すると、中の関数(lambda (n) ...)が出てくる。9だと、(self self)を呼んでるから、 評価すると、中の関数(lambda (n) ...)が出てくる。8だと、(self self)を呼んでるから、 ・・・ 評価すると、中の関数(lambda (n) ...)が出てくる。0になったとき、(self self)を呼ばない。再帰終了だ。
タケノコみたいに中の関数を生み出していく。フシギ。
じゃ、どうやって呼び出すか。
そうそう。初期関数と、繰り返し関数が必要だった。
(初期関数 繰り返し関数)
初期関数に繰り返し関数を作用させたもの。
初期関数と繰り返し関数は、いっしょだから。
(fact-maker fact-maker)
こう書ける。「何か」の原動力だ。
このままでは、階乗の再帰関数が帰ってくるだけなので、数を与える。
((fact-maker fact-maker) 10) ; 3628800
出た!!
つまり、こう書ける
えぃ!!
(((lambda (self) ; 初期関数 (lambda (n) (if (zero? n) 1 (* n ((self self) (- n 1)))))) (lambda (self) ; 繰り返し関数 (lambda (n) (if (zero? n) 1 (* n ((self self) (- n 1))))))) 10)
「名前が消えた」
再帰を名前無しで書くことに成功しました。
初期関数は1回しか使ってないので、初期関数は、こんな感じでも構わない訳。
(((lambda (self) ; 初期関数 (lambda () (* 10 ((self self) 9)))) (lambda (self) ; 繰り返し関数 (lambda (n) (if (zero? n) 1 (* n ((self self) (- n 1))))))))
再帰にはじめのめの一歩がいる。後は繰り返し関数をどんどん使っていく。
ここまでが第一段階。ここまで理解できれば後は簡単だ!!
再帰を抽象化していこう!!
しまった。重要な事を忘れていた。「関数には引数が必要」だよね。
忘れていた部分を抽象化しよう。
引数の処理部分。
((self self) (- n 1))
(f arg)と置くと、
((lambda (arg) (f arg)) arg)
展開して、
((lambda (arg) ((self self) arg)) (- n 1))
動かす。
(define fact-maker (lambda (self) (lambda (n) (if (zero? n) 1 (* n ((lambda (arg) ((self self) arg)) (- n 1))))))) ((fact-maker factmaker) 10)
いいね!!
lambdaを外に出すと。
(define fact0 (lambda (f) (lambda (n) (if (zero? n) 1 (* n (f (- n 1)))))))
動かすには、
コレが1個。
(lambda (g) (fact0 (lambda (arg) ((g g) arg))))
これで一個の関数が帰ってくるから、fact-makerみたいにすると、
(((lambda (g) (fact0 (lambda (arg) ((g g) arg)))) (lambda (g) (fact0 (lambda (arg) ((g g) arg))))) 10)
うん。これで括り出された!!
ちなみに、(self self)だけを括り出すと、無限ループになっちゃう。
第二段階完了。
突き進め!!
fact0を外に出して、
(((lambda (f) ((lambda (g) (f (lambda (arg) ((g g) arg)))) (lambda (g) (f (lambda (arg) ((g g) arg)))))) fact0) 10)
うんうん。
Yって名前を付ける
名前重要。
(define Y (lambda (f) ((lambda (g) (f (lambda (arg) ((g g) arg)))) (lambda (g) (f (lambda (arg) ((g g) arg))))))) ((Y fact0) 10)
YがYコンビネータと呼ばれる。再帰関数の定義。Yを不動点演算子というらしい。
Yを分解すると、
((Y fact0) 10) ((fact0 (Y fact0)) 10) ((fact0 (fact0 (Y fact0))) 10) ((fact0 (fact0 (fact0 (Y fact0)))) 10)
切っても切ってもfact0が出てくる。楽しい。
ちなみに、MIT Schemeの盾を見るとThe Scheme Programming Language
(Y F) = (F (Y F))
なんて書いてあったりする。
つまり、いっぱい書いとけば・・・。
((fact0 (fact0 (fact0 (fact0 (fact0 (fact0 (fact0 (fact0 (fact0 (fact0 (fact0 (fact0 "ここまではいかない")))))))))))) 10)
ちゃんと求まったりする。Yコンビネータなんて、案外単純なもんだ。
と思ったが、fact0だけの定義は「有限」。Yの定義は「無限」なので、意味がちょっと違うっぽい。
アレ？無限ってもしかして・・・
...デバッグ中
あぁ〜無限ってことはつまり、遅延評価してるってことだ。
次をクレ、次をクレ、次をクレ・・・次はイラナイ (間違い)
ん？違う。ちがう。ちがぁ〜〜〜う。
クレとは要求してない。こうじゃない。次を渡してるだけだ。
次を渡す、次を渡す、次を渡す・・・次を渡したが使わなかった
おぉぉぉぉ遅延してる!!
評価よりも先に関数がある。関数が一歩先を行っちゃってるんだ。一個先に関数を渡しておけば、遅延出来る。無限が扱える。次がわからないから、最初に一個渡しておく。うはぁ〜スゲ〜。
「遅延評価は、1個先の関数を先読みしてる」
遅延評価の仕組みまでわかってしまった。
全部展開すると
さて、全部展開すると名前の無い再帰が作れる。
(((lambda (f) ((lambda (g) (f (lambda (arg) ((g g) arg)))) (lambda (g) (f (lambda (arg) ((g g) arg)))))) (lambda (f) (lambda (n) (if (zero? n) 1 (* n (f (- n 1))))))) 10)
わかっちゃったよオイ!!
しかっし
引数が一個しか取れないので、applyしとく。
(define Y (lambda (f) ((lambda (g) (f (lambda arg (apply (g g) arg)))) (lambda (g) (f (lambda arg (apply (g g) arg)))))))
反復のfactをしてみる。
((Y (lambda (f) (lambda (n acc) (if (zero? n) acc (f (- n 1) (* acc n)))))) 10 1)
いいね!!
もうちょっと
なんか2度呼ぶのが許せない。
letする。
(define Y (lambda (f) (let ((h (lambda (g) (f (lambda arg (apply (g g) arg)))))) (h h))))
letをlambdaに置き換える。
(define Y (lambda (f) ((lambda (h) (h h)) (lambda (g) (f (lambda arg (apply (g g) arg)))))))
スッキリした。
まとめ
- Yコンビネータは引数に、はじめの一歩を取る。
- 再帰には、初期関数と、繰り返し関数が必要なので,初期関数に、繰り返し関数を与える。
- その際、自分自身(はじめの一歩)が生み出されるので、引数をて与え実行する。
- 繰り返し関数は、初期関数と、繰り返し関数を生み出すので・・・再帰には・・・
理解した。
と思ったけど
まだまだYコンビネータの「はじめの一歩」だったらしい。
- 不動点オペレータについて
- 相互再帰の例
- Fixed point combinator - Wikipedia, the free encyclopedia
- Yのα変換、β変換もうすぐそこだ。
まだまだ先はながいぞぉ〜。
