tail_calling.py

import functools


class TailReturn(BaseException):
    def __init__(self, f, args, kwargs):
        self.f = f
        self.args = args
        self.kwargs = kwargs


def tail_return(f, *args, **kwargs):
    raise TailReturn(f, args, kwargs)


class TailRecurse(BaseException):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs


def tail_recurse(*args, **kwargs):
    raise TailRecurse(args, kwargs)


def tail_calling(f):
    def _wrapper(*args, **kwargs):
        f_ = f
        while True:
            f_.func_globals[f_.__name__] = tail_recurse
            try:
                return f_(*args, **kwargs)
            except TailReturn as e:
                f__ = getattr(e.f, '_tail_call', e.f)
                args = e.args
                kwargs = e.kwargs
            except TailRecurse as e:
                f__ = f_
                args = e.args
                kwargs = e.kwargs
            finally:
                f_.func_globals[f_.__name__] = f_
            f_ = f__

    functools.update_wrapper(_wrapper, f)
    _wrapper._tail_call = f
    return _wrapper


@tail_calling
def bar(a):
    print 'bar', a
    if a:
        tail_return(foo, a-1)


@tail_calling
def foo(a):
    print 'foo', a
    if a:
        tail_return(bar, a-1)


@tail_calling
def fib(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fib(n-1, next, current+next)


import sys
sys.setrecursionlimit(10)
foo(100)
print fib(10000, 0)