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

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

Stephen Thorne
Guest
Posts: n/a

 08-29-2004
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
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/sc...ultimethods.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==0)
@takes(int)
@staticmethod
def a(x):
return 1

@when(lambda 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.

Regards,
Stephen Thorne.

Jack Diederich
Guest
Posts: n/a

 08-29-2004
On Sun, Aug 29, 2004 at 03:59:17PM -0700, Stephen Thorne wrote:
> 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==0)
> @takes(int)
> @staticmethod
> def a(x):
> return 1
>
> @when(lambda 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()

@takes seems like an extra version of @where

> 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?

This screams for a stack frame hack, so here it is.

import inspect
def multi(when=None):
def build(func):
try:
# get the existing version of our func to fall back on
except KeyError:
if (when is None):
return func
def _func(*args, **opts):
if (when(*args, **opts)):
return func(*args, **opts)
else:
return _func
return build

@multi(lambda x == 0)
def fact(x):
return 1

@multi(lambda x > 0)
def fact(x):
return x * fact(x-1)

print fact(0)
print fact(100)

Just because it is possible doesn't make a good idea *wink*,

-Jack