Y Combinatorについて理解した(つもり)。まとめ。
Y Combinatorとは
以下のブログが非常に分かりやすかった。感謝!
関数を引数にとり、新しい関数を返す関数Fとする。
FをY Combinatorに適用すると、再帰関数fができる。
この再帰関数fは最初の関数Fの不動点である。
不動点であるため、この再帰関数fを関数Fに適用すると再帰関数fができる。
これで関数で再帰できることになる。
関数の引数として受け取った関数で再帰できるので、関数の名前が不要である。
無名再帰ともいうようだ。
と書いていて、本当に理解したのか怪しくなってくるなぁ...
Y Combinatorの求め方
Y Combinatorの求め方は次のブログが参考になった。
こちらにも感謝!
Y Combinator
http://www.loveruby.net/ja/misc/ycombinator.html
自分なりにまとめ直すと、以下の通り。
階乗を求める関数を元に、Y Combinatorを使って名前の定義を不要にするまで。
まずは階乗を求める関数。
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
(fact 10) ; => 3628800
階乗を求める関数を作る関数。
(define fact-maker
(lambda ()
(lambda (n)
(if (= n 0)
1
(* n ((fact-maker) (- n 1)))))))
((fact-maker) 10) ; => 3628800
(fact-maker)を一番外側のlambdaの仮引数fで受け取るようにする。
再帰時には自分自身を渡さなくてはならないので (f f)となる。
(define fact-maker
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n ((f f) (- n 1)))))))
((fact-maker fact-maker) 10) ; => 3628800
(f f) を f と書きたい。
((f f) arg) は ((lambda (arg) ((f f) arg)) arg) と同じ。
置換すると
(define fact-maker
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n ((lambda (arg) ((f f) arg)) (- n 1)))))))
fact0を以下のようにおき、(lambda (arg) ((f f) arg)) を 渡すようにすれば
(define fact0
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))
(define fact-maker
(lambda (f)
(fact0 (lambda (arg) ((f f) arg)))))
となる。
ここで f を g に置き換えると
(define fact-maker
(lambda (g)
(fact0 (lambda (arg) ((g g) arg)))))
となる。
よって、
(fact-maker fact-maker)
は、以下の式となる。
((lambda (g)
(fact0 (lambda (arg) ((g g) arg))))
(lambda (g)
(fact0 (lambda (arg) ((g g) arg)))))
fact0を外に出すと
(lambda (f)
((lambda (g)
(f (lambda (arg) ((g g) arg))))
(lambda (g)
(f (lambda (arg) ((g g) arg))))))
となる。
これが Yコンビネータ。
(define Y
(lambda (f)
((lambda (g)
(f (lambda (arg) ((g g) arg))))
(lambda (g)
(f (lambda (arg) ((g g) arg)))))))
(define fact
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))
((Y fact) 10) ; => 3628800
Micro Schemeで実行
現在、作成中の Micro Scheme で実行してみる。
(define Y
(lambda (f)
((lambda (g)
(f (lambda (arg) ((g g) arg))))
(lambda (g)
(f (lambda (arg) ((g g) arg)))))))
;=> [:Y,
[:closure,
[:f],
[[:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]],
[:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]]],
[{:Y=>[...]},
{:true=>true, :false=>false},
{:+=>[:built_in, #<Proc:0x8d520c0@uschemer.rb:8 (lambda)>],
:-=>[:built_in, #<Proc:0x8d52098@uschemer.rb:9 (lambda)>],
:*=>[:built_in, #<Proc:0x8d52070@uschemer.rb:10 (lambda)>],
:/=>[:built_in, #<Proc:0x8d52048@uschemer.rb:11 (lambda)>],
:"="=>[:built_in, #<Proc:0x8d52020@uschemer.rb:12 (lambda)>],
:<=>[:built_in, #<Proc:0x8d51ff8@uschemer.rb:13 (lambda)>],
:>=>[:built_in, #<Proc:0x8d51fd0@uschemer.rb:14 (lambda)>],
:<==>[:built_in, #<Proc:0x8d51f6c@uschemer.rb:15 (lambda)>],
:>==>[:built_in, #<Proc:0x8d51f44@uschemer.rb:16 (lambda)>]}]]]
(define fact
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))
;=> [:fact,
[:closure,
[:f],
[:lambda, [:n], [:if, [:"=", :n, 0], 1, [:*, :n, [:f, [:-, :n, 1]]]]],
[{:fact=>[...]},
{:Y=>
[:closure,
[:f],
[[:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]],
[:lambda, [:g], [:f, [:lambda, [:arg], [[:g, :g], :arg]]]]],
[...]]},
{:true=>true, :false=>false},
{:+=>[:built_in, #<Proc:0x8d520c0@uschemer.rb:8 (lambda)>],
:-=>[:built_in, #<Proc:0x8d52098@uschemer.rb:9 (lambda)>],
:*=>[:built_in, #<Proc:0x8d52070@uschemer.rb:10 (lambda)>],
:/=>[:built_in, #<Proc:0x8d52048@uschemer.rb:11 (lambda)>],
:"="=>[:built_in, #<Proc:0x8d52020@uschemer.rb:12 (lambda)>],
:<=>[:built_in, #<Proc:0x8d51ff8@uschemer.rb:13 (lambda)>],
:>=>[:built_in, #<Proc:0x8d51fd0@uschemer.rb:14 (lambda)>],
:<==>[:built_in, #<Proc:0x8d51f6c@uschemer.rb:15 (lambda)>],
:>==>[:built_in, #<Proc:0x8d51f44@uschemer.rb:16 (lambda)>]}]]]
((Y fact) 10)
;=> 3628800
おーーー。動いた。
ちょっと感動...
