为什么不能像定义中那样实现定点组合器？

Question

我正在尝试像 Curry 定义的那样实现 Y 组合器。

此代码不起作用。它会导致无限递归。

F = (lambda f: (lambda x: (1 if x == 0 else (x * (f(x-1))))))    
Y = (
    lambda f: 
    (lambda x: f(x(x)))
    (lambda x: f(x(x)))
)
Y(F)(3)

但是，这个确实有效：

Y = (
    lambda f: 
    (lambda x: f(
        lambda v: x(x)(v)
    ))
    (lambda x: f(
        lambda v: x(x)(v)
    ))
)
Y(F)(3)

为什么第一个不起作用，而第二个起作用？

Answer 1

Python 急切地计算所有函数参数，这就是导致 Y 组合器无限递归的原因。正如链接的维基百科文章中所述：

在严格的编程语言中，Y 组合器将扩展直到堆栈溢出，或者在尾部调用优化的情况下永远不会停止。

为了防止这种“急切”，可以x(x)用另一个 lambda 函数替换直接函数调用。隐藏在 lambda 函数内部会阻止它直接求值。这就是您在第二个版本中所做的事情：lambda v: x(x)(v)。这种形式被称为 Z 组合器（参见上面的维基百科文章）。