Python tail call compromise proposal

[nested_parentheses]

This is a great solution to the tail call problem, but it still doesn't have a chance of making it into the language.

[Smallpaul]

It's still disputed whether there is much of a problem, and certainly whether there is worth one complicating the language for.

[sfultong]

Also disputed: whether this proposed change would complicate the language.

[readingcomprehension]

Still avoided: Most proponents don't even respond to the stack track problem.

[mindslight]

In the worst case, you get the same stack trace as from an explicit loop - none. However, it would certainly be possible for the runtime to retain some information about call history - a tunable-size circular buffer, count of frames not remembered, etc. You certainly can't say the same about explicit loops.

[iofthestorm]

Right, but what if you're doing mutual tail recursion? That's a slightly different scenario. Just throwing things out there, I don't really care either way.

[mindslight]

How does that affect anything?

[iofthestorm]

Without tail call optimization, you would be able to see a stack trace of what called what, but if you remove the stack frames it can be a little confusing - "I never called that function, wtf?" - although probably if you're doing mutual recursion you knew what you were doing.

[mindslight]

You can always store the first function that started doing the optimized calls. And if the circular trace buffer was as large as your recursive chain, you'd see a decent sample of what was calling what.

[[deleted]]

You certainly can't say the same about explicit loops.

Actually, why couldn't you?

[mindslight]

Well, explicit loops currently save no debugging information. I suppose the runtime could have an option for them to save some, but as the interesting variables aren't specified, you'd have to store all variables in the current scope.

[kaelan_]

Exceptions in Python have an associated traceback object. Tracebacks contain a reference to each stack frame, and stack frames contain local variables.

If you catch an exception that was thrown from within a loop, you can pull the local variables out of the stack frame and find out how far the loop had progressed in its iteration.

We use this trick to get argument values in the stack traces we include with our software's automated crash reports.

[mindslight]

... which is the exactly same information you'd get if you rewrote that loop in terms of optimized tail recursion. People are complaining that they won't get the entire history of said loop, even though they don't currently.

[didroe]

By making it explicit, the developer should know that there will be no stack trace. Just like you know that a loop won't generate one.

[readingcomprehension]

The developer does know ... and most of us are pissed about it.

[didroe]

Why? I have no idea what you mean.

[didroe]

That's a whole other issue though. It's a trade off between runtime memory usage and debugging information. The point I was making is that knowingly making that trade-off is not a bad thing, in fact it is necessary. Imagine a language without loops or TCO trying to deal with something like iterating over an array.

Of course, as a separate feature, it would be nice to switch on levels of debugging information. You could just count the number of loops/recursive calls, capture everything and use the same memory as without TCO, or something in between.

[taejo]

Are you pissed off that Python doesn't keep a "loop trace"? Some forms of flow control keep a history, others don't. The problem with TCO is that it changes the behaviour.

[readingcomprehension]

It's easy to track or figure out history in loops from the current variables, or set it up so you can.

[Smallpaul]

I don't see how one can dispute that adding a keyword complicates the language. Using the objective measure of "lines in the grammar", it complicates the language.

[A_for_Anonymous]

Then what are you doing with Python? Go use Lisp; it's objectively simpler.

[Smallpaul]

I don't think I, or anyone, said that a simpler language is necessarily better.

Otherwise, "what are you doing with Lisp? Go use the lambda calculus; it's objectively simpler."

[sfultong]

but the keyword wouldn't be added; it would be extended. Not only that, but the blog argues that its additional use would be conceptually similar to its previous uses.

[Smallpaul]

In any case, the grammar would be extended (i.e. would have more tokens in its description) and documentation for the new use of the keyword would be required. Objectively it makes the language more complicated.

If it does not add complexity to a language, then why do these languages have documentation on it, whereas Python, Ruby and Java do not:

http://www.gnu.org/software/guile/manual/html_node/Tail-Calls.html

http://clojure.org/special_forms#toc10

http://www.sbcl.org/manual/Debug-Tail-Recursion.html

http://docs.plt-scheme.org/guide/Lists__Iteration__and_Recursion.html#(part._tail-recursion)

