Menu Home

Eliminating Tail Calls in Python Using Exceptions

I was working through Kyle Miller‘s excellent note: “Tail call recursion in Python”, and decided to experiment with variations of the techniques.

The idea is: one may want to eliminate use of the Python language call-stack in the case of a “tail calls” (a function call where the result is not used by the calling function, but instead immediately returned). Tail call elimination can both speed up programs, and cut down on the overhead of maintaining intermediate stack frames and environments that will never be used again.

The note correctly points out that Python purposely does not have a goto statement, a tool one might use to implement true tail call elimination. So Kyle Miller built up a data-structure based replacement for the call stack, which allows one to work around the stack-limit for a specific function (without changing any Python configuration, and without changing the behavior of other functions).

Of course Python does have some exotic control-flow controls: raise and yield. So I decided to build an exception based solution of our own using raise .

Please read on for how we do this, and for some examples.

Let’s see an example of the problem. Notice the (silly) self-calling function doesn’t succeed as it runs-out the call stack before finishing its calculation.

In [1]:
def recursive_example(n, d=1):
    if n <= 1:
        return d
        return recursive_example(n - 1, d + 1)

except Exception as ex:
maximum recursion depth exceeded in comparison

Of course, catching excess recursion neatly (as Python did above) is a feature. It is one way to stop possible run-away recursions.

However, if we want one particular function to exceed this limit (especially for tail calls, which should require no memory overhead!): we need to set up a framework similar to “Tail call recursion in Python”.

First we build a “thunk” to represent the evaluation of a function with all arguments specified, but that hasn’t happened yet. We implement pending calculations with the class data_algebra.pending_eval.PendingFunctionEvaluation (source here). The extra bit is: we have PendingFunctionEvaluation extend Exception, so we can use raise to jump out of our current function context.

Then, when we have what would normally be a “tail call” of the form “return f(x)“, we instead write “raise PendingFunctionEvaluation(f, x)“. The idea is: we end our current function by raising the exception, and the exception itself has the instructions for the desired next step or continuation of the calculation. An outer wrapper then iteratively evaluates any PendingFunctionEvaluations encountered. Thus any tail recursion is replaced by iteration, and we have eliminated the stack and memory use of the tail calls. It should also be possible to use a return-style notation with the PendingFunctionEvaluation wrapper, but we feel the raise notation more clearly documents intent.

An example is given here:

In [2]:
import data_algebra.pending_eval as pe

def recursive_example_ex(n, d=1):
    if n <= 1:
        return d
        # eliminate tail-call by using exception
        # instead of return recursive_example_ex(n-1, d+1)
        raise pe.PendingFunctionEvaluation(
            recursive_example_ex, n - 1, d + 1)

pe.eval_using_exceptions(recursive_example_ex, 100000)

Nota bene: the raise will throw-through any intermediate functions, so any non-tail calls (direct or indirect) to these throwing functions would have to go use the eval_using_exceptions() guard! After working some examples, we have settled that the original return-based mechanism is better. The exceptions are too hard to manage and don’t add much. For our adaptation of the return-based example, please see here.

We can also specialize the method for method-calls as we show below. The pattern we are using is a simple one: methods ending in an underbar raise exceptions in place of tail-calls (and only call the underbar versions of methods), and an outer method without an underbar performs the exception handling.

In [3]:
class C:

    def f_(self, n, d=1):
        if n <= 1:
            return d
            # Eliminate tail-call by using an exception.
            # instead of: return self.f_(n-1, d+1), use:
            raise pe.PendingFunctionEvaluation(
                self.f_, n - 1, d + 1)

    def f(self, n, d=1):
        return pe.eval_using_exceptions(self.f_, n=n, d=d)

o = C()

And there you have it: low-space exception based tail call elimination. This is one of the ideas we are considering using to remove the deeply nested object traversal limit from the upcoming Python version of rquery (the other being a non-recursive tree-visit iterator).

Categories: Computer Science Programming Tutorials

Tagged as:


Data Scientist and trainer at Win Vector LLC. One of the authors of Practical Data Science with R.

%d bloggers like this: