Sunday, 26 April 2009

When celebrity programmers attack: Guido on tail calls

Guido van Rossum, the celebrity programmer responsible for the Python programming language, published a horribly misinformed blog post last week that was meant to explain why tail calls are "unpythonic" and do not deserve a place in the Python language.

Given the simplicity of the subject matter and the widespread availability of accurate information from experts like Will Clinger, it seems remarkable that anyone would still be confused about tail calls. Although the presence or absence of tail calls in Python is unimportant, this is still serious because Python is the new BASIC and, consequently, Guido is abusing his celebrity status by misguiding a huge number of young programmers. Indeed, this is very visible on the ensuing Reddit discussions where the majority of comments are factually incorrect.

Definitions

A tail call is a call that appears as the last thing a function does before it returns. In functional languages, this means the caller is returning the result of a function call (the tail call).

Tail call elimination, aka Tail Call Optimization (TCO), optimizes the stack space consumed by tail calls in order to allow the callee to be thought of by the programmer as a continuation of the caller, as if the body of the callee had been placed at the end of caller.

Dispelling the myths

Many people believe that tail calls exist as a workaround for the absence of loops in functional languages, allowing loops to be rewritten as tail recursive functions. This is a myth. In reality, many functional languages including both OCaml and F# provide loops as core language constructs and both loops and tail calls are widely used in such languages.

Many old programmers believe that tail call elimination is an academic curiosity. This is no longer true. In reality, tail call elimination has been implemented in .NET for eight years and will become a fully supported mainstream feature when Visual Studio 2010 is released next year. LLVM (used by Apple) also has full support for tail call elimination.

Some people misinterpret the "optimization" in TCO to mean that tail calls are supposed to be fast. In fact, TCO is an optimization in space to reduce memory consumption and tail calls can even be slower than non-tail calls, e.g. ILX tail calls on .NET.

Many people assume that the function called by a tail call must be statically known and some people even believe that tail calls may only call the function they are in. These are myths. In reality, all calls in tail position are tail calls and tail call elimination should handle all tail calls whether they are to statically known functions or not, i.e. given a variable containing a function you can tail call that function safe in the knowledge that the space consumption will be eliminated. Indeed, this is the essence of the revelation.

The revelation

Almost all non-functional programmers are unaware that tail calls facilitate a programming paradigm that they have never seen.

The ability to tail call to functions that are not statically known is the foundation that makes many combinators useful. This is a style of programming where functions are composed in order to create a pipeline for values to flow through. Without tail call elimination, every stage in the pipeline would leak stack space and the whole approach becomes unusably unreliable. The only workaround is tantamount to replacing the calling convention and destroys many valuable features including interoperability and the ability to dynamically load libraries.

This is the real reason why tail calls are valuable.

15 comments:

Ian Bicking said...

You mention one technique, the use of a pipeline, but that's something that can be achieved without tail call optimization (though not as seamlessly). Also, it only works for a certain kind of pipeline -- a pipeline where a function transforms the return value won't be optimizable along those lines anyway.

I've yet to see an algorithm or system that is clearer by using a technique enabled by TCO. You should be able to present an example right now using Python... obviously it will fail at a certain scale because of the lack of TCO, but if it's such a neat technique then maybe you'll win some points for things-some-people-wished-Python-could-do.

burito said...

And Tail Recursion, the actual subject of Guido's post, is a specific sub-case of Tail Calling.

DT said...

While I'd be inclined to agree that Guido may have been a bit off in his trivialization of tail calls, none of the vehement responses I've seen so far address his first (and IMHO) most important criticisms.

Namely, tail calls interfere with proper stack traces and reliant code will fail to run without it. That implies a divergence of behavior between debug and release modes where stack frames are preserved and optimized out, respectively. That's a hefty complexity price tag for an optimization, even a "paradigm enabling" one.

Flying Frog Consultancy Ltd. said...

@Ian Bicking

State machines are by far the best example of a practical application of tail calls. States are functions and changes of state are tail calls between them. For tail calls to dynamic locations, consider an extensible state machine. For concrete applications of state machines, look at lexers and parsers.

@ burito

Actually that is another myth. Read Will Clinger's paper about "proper tail recursion" that I cited from this article and you will see that the term is used to refer to the general case.

@ DT

You're absolutely right and that is a genuine trade-off.

Phil said...

On a much less substantive note, please don't credit Apple for LLVM. Though they fund a handful of current developers, they don't own it, at all. The University of Illinois (employer of the project lead, Vikram Adve, Rob Bocchino, and maybe others) does. Work on it is supported as a service to the world, with the only payment expected in return being attribution.

Paddy3118 said...

Could you refer to specific cases where GvR gets it wrong in his post with what you think should be right for Python?

You read as being maybe knowledgeable in TCO but not in Python, which detracts from your ability to persuade.

- Paddy.

Flying Frog Consultancy Ltd. said...

@ Phil

Thanks. I have corrected this mistake.


@ Paddy3118

Guido's assertion that TCO is incompatible with "nice stack traces" is wrong. Many production quality language implementations provide both tail calls and perfectly usable stack traces (e.g. OCaml, F#). Guido means that it would break backwards compatibility in Python but even that is not true: you can easily re-inject the missing info into a debug stack.

Guido presents only the myth of tail calls existing solely as a workaround for the lack of loops in functional languages. He then uses that myth to substantiate tail calls not adding much to Python.

Guido implicity assumes the myth that tail calls may only be to static locations (what he incorrectly calls "tail recursion"). In reality, that is not true and Guido's explanation of why Python's dynamic features prevent proper TCO is completely wrong.

Ultimately, I have no desire to see tail calls in Python because I would not touch that language with a forty foot pole. My only interest is in seeing the truth represented fairly and accurately, particularly to young programmers.

resistor said...
This comment has been removed by the author.
Ganesh Sittampalam said...

My general experience is that tail calls do make F# debugging substantially harder in practice (to the point that turning them off with a compiler flag is often worthwhile for debugging).

Paddy3118 said...

Having read GvR's follow up post, I can't help but cast you in the role of "academic" that he speaks of.

I like that the debate has come down to "here are the problems in implementations given so far. Submit something better for inclusion in Python or it will most likely not be added". (my interpretaion).

It would be good if the debate shifted now to how to better implement TCO in Python if its proponents are still interested.

- Paddy.

Flying Frog Consultancy Ltd. said...

@ Ganesh

I'm surprised to hear that having not had a problem myself (in fact, I only very rarely use the debugger) but you may have luck requesting better support from Don Syme at Microsoft. Is the behaviour any different from Haskell's?


@ Paddy

I will leave the discussion of whether or not tail calls belong in Python to its users.

Ganesh Sittampalam said...

I have the impression that use of tail calls in compiled F# code will be reduced, both because it's apparently quite slow on .NET and to improve debugging.

GHCi's debugger uses an execution trace rather than a stack so the issue doesn't arise.

namekuseijin said...

Excellent post.

leoboiko said...

Rule of thumb: whenever python people refuse to do something because it’s unpythonic, it’s something worth doing.

jay paul said...

Excellent post and wonderful blog, I really like this type of interesting articles keep it u.

HP - ENVY TouchSmart Sleekbook 15.6" Touch-Screen Laptop - 6GB Memory - 750GB Hard Drive - Modern Silver

HP - ELITE 15.6" Laptop - 8GB Memory - 180GB Solid State Drive