The Skeptical Methodologist

Software, Rants and Philosophy

Resolving the Python TCO Problem

The BDFL of Python has recently stirred up a hornets nest when he fully explained why the so-called ‘tail call optimization’ will never be in Python.  Lovers of functional languages have responded, and I think we’re all the wiser for both of their points of view.

Guido’s post mentions the accusation that Python is becoming the “Basic of the Future”, which the author responds might be more of a badge of honor than a derogatory statement.  This is because Python was originally conceived as a teaching language, and you can see that much of what Guido does in design work is to strive to make Python as easy to learn and understand as possible.  His biggest overall gripe about TCO is that it screws up stack traces, and it is only useful in a handful of circumstances anyway.

In a way, this can be expected.  After all, part of the Zen of Python is that “Explicit is better than Implicit”.  Behind the scenes optimizations are a good example of the implicit things the BDFL is looking to prevent.

So lets make TCO no longer an optimization.  Let’s just simply talk about tail calls, and the optimization is simply a side effect.  Much of what Joe Marshall talks about refers to the power of tail calls, mainly via continuation passing.  It makes certain ideas very easy to implement.  Perhaps the reason Guido believes there is little use for continuation-passing style constructs which Joe brings up is because it is a newer idea, and quite frequently, new ideas are completely useless until we find a use for them.  And then they explode into a world in which we can’t remember living without them.

I’d propose a change to the Python language that makes tail calls explicit, backwards compatible and, in my opinion, Pythonic.  That is to say, in the same pattern that other interesting function/control flow mechanisms have been implemented.  Check out the following example, which I’m not going to give as anything fancy, because it’s pretty obvious and simple what I’m after.  Let’s compare a normal recursive function call in our extended Python to a tail call version.

def func(recursiveFunc):

return recursiveFunc()

That’s our current vanilla implementation.  Nothing really to see here, except that it’s inefficient yet easy to debug.  Now the tail call version:

def func(recursiveFunc):

continue recursiveFunc()

The use of continuations is very explicit, which is in the Zen of Python.  But how else is it really Pythonic?  Compare a tail call function to a Python generator, which were added to the language more recently:

def sillyIterator(lst):

for elem in lst:

yield elem

The yield keyword was introduced for generators (and extended to allow for co-routines) as a different mechanism of returning a value from a function with interesting control flow.  The language identifies functions that yield values instead of returning them and behind the scenes turns those into generators.  Is it implicit?  Not really -  you can see from the code itself that it’s a generator.  It yields.  Likewise, the new use of the ‘continue’ keyword would also signify the function is using a ‘continuation’.

Does this work?  Can we ‘abuse’ (if you want to call it that!) the ‘continue’ keyword like this?  I’m no expert, but in the current Python standard, I believe continue, like break, is meant to be and is always used as a standalone statement in loops.  It takes no ‘arguments’, and thus, if we added it to the language in the way I’m proposing, it’d be easy for the parser to tell when we’re continuing in a loop versus continuing from a function (a continuation).  If we’re in a loop and we simply continue, we go back to the top of the loop.  If we continue with an argument, then we’re using a function as a continuation.

Can there be ambiguous uses?  First of all, using recursion in a loop probably doesn’t happen as much as you think because people who think recursively hate loops and people who use loops hate recursion (I keed).  But secondly, no, there is no ambiguity.  A continuation only makes sense with a function as its argument.  There can be no ‘continue’ statement in a recursive call that passes nothing – that doesn’t make any sense.  There is a clear deliniation between using continue to return to the top of your loop and using it for continuation passing.  If you want a recursive call to simply return nothing, then use a return statment with no arguments.  This mixing of continues and returns parallels with how generators mix yields with returns.

What if I write a loop and I mean to call a function as a continuation but I leave the function off?  Then, yes, this will use the loop-style continue.  But it’s a parse error anyway, and if you weren’t in a loop, the function wouldn’t even make sense.  The opposite, somehow accidentally adding an argument to a continue statement you meant to use as a loop-style continue would also be an error, although it would be easier to catch since only a few things would be able to be used as a continuation (any fully evaluated callables, to be specific).  We can’t design all potential bugs out of the language, but the potential for ‘continue’ accidents happening is pretty small, and mixing intricate loop logic (continue is pretty rare as it is and only shows up in more complex loops) with intricate functional logic (continuation passing, like any other tool, has specific uses) either means you’re in over your head and doing it wrong anyway, or potentially awesome, in which case you won’t make any errors.

Is this really abuse?  I’d argue no.  Both the concept and the name flow from the word – continue obviously looking very similar to ‘continuations’, which is what we’re doing, and the idea of ‘continuing’ on to a different function also makes intuitive sense rather than returning the value of that function evaluated, signified with the ‘return’ statement.  More importantly, it does not differ that much from the way the keyword is already used.

