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

Discussion in 'Python' started by Stephen Thorne, Aug 29, 2004.

  1. 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.
    Stephen Thorne, Aug 29, 2004
    #1
    1. Advertising

  2. Re: Implementations of Multi-Methods and Tail Call Elimination (Orhow I stopped worrying and learned to love decorators)

    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
    Jack Diederich, Aug 30, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Robert Kern
    Replies:
    6
    Views:
    315
    Duncan Booth
    Oct 20, 2003
  2. Frederick Gotham

    Worrying Prevalence of K++ Compilers

    Frederick Gotham, Nov 8, 2006, in forum: C++
    Replies:
    9
    Views:
    345
    werasm
    Nov 9, 2006
  3. mano
    Replies:
    3
    Views:
    1,922
    steve.kim
    Jan 31, 2007
  4. Hrvoje Blazevic

    tail call elimination

    Hrvoje Blazevic, Jan 27, 2008, in forum: Ruby
    Replies:
    2
    Views:
    109
    Paul Brannan
    Feb 21, 2008
  5. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    295
    Robert Klemme
    Apr 20, 2011
Loading...

Share This Page