Python - Iteratively generated lambda doesn't work

Question

I'm having a bit of trouble understanding how Python treats and evaluates lambdas at runtime.

Iteratively building up an integer

Consider the following code (Python 3.5.2):

x = 0
for iteration in range(3):
    x = x + 1
print(x)

As expected, this prints 3. Here is my understanding of the way x changes over 3 iterations:

• Initial Value: x
• Iteration 1: x+1
• Iteration 2: (x+1) + 1
• Iteration 3: ((x+1) + 1) + 1

Iteratively building up a lambda

Consider the following code:

add3 = lambda x: x
for iteration in range(3):
    add3 = lambda x: add3(x) + 1
print(add3(0))

Here is my understanding of the way add3 should change over 3 iterations:

• Initial Value: lambda x: x
• Iteration 1: lambda x: (lambda x: x)(x) + 1
• Iteration 2: lambda x: (lambda x: (lambda x: x)(x) + 1)(x) + 1
• Iteration 3: lambda x: (lambda x: (lambda x: (lambda x: x)(x) + 1)(x) + 1)(x) + 1

Instead, calling add3 causes the maximum recursion depth to be exceeded. My first thought was that Python is dynamically looking up the function body from its name at call time, rather than storing the function's code as part of the function. However, even the following code does not work:

functionList = [lambda x: x] #Store each iteration separately
for i in range(3):
    oldFunction = functionList[-1]
    newFunction = lambda x: oldFunction(x) + 1 #Should be a completely new lambda object
    functionList.append(newFunction)
print(functionList[-1](0)) #Causes infinite recursion

Even with no named functions whatsoever, and following the suggestion here (although I may have misunderstood his answer), it still fails:

functionList = [lambda x: x]
for i in range(3):
    functionList.append(lambda x, i=i: functionList[-1](x) + 1)
print(functionList[-1](0)) #Causes infinite recursion

The four lambdas contained in functionList are completely separate objects in memory:

>>> print(functionList)
[<function <lambda> at 0x00000266D41A12F0>, <function <lambda> at 0x00000266D41D7E18>, <function <lambda> at 0x00000266D41D7730>, <function <lambda> at 0x00000266D41D7840>]

Could someone please explain this behavior?

Answer 1

This behavior has nothing to do with 'iterational' lambda generation. When you say add3 = lambda x: add3(x) + 1, the add3 object is replaced with a lambda calling itself recursively with no termination condition.

So when you call add3(0), it becomes:

add3(0) = add3(0) + 1 = (add3(0) + 1) + 1 = ((add3(0) + 1) + 1) + 1

And this goes on forever (well, until the maximum recursion depth is exceeded).

---

As for other examples, the second function in your list already fails with RecursionError: maximum recursion depth exceeded.

I've got this code for you:

import copy

flist=[lambda x: x]
flist.append(lambda x: copy.deepcopy(flist[-1])(x) + 1)

>>> flist
[<function <lambda> at 0x101d45268>, <function <lambda> at 0x101bf1a60>]

So we made sure that we call a copy of a function. flist[-1](0) results in a RecursionError, and the error is raised in the deepcopy module. So, this means that copy.deepcopy(flist[-1])(x) means 'copy the last element currently in the list and run the copy'.

Here it is: the last element of the list calls itself over and over again.

Answer 2

You are correct that it is evaluated at run time. Because of that, add3, when referenced in itself, is calling itself, not the old add3. In the case of your loop, you are always using [-1]. Since it is evaluated at run time, the first one calls the one at the end of the list. The one at the end of the list then calls the one at the end of the list which calls the one at the end of the list... The list is not changing by the time the functions are being called. Therefore, the first function is called once, and then the last function is called infinitely. What you want is to use [i] instead of [-1]. It is very good that you used a default argument for i in your lambdas because default arguments are evaluated at definition.

Answer 3

Python allows you to access variables in the enclosing scope, but you are changing those variables during the loop.

add3 = lambda x: x
for iteration in range(3):
    # This add3 will call itself!
    # It always uses the *current* value of add3,
    # NOT the value of add3 when it was created.
    add3 = lambda x: add3(x) + 1
print(add3(0))

You will need to create a new binding:

add3 = lambda x: x
for _ in range(3):
    add3 = (lambda f: lambda x: f(x) + 1)(add3)
print(add3(0))

This creates a new scope each time through the loop, which lets you bind with the current value of add3 rather than the future value of add3.

Languages which behave the way you describe are somewhat rare. Haskell is one example of such a language. In C++ you could achieve this by implicitly copying the lambdas using [=] for the capture list. Python just doesn't do this without some extra work.

Answer 4

Here's how add3 actually changes throughout the loop:

• Initial Value: lambda x: x
• Iteration 1: lambda x: add3(x) + 1

add3 is not immediately substituted inside the lambda body! It gets looked up when the function is executed.

• Iteration 2: lambda x: add3(x) + 1 again
• Iteration 3: still lambda x: add3(x) + 1

At the end, when you call add3, the recursive call to add3 inside the lambda body looks up the current value of add3, not the value when the lambda was defined. add3 calls itself, which calls itself, which calls itself, and so on until stack overflow.

---

Your attempted fix doesn't work because oldFunction still gets looked up at function execution time, so it still finds the final oldFunction instead of the oldFunction from function definition time. You didn't do anything to change that.

---

For comparison, when you do x = x + 1, x is immediately substituted, so in the first version, the values of x are successively 0, 1, 2, and 3. You don't have x = ((x+1) + 1) + 1 at the end; you just have x = 3.

Answer 5

Except for the name and name binding, the expression lambda <args>: <expression> creates a function that equals the result of def f(<args>): return <expression>. The statement f = lambda <args>: <expression> does not even have the name binding difference. However, some people falsely assume other differences. Many puzzles with lambda are illuminated by replacing it with equivalent defs. For the code above, we get the following.

def add3(x): return x
for iteration in range(3):
    def add3(x): return add3(x) + 1
print(add3(0))

Does this make it more obvious that the second def negates the first, by rebinding add3 to a new function object? And that executing the second def statement more than once is redundant? Is it still a surprise that a recursive function with no terminal base case to stop it raises Recursion Error?