Just as many claim most recursive calls can be turned into loops, it also seems altogether poetically just that loops and recursion have other similar concepts.  In this case, continuing in a loop means return to the top of the loop, continuing in recursion means go back ‘up’ to the next function.  If you were to use a ‘trampoline’ similar to what Guido has suggested in his post, continue would practically mean the same thing and have the same effect.  Putting the continue statement in a loop that simulates a trampoline does the same thing as a continuation in a function – we pass control onto the next function in the line in either case.  Kinda.  If you squint at it funny.

Just as some have claimed continuations are the ‘goto’ of functional languages, it’s ironic that the continue statement started out its own life as a replacement for ‘goto’ in loops.  They’re parallel constructs and its altogether too fitting to just use the same keyword to do both.

Python is a learning language, but learning procedural code is not where we’re headed.  In the future, students and amateurs are going to need to learn functional style as well as imperative style, and as such, Python should  be their introduction to both.  It already handles the paradigm quite well.  The ‘self’ argument to methods is quite functional (in my own opinion), as it allows methods to be passed around like first class objects without being tied to an object.  Generator expressions too are rather functional, yet these things are easy to learn and very Pythonic.  Why not continuations too?  But explicit – it’s better than implicit, and in a style that already fits into the way Python has expanded in the past towards different ways of returning from functions.  With the keyword, it suddenly becomes ok to optimize behind the scenes because the user knows its a tail recursive call.  The parser too can annotate information in the callstack to make it easier to debug.  After all, the yield statement makes debugging slightly more difficult, but is still in.

Don’t make it an optimization, make it a feature, and settle this whole debate.

About these ads

April 29, 2009 - Posted by | Uncategorized

