Re: [Python-ideas] A Continuations Compromise in Python
On Mon, May 4, 2009 at 6:16 PM, Mike Meyer <mwm@mired.org> wrote:
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?
On Mon, May 04, 2009, John Graham wrote:
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. Recursive algorithms are natural for nested datastructures, but you will almost never find a nested datastructure that is a thousand levels deep. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ "It is easier to optimize correct code than to correct optimized code." --Bill Harlan
Aahz wrote:
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.
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. - Jacob
Jacob Holm wrote:
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.
On Tue, May 5, 2009 at 7:18 AM, MRAB <google@mrabarnett.plus.com> wrote:
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.
On Mon, May 4, 2009 at 6:26 PM, John Graham <john.a.graham@gmail.com> wrote:
There's many forms of recursion that do not involve unbounded recursion. Consider a call to len() that calls len() on another object. -- Adam Olsen, aka Rhamphoryncus
On Mon, May 04, 2009, John Graham wrote:
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. Recursive algorithms are natural for nested datastructures, but you will almost never find a nested datastructure that is a thousand levels deep. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ "It is easier to optimize correct code than to correct optimized code." --Bill Harlan
Aahz wrote:
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.
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. - Jacob
Jacob Holm wrote:
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.
On Tue, May 5, 2009 at 7:18 AM, MRAB <google@mrabarnett.plus.com> wrote:
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.
On Mon, May 4, 2009 at 6:26 PM, John Graham <john.a.graham@gmail.com> wrote:
There's many forms of recursion that do not involve unbounded recursion. Consider a call to len() that calls len() on another object. -- Adam Olsen, aka Rhamphoryncus
participants (6)
-
Aahz -
Adam Olsen -
Greg Ewing -
Jacob Holm -
John Graham -
MRAB