[Python-ideas] A Continuations Compromise in Python

[John Graham]

On Tue, May 5, 2009 at 7:18 AM, MRAB <google at mrabarnett.plus.com> wrote:
> Jacob Holm wrote:
>>
>> Aahz wrote:
>>>
>>> On Mon, May 04, 2009, John Graham wrote:
>>>>
>>>> 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?
>>>
>>> Who has said that recursive algorithms are "generally" frowned upon?
>>> What people have said is that Python is not focused on recursive
>>> algorithms the way TCO-languages are, but that is also true of e.g.
>>> functional programming style.
>>
>> An unfortunate result of "Python is not focused on recursive algorithms"
>> is that such algorithms become much harder to work with.  Yes, there is
>> always a way to write it without recursion, and often the non-recursive
>> version will run faster because of the slow function calls.  However, the
>> non-recursive version is usually much less readable/maintainable, which is
>> really a shame in a language designed for readability.
>>
>>
>>> Recursive algorithms are natural for
>>> nested datastructures, but you will almost never find a nested
>>> datastructure that is a thousand levels deep.
>>
>> Balanced trees are not the only data structures in the world.
>>
>> Depth-first traversal of a graph is most easily expressed using recursion,
>> and graphs with thousands (or even millions) of vertices are not uncommon.
>>
>> Also, there are many other types of problems where a recursive algorithm
>> is the most natural.  Most discrete optimization problems fall in this
>> category.  For toy examples, look at almost any type of puzzle-solving.
>>
>>
>> The proposed "continue <functioncall>" feature doesn't help these cases,
>> because they don't use tail calls.  For that you need something like
>> Stackless.  I'm -1 on the spelling anyway because it would kill the idea of
>> using "continue <expression>" in a for-loop as a way to send the value of
>> <expression> to the generator being iterated over.
>>
>> I'm +0 on the idea of using syntax to explicitly request tail call
>> optimization.
>>
>> I'm +1 on doing implicit tail-call optimization, even if it does make the
>> stack trace less useful.
>>
> Could Python implement tail recursion optimisation and somehow 'fake'
> the stack trace? I'm thinking that the stack trace would contain a
> repeating pattern of calls, so it would store and show the pattern of
> calls and the count of how many times the sequence was repeated.

Plain recursive tail calls might be faked by just saying "You called
this a whole bunch".  But message passing sorts of tail calls, where
you are calling other methods and functions, could really use a stack
trace.  The way this sort of thing is dealt with in other languages is
to put the stack trace in one part of a 'history' object, and then the
tail-call history in another.  They show up the same way, but the
stack part of the history is not limited (except to the size of the
stack) while the tail call part is put on a large circular buffer.
You can potentially lose information in the trace this way too, but
it's a pragmatic solution and it's as least as 'pretty' as setting the
stack limit so low anyway.