How can I write a Python decorator to increase stackdepth

Questions

BACKGROUND

When playing around, I often write simple recursive functions looking something like:

def f(a,b):
    if a>=0 and b>=0:
        return min( f(a-1,b) , f(b,a-1) ) # + some cost that depends on a,b
    else:
        return 0

(For example, when computing weighted edit distances, or evaluating recursively defined mathematical formulas.)

I then use a memoizing decorator to cache the results automatically.

PROBLEM

When I try something like f(200,10) I get:

RuntimeError: maximum recursion depth exceeded

This is as expected because the recursive implementation exhausts Python s stack space/ recursion limits.

WORKAROUNDS

I usually work around this problem by one of:

• Increasing recursion limit with sys.setrecursionlimit (only works up to about 1000 depth)
• Using a for loop to fill up the cache for smaller values
• Changing the function to use a list as a manual stack (via append and pop calls) (in other words, moving from a recursive implementation to an iterative one)
• Using an alternative programming language

but I find all of these quite error prone.

QUESTION

Is there a way to write an @Bigstack decorator that would simulate the effect of having a really big stack?

Note that my functions normally make several recursive function calls so this is not the same as tail recursion - I really do want to save all the internal state of each function on the stack.

WHAT I VE TRIED

I ve been thinking about using a list of generator expressions as my stack. By probing the stackframe I could work out when the function has been called recursively and then trigger an exception to return to the decorator code. However, I can t work out a way of gluing these ideas together to make anything that actually works.

Alternatively, I could try accessing the abstract syntax tree for the function and try transforming calls to recursive functions to yield statements, but this seems like it s heading in the wrong direction.

Any suggestions?

EDIT

It certainly looks like I am misusing Python, but another approach I have been considering is to use a different thread for each block of, say, 500 stack frames and then insert queues between each consecutive pair of threads - one queue for arguments, and another queue for return values. (Each queue will have at most one entry in it.) I think this probably doesn t work for some reason - but I ll probably only work out why after I ve tried to implement it.

Answers

To get around the recursion limit, you can catch the RuntimeError exception to detect when you ve run out of stack space, and then return a continuation-ish function that, when called, restarts the recursion at the level where you ran out of space. Call this (and its return value, and so on) until you get a value, then try again from the top. Once you ve memoized the lower levels, the higher levels won t run into a recursion limit, so eventually this will work. Put the repeated-calling-until-it-works in a wrapper function. Basically it s a lazy version of your warming-up-the-cache idea.

Here s an example with a simple recursive "add numbers from 1 to n inclusive" function.

import functools

def memoize(func):
    cache = {}
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        key = args, tuple(sorted(kwargs.items()))
        if key in cache:
            return cache[key]
        else:
            result = func(*args, **kwargs)
            if not callable(result):
                cache[key] = result
            return result
    return wrapper

@memoize
def _addup(n):
    if n < 2:
        return n
    else:
        try:
            result = _addup(n - 1)
        except RuntimeError:
            return lambda: _addup(n)
        else:
            return result if callable(result) else result + n

def addup(n):
    result = _addup(n)
    while callable(result):
        while callable(result):
            result = result()
        result = _addup(n)
    return result

assert addup(5000) == sum(xrange(5001))

Rather than returning the lambda function all the way back up the call chain, we can raise an exception to short-circuit that, which both improves performance and simplifies the code:

# memoize function as above, or you can probably use functools.lru_cache

class UnwindStack(Exception):
    pass

@memoize
def _addup(n):
    if n < 2:
        return n
    else:
        try:
            return _addup(n - 1) + n
        except RuntimeError:
            raise UnwindStack(lambda: _addup(n))

def _try(func, *args, **kwargs):
    try:
        return func(*args, **kwargs)
    except UnwindStack as e:
        return e[0]

def addup(n):
    result = _try(_addup, n)
    while callable(result):
        while callable(result):
            result = _try(result)
        result = _try(_addup, n)
    return result

This remains pretty inelegant, though, and still has a fair amount of overhead, and I can t imagine how you d make a decorator out it. Python isn t really suited to this kind of thing, I guess.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/13501896/how-can-i-write-a-python-decorator-to-increase-stackdepth

Related