6 ms·

Joe Marshall's take on Guido Van Rossum's post on tail recursion

74 points by TY 17y ago

deleted 17y ago
[deleted]
Shamiq 17y ago
AskHN: If you were to describe this to a slow, first year CS student, how would you do that?
- mkramlich 17y ago
  I tried to summarize Marshall's argument. Let me know if it makes sense, and answers your question.
mkramlich 17y ago
Well written. Though it seems the whole article could have been said more concisely as: "Guido's decision is wrong because it causes Python to use more resources than necessary in certain cases." [where resources is any one of: stack, heap, file descriptors, etc.] Which is non-ideal, in isolation, certainly. But Guido's whole post was about saying there are trade-offs, and he doesn't like the trade-off made in the other direction. (Misleading stack traces, etc.) Guido does seem to understand both sides of the argument. But ultimately it is a design decision. And he made it.
- Shamiq 17y ago
  Gotcha. Thanks.
- allertonm 17y ago
  Almost, there is one unstated additional qualification: all the above is only true if you don't believe in (or cannot use) boring old iterative loops and must implement an algorithm recursively. I found it hard to believe the article went to the extent of explaining TCO (with assembly language!) and space complexity without bothering to mention this little assumption. Since Python favours iteration over recursion I have some sympathy with GVR on this one.
  - wingo 17y ago
    The "Lambda: The Ultimate GOTO" paper shows a still-timely example of when you might want to express a state machine as mutually recursive functions. Granted, they compare to the actual GOTO, but you can't make state machines of any manageable size with iteration, either.
DarkShikari 17y ago
I understand what Guido is saying to some extent. I thought through it, and my logic seems to go as follows. 1. Compilers are not perfect. In fact, they are incredibly dumb and get things wrong all the time. Add in the fact that the compiler often does not have enough information to properly make an optimization, the output goes from "retarded" to "braindead." 2. If you make certain types of optimizations and tell people that it is fine to rely on them--even if those optimizations will not always work--performance on average will get worse. Tail recursion seems like a classic case of an optimization which, if one relied on it but the optimization failed, would have catastrophic results (a crash due to running out of stack space). In a very simple language like Scheme, relying on tail recursion is probably not a problem because of how simple such an optimization is. But with something of the complexity of python, it might not be as safe. Given the catastrophic number of regressions in compilers these days, imagine what would happen if your program was made for Python 2.5, which had tail recursion optimization, and then you updated to 2.6, and due to a change in optimization code, it failed to do tail recursion optimization on one particular function? Your program would crash. I think in general it is never safe to make the assumption that an optimizer will make a particular "good decision". Compilers and optimizers are incredibly stupid, and relying on them to be smart is a sure way to end up with all sorts of problems. Yet with something like a C compiler and loop unrolling, the consequences of such a thing can never be too bad: even in the worst case, you only lose performance. But with tail recursion, a failure could mean an actual crash.
- silentOpen 17y ago
  Garbage collected languages are good examples of places where people regularly trust complex abstractions. Compiler behavior is analogous.
  - DarkShikari 17y ago
    Which is often equally dangerous--applications which rely on garbage collection often use vastly more memory than applications that don't. A particularly analogous situation, however, would be a C application that relies on a non-guaranteed GC, i.e. one that is not guaranteed to garbage collect all objects. In such a case, you're almost sure to eventually run out of memory. This is as opposed to the Java GC, which, while potentially inefficient, will (AFAIK) GC all objects. Another analogous situation would be an application built to run on a server with 2 gigabytes of memory. The application uses 1.6 gigabytes and uses GC. A change in GC results in the program actually needing 2.4 gigabytes despite the actual internal memory usage never changing, and your servers grind to a halt.
herdrick 17y ago
What I think stood out most as mistaken about Guido's post was his conflating recursion and recursive data structures in his third point. "For practical purposes, Python-style lists (which are flexible arrays, not linked lists), and sequences in general, are much more useful to start exploring the wonderful world of programming than recursion... Most of Python's library is written with sequences and iterators as fundamental building blocks (and dictionaries, of course), not linked lists, so you'd be locking yourself out of a lot of pre-defined functionality by not using lists or sequences." Well, chained cons cells are lists, too, and recursive functions are good for much more than operating over recursive data structures. Recursion is often the only simple solution in messy real world stuff. Just last week I wrote recursive code to do one of the most real-worldy and least Computer Science-y thing imaginable: get data from a public API. I didn't see any reasonable alternative to recursion. (But since that project was, sadly, not written in a language with TCO I am stuck with a function that's going to break if our little Twitter app gets popular, at which point I'll have to do unreasonable hack.) But I admire Guido and could be misinterpreting what he said.
- dkarl 17y ago
  I think what he meant is that beginners have an easier time with iterators and list indexing than with recursive techniques. An important target group for Python is beginners and non-programmers who do some programming in support of their primary work. That's why Guido values stack traces over tail call optimization. For Python, supporting beginners and amateurs is a higher goal than writing elegant functional code. Even for problems with elegant recursive solutions, beginners seem to find it easier to cobble together a more complicated loop-based solution than to find the simple recursive one. I know that makes everyone really sad :-( and maybe the long-term solution is to fix the school curriculum to teach programming earlier and better, but for now it's reality.
  - herdrick 17y ago
    Good points. But favoring Python lists over recursion is like favoring chocolate over logging. However, I'm probably just playing gotcha here. My apologies to HN and Guido. My more important point is that recursion is good for real world stuff.
