[Python-ideas] A Continuations Compromise in Python

[Steven D'Aprano]

On Sun, 3 May 2009 09:22:17 am Adam Olsen wrote:
> On Sat, May 2, 2009 at 2:27 PM, John Graham <john.a.graham at gmail.com> 
wrote:
> > Hi all
> >
> > It was suggested I post this idea to the python-ideas list.  I
> > apologize in advance for its length, I tried to be thorough :)
> >
> > Recently there's been some debate over the Tail-Call-Optimization
> > and its use in Python.  Some advocates coming from languages that
> > support this optimization say that it makes recursive code far more
> > efficient,
>
> 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.


> > and indeed allows some things to happen that could not otherwise
> > occur without running out of stack space.
>
> Use a trampoline.

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?


> It's the same thing you propose, only it uses 
> existing syntax.  It's got a few rough edges, but they're quite
> manageable, and in no way justify the vast bikeshed this issue has
> garnered.

For the record, I find the OP's idea dubious. I don't like having yet 
another way of spelling "exit this function and return this result": 
return, yield, and now (proposed) continue. So a *very* tentative -0 on 
the suggestion. Maybe +0.

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:

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

I don't know whether such a thing is even possible, let alone how to go 
about doing such a thing, but if it did exist, I'd use it.



-- 
Steven D'Aprano