0

I would like to turn the following pseudocode into Python code without inducing infinite recursion.

u(x) = x^2

for i = 0 to 5
v(x) = u(x)^2
u(x) = v(x)

print(u(x))

Here is my attempt, which produces the error "maximum recursion depth exceeded":

import sympy as sym

u = lambda a: a**2

for i in range(0,5):
  print('Starting loop',i)
  v = lambda b: u(b)**2
  u = lambda c: v(c)
  print('Ending loop',i)

x = sym.symbols('x')
print(u(x))
Robᵩ
  • 163,533
  • 20
  • 239
  • 308

2 Answers2

3

Python variables are bound by name, and a for loop does not actually create a new scope. So when you do lambda c: v(c), you are actually creating a function that will look up v from its surrounding scope when its being executed. This means that updates to v are all applied when the function is executed.

In particular, it means that the following two definition already create an infinite loop:

v = lambda b: u(b)**2
u = lambda c: v(c)

Because v calls u, and u calls v. It does not matter that the values are updated later, since the value will be looked up when the function is called.

You can visualize this easily using the following:

>>> x = lambda: y
>>> y = 2
>>> x()
2
>>> y = 5
>>> x()
5

Even though the function x is never updated, it will still use the updated value for y.

What you need here is a closure to put get references to the original functions in a separate scope so that later changes do not affect the function. A simple way is to add another function where the function you want to call is passed as an argument. Since functions create new variable scopes, these will be then independent of the original definitions:

for i in range(0, 5):
    print('Starting loop', i)
    v = (lambda u: lambda b: u(b)**2)(u)
    u = (lambda v: lambda c: v(c))(v)
    print('Ending loop', i)

See also this question on how binding works and how closures help there.

poke
  • 369,085
  • 72
  • 557
  • 602
  • Yeah, wrapping a function closure in another function is the canonical way of dealing with lexical scoping with late binding. However, using the keyword-argument hack in Python lets you force "early binding" and it looks a bit more readable to my eyes. Although, it *does* rely on a common language gotcha (keyword arguments are evaluated at definition time) to deal with *another* common language gotcha (late-binding, lexically scoped closures). – juanpa.arrivillaga Jun 05 '17 at 23:45
2

Try using these two lines:

v = lambda b, u=u: u(b)**2
u = lambda c, v=v: v(c)

This forces the values of u and v to be captured at the moment of lambda construction. Otherwise, the evaluation will be deferred until the lambdas are invoked.

Here is the complete program:

import sympy as sym

u = lambda a: a**2

for i in range(0,5):
  print('Starting loop',i)
  v = lambda b, u=u: u(b)**2
  u = lambda c, v=v: v(c)
  print('Ending loop',i)

x = sym.symbols('x')
print(u(x))

And here is the result:

$ python3 xx.py 
Starting loop 0
Ending loop 0
Starting loop 1
Ending loop 1
Starting loop 2
Ending loop 2
Starting loop 3
Ending loop 3
Starting loop 4
Ending loop 4
x**64
Robᵩ
  • 163,533
  • 20
  • 239
  • 308
  • 2
    Yes, this is precisely about what the closures capture. They capture the name, not the value, of the enclosing scope's variables. – Robᵩ Jun 05 '17 at 23:31
  • Ture, Python is not truly functional language. Perhaps dark magic like accessing func_code, rather than function itself might help – Serge Jun 05 '17 at 23:35
  • @user46944 lexically-scoped closures are for both `lambda` functions and normal, `def` defined functions. Lexical scoping isn't odd at all, it is pretty much used in all the major languages that I know of. – juanpa.arrivillaga Jun 05 '17 at 23:35
  • 1
    @Serge what? No, that isn't what you should do at all. Just be aware of the semantics of closures and use them appropriately. – juanpa.arrivillaga Jun 05 '17 at 23:36