[Python-ideas] A Continuations Compromise in Python

[John Graham]

>
> The version above avoids all that by doing what the OP suggested, and
> leaving it up to the programmer to decide what is and what is not a
> tail call. This mostly just demonstrates that this can be done with
> existing language constructs without the need for changes to the
> language.

So you think a tail-call decorator approach would work, so long as the
programmer enforces themselves that it is a tail call?  This seems
like a good compromise, if there is an implementation in the cookbook
that does this sort of simple optimization.  What might be a good
approach is to watch how popular that sort of decorator is, and if it
turns out to be more popular than is expected, perhaps putting it in
the language would sound like a better idea.  I'd rather the
trampoline that implements tail calls be written in C than in Python,
if it is heavily used.

> Of course, we still don't have a solid use case for this, which is why
> I haven't bothered to really flesh it out by catching programmer
> errors, making the API a bit cleaner, etc.
>
>> 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?
>
> Because it's a very powerful, practical approach to a very large set
> of problems. Anyone whose had more than a smattering of education in
> math will have seen recursively defined functions or sequences of some
> sort, and will intuitively try writing them - and then wonder why it
> doesn't work in non-recursive languages (yes, I've seen that
> happen). Powerful, practical and intuitive sounds pythonic to me.
> O< ascii ribbon campaign - stop html mail - www.asciiribbon.org
>

Sorry, that was a sneaky trick question.  I just wanted to make sure
we're all on the same page that recursion *CAN* be a good way to write
some things, even clearer than loops.  The problem is that there are a
whole host of things, like the graph traversal Jacob has pointed out,
that can't work with such a low stack limit.  I just find it annoying
that the theoretically 'correct' and admittedly 'elegant' solution to
a few pretty standard graph problems can't be expressed in Python
because we hit the stack.  (I'm excluding those that Jacob makes note
can't use tail calls anyway)

I also pointed out the continuation-passing-style web server, the
actor model and messages as well as the generic trampoline replacement
as all use cases.  None of these are all that wide-spread, but I guess
my point is that if there were a language feature that could help in
all of these areas, that must count for something.  There is no one
'killer' use case, but there's a good half dozen or so we've pointed
out.  Surely that puts the proposal on the same footing, at least, as
co-routines.

I also don't want to discount the performance benefit.  I know I said
above, my main thrust is towards allowing 'correct' implementations of
algorithms to run in Python without hitting the stack limit, but it is
a completely valid sub-issue if performance can noticeably increase,
as Arnauld just linked to and I'll be reading here in a moment.

Some have also mentioned that they're not fans of the actual keyword
use.  I wanted to try and split those two debates apart, whether or
not it is warranted, which I believe it is, and how it should be
implemented.  I had another proposal on the actual keyword front,
"return from", which looks like it would kind of provide some symmetry
to the 'return' and 'yield' constructs and also reads pretty
intuitively, in my opinion.

Thanks everyone for your input so far.
-JG