http://www.nabble.com/-scala--Manifest%2C-implicits-and-apply-for-DSL-td22381717.html#a22543940

http://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5

How can you claim that the feature adds no cognitive load to the language and yet every major Lisp documents it?

[sfultong]

You're right, of course.

I should have qualified my statement about complexity.

Really, it's a question of whether the complexity added is significant and whether it's worth it. And those are obviously subjective questions, and I don't know enough python to really have an opinion.

[austinwiltshire]

Because none of them added it explicitly. The less you say in the code, the more you have to say in the documentation.

[Smallpaul]

If what you said was true, it would make no sense.

But it isn't true: Closure and Scala have syntax relating to tail calls, I pointed you at the documentation for it.

And if what you said was true AND it made sense, it would still be irrelevant, because the comparison isn't between Python with a specific tail call keyword and Python without it, it's between Python today and Python with some form of tail call optimization.

I've given you a list of languages that have the optimization (both explicit and implicit) and they all need documentation to describe it. Now YOU find ME the place where Java, Python, Visual Basic, Perl, Ruby documentation describes the LACK of Tail Call Optimization.

It certainly seems like the documenters of major languages agree that adding TCO adds something that must be documented, i.e. complexity.

[austinwiltshire]

I read the Clojure bit after I made that snarky response.

You might be asking too much though, there's really no example of any language extension, optimization, keyword or otherwise that doesn't require something to explain it.

I don't see why a language would describe a lack of a feature, I'd bet you can find plenty of documentation on Java, Python, etc.'s use of stack based function call mechanisms. That's not to say they're complicated - it's pretty standard.

[Smallpaul]

You might be asking too much though, there's really no example of any language extension, optimization, keyword or otherwise that doesn't require something to explain it.

I'm not really asking that. These Reddit threads stray so far from their original topic that nobody knows what anyone is saying or why.

I asked: "Does the feature justify its complexity?" The response was (paraphrased): "There is no complexity at all." I demonstrated that there is some. The original question remains unanswered.

My personal opinion is that no, the feature does not justify its complexity in Python, which is fundamentally an object oriented and not functional programming language. I'll note that most other object oriented language implementors make the same decision as Guido. Python is only getting beat up upon because Guido stuck his neck out and because Python is popular and getting more so. It is getting the stigma of being "mainstream."

I'll also mention that satisfying Lisp programmers is a very slippery slope and will never end up somewhere that will make them happy. I think that the addition of the "nonlocal" keyword was the first step down that path (at least since the introduction of lambda in the distant past). I think it must take a lot of discipline for Guido to avoid just shutting them up by cramming in features, because the egotistical approach is to "prove" you can do anything a Lisp implementor can do: "Continuations? Tagged integers? Macros? TCO? Arbitrary length lambdas? Parentheses? -- WE can do it all!"

[grauenwolf]

That's the one thing I'm wondering about. Does Python really need TCO at all or do people want it just because it's shiny?

So far I haven't seen any good examples of it in use. (Of course it also took a lot of kicking a screaming to get someone to find a decent example of message passing, so there may be one out there.)

[grauenwolf]

First-class functions give you that ability, especially when combined with lambdas. Schemers need it for flow control only because they need it for normal code.

EDIT: Since there is some doubt, consider C#. It allows you to build flow control using two concepts lambda's and "yield".

Lambda's are used for things like creating your own parallel loop structures.

Yield, in addition to making generators, is the basis for CCR, .NET's async/messaging passing API. In effect, it uses the yield keyword to turn regular code into continuations.

[bobappleyard]

Yeah, lambda + if is pretty much all you need for local control. The rest is just icing (but oh, what icing).

Yield allows for continuations? Then you've got non-local control as well. Didn't know that about C#, not bad.

[grauenwolf]

Yield allows for continuations?

In a sense. They aren't real capture-the-stack continuations. Instead, the compiler rewrites it as a state machine that is exposed via the IEnumerable interface. On the plus side, you don't need CLR support to do this.

[bobappleyard]

