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

user_13331635 0
Viewed 337

I'm trying to implement the Y-combinator like in the definition by Curry.

This code does not work. It causes infinite recursion.

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)

However, this one does work:

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

Why is the first one not working, but the second one is?

lambda-calculus python-3.x python
2 Answers

Python evaluates all function arguments eagerly and this is what causes infinite recursion for the Y-combinator. As stated in the 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.

In order to prevent that "eagerness", one can replace the direct function call x(x) with another lambda function. Being hidden inside that lambda function prevents it from evaluating straightaway. That's what you've done in your second version: lambda v: x(x)(v). This form is then known as the Z-combinator (see the Wikipedia article above).

user_37672390

The first string prints out the following error:

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

It causes an infinite loop.

user_147052100
Related