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:
- Stack traces help debug, TRE makes them useless
- TRE Is Not An Optimization (it creates a class of code that explodes without it)
- Guido does not subscribe to the “Recursion is the basis of all programming” idea
- 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.
About Jayson Vantuyl
I live in San Francisco, California; have an awesome son, David; and make machines do (subjectively) interesting things. I'm generally an all around handy fellow.
13 comments
Regarding the 'recursion is fundamental' point, I was just reading about this in A Discipline of Programming, by Dijkstra:
http://www.amazon.com/Discipline-Programming-Prentice-Hall-Automatic-Computation/dp/013215871X
..and he pretty convincingly argues that recursion is less fundamental than repetition. The book uses a language devised for its needs that lacks recursion, and it doesn't really suffer for that lack.
At a fundamental level, I think that recursion and repetition share the concept that they are operating on a block of code that is conceptually complete. This is really why Python blocks feel so natural for some people, why curly braces were put into C, etc. At any rate, recursion is just one method for achieve repetition, so it's kind of muddy anyway.
Fun fact. Repetition comes from the word repeat, right? Recursion comes from the word recur? Mmmmmm. I sense semantics coming on.
I think Dijkstra's point was that self-recursion wasn't necessary. TRE is useful for a number of cases that have nothing to do with self-recursion.
That said, there are some processes (parsing, notably) where self-recursion has some seriously simplifying effects. The problem is that there is more than one way to build a data-structure. Some people want to do it with the call stack. Some want to do it in a loop with an explicit data structure.
Functional people, Erlangers in particular, love to build these structures with calls, message passing, and processes. I think that the best solution for a particular problem is the one that is most easily understood. That's partly why I'm careful not to eliminate such a useful construct.
In the end, if Python had supported TRE but not standard recursion, would Guido be arguing that we shouldn't add standard recursion because code could be written with it that would break (due to the stack)? No, he wouldn't. I suspect he wouldn't because standard recursion is so obviously useful. I propose that tail-recursion without stack overflows is very useful, although perhaps not as obviously to some people.
This comment has been removed by the author.
This comment has been removed by the author.
"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."
No, I'm saying that such code should be rewritten using a loop. Most tail-recursive code can be easily rewritten using loop, and the rest takes just a little effort. And it will always become faster when rewritten as a loop: given other semantics in Python, TRE/TCO wouldn't be able to eliminate the full cost of the function call.
In effect, the proponents of TRE/TCO have it backwards. Functional languages usually don't have explicit loops, so anything "loopy" has to be written using tail recursion (or using a built-in looping operator like map). Therefore in such languages TCO is essential so that algorithms achieve their theoretical time/space characteristics.
Maybe it's time to quip "You can write Haskell in any language." :-)
[Sorry for the deleted comments, I had a bit of trouble getting a blank line after the quotation.]
Following up on your "pass EXPR" proposal, your example is not very convincing -- every cmd_foo() function would have to explicitly end with "pass self.main()", which is easy to forget. I also don't get the connection with coroutines (which Python does better with yield, see David Beazley's tutorial at http://dabeaz.com/coroutines/).
I'm also not sure I understand the semantics you propose, and how this would be backwards compatible. It seems you are proposing that "pass EXPR" means something like "return the value of EXPR, but evaluate the final call in the current frame."
Would "pass 2+2" be equivalent to "return 2+2" ?
How is that compatible with the existing "pass" semantics, which don't involve returning at all?
Since pass would be tail-recursion, there's really no point in considering an expression. The return value would just be thrown away. That said, "pass 2+2" would be the same as calling a function:
:def f():
: 2+2
It would also be just as nonsensical. It would presumably happen in the same stack-frame.
Currently:
:def f():
: pass
Is exactly equivalent to:
:def f():
: return
Both of which return None under my proposal. I readily admit that it's not the same as using pass in other contexts (classes, if-statements, except). I'm flexible. We could make a new keyword. Maybe "recurse".
The important part of the proposal isn't the syntax. I don't think that all tail recursive functions are easily written as loops. My example was not really the best, largely because I tried to keep it short. :(
The problem with using a loop largely has to do with the situation where there are really complex branching conditions. In that case, your loop becomes very ungainly.
I've recently been writing a framework that heavily jumps around in an evented RPC-like way. This sort of construct would have make my code much clearer. Right now there are combinations of loops and if-statements that I'm really not very fond of.
Here's a link to how I would be able to refactor it with the construct I proposed. Look at the idiom_nice_example file. This is about half the length and five times as clear as what I have done with generators.
In my particular case, I could have passed between the networking code, which would have been particularly nice when I had situations where I was blocked waiting on the network.
Notice how I sometimes tail-recurse and sometimes make normal function calls? The nice thing about this is that it builds a functional call stack at times when I'm actually recursing--which using generators for coroutines doesn't really do.
I think there's a use for this in Python. It may not be a type of programming that everyone does, but this sort of thing could make things like Twisted drastically different.
Or not. I'm not really going to get worked up about it. I just think that people are thinking of tail-recursion where simple loops would do. I think my example above is much cleaner than the current idiom. In the above link, take a look at the idiom_current and idiom_new files.
I think that having explicit tail-recursion is actually pretty Pythonic, has no side-effects for old code, has minimal impact at runtime, and has enough use-cases that it's harmless to add.
The only limitation I can see is that it would have to be disallowed immediately within a try or with block (perhaps it could be treated as a return statement, but you wouldn't have the benefit of avoiding stack-frame build-up, which is kind of the point).
There's a very simple way to do this in python, without adding a new keyword. You just need to explicitly return your continuation, and stick a loop around it.
def do_something():
....if some_condition:
........return [exit_a, arg1, arg2]
def loop(func, *args):
....while func is not None:
........x = func(*args)
........func, args = x[0], x[1:] # PEP 3132 cleans this up
Lots of ways to improve this, such as handling keyword arguments, or returning a value at the end. It also has one major advantage over a keyword: functions with wrappers (such as bound methods) will Just Work, rather than requiring careful bodges.
Jason, sorry for being dense, but I'm still not sure I understand the exact semantics you are proposing for 'recurse'. Is it just like 'return' except that it executes in the current stack frame? Or is there more to it?
I'm worried that you just haven't thought it through enough, or that you don't understand Python well enough at this level, or alternatively that you're in too much a hurry to explain it well.
For example, your "nice" example contains a 'recurse' statement inside a 'try' block. If an exception happens during the final call made with 'recurse', should it be handled by one of the except blocks? I don't see how to implement that without some kind of stack.
I'm also thinking that tail self-recursion can be emulated quite easily by inserting 'while True:' at the top of the function body and 'break' at the end, and replacing tail-recursive calls with assignment to the arguments and a 'continue' statement.
I agree with Adam that your state machine example can be solved quite elegantly using a small framework that lets you pass the next action to be executed as a return value.
It is just executes the function in the same stack frame. I see it as allowing not so much an optimization but as a way to right code that has much more of a state-machine feel. It's mostly useful when you have complex tear-down constraints or, in my experience, network protocol handling (where there are about three concerns to be juggled).
As I see it, a recurse can be handled the same way as a return, but with a little stack magic. My point of using the try block was to illustrate that point. I wouldn't have the recurse call actually be caught by the try block--just everything up to it.
Lots of while statements, breaks, continues, and state variables just don't read as clearly as recursing to a known next state. Sure, you CAN do it as a loop, but there are so many state variables and breaks that it's just not obvious what happens. More importantly, a forgotten return or break makes for strange behavior that you just can't get by breaking it apart into a state description.
I just see it as easier to read, less prone to screw up, in some cases generating more sane stack traces than a looped construct, and, unless I'm missing something in the internals, not really that hard to implement.
It doesn't make a big difference for a lot of people but it appears to be not that disruptive (unless you used recurse as a variable name).
"Lots of while statements, breaks, continues, and state variables just don't read as clearly as recursing to a known next state"
Let's just agree to differ here. I happen to find code written in the recursive style harder to read. You can write clean code or spaghetti in either style.
A direct conversion to a single function with a while loop would be quite bad, looking like this:
def foo():
....state = 'start'
....while True:
........if state == 'start':
............blahblah
............state = 'someother'
........elif state == 'someother':
............blahblah
............if whatever:
................state = 'start'
............else:
................state = 'more'
........elif state == 'more':
............blahblah
That quickly becomes unmanageable. However, *most* problems can be translated into a simple for-loop rather than a generic state machine, and the few that are left can be left as separate functions as in my previous comment.
If there's a use case that doesn't fit with either solution I'd like to hear it.
@Adam Olsen
There's something like that already -- I believe it's called "trampolining" in Scala.