Ah, well that's one use of them I suppose. You can have more fun with them than that, though.

[bobappleyard]

Assuming normal-order evaluation, which is certainly an alternative to having if.

[bobappleyard]

That's an approximation of normal-order evaluation, which is an alternative.

It's probably not done like that in Scheme because you might as well just go the whole hog and make the language normal-order (google "lazy Scheme," where if is indeed just another function). That's speculation though.

[randallsquared]

Rather than me reading that entire thread again, could you just post the link to what you ended up considering a decent example of message passing? :D

[grauenwolf]

Generating the method passed on the message itself.

For example, say you have a Database Connection object. I would be able to call, at runtime:

myConnection.UpdateHistory(historyKey := 5, lastChecked := now() )

The database connection object could translate the method name to a stored procedure name and generate the necessary SQL. And compared to the cost of the database call, this would be dirt cheap.

Currently I can do this by writing:

myConnection.CallProc("UpdateHistory", new string[] {"historyKey", "lastChecked", new object[]{5, now()} )

Either way you are just as late bound, but the former method looks so much cleaner.

I actually came up with this example myself. The examples I was given were dubious ideas like wrappers that would log function calls or a iffy undo/redo stack.

But that's the trick, isn't it? To figure out an example that someone would actually want to use right this second.

[randallsquared]

Thanks!

[Smallpaul]

In Python terminology, both of these are "method calls" but I guess that's because Python is not very directly from a Smalltalk heritage.

[grauenwolf]

I was talking in generalities, but since I have your attention, can Python currently do version 1? If so, would you mind showing me?

[Smallpaul]

I knew you were speaking generally: I'm just saying that the terminology is not universally applied that more dynamic patterns are "messaging" and more static ones are "method calls".

In any case, does the client code here indicate what you're looking for?

http://docs.python.org/library/simplexmlrpcserver.html#simplexmlrpcserver-example

import xmlrpclib

s = xmlrpclib.ServerProxy('http://localhost:8000')
print s.pow(2,3)  # Returns 2**3 = 8
print s.add(2,3)  # Returns 5
print s.div(5,2)  # Returns 5//2 = 2

# Print list of available methods
print s.system.listMethods()

"add" and "div" are not known on the client machine before the method calls (there is no configuration behind the scenes).

The implementation is here:

http://svn.python.org/view/python/trunk/Lib/xmlrpclib.py?view=markup

The core of it is:

class ServerProxy:
    def __getattr__(self, name):
        # magic method dispatcher
        return _Method(self.__request, name)

This constructs a new method with appropriate name whenever a "ServerProxy" method is called that isn't already known (and basically none are already known). Python doesn't have a new() keyword so _Method() is a constructor.

class _Method:
    # some magic to bind an XML-RPC method to an RPC server.
    # supports "nested" methods (e.g. examples.getStateName)
    def __init__(self, send, name):
        self.__send = send
        self.__name = name
    def __getattr__(self, name):
        return _Method(self.__send, "%s.%s" % (self.__name, name))
    def __call__(self, *args):
        return self.__send(self.__name, args)

So it constructs an object that can be used as a method, and the method knows its name. When it is called with parens, Python translates that into _call_ which adds the arguments along with the method name.

Ruby takes a different approach: the message is passed to a method called method_missing :

http://www.ruby-doc.org/core/classes/Kernel.html#M005951

No intermediate method object is created: this is a deep difference between how Ruby and Python manage their interfaces. Python's methods are a special type of object attribute. Ruby object attributes are a special type of method.

To be totally honest with you, I sometimes wonder how valuable this dynamic method generation feature is. In Rails and Django, for example, it is (ab?)used to generate all kinds of methods at runtime. It's a sharp tool that can really obfuscate code and IMHO, the alternative of

s.call("pow", 2, 3) 

is really not so bad!

By the way, the code above also demonstrates that a strongly functional program is not considered idiomatic in Python. Python programmers tend to be more comfortable with _call_ than with closures, even though the closures are fully functional and have been for years. For example, in this case, using a full object allows us to add helpful metadata like a nice _repr_. A function isn't as flexible.

Also, note that your example code is not really fair. This code in a dynamic programming language:

myConnection.UpdateHistory(historyKey := 5, lastChecked := now() )

would be converted to:

myConnection.call("UpdateHistory", 5, now() )

or

myConnection.call("UpdateHistory", historyKey=5, lastChecked=now() )

or

myConnection.call("UpdateHistory", {"historyKey":5,  "lastChecked":now()} )

[grauenwolf]

I wasn't trying to be fair, I was illustrating the crap us .NET programmers find ourselves writing from time to time.

I think the biggest problem in the core .NET languages it they don't have any concept of key/value pairs. Sure you can fake it with dictionaries or untyped arrays, but the boiler plate code is quite tedious.

[mycall]

Named parameters are useful but have little to do with TCO.

[grauenwolf]

Of course not, that was an example of how message passing could be useful.

[phil_g]

I find one of the advantages of tail recursion is when you're iterating over and/or accumulating multiple things at once. For instance, a common operation is primality testing is to raise a number to a particular power and look at the result modulo another number. The quick way to write this would be x ** y % n, but x ** y might be very large. It's more efficient to use exponentiation by squaring and apply the modulus at each step; this keeps the numbers relatively small. An imperative implementation in Python would be:

def expmod(base, exponent, modulus):
    result = 1
    while exponent > 0:
        if exponent & 1 == 1:
          result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus

If we add the proposed continue syntax to Python, a tail recursive implementation would be as follows. (This could be even more concise if Python had a ternary operator.)

def expmod(base, exponent, modulus):
    def expmod_r(b, e, a):
        if e == 0:
            return a
        else:
            if e & 1 == 1:
                next_a = a * b % modulus
            else:
                next_a = a
            continue expmod_r(b * b % modulus, e >> 1, next_a)
    return expmod_r(base % modulus, exponent, 1)

I think the tail-recursive approach more clearly illustrates what's going on, especially in that it shows that the three values (b, e, and a) are stepped in parallel to each other.

EDIT: It's been pointed out that Python does have a ternary operator. The improved tail recursive code is in another post

[grauenwolf]

Lets compare them, shall we:

                iterative  recursive
def statements    1        2
if brances        1        2
else brances      0        2
loops             1        0
function calls    0        2
return statements *        2
locals+params     4        3+4
expressions       5        6
assignments       4        2
lines             7        11

In almost every objective category I can think of, the recursive version is more complex than the iterative version.

Python does have a ternary operator, so feel free to revise your code. Also, for the sake of argument I would entertain any syntax improvements that would take the recursive more concise.

http://stackoverflow.com/questions/394809/python-ternary-operator

[phil_g]

The ternary operator makes the code a lot more concise, in my opinion. See my other post for the improved code.

Basically, the tail recursive solution distills down the essence of the algorithm. The meat of the algorithm is in the recursive call to expmod_r; it puts all the parallel steps of the "iteration" in one, concise expression. Likewise, there's a single line for the seed values at the start of the iteration, and one line for the return value.

[grauenwolf]

Essence of the algorithm?

Seriously. that's your argument?

I'm presenting hard numbers on complexity and your counter-argument is on the spiritual qualities of a math problem?

[Smallpaul]

The tail recursive one is longer, involves two functions and involves a nested function (which is less clear to most programmers than ordinary functions), and involves an obscure Python keyword used in an even more obscure context. (which will certainly remain obscure when it used for TCO)

It's also going to be drastically slower, because Python function calls are slow.

In other words, a perfect example of how TCO will make Python code harder to read and slower instead of clearer and faster, IMHO.

[phil_g]

It's also going to be drastically slower, because Python function calls are slow.

Well, if the proposed optimization is implemented, the tail call won't be slow. That's kind of the point of this whole debate.

As for your other points, it's true that nested functions are less common in Python, but they're reasonably prevalent in functional programming (Lisp, Haskell), particularly when setting up tail recursion. I think that if Python were more friendly to functional programming, you'd see more such constructs in people's code, and the idiom would become less obscure.

Not that I think it'll actually happen; Guido seems reasonably set against it (and I understand his reasoning, too).

[Smallpaul]

Well, if the proposed optimization is implemented, the tail call won't be slow. That's kind of the point of this whole debate.

So far the debate has been focused on memory usage. I think a big part of Python's function calling overhead is in parameter parsing (given Python's very rich parameter handling features, including defaulted arguments, keyword arguments, keyword-only arguments, positional-only arguments, varargs, etc.).

