[Python-ideas] A Continuations Compromise in Python

[Adam Olsen]

On Sun, May 3, 2009 at 1:02 AM, Steven D'Aprano <steve at pearwood.info> wrote:
> On Sun, 3 May 2009 09:22:17 am Adam Olsen wrote:
>> Premature optimization, irrelevant.
>
> It's hardly "premature" to notice that recursive code in Python is
> significantly slower and less efficient than in other languages. This
> is a known problem, or at least issue, since some people consider that
> the solution (tail-recursion optimization) is worse that the problem.

If you need a tail recursive algorithm, you need it to have O(1) space
consumption.  Constant overhead from each call is minor in comparison.
 We wouldn't even have this discussion if constant overhead was given
by itself, but we would have it if O(1) space consumption was given by
itself.


> Up until a month or so ago, I'd never heard of the term "trampoline"
> (apart from the thing you jump up and down on), and I still don't know
> what it means. Checking Wikipedia, I see that in computing, trampoline
> has *eleven* definitions. Which one do you mean?

    * Used in some LISP implementations, a trampoline is a loop that
iteratively invokes thunk-returning functions. A single trampoline is
sufficient to express all control transfers of a program; a program so
expressed is trampolined or in "trampolined style"; converting a
program to trampolined style is trampolining. Trampolined functions
can be used to implement tail recursive function calls in
stack-oriented languages.[1]

For example, something like this (but obviously with arguments and the
ability to finish looping):

def a():
    return b

def b():
    return a

def trampoline(func):
    while True:
        func = func()


> Just tossing a wild idea out there... is it conceivable to build a
> decorator that optimizes a tail-call recursive function? Then it
> becomes a matter of explicit programmer choice whether or not to do so,
> with no new syntax. You would have the choice of:

Yes, there's a lot of weird bytecode hacks out there.


> * write a function as tail-recursion because it is most expressive and
> simple algorithm, and live with the inefficiency (which as Adam points
> out, may not be a problem in practice);
>
> * manually re-write it as a for-loop, exchanging simplicity for runtime
> efficiency; or
>
> * decorate the recursive function, giving up some debugging information
> for efficiency, but keeping the simplicity of the tail-recursive form.

One unfortunate point of confusion is that giving up debugging
information is only an issue if you want to do it *by default*,
applying it to the entire language.  In contrast, any infinite loop
should use O(1) space, and therefor cannot retain any debugging
information.


-- 
Adam Olsen, aka Rhamphoryncus