关于Y combinator的一点问题

既然Python有lambda函数,自然也能实现Y Combinator了。众所周知Y Combinator 是\( (\lambda y.(\lambda x. y(x \  x))(\lambda x. y(x \  x))) \),所以我照葫芦画瓢写了一个:

>>>Y=lambda y:(lambda x:y(x(x)))(lambda x:y(x(x)))
>>>f=lambda fact: lambda n: 1 if n==0 else n*fact(n-1)
>>>Y(f)(5)

然后就堆栈溢出了……

这篇文章中作者写的是y = lambda f: (lambda x: f(lambda n: x(x)(n)))(lambda x: f(lambda n: x(x)(n))),和上面那个版本的本质区别是把x(x)换成了lambda n: x(x)(n),两个函数从效果上是一样的(就是传一样的参数返回值肯定一样),但只有后者能成功运行。

这两者的区别我想了很长一段时间,我觉得原理应该是这样:Python在给调用Y(f)前肯定要把它算清楚,对于我的Y Combinator,在传入y后不管怎么展开都始终存在一个函数调用——就是Y(f)=f(Y(f))=f(f(Y(f)))……无穷无尽。而第二个版本最终会展开成 f(lambda n: (lambda x: f(lambda n: x(x)(n))((lambda x: f(lambda n: x(x)(n)))(n)))f的参数是一个lambda函数而非待计算值,所以能成功运行。

这其中有种惰性求值的思想在其中。

One thought to “关于Y combinator的一点问题”

  1. 同样意义的代码haskell里能成功运行,这就是惰性求值的意义所在吧。

发表评论

电子邮件地址不会被公开。 必填项已用*标注