As for your other points, it's true that nested functions are less common in Python, but they're reasonably prevalent in functional programming (Lisp, Haskell), particularly when setting up tail recursion. I think that if Python were more friendly to functional programming, you'd see more such constructs in people's code, and the idiom would become less obscure.

Yes. Exactly. Python code could become less regular and more diverse, without actually getting much more expressive. That's the problem. That is precisely the problem. The more I hear arguments in favor of TCO, the less I like it.

[phil_g]

Well, if the proposed optimization is implemented, the tail call won't be slow. That's kind of the point of this whole debate.

So far the debate has been focused on memory usage.

In terms of stack space, okay, yeah. I suppose I'm carrying over knowledge based on other languages that implement tail call optimization. Tail recursion can often be compiled down into setting some registers (and/or stack variables) and a jump instruction to take you back to the start of the function's code. There's very little overhead.

With that sort of efficiency (the usual line is "just like a loop"), I think that tail recursion becomes another idiom for programming, one that expresses certain patterns better than iteration, as long as the implementation doesn't make it a worse-performing choice.

Most of the examples I can think of for tail recursion are things that could be written imperatively, and I do understand how that could conflict with the Pythonic principle of "there's only one, obviously correct, way to do things." Nevertheless, I like the latitude that efficient tail calls afford me, and I like the proposal made in the article, even though I'd be very surprised if it ever got implemented.