Herring 17y ago
I must be missing something. Why can't we skip the drama & add it as an option?
- Daniel_Newby 17y ago
  Several good reasons. Firstly, Python is sufficiently dynamic that you cannot easily tell at compile time which function will be called at run time: the code can call a function that rewrites the name space as a side effect. That's generally a terrible idea, but somebody is probably doing it. EDIT: Actually, it is not a bad idea. Consider an object that plugs a worker method into itself (self.worker = some_function) and then calls it on the object, like self.worker( self ). This is pretty reasonable for Python code, but it would be hard to analyze sufficiently at compile time to eliminate tail calls. Secondly, it is difficult to deal with a tail recursive call inside a try-catch block. Consider a multithreaded recursive tree manipulation algorithm that locks nodes as it descends into them, using finally blocks to guarantee lock release during exception unwind. The core algorithm can undergo tail call elimination, possibly releasing references to numerous large data structures. Yet the exception handling variables must remain on a stack, and some references to core algorithm variables may need to be retained. It is possible to do a hybrid stack elimination, but not easy. And the exception backtrace would have bizarre gaps where variables were eliminated, complicating debugging.
  - shiro 17y ago
    > you cannot easily tell at compile time which function will be called at run time: the code can call a function that rewrites the name space as a side effect. I think you don't need to know which function will be called at compile time to do tail call elimination, in general. As far as the compiler can see a function call, and can see the caller has nothing to do except returning the result of the call, then the compiler doesn't need to know which function is called (It doesn't even matter if the callee has some "wrappers" like decorators. The caller can just jump to the wrapper entry). Is there something peculiar about Python that makes it difficult? (I don't understand how your self.worker example prevents tail call elimination, but maybe that's because I don't know enough about Python.) > Secondly, it is difficult to deal with a tail recursive call inside a try-catch block. A call made inside try-catch block is not a tail call, almost by definition. The compiler may perform something clever, but from the programmers POV, it's sufficient to regard them as non-tail calls.