25 Comments »

  1. While I personally would like to see some kind of TCO in Python as well, it really isn’t that big a deal. Problems that are easier using recursion WITHOUT requiring something to happen after the recursive call just aren’t that common.

    Comment by Jason Baker | April 29, 2009 | Reply

  2. I like the idea of allowing tail-call optimization to be explicitly invoked, but wouldn’t it be much simpler to use a new keyword rather than overloading an existing one? Then you could delete the second half of this post and give the TCO opponents one less thing to protest.

    Comment by Drew Frank | April 29, 2009 | Reply

  3. I agree that this is the most pythonic solution I’ve seen so far. Brilliant idea.

    Re: Jason, see continuation passing style.

    Comment by Sean McQuillan | April 29, 2009 | Reply

  4. Excellent idea !

    The overloading of the continue key-word is not perfect but it seems good enough.

    Please write a PEP ! (the blog post seems a good starting point)

    Comment by Lionel Barret | April 30, 2009 | Reply

  5. Great idea. Somehow the whole debate reminded me of yield, but I couldn’t put my finger on why.

    Comment by Ryan Fugger | April 30, 2009 | Reply

  6. copied from reddit :

    > PEP! PEP! PEP!

    First, it needs to be posted on python-ideas.

    Then if interest is reached (and possibly something that kinda looks like a consensus), it can be proposed to python-dev on the path to become an actual PEP.

    If it’s made straight into a PEP and posted to python-dev, it’s going to be blasted hard.

    Comment by Lionel Barret | April 30, 2009 | Reply

  7. > First, it needs to be posted on python-ideas.

    Or maybe someone who really wants this can just go ahead and write a patch for CPython. With working code for people to play with, the rest will follow automatically. If the concept is as good in practice as it is on paper, that is.

    (Or did all of you TCO-or-death folks assume that implementation is someone else’s problem?)

    Comment by Fredrik | April 30, 2009 | Reply

  8. Jason-
    The problems that continue currently solves can be solved manually with flag variables and normal loops, so its already solved a problem that doesn’t come up often. It’s pretty rare you see it, most often the only abnormal loop control construct you see is break. I think tail calls could become more common as people found more and more elegant solutions involving them.

    Drew-
    The way we overload continue here is good because its automatically backwards compatible – the use I’m proposing is currently a syntax error. A new keyword could potentially conflict with words already in programs.

    Fredrik/Lionel-
    I’d be happy to politically push for this on python-ideas, although I must admit going back to school and balancing work has severely limited my schedule meaning I most likely can’t implement this in CPython myself… (I don’t think it’s someone else’s problem! :)

    Comment by austinwiltshire | April 30, 2009 | Reply

  9. Yes, this seems like a good syntax.

    Comment by Chris Dew | April 30, 2009 | Reply

  10. Yes, an excellent idea it is.

    But your examples are confusing, I guess you meant
    def recursiveFunc(args):
    continue recursiveFunc(args)

    Comment by Name Required | April 30, 2009 | Reply

    • No, he meant exactly what he said. It’s a higher-order function.

      And instead of overloading “continue”, why not just “tail”:

      def func(recursiveFunc):
      tail recursiveFunc()

      Comment by Sandro | April 30, 2009 | Reply

  11. Clojure also makes tail calls explicit, in a way, using (recur). Maybe it would be interesting to compare notes? Some links:

    http://www.windley.com/archives/2008/11/tail_optimized_mutual_recursion_in_clojure.shtml

    http://clojure.org/special_forms#recur

    http://clojure.org/functional_programming

    Comment by Claus Brod | April 30, 2009 | Reply

  12. Reusing a keyword is attractive. If you turn tail into a keyword suddenly everyone link list implementations will fail :). Anyone who used tail as a variable will have to change it for no good reason. Reusing keywords is a feature.

    Comment by Albert | April 30, 2009 | Reply

  13. In the past Guido has been extremely resistant to reusing keywords for unrelated features, and I suspect that he would not approve this. In particular, tav’s block syntax comes to mind, but that’s not a good example since ‘with’ was a crummy keyword to use for that feature. I also feel like novice users would trip right over that when they see it. If you’re learning Python for the first time and you see ‘continue mycall(…)’ in a loop, what would you think? Keep in mind that you’re new to Python and you are diving in head first instead of reading all the docs first, because that’s how people actually learn languages.

    I feel like a better compromise would be to do TCO for really deep stacks. Stack traces for recursive functions aren’t really useful beyond the top and bottom 20 frames. OTOH, that’s still a fairly complicated imposition on the implementation. I think it’s unlikely to ever make it in.

    Comment by Reid Kleckner | April 30, 2009 | Reply

  14. I suggest “continue as” rather than just “continue”? It is a closer map from english meaning to actual semantics.

    This raises the question, is this a defined enough notion to be applied not just to functions, but to iterators as well? Why does this have to be about tail calls specifically, maybe Python could benefit from having this feature:

    def __next__(self):
    if condition:
    return self.stuff[self.currIndex]
    else:
    continue as otherObject

    Enjoy my half-formed thoughts!

    Comment by sjbrown | April 30, 2009 | Reply

  15. I don’t think the only problem with block syntax was ‘with’ keyword.

    The first time you see ‘yield’ you probably would feel the same way.

    Comment by Albert | April 30, 2009 | Reply

  16. The o.p. suggestion is shiny and sweet… and so to pass a continuation:

    func1(&continue func2());

    then

    def func1(continuation):
    continue continuation

    Comment by aminorex | April 30, 2009 | Reply

  17. This reminds me of Clojure’s (recur) – maybe it’d be a good idea to compare notes: http://clojure.org/special_forms#toc10

    Comment by Claus Brod | April 30, 2009 | Reply

  18. How about the keyword ‘recurse’ which isn’t used for anything, and could refer to the current method.

    def fn(x):
    recurse(x-1)

    or maybe even:

    def fn(x):
    recurse fn(x)

    Comment by Tim Ottinger | April 30, 2009 | Reply

  19. I like it. I like it. I like it.

    so what happens next? I’ve never gotten involved in getting features added to Python before.

    It certainly makes it look pythonic and still gets you all the benefits of being python.

    regs

    Konrad

    Comment by konrad | April 30, 2009 | Reply

  20. All,

    As per Lionel’s advice, I’m going to try and capture the original post and some of your ideas into a write up to post on Python ideas. The biggest hangup people have had was the reuse of the continue keyword, so I believe I’ll focus on that justification as well as alternatives such as sjbrown’s continue as or introducing a new keyword like tail or recurse.

    Thanks for your ongoing comments, they’ve been really helpful in building on this idea.

    Comment by austinwiltshire | April 30, 2009 | Reply

  21. “tail” is a bit too short and likely to collide with words used everywhere … how about “tailcall”, no need for higher-order function semantics or whatever, just as an alternative “return”:

    def func1(x):
    return otherfunc(x)

    def func2(x):
    tailcall otherfunc(x)

    —–sharks

    Comment by Sharkey | April 30, 2009 | Reply

  22. “continue as” is suggested above, and that’s a great idea. But that gave me another idea — what about “return as”? Check out PEP 380, which I believe is now accepted (and an example implementation is at http://www.cosc.canterbury.ac.nz/greg.ewing/python/yield-from/); they managed to add “yield from” to allow a generator to delegate to another generator, so this type of change is possible. Actually, that page has an implementation, so it’s at least possible to talk about adding the syntax…

    Comment by Wm Tanksley | May 14, 2009 | Reply

  23. [...] the scenes from a sufficiently smart compiler.  This is why I was an advocate of an explicit TCO via a keyword, although since I got branded a dirty little schemer (despite not knowing the language!), that idea [...]

    Pingback by My Five Things « The Skeptical Methodologist | May 31, 2009 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: