2018-03-08 | 研究与探索 | UNLOCK

关于Y combinator的一点问题

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

1
2
3
>>> 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函数而非待计算值,所以能成功运行。

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