Python function composition (max recursion depth error, scope?)

Question

What is wrong with this function? It seems like a scope error (although I thought I had fixed that by placing each callable in the list, instead of using it directly). Error is max recursion depth reached (when calling comp(inv,dbl,inc))...

Note: the question is: why is it even recursing, not why it's reaching the max depth...

def comp(*funcs):
    if len(funcs) in (0,1):
        raise ValueError('need at least two functions to compose')
    # get most inner function
    composed = []
    print("appending func 1")
    composed.append(funcs[-1])
    # pop last and reverse
    funcs = funcs[:-1][::-1]
    i = 1
    for func in funcs:
        i += 1
        print("appending func %s" % i)
        composed.append(lambda *args, **kwargs: func(composed[-1](*args,**kwargs)))
    return composed[-1]

def inc(x):
    print("inc called with %s" % x)
    return x+1
def dbl(x):
    print("dbl called with %s" % x)
    return x*2
def inv(x):
    print("inv called with %s" % x)
    return x*(-1)

if __name__ == '__main__':
    comp(inv,dbl,inc)(2)

Traceback (if it helps):

appending func 1
appending func 2
appending func 3
Traceback (most recent call last):
  File "comp.py", line 31, in <module>
    comp(inv,dbl,inc)(2)
  File "comp.py", line 17, in <lambda>
    composed.append(lambda *args, **kwargs: func(composed[-1](*args,**kwargs)))
  File "comp.py", line 17, in <lambda>
    composed.append(lambda *args, **kwargs: func(composed[-1](*args,**kwargs)))
  File "comp.py", line 17, in <lambda>
    composed.append(lambda *args, **kwargs: func(composed[-1](*args,**kwargs)))
  (...)
  File "comp.py", line 17, in <lambda>
    composed.append(lambda *args, **kwargs: func(composed[-1](*args,**kwargs)))
RuntimeError: maximum recursion depth exceeded while calling a Python object

See http://stackoverflow.com/questions/6035848/python-closure-not-working-as-expected/6035865 and similar questions — Jochen Ritzel, Aug 01 '11 at 15:05

sth · Accepted Answer · 2011-08-01T15:09:44.067

5

The lambda function you create builds a closure over the composed variable:

composed.append(lambda *args, **kwargs: func(composed[-1](*args,**kwargs)))

This means that composed[-1] isn't evaluated when you create the lambda function, but when you call it. The effect is, that composed[-1] will be calling itself recursively again and again.

You can solve this problem by using a helper function (with its own scope) to create the lambda functions:

def comp2(f1, f2):
    return lambda *args, **kwargs: f1(f2(*args, **kwargs))

...
for func in funcs:
     composed.append(comp2(func, composed[-1]))

edited Aug 01 '11 at 15:09

answered Aug 01 '11 at 15:00

sth

222,467
53
283
367

1

The other problem is that `for func in funcs` loop, so the `func` in each lambda is the same. – Jochen Ritzel Aug 01 '11 at 15:04
So I just tried doing it by explicitly calling composed[i], but it still has the same problem. Shouldn't it then just call composed[10](composed[9](composed[8](...)))? – o1iver Aug 01 '11 at 15:05
I think what jochen just said might be the actual problem – o1iver Aug 01 '11 at 15:05
1

@o1iver: The closure over `composed` causes the recursion, and the closure over `func` will cause wrong results to be calculated. Also the `inc`,... functions probably shouldn't return lambda functions, but normal values. – sth Aug 01 '11 at 15:17
Ok I have fixed it now as you were saying, makes sense now. Thanks! – o1iver Aug 01 '11 at 15:30

score 1 · Answer 2 · answered Aug 01 '11 at 15:18

I don't know why you generate to many functions to begin with. There is a simple version of your code:

def compose(*funcs):
    if len(funcs) in (0,1):
        raise ValueError('need at least two functions to compose')

    # accepting *args, **kwargs in a composed function doesn't quite work
    # because you can only pass them to the first function.
    def composed(arg):
        for func in reversed(funcs):
            arg = func(arg)
        return arg

    return composed

# what's with the lambdas? These are functions already ...
def inc(x):
    print("inc called with %s" % x)
    return x+1
def dbl(x):
    print("dbl called with %s" % x)
    return x*2
def inv(x):
    print("inv called with %s" % x)
    return -x

if __name__ == '__main__':
    f = compose(inv,dbl,inc)
    print f(2)
    print f(3)

Yes the functions were wrong... copied them from the command line — o1iver, Aug 01 '11 at 15:29
Great answer. I was doing this way to complicated... And good point about the args only being for the first function. Thanks! — o1iver, Aug 01 '11 at 15:31
Although I just tried out something and sth's way of doing it allows you to use *args and **kwargs. — o1iver, Aug 01 '11 at 15:41

Python function composition (max recursion depth error, scope?)

2 Answers2

Linked