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

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

第一个字符串打印出如下错误：

RecursionError: maximum recursion depth exceeded in comparison
Fatal Python error: _Py_CheckRecursiveCall: Cannot recover from stack overflow.
Python runtime state: initialized

它会导致无限循环。

Answer 2

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 组合器（参见上面的维基百科文章）。

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

Why is it not possible to implement fixed-point combinator like in the definition?

python

lambda-calculus

python-3.x