Tail call optimization

tailcal.py

#
# By Nimrod Aviram and Eyal Lotem
#

import functools

class TailCallFunc(object):
    def __init__(self, func):
        self.func = func

    def __call__(self, *args, **kwargs):
        res = self.func(*args, **kwargs)
        while True:
            if not isinstance(res, tailCall):
                return res
            res = res.func(*res.args, **res.kwargs)

    def tailCall(self, *args, **kwargs):
        return self.func(*args, **kwargs)

    def __get__(self, obj, type):
	return functools.partial(self, obj)

class tailCall(object):
    def __init__(self, func):
        self.alreadyCalled = False
        if isinstance(func, TailCallFunc):
            self.func = func.func
        else:
            self.func = func

    def __call__(self, *args, **kwargs):
        if self.alreadyCalled:
            raise
        self.args = args
        self.kwargs = kwargs
        self.alreadyCalled = True
        return self

@TailCallFunc
def f(x):
    if x == 0:
        return 'qwe'
    return tailCall(f)(x - 1)

assert f(10010) == 'qwe'

class Maybe(object): 
    def __init__(self, *value):
        if value:
            [self.value] = value
            self.isJust = True
        else:
            self.isJust = False

    @classmethod
    def wrap(cls, *args, **kw):
        return cls(*args, **kw)

    @TailCallFunc
    def bind(self, f):
        if self.isJust:
            return tailCall(f)(self.value)
        return self

assert Maybe(10010).bind(f) == 'qwe'

# not sure if this ever worked...

@TailCallFunc
def liftM(f, x):
    wrap = type(x).wrap
    return tailCall(x.bind)(lambda unwrapped: wrap(f(unwrapped)))