Implementations of Multi-Methods and Tail Call Elimination (Or how I stopped worrying and learned to love decorators)

[Stephen Thorne]

Decorators have been getting lots of air-time at the moment, but only
really the syntax. After a short discussion on irc the other night I
decided to download python2.4 from experimental and write out some
truely worthy decorator hacks.

I implemented multimethods as a warm-up, and then implemented tail
call elimination. Presented here is a brief synopsis of both, and then
the implementations.
http://thorne.id.au/users/stephen/scripts/multimethods.py
http://thorne.id.au/users/stephen/scripts/tailcall.py

Multimethods come first, because I wrote them first. I don't really
like the implemetation - I'm sure it can be improved. I especially
dislike having to use the @staticmethod decorator, and having to have
the functions in alphabetical order.

class fact(MultiMethod):
    @when(lambda x:x==0)
    @takes(int)
    @staticmethod
    def a(x):
        return 1

    @when(lambda x:x>0)
    @takes(int)
    @staticmethod
    def b(x):
        return x * fact(x-1)

    @staticmethod
    def c(x):
        raise ValueError("Invalid argument to fact()")
fact = fact()

Okay. Lots of sugar required to do it, but look! its a multimethod!
fact(10.1) raises an error, fact(0) == 1 and fact(5) == 120.

The implementation looks like this:
def takes(*arg, **kwargs):
    def _(f):
        def check(*x, **xs):
            def test(a,b):
                return b is None or isinstance(a,b)
            if len([True for (a,b) in zip(x, arg) if not test(a,b)]):
                raise NextMethodException()
            if len([True for (a,b) in kwargs.keys() if not
test(xs.get(b,None),lb)]):
                raise NextMethodException()
            return f(*x, **xs)
        return check
    return _

def when(f):
    def _(d):
        def check(x):
            if not f(x):
                raise NextMethodException()
            return d(x)
        return check
    return _

class NextMethodException(Exception):
    pass

class MultiMethod:
    def __call__(self, *arg, **kwargs):
        for i in dir(self):
            if i[0] == '_': continue
            try:
                return getattr(self, i)(*arg, **kwargs)
            except NextMethodException: pass

Okay, thats multimethods. I really don't like the implementation all
that much, I'm sure there's a better way to do it than using
exceptions like that. Suggestions?

Next is tail call elimination. This is an example usage:

from tailcall import tail, call, eliminate
import operator
@eliminate
def fact(n):
     if n == 0: return 1
     return tail(operator.mul, n, call(n-1))

fact(10000) is a really larger number by the way.

Now the implementation:
class call(object):
    def __init__(self, *x):
        self.x = x

class tail(object):
    def __init__(self, op, args=[]):
        self.op = op
        self.x = list(args)
        self.value = None
        self.parent = None

    def evaluate(self):
        top = current = self
        while not current is None:
            if len([True for elem in current.x if type(elem) in (call,
tail)]):
                for n,elem in enumerate(current.x):
                    if type(elem) is tail and elem.value:
                        elem = current.x[n] = elem.value
                    elif type(elem) == call:
                        elem = current.x[n] = self.op(*elem.x)
                    elif type(elem) == tail:
                        elem.parent = current
                        current = elem
            else:
                result = current.op(*current.x)
                if type(result) in (tail,call):
                    result.parent = current
                    current = result
                else:
                    current.value = result
                    current = current.parent
                    if current is top:
                        return result
Big ugly loop.

Before you try, it doesn't work on ackerman's. Patches accepted.

Comments? Improvements? Suggestions? Flames?

Regards,
Stephen Thorne.