On Tail Recursion Elimination

There was a bit of a controversial post on Guido van Rossum's blog that I thought deserved a little comment.

To sum up Guido's argument, he doesn't feel like implementing Tail Recursion Elimination (henceforth referred to as TRE) in Python because:

1. Stack traces help debug, TRE makes them useless
2. TRE Is Not An Optimization (it creates a class of code that explodes without it)
3. Guido does not subscribe to the "Recursion is the basis of all programming" idea
4. Due to Python's highly dynamic namespaces, it's very nontrivial to know if a call is a recursion.

The funny thing is that, even though I am a big supporter of TRE, I actually agree with all of these points.  Taking them in turn:

Stack traces are critical to debugging code.  Ruby and Erlang both started out with uglier stack traces than they have today.  They were adjusted because they are important.  Similarly, the most difficult Python frameworks have always been that way due to their affect on stack traces.  Zope and Twisted--I mean you.  Zope would create absolutely titanic stack traces.  Twisted, on the other hand, creates virtually no useful stack traces (as a consequence of the deferred model).

While I find this to be telling, I would caution against considering this in the context of TRE.  Why?  Simple.  Some styles of programming don't generate good stack traces.  As an example, consider the construct of a loop.  Loops don't generate stack traces.  When code explodes in a loop, you have no idea what state led-up to that explosion.  Does that mean that loops are "bad"?  No.  It simply means that what we want is not a stack-trace, but rather information about what led up to the failure.

For some classes of code, stack-traces provide that fairly economically.  The catch is that other types of code don't benefit from them at all.  Guido's statement that you can trivially rewrite any TRE function as a loop is very practical, but it actually detracts from his point.  It's pretty clear that the type of code that benefits from tail recursion doesn't benefit from stack-traces.  This means that effectively he's deciding that Python just doesn't tailor to a certain type of code.  I'm mildly opposed to this and I think there's a good case for a type of TRE in Python.

Taking the second point, Guido has this right.  The fact that there is code that would explode without TRE is a good reason not to just add it to the language.  That said, it doesn't mean that we shouldn't do it.  In fact, it is largely an argument to do so in the main Python runtime.  If anything, fragmenting the Python codebase is negative.  However, TRE tailors to a certain type of code, and the fragmenting effect of that reality means that he is really choosing between fragmenting the Python codebase and driving people to other languages that handle the use-case better.  He might be okay with that, but I don't really believe it to be necessary.

Taking the third point, talking about the "basis of all programming" is a little tough.  From a very high level, design a language without recursion.  What's left that defines programming?  In all seriousness, I think that the statement that "recursion" is the basis for all programming has a strong case assuming that you mean "recursion" in terms of the function call (or subroutine, or whatever you call it).

Without functions, you don't really have anything but a long list of instructions.  All control statements are pretty much functions or branches.  Branches without the concept of subroutine are effectively goto statements, which have always been as controversial as they can be useful.  The point being that TRE allows you to turn one of the most fundamental constructs of programming and use it in a way that increases its utility.  If recursion isn't the basis of all programming, it's still pretty fundamental.

Addressing the final point, I recall part of the Zen of Python, "Explicit is better than implicit."  The statement that Python has difficulty (at compile time) determining whether a call is recursion is a good one.  There's a really simple solution to this.  Add a keyword to make tail-recursion explicit.  Perhaps we could propose abusing the pass keyword.  Basically, where pass is used now, consider it to mean "pass None".  The idea is that it is either passed a function call or None to indicate tail recursion.  The nice bit of magic here is that it reuses an existing keyword compatibly, clearly indicates what's happening, easily translates to bytecode, and works really well for TRE's most powerful use-case (coroutines).

So, as an example, consider the following code:

class cli:

  def start(self):

    print "Welcome to the CLI"

    pass self.loop()

  def main(self):

    print_prompt()

    cmd,args = parse_line()

    cmd = getattr(self,'cmd_' + cmd,None)

    if cmd is not None and callable(cmd):

      pass cmd(*args)

    else:

      print "Command not found"

    pass self.start()

  def cmd_help(self):

    ...

    pass self.main()

...

The above code may seem slightly convoluted, but it's actually interesting because it tackles one use-case that Python is bad at.  Admittedly, the above could have been factored as a loop, but the more steps you insert into the process, the uglier it gets.  What is the purpose of continually having to implement some sort of mini-scheduler in a  loop?  Why have all this convoluted logic that has to handle a random series of states and detect an "end-state".  This is just simpler, and more importantly "Beautiful is better than ugly."

Critics might say that loops give you an easier understanding of the top-level flow of the program.  I would contend that any problem that needs the above technique would instead result in a loop so complex that it would generally serve to reduce the understanding of the problem--replete with various ifs, returns, whiles, and breaks.

In assembly, C, or any number of other systems, this would have been implemented with goto statements.  The problem with goto statements is that they very easily obscure the boundaries of single bits of code and can poorly document the intent of the goto.  This is a nice abstraction that allows the use of goto-like functionality without losing information about what's supposed to be going on.  There comes a point where the above would get factored into a general state machine implementation, but it's not really necessary.

Another thing to notice about the above is that it gives you a really good point for debugging.  Any Python implementation of the above type of problem would not have stack-traces to debug.  However, the pass statement gives you a place to track behavior.  In a debugger it's pretty clear what's going on.  At the beginning of each iteration, the function arguments clearly define the state of execution.

This is something that is much more useful that implementing this with a loop.  With a loop, the state is invisibly contained in the current binding namespace.  Temporary values easily leak.  There's not a clear point where the state of the iteration is distilled.  This is why people want TRE.

There are just a lot of situations where people would benefit from greater control over the constructs of flow control.  Right now we've already abrogated the model of nested-call-return with generators.  Most control structures that are difficult in Python could benefit from further disentangling the assumptions of function calls.

Someday, I would love to see the work that was started with generators end with easy coroutines, promises / lazy evaluation, message passing, and smarter code replacement.  Every language has idioms for what a recursion or evaluation means.  We have the opportunity to make this handling explicit, and I suspect that we would benefit from it.