njharman 17y ago
So, we need tail recursion so we can prematurely optimize the space/time of our programs. Sarcasm aside I'm sure for some people, for some applications that is needed. But there are plenty of languages that do that and do that well. Why do people want every language to be "their" language. For Python I'm glad Guido is following the Zen of Python.
- Hexstream 17y ago
  I think the "premature optimization" phrase is usually used in contexts where you have to perform said optimizations by hand... (of course in some cases you'll have to consciously write a procedure as tail-recursive).
nostrademons 17y ago
He never addresses the stack trace issue. Unless someone can figure out how to preserve useful stack traces while doing TCO, I'm still firmly in Guido's camp. My boss made an observation recently. He did RoboCup when he was in college, and he found that the success of a team was almost directly correlated with the extensiveness of their debugging tools. The teams that built instrumentation to figure out exactly what their robot was "thinking" tended to kick the ass of the teams that coded very carefully and hoped it all worked. A major component of Java and Python's productivity improvement over C++ comes from the ability to easily get clean, readable stack traces whenever anything goes wrong. It's already a huge pain when your Java stack trace says <compiled code> instead of giving you a method and line number; anything that makes that the default will cause far more headaches in debuggability than it solves.
- eggnet 17y ago
  I think a debug command line switch to python would suffice. You could use the heap to store stack traces when TCO is in use.
  - deleted 17y ago
    [deleted]
  - ralph 17y ago
    Using the heap to store stack traces when TCO is in use and a "debugging" flag is set won't work. It could cause memory to be exhausted. You're effectively causing each recursion to consume memory; something TCO is trying to avoid. If the coder assumes TCO then they could have written code which will exhaust memory once the "debugging flag" starts storing stack trace information.
- wingo 17y ago
  The thing is, usually when you want the stack frames, /they are there/. They're present because they form part of the continuation of the computation. Tail calls, because they don't form part of the continuation, are usually not interesting at all in stack traces. To put it another way: a python backtrace doesn't include statements that were already executed. "Of course it doesn't, they're already executed!", you say -- well so have the tail calls! They are exactly equivalent (google for CPS transformation).

74 points by TY 17y ago

deleted 17y ago

[deleted]

Shamiq 17y ago

AskHN: If you were to describe this to a slow, first year CS student, how would you do that?

mkramlich 17y ago
I tried to summarize Marshall's argument. Let me know if it makes sense, and answers your question.

mkramlich 17y ago

Well written. Though it seems the whole article could have been said more concisely as: "Guido's decision is wrong because it causes Python to use more resources than necessary in certain cases." [where resources is any one of: stack, heap, file descriptors, etc.] Which is non-ideal, in isolation, certainly. But Guido's whole post was about saying there are trade-offs, and he doesn't like the trade-off made in the other direction. (Misleading stack traces, etc.) Guido does seem to understand both sides of the argument. But ultimately it is a design decision. And he made it.

Shamiq 17y ago
Gotcha. Thanks.
allertonm 17y ago
Almost, there is one unstated additional qualification: all the above is only true if you don't believe in (or cannot use) boring old iterative loops and must implement an algorithm recursively. I found it hard to believe the article went to the extent of explaining TCO (with assembly language!) and space complexity without bothering to mention this little assumption. Since Python favours iteration over recursion I have some sympathy with GVR on this one.
- wingo 17y ago
  The "Lambda: The Ultimate GOTO" paper shows a still-timely example of when you might want to express a state machine as mutually recursive functions. Granted, they compare to the actual GOTO, but you can't make state machines of any manageable size with iteration, either.

DarkShikari 17y ago

I understand what Guido is saying to some extent. I thought through it, and my logic seems to go as follows. 1. Compilers are not perfect. In fact, they are incredibly dumb and get things wrong all the time. Add in the fact that the compiler often does not have enough information to properly make an optimization, the output goes from "retarded" to "braindead." 2. If you make certain types of optimizations and tell people that it is fine to rely on them--even if those optimizations will not always work--performance on average will get worse. Tail recursion seems like a classic case of an optimization which, if one relied on it but the optimization failed, would have catastrophic results (a crash due to running out of stack space). In a very simple language like Scheme, relying on tail recursion is probably not a problem because of how simple such an optimization is. But with something of the complexity of python, it might not be as safe. Given the catastrophic number of regressions in compilers these days, imagine what would happen if your program was made for Python 2.5, which had tail recursion optimization, and then you updated to 2.6, and due to a change in optimization code, it failed to do tail recursion optimization on one particular function? Your program would crash. I think in general it is never safe to make the assumption that an optimizer will make a particular "good decision". Compilers and optimizers are incredibly stupid, and relying on them to be smart is a sure way to end up with all sorts of problems. Yet with something like a C compiler and loop unrolling, the consequences of such a thing can never be too bad: even in the worst case, you only lose performance. But with tail recursion, a failure could mean an actual crash.

silentOpen 17y ago
Garbage collected languages are good examples of places where people regularly trust complex abstractions. Compiler behavior is analogous.
- DarkShikari 17y ago
  Which is often equally dangerous--applications which rely on garbage collection often use vastly more memory than applications that don't. A particularly analogous situation, however, would be a C application that relies on a non-guaranteed GC, i.e. one that is not guaranteed to garbage collect all objects. In such a case, you're almost sure to eventually run out of memory. This is as opposed to the Java GC, which, while potentially inefficient, will (AFAIK) GC all objects. Another analogous situation would be an application built to run on a server with 2 gigabytes of memory. The application uses 1.6 gigabytes and uses GC. A change in GC results in the program actually needing 2.4 gigabytes despite the actual internal memory usage never changing, and your servers grind to a halt.

herdrick 17y ago

What I think stood out most as mistaken about Guido's post was his conflating recursion and recursive data structures in his third point. "For practical purposes, Python-style lists (which are flexible arrays, not linked lists), and sequences in general, are much more useful to start exploring the wonderful world of programming than recursion... Most of Python's library is written with sequences and iterators as fundamental building blocks (and dictionaries, of course), not linked lists, so you'd be locking yourself out of a lot of pre-defined functionality by not using lists or sequences." Well, chained cons cells are lists, too, and recursive functions are good for much more than operating over recursive data structures. Recursion is often the only simple solution in messy real world stuff. Just last week I wrote recursive code to do one of the most real-worldy and least Computer Science-y thing imaginable: get data from a public API. I didn't see any reasonable alternative to recursion. (But since that project was, sadly, not written in a language with TCO I am stuck with a function that's going to break if our little Twitter app gets popular, at which point I'll have to do unreasonable hack.) But I admire Guido and could be misinterpreting what he said.

dkarl 17y ago
I think what he meant is that beginners have an easier time with iterators and list indexing than with recursive techniques. An important target group for Python is beginners and non-programmers who do some programming in support of their primary work. That's why Guido values stack traces over tail call optimization. For Python, supporting beginners and amateurs is a higher goal than writing elegant functional code. Even for problems with elegant recursive solutions, beginners seem to find it easier to cobble together a more complicated loop-based solution than to find the simple recursive one. I know that makes everyone really sad :-( and maybe the long-term solution is to fix the school curriculum to teach programming earlier and better, but for now it's reality.
- herdrick 17y ago
  Good points. But favoring Python lists over recursion is like favoring chocolate over logging. However, I'm probably just playing gotcha here. My apologies to HN and Guido. My more important point is that recursion is good for real world stuff.

Herring 17y ago

I must be missing something. Why can't we skip the drama & add it as an option?

Daniel_Newby 17y ago
Several good reasons. Firstly, Python is sufficiently dynamic that you cannot easily tell at compile time which function will be called at run time: the code can call a function that rewrites the name space as a side effect. That's generally a terrible idea, but somebody is probably doing it. EDIT: Actually, it is not a bad idea. Consider an object that plugs a worker method into itself (self.worker = some_function) and then calls it on the object, like self.worker( self ). This is pretty reasonable for Python code, but it would be hard to analyze sufficiently at compile time to eliminate tail calls. Secondly, it is difficult to deal with a tail recursive call inside a try-catch block. Consider a multithreaded recursive tree manipulation algorithm that locks nodes as it descends into them, using finally blocks to guarantee lock release during exception unwind. The core algorithm can undergo tail call elimination, possibly releasing references to numerous large data structures. Yet the exception handling variables must remain on a stack, and some references to core algorithm variables may need to be retained. It is possible to do a hybrid stack elimination, but not easy. And the exception backtrace would have bizarre gaps where variables were eliminated, complicating debugging.
- shiro 17y ago
  > you cannot easily tell at compile time which function will be called at run time: the code can call a function that rewrites the name space as a side effect. I think you don't need to know which function will be called at compile time to do tail call elimination, in general. As far as the compiler can see a function call, and can see the caller has nothing to do except returning the result of the call, then the compiler doesn't need to know which function is called (It doesn't even matter if the callee has some "wrappers" like decorators. The caller can just jump to the wrapper entry). Is there something peculiar about Python that makes it difficult? (I don't understand how your self.worker example prevents tail call elimination, but maybe that's because I don't know enough about Python.) > Secondly, it is difficult to deal with a tail recursive call inside a try-catch block. A call made inside try-catch block is not a tail call, almost by definition. The compiler may perform something clever, but from the programmers POV, it's sufficient to regard them as non-tail calls.

njharman 17y ago

So, we need tail recursion so we can prematurely optimize the space/time of our programs. Sarcasm aside I'm sure for some people, for some applications that is needed. But there are plenty of languages that do that and do that well. Why do people want every language to be "their" language. For Python I'm glad Guido is following the Zen of Python.

Hexstream 17y ago
I think the "premature optimization" phrase is usually used in contexts where you have to perform said optimizations by hand... (of course in some cases you'll have to consciously write a procedure as tail-recursive).

nostrademons 17y ago

He never addresses the stack trace issue. Unless someone can figure out how to preserve useful stack traces while doing TCO, I'm still firmly in Guido's camp. My boss made an observation recently. He did RoboCup when he was in college, and he found that the success of a team was almost directly correlated with the extensiveness of their debugging tools. The teams that built instrumentation to figure out exactly what their robot was "thinking" tended to kick the ass of the teams that coded very carefully and hoped it all worked. A major component of Java and Python's productivity improvement over C++ comes from the ability to easily get clean, readable stack traces whenever anything goes wrong. It's already a huge pain when your Java stack trace says <compiled code> instead of giving you a method and line number; anything that makes that the default will cause far more headaches in debuggability than it solves.

eggnet 17y ago
I think a debug command line switch to python would suffice. You could use the heap to store stack traces when TCO is in use.
- deleted 17y ago
  [deleted]
- ralph 17y ago
  Using the heap to store stack traces when TCO is in use and a "debugging" flag is set won't work. It could cause memory to be exhausted. You're effectively causing each recursion to consume memory; something TCO is trying to avoid. If the coder assumes TCO then they could have written code which will exhaust memory once the "debugging flag" starts storing stack trace information.
wingo 17y ago
The thing is, usually when you want the stack frames, /they are there/. They're present because they form part of the continuation of the computation. Tail calls, because they don't form part of the continuation, are usually not interesting at all in stack traces. To put it another way: a python backtrace doesn't include statements that were already executed. "Of course it doesn't, they're already executed!", you say -- well so have the tail calls! They are exactly equivalent (google for CPS transformation).