Tail Recursion Elimination

I find this post by a language designer perplexing.

The fool-proof way of getting proper tail recursion is transformation of the program into a form in which all control flow is expressed in the form of function calls in tail position, including the returns. The standard target is continuation passing style. In this form, the stack-building constructions appear directly in the code. The ones that are merely administrative (bookkeeping the stack without real utility) can be eliminated at compile-time. Those administrative constructs include the ones that would make tail-calls use "stack space".

Guido refers to how every "stack frame" is heap allocated so they can't be reused. That's a design choice in the compiler's closure conversion mechanism.

Guido also refers to stack traces and exceptions, but these would be explicitly represented in the all-tail-call form of the program as well. What he means is that the language has no tail positions because there is always implicit work to be done in the language as he defines the semantics. That seems like an odd thing to brag about, but that's what he's doing.

But then I'm one of the programmers who has been permanently warped by learning about CPS, and I thoroughly rely on tail recursion being available and implemented efficiently.

I've been doing some programming with Haskell lately, and what I notice is that almost nothing I write is tail recursive. Why? Because anything that I might write that would be tail recursive uses a combinator (foldX, map, whatever) instead. Only rarely do I write a tail-recursive function, and even for those I'm probably missing some combinator somewhere that could solve my problem.

Python, of course, doesn't use "combinators", but provides loops and iterators and a number of other things that are different, but pretty much just as good. Better some ways, worse others, and that's all you can really ask for from a language since "uniformly better" isn't really on the menu.

The more I learn about functional programming, and modern functional programming in particular, the more this sounds like a gigantic argument over Python not having a compiler optimization that doesn't even make sense for Python anyhow. If you're trying to write a tail recursive function in Python, you've almost certainly passed up a "more Pythonic" solution, which is to say, a solution that is more idiomatic, runs faster, and will make sense to your fellow Python programmers. If you're writing something so painfully functional that you need Python to optimize tail-recursion, it's probably time to get out of Python altogether... it is not a functional language, and while you can dip into old-style functional ("first-order functions", "closures"), it does not and can not do new-style functional ("immutable", "monads", "continuation passing") worth a crap.

Tail recursion is the functional answer to the "private" attribute in OO languages, a language design issue that got falsely enshrined in the paradigm itself as the One True Way to program. It's not. It's a compiler hack, and you don't need it in Python, any more than Python programs come crashing down because they don't have "private" variables. (Yes, I know about double-underscores... all about them. That's why I never use them.) Just as you very nearly don't need tail recursion (directly) in Haskell.

I write fluent Python and Erlang and decent Haskell, and I miss OO in Erlang and Haskell (even a basic purely-functional variant, and yes I know about typeclasses in Haskell and various Erlang hacks, I use some myself; I know how to get it done in the native style) far more often and far more acutely than I miss tail recursion in Python.

"I'm inclined to conclude that the author doesn't know much about ... python."

http://en.wikipedia.org/wiki/Guido_van_Rossum

He responded directly to a comment I made on yesterday's blog post:

  I hate that Python doesn't have Tail-Call Optimization,
  though it does have the best stack traces of any language
  I've seen, which mostly makes up for it.

  Not being able to cleverly recurse isn't so bad when you
  never have to deal with anonymous "you tried to get the 
  head of an empty list" exceptions!

With the python installed on my phone, the g(5) example does return the correct result 0, not 4 as the author of that blog post claims. So this kills one of his arguments againt tail call eliminaton. From that example, I'm inclined to conclude that the author doesn't know much about either functional programming nor python. Given that I know who the author claims to be, I think I will just put python on my list of languages to be wary about.

And, by the way, Common Lisp does quite well treating TCO as an optional optimization.

Why did this have to show up right when I'm getting excited about trying Python?