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

[Jack Diederich]

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