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

[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.

 

[Jack Diederich]

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()

@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
try_instead = inspect.currentframe(1).f_locals[func.__name__]
except KeyError:
try_instead = None
if (when is None):
return func
# else, cascade
def _func(*args, **opts):
if (when(*args, **opts)):
return func(*args, **opts)
else:
return try_instead(*args, **opts)
return _func
return build

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

@multi(lambda x: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