Joe Marshall's take on Guido Van Rossum's post on tail recursion
funcall.blogspot.com
funcall.blogspot.com
But I admire Guido and could be misinterpreting what he said.
My more important point is that recursion is good for real world stuff.
No, no, it's not at all, not when you approach it from Guido's point of view. To him, the crucial question is, "What's the right way for beginners to process data?" Python and its built-in data structures support iteration and list indexing because that's how beginners do it. Python does not support tail calls because Guido thinks it's a mistake to teach recursion to beginners.
I think everyone is misunderstanding Guido's point because they just can't imagine anyone taking his point of view, so they imagine him saying something else. Joe Marshall even called Guido's main points (which he correctly identified, and then ungraciously caricatured) "a sideshow" and said the "true argument" is about the power of recursion. Sorry, Guido doesn't care about the power of recursion, because it isn't valuable to his target programmers, the programmers he wants to serve. He really thinks tail call support would be a very minor feature in Python because it's not important whether you can program in Python that way. He thinks complete stack trace information is very important because it makes things easy and transparent for beginners. That's what's important to Guido and, I would argue, to most Python programmers. When it comes to the future of Python, that's what matters, and Joe Marshall is the sideshow.
I agree that Python's emphasis on beginner-friendliness was the smart choice and led, ironically, to its current dominance in numerical computation.
In practice: you can easily add pre-tail-call tracing, you have the option of starting a debugging REPL on error, using iterators is very idiomatic, it makes implementing coroutines and fully-functional closures easier, etc.
I happen to think the most significant benefit of TCO is being able to set up "looping" tail calls between multiple functions, but that's just me.
* Somewhere between Python and Javascript, specifically.
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.
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).
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.
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.
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.
If some_function calls a bunch of random functions, it is very, very hard to tell if those calls will execute "self.worker = some_other_function" as a side effect. This happens because everything in Python can be changed on the fly; languages with true constants don't have this problem.
> A call made inside try-catch block is not a tail call, almost by definition.
Right, and since Python makes wide use of exceptions, true tail call elimination is often impossible. The best you can get is partial elimination, and it is a PITA.
I still don't see, since changing self.worker at runtime does not matter at all. Whether a call is at tail position or not can be determined only looking at the caller code. If self.worker(self) appear at the tail position, compiler can generate code sequence something like this:
discard caller's frame.
push the value of 'self' as argument.
retrieve value of 'worker' attribute.
jump to the method pointed by the value.
The only construct I can think of so far that prevents compile-time tail call elimination is first class macros, since with them the compiler cannot determine a call is tail position or not. It is the extreme end of dynamism. But even with them, you can do runtime tail call elimination. It might not be as efficient, though.
> Right, and since Python makes wide use of exceptions, true tail call elimination is often impossible.
Wait... are we talking about the same thing?
What I mean by tail call elimination is converting tail calls to jumps. It has nothing to do with non tail calls, hence wide use of try-catch block has nothing to do with "true tail call elimination".
What you can argue is something like: because try-catch block is so abundant in Python code that tail call elimination won't add much value to typical Python programs. I don't know if it's true or not, but it's plausible. (E.g. C++ has to run destructors when stack-allocated objects goes out of scope, which makes most of calls non-tail calls, hence effects of tail call elimination will be limited.)
Questions about whether it'd be better if Python supported tail-call elimination, type inference, macros, etc. need to consider not just the theoretical power advantage, but the extent they would tend to fragment the existing community, make existing code harder to use/maintain, etc.
FWIW, Lua (http://lua.org) is stylistically quite similar to Python, and has an equally strong focus on keeping things simple, but approaches it differently. Its designers kept the core language extremely small, yet easily extensible in Lua or C. It's very interesting to compare and contrast its design with Python's. (It's also a great language in its own right, and it has TCO.)
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.
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.
TCO is not very hard to implement in a compiler/interpreter if considered from the beginning. Unless your compiler/interpreter was designed very poorly, it probably isn't very hard to implement later, either.
Given this, it doesn't really make sense to not trust TCO because it's somehow black magic. There may be other arguments against wanting TCO in your language of choice ("I really need backtraces all the time and I can't sacrifice simple, provable interpreter optimizations!") but reliability can't be it.
I wouldn't say it's black magic at all--it's just that from my experience you can rarely even trust compilers with the most basic of things, let alone black magic.
I'd prefer GC over memory leaks...
A "non-leaky" optimization would be one where the compiler can always optimize away a specific coding pattern. Though, to some, tail-call elimination is dark magic, in reality the optimization can always be performed. As alluded to in the article, all that's necessary is to replace the existing stack frame when returning a value.
And once you make an optimization non-leaky, it cannot ever become leaky again in any particular situation whatsoever, or it could break existing programs.
Proper tail recursion is much more fundamental property of language. Whether you have a guaranteed proper tail recursion or not affects the behavior of the program in terms of complexity (as discussed in Joe's article). Consequently it affects your choice of algorithms and coding styles. An example is that you start feeling very natural to represent state machine in terms of function calls (function = state, tail call = transition).
I don't claim that proper tail recursion is the only correct answer. It is a design choice. But if you opt out, you'd better understand what you're trading.
That said, I agree with you that optional TCO which you can't rely on isn't very useful. The proper tail recursive language, like Scheme, defines exactly what are tail calls so programmers can rely on it.
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.
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.