CODEWITHSUNDEEP
pythonlambdaevaluationdelayed-executionfixpoint-combinators
lo tolmencre
lo tolmencre

Reputation: 3954

Delaying Evaluation with Abstractions in the Y-Combinator

I am having some problem wrapping my head around how evaluation delaying works. I am trying to understand it with the Y-Combinator:

If we write a simple version of the Y-Combinator we get problems with infinite recursion:

Ysimple = (lambda f : (lambda x : f(x(x))) (lambda x : f(x(x))))

When we build a recursive function, the problem appears:

almost_factorial = lambda f : lambda n : 1 if n == 0 else n * f(n-1)

factorial = Ysimp(almost_factorial) # <- infinite recursion

Ysimple = (lambda f : (lambda x : f(x(x))) (lambda x : f(x(x)) ))
[Previous line repeated 995 more times] RecursionError: maximum recursion depth exceeded

But we can wrap either the second or both of the f(x(x))-expressions in a delaying abstraction:

Ydelay = (lambda f : (lambda x : f(x(x))) (lambda x : f(lambda y: x(x)(y))) )

And now the code works just fine. But why?

If we have ONLY Ysimple in our file nothing gets evaluated. So I assume only lambdas get evaluated that are the top-level expression.

I did some manual evaluation steps but I don't see the reason in them for the delay happening:

Ysimple F =  (lambda f : (lambda x : f(x(x))) (lambda x : f(lambda y: x(x)(y)))) F
          -> (lambda x : F(x(x))) (lambda x : F(lambda y: x(x)(y)))
          -> F( (lambda x : F(lambda y: x(x)(y))) (lambda x : F(lambda y: x(x)(y))) )


Ydelay F =  (lambda f : (lambda x : f(x(x))) (lambda x : f(x(x)))) F
         -> (lambda x : F(x(x))) (lambda x : F(x(x)))
         -> F( (lambda x : F(x(x))) (lambda x : F(x(x))) )

Where does the delay happen here? In both cases F is the top-level expression and also in both cases lambda x is at level below F. What role does the delay lambda y play?

Edit:

Similarly, why how does the delay work in the first line here:

(lambda x : x(x)) (lambda y: lambda x : x(x)(y))
(lambda x : x(x)) (lambda x: x(x))

Upvotes: 2

Views: 124

Answers (1)

lo tolmencre
lo tolmencre

Reputation: 3954

When we translate the lambda expressions into ordinary function syntax the whole thing becomes more apparent:

def f(x):                       # lambda x : x(x)
    return x(x)

def g(y):                       # lambda y: lambda x : x(x)(y)
    def fg(x):
        return (x(x))(y)
    return fg


f(g) # does not recurse infinitely

When we manually evaluate the expression corresponding to (lambda x : x(x)) (lambda y: (lambda x : x(x))(y)) we get

f(g) = g(g) = lambda x : x(x)(g)

while evaluating the one corresponding to (lambda x : x(x)) (lambda y: y(y)) yields

f(f) = f(f) = f(f) = ...

And we can now see why the abstraction halts the recursion.

Upvotes: 1

Related Questions