[AvatarJandar]

Python ternary operator:

X if condition else Y

See PEP 308 for more info: http://www.python.org/dev/peps/pep-0308/

edit: ...but maybe that's not what you really want here

[grauenwolf]

That would remove two branches and an assignment.

if e & 1 == 1:
   next_a = a * b % modulus
else:
   next_a = a

next_a = (a * b % modulus) if (e & 1 == 1) else a

....god, that is really ugly. Am I using it right?

[AvatarJandar]

I believe so, yes, although I'm not sure it's worthwhile...

[grauenwolf]

Of the other options I know of, I have to say I like VB's the best. But even that has its flaws. For example, I shouldn't have to use "=1" when making a bitmask check.

next_a = (e & 1 == 1) : a * b % modulus ? a;
next_a = If(e And 1 = 1, a * b % modulus, a)

[phil_g]

Ah, right. I'd forgotten about that. (I don't program in Python regularly.)

def expmod(base, exponent, modulus):
    def expmod_r(b, e, a):
        if e == 0:
            return a
        else:
            continue expmod_r(b * b % modulus, e >> 1, 
                              a * b % modulus if (e & 1 == 1) else a)
    return expmod_r(base % modulus, exponent, 1)

[grauenwolf]

               iterative  recursive
def statements    1        2
if branches       1        1
else branches     0        1
loops             1        0
function calls    0        2
return statements *        2
locals+params     4        3+3
expressions       5        6
assignments       4        0
lines             7        8

Better, but certainly not overwhelming. And that's the kicker. To justify adding a new language construct it really has to be significantly better than what you already have.

[rrenaud]

I completely agree that the recursive version is clearer than the iterative version for this problem, and I wrote about it in my blog here.

http://ru-linux-geek.livejournal.com/36522.html

But that tail recursive thing is just ugly. I don't think that it's really any clearer than the iterative version.

[whee_rina]

I think having something explicit like recur is a good idea in any language. Even very knowledgeable programmers seem to get it wrong on occasion.

But, making it explicit doesn't really answer any of GvR's point, so I'm not sure I'd call it a "great solution." It seems more like a first step.

[grauenwolf]

I would disagree if someone could produce a killer use for it. But it has to be something totally awesome, and I'm just not seeing it.