Samuel Li Samuel Li - 4 months ago 8
Python Question

Python - Iteratively generated lambda doesn't work

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

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.

Comments