关于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函数而非待计算值，所以能成功运行。

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