そろそろ分かっておきたいY Combinator

もうすぐ年明けだし,Yコンビネータの魔法みたいな動きに惑わされる人
たちがでてくるんじゃないかなと思ってRubyで解説してみます.
 

Y Combinatorって何?

3年周期くらいでお騒がせのYさんってそもそも何なのかという話ですが,動機として

再帰の時に自分の名前を使わずに,なんとかして関数そのものを呼びたい

というのがあって,例えば階乗とかしたいときに

def fact(n); n == 0 ? 1 : n * fact(n-1); end
#                            ここを消したい!

と言う事です.
何が嬉しいのかというと,さっぱり分かりませんし,arguments.calleeとか普通に名前使える所では使えばいいんじゃないのかな.
 

前置き

Ruby1.9のlambdaでは

->{|n| puts n}[3] #=> 3

ちょっとネストしたりすると分かりづらいので説明では

lambda{|n| puts n}[3] #=> 3

としますね.
ちなみに[]は配列の要素指定では無く.『.call』の別名です.
 

Rubyで分かるY Combinator

これのfactという名前をなんとか消したい.

def fact(n); n == 0 ? 1 : n * fact(n-1); end

 
だったら,factのメソッドを生成するものを定義すればいいじゃないかという事で.
fact_makerというfactを生成するlambda作る事にします.

fact_maker = lambda{|proc| lambda{|n| n == 0? 1 : n * proc[(n-1)] }}
puts fact_maker[5] #=> <Proc:0xb7c399cc@./ycombinator.rb:8>

引数に5を入れたらProcが返ってきた!Rubyのバグですか!
違います.よく見ると当然のことですね.
fact_makerはfactを生成するだけですので,それに5とか与えられてもね.
 
これが正しい呼び出し方

fact_maker = lambda{|proc| lambda{|n| n == 0? 1 : n * proc[proc][(n-1)] }}
puts fact_maker[fact_maker][5]

 
変更した点は二箇所

  1. fact_maker[fact_maker]
  2. proc[proc]

つまり

  1. fact_maker呼び出し
  2. 次回に呼ぶfact_maker渡し
  3. 生成された関数に引数渡し

という流れになります.
しかし,やっぱりfact_makerという名前が残ってしまった.しかもproc[proc]というのもちょっとダサい.
そこでfact_maker[fact_maker]の部分を生成するものを作ることにしましょう.
これには

5 #=> 5
lambda{|n| n}[5] #=> 5

が等価だって事を利用します.
上と下が違うのはlambdaを挟んで遅れて評価しているという点です.(これ重要)
  
これを何も考えずに当てはめてみると.

fact_maker = lambda{|proc| lambda{|n| n == 0? 1 : n * lambda{|args| proc[proc][args] }[(n-1)]} }
puts fact_maker[fact_maker][5] #=> 120

になります.
 
そして,ここから一気にその部分を外に抜き出すと..

fact_maker = lambda{|f| lambda{|n| n == 0? 1 : n * f[(n-1)]} }
proc_proc = lambda{|proc| fact_maker[lambda{|args| proc[proc][args] }]}

これでproc[proc]という呼び出しが fact_maker のlambda内から消えましたね.
 
次は肝心の fact_maker[fact_maker] の部分を消す所ですが,これは簡単ですね.
なぜなら fact_maker って proc[proc] の事なんですから.

fact_maker = lambda{|f| lambda{|n| n == 0? 1 : n * f[(n-1)]} }
proc_proc = lambda{|proc| fact_maker[lambda{|args| proc[proc][args] }]}
puts proc_proc[proc_proc][5] #=> 120

 
次は proc_proc から fact_maker という名前も消したいと思います.
これも引数から取るようにすればいいので.

fact_maker = lambda{|f| lambda{|n| n == 0? 1 : n * f[(n-1)]} }
proc_proc = lambda{|f| lambda{|proc| f[lambda{|args| proc[proc][args] }]}}
puts proc_proc[fact_maker][proc_proc[fact_maker]][5] #=> 120

 
次はproc_proc[proc_proc]の部分を一つにしてしまいましょう.
面倒ですので.

fact_maker = lambda{|f| lambda{|n| n == 0? 1 : n * f[(n-1)]} }
pppp = lambda do |f| 
  lambda{|proc| f[lambda{|args| proc[proc][args] }]}[
    lambda{|proc| f[lambda{|args| proc[proc][args] }]}
  ]
end
puts pppp[fact_maker][5] #=> 120

  
次に fact_maker はもう fact_ を make しないので名前を変えてしまいましょう.

fact = lambda{|f| lambda{|n| n == 0? 1 : n * f[(n-1)]} }
pppp = lambda do |f| 
  lambda{|proc| f[lambda{|args| proc[proc][args] }]}[
    lambda{|proc| f[lambda{|args| proc[proc][args] }]}
  ]
end
puts pppp[fact][5] #=> 120

 
それで Y Combinator って何かっていうと.

fact = lambda{|f| lambda{|n| n == 0? 1 : n * f[(n-1)]} }
Y = lambda do |f| 
  lambda{|proc| f[lambda{|args| proc[proc][args] }]}[
    lambda{|proc| f[lambda{|args| proc[proc][args] }]}
  ]
end
puts Y[fact][5] #=> 120

これの事なんですね.
factが参照しているlambdaの引数に自分自身の名前を入れてくれるようなんです.
ファンタジーですね.
 

Unlambda

The Unlambda Programming Language
について調べていたら Y Combinator なんて勉強する羽目に..恐ろしい子