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

Question

我正在尝试实现 Y 组合器 like in the definition by Curry .
此代码不起作用。它会导致无限递归。

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 组合器无限递归的原因。如 linked Wikipedia article 中所述:

In a strict programming language the Y combinator will expand until stack overflow, or never halt in case of tail call optimization.

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