[Python-ideas] A Continuations Compromise in Python

[John Graham]

On Mon, May 4, 2009 at 6:16 PM, Mike Meyer <mwm at mired.org> wrote:
> On Sun, 3 May 2009 23:24:44 -0600
> Adam Olsen <rhamph at gmail.com> wrote:
>
>> On Sun, May 3, 2009 at 4:13 PM, Mike Meyer <mwm at mired.org> wrote:
>> > That looks every bit as significant as the change you get from a list
>> > comprehension to me - and these are simplified by ignoring keyword
>> > args.
>>
>> Yet you only need to do that once.
>
> Well, once every time you call a callable that needs a
> trampoline. That would include any recursive calls that weren't
> properly tail recursive. That could get ugly pretty fast.
>
>> At best (with a significant userbase) it'd go in the stdlib.
>> Otherwise you can put it in the cookbook.
>
> That still applies, though. I think a decorator could do the job
> (only the usage example has been tested):
>
>    class trampoline(object):
>        """Provides a trampoline for functions that need one.
>
>        Such functions *must* return a triplet of (nextfunc, args,
>        kwdargs) to pass control to nextfunc (which must be also be a
>        trampoline'd function with the given args & kwdargs; or a pair
>        (None, results) to return to their caller.
>
>        Usage:
>        @trampoline
>        def tramploop(count):
>           if count:
>              print count
>              return tramploop, (count - 1,), {}
>           else:
>              return None, None
>
>        @trampoline
>        def ack(m, n):
>           if m == 0:
>              return None, n + 1
>           elif n == 0:
>              return ack, (m - 1, 1), {}
>           else:
>              return ack, (m - 1, ack(m, n - 1)), {}
>
>        """
>
>        def __init__(self, func):
>            self.func = func
>
>        def __call__(self, *args, **kwds):
>            next = self
>            while True:
>                res = next.func(*args, **kwds)
>                if not res[0]:
>                    return res[1]
>                next, args, kwds = res
>
> Assuming this (or more likely something like it) works, there's not
> much use for any way to make the system do TCO for you, other than
> performance. And IIRC, that wasn't the OP's issue.
>
>      <mike
> --
> Mike Meyer <mwm at mired.org>              http://www.mired.org/consulting.html
> Independent Network/Unix/Perforce consultant, email for more information.
>
> O< ascii ribbon campaign - stop html mail - www.asciiribbon.org
>

As I recall, a few people have advocated a TCO decorator, which I
imagine would look a lot like your trampoline decorator, and it
usually falls apart in corner cases.  I don't have any examples with
me though.  I do have a question though, if recursive algorithms are
generally frowned upon (and I'd say, without TCO, anything too complex
hits the stack quick) why is recursion even supported?  What is the
'Pythonic' use of recursion?