2010/01/12 11:06:16
pythonでY-combinator(Z-combinator?)
SICPも2章に入り、お約束らしいchurch数のあたりでプチ詰まり。
とか参考にしながら、後者のほうはperlのコードがあるから理解しやすいなぁとかいいながら読み進めるが、途中からさっぱりわからん。というより、Y-combinatorを理解しないと先に進めなさそうなので、Y CombinatorとTuringとChurchの狭間でを行ったりきたりしながらくらいつく。
一通り理解した気がしたところで、perlのZ-combinatorをpythonで書いてみた。
まず階乗のpython2.5から導入されたという、3項演算子を使ってみた。
>>> def f(n):
... return 1 if n < 2 else n * f(n-1)
こんな感じで書けるがなんか、、、perlの三項演算子のほうが好き。
で、早速Z-combinator
Z = lambda f: (lambda x : lambda y : f(x(x)))(lambda x : lambda y : f(x(x)))
fact = lambda f : lambda n : 1 if n < 2 else n * f(FORCE)(n-1)
FORCE = lambda a : a
実行
>>> Z(fact)(FORCE)(7)
5040
pythonはラムダ式が書けるのでperlよりはすっきりと書ける感じ。
一応pythonでもY-combinatorの形で実行したけどこれは無限ループした。
Z = lambda f: (lambda x : f(x(x)))(lambda x : f(x(x)))
perlやpythonのばあい、クロージャにして無理やり遅延させるので
our $FORCE = sub { my $a = shift; $a };
評価が先送りになんのはわかるんだけど、schemeで
(f 5)
を
((lambda (x) (f x)) 5)
にすると遅延するのがよくわからんかった。書き方変えてるだけにしか見えないんだけど。これはクロージャと同じものなのだろうかそれとも評価の順番が違うからなのか?