Yコンビネータ(2)

Y Combinatorをほぼそのままrubyに書き換えただけです．

ちなみに，ポール・グレアム関連でYコンビネータについて聞いたことがあるだけで，λ計算を勉強したことは無い．λ計算関連のページを検索してみるか．

素朴な階乗：

fact = lambda{|n| (n==0)? 1: n * fact[n - 1] }
p fact[5]

ラムダ式の中からfactを消す．代わりに呼び出し元が二重になった．

fact = lambda{|f| lambda{|n| (n==0)? 1: n * f[f][n - 1] }}
p fact[fact][5]

いまのfactは元々のfactを作り出すラムダ式．

f[f][n-1]をf[n-1]に変形するための準備その1
f[f]をラムダ式にしてしまう．これでlambda{...}[x]はf[x]に変形できる．

fact = lambda{|f| lambda{|n|
  (n==0)? 1: n * lambda{|x| f[f][x]} [n-1] }}
p fact[fact][5]

lambda{|x|f[f][x]}をfの代わりに引数として渡すように変形する．

fact = lambda{|g|
  lambda{|f|
    lambda{|n| (n==0)? 1: n * f[n-1] }
  } [lambda{|x|g[g][x]}]
}
p fact[fact][5]

外側のlambdaを分離する．

fact = lambda{|f| lambda{|n| (n==0)? 1: n * f[n-1] }}
factX = lambda{|f| fact[lambda{|x| f[f][x]}]}
p factX[factX][5]

factXの中にfactが入ってしまったが，そのうち消える予定．

呼び出しもとの factX[factX]を整理

fact = lambda{|f| lambda{|n| (n==0)? 1: n * f[n-1] }}
factX = lambda{|f| fact[lambda{|x| f[f][x]}]}
pseud_y = lambda{|x| x[x]}
p pseud_y[factX][5]

pseud_yのx[x]はfactX[factX]だから展開して，

fact = lambda{|f| lambda{|n| (n==0)? 1: n * f[n-1] }}
pseud_y = 
  lambda{|f| fact[lambda{|x| f[f][x]}]}[
  lambda{|f| fact[lambda{|x| f[f][x]}]}]
p pseud_y[5]

pseud_yからfactを外に出して，

fact = lambda{|f| lambda{|n| (n==0)? 1: n * f[n-1] }}
pseud_y = lambda{|g|
  lambda{|f| g[ lambda{|x| f[f][x]}]}[
  lambda{|f| g[ lambda{|x| f[f][x]}]}]
}
p pseud_y[fact][5]