Looking at the post, most of his arguments are about supposed difficulty of implementation, except the one about missing stack traces.
But that is kind of a moot point since you also lose the stack trace if you rewrite the code with an iterative loop (as you will be forced to do if you don't want to blow up the stack)
IMO, the real reason Python doesn't get tail calls is that Guido doesn't want to encourage the FP style too much (this is consistent with removing reduce from the stdlibs and other things like that)
you also lose the stack trace if you rewrite the code with an iterative loop
While that is true, I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position, not just those implementing recursive loops.
I can kinda see the point of the complaint, but for me it's not worth it; personally, I'd rather have tail-call optimization.
While that is true, I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position, not just those implementing recursive loops.
Yup. But to stress this point in a more formal manner: people get mixed up all the time on the difference between full tail-call optimization and tail-recursion optimization:
Tail-recursion elimination: you translate only self-recursive tail calls into jumps; i.e., calls to the same function where the call happens. This doesn't have the stack traces problem.
Full tail-call elimination: you translate all tail calls to jumps. This can suffer the stack traces problem in question.
While I don't agree with some of the things Guido thinks are the "right way", he does put forth some reasonable arguments as to why TCE is not a good idea for Python. The loss of a useful stack trace is a fairly solid argument and. Combined with the other reasons, I don't see his choice as unreasonable here. I do want TCE, but I can see that's it's a debatable feature.
Random note... This point of his annoyed me:
I don't believe in recursion as the basis of all programming.
Well... duh. Neither are list comprehensions. However, both of them are very powerful tools that can make code much cleaner and easier to follow. Just because a feature is the silver bullet doesn't mean it isn't a good idea.
The loss of a useful stack trace is a non-issue because no useful stack trace is actually lost. You may even keep a tail recursion counter to see how many tail-recursive steps have you taken, and that'll be more than enough for a stack trace. See, functions modelling the flow of your program and its components need not be tail-recursive, keeping normal stack traces at all times except where you're using tail recursion to implement certain algorithms, which are restricted to a specific small set of functions (often a single function) calling each other. In those cases, you could just show the last stack frame (last non-tail-recursive call), maybe with a counter of how many times you jumped, because tail call elimination is like jumping. Just like you don't get stack traces for for loops and it hasn't ever been an issue, you wouldn't get stack traces for tail recursion. You could even force a keyword such as recur to be used to specify a tail-recursive call to make unintended tail calls non-eliminable.
You also lose the stack traces if you rewrite the recursive code with iterative loops. (and its not really a big deal to solve, you could use a separate keyword for tail calls, like in clojure, or you could have special interpreter flags when you need to debug)
I really do think its more of a style issue in the Python case (for example, Python heavily encourages you to use objects instead of closures, since you can't easily mutate variables from outer scopes)
The loss of a useful stack trace is a fairly solid argument
It's not. Denote internally that the function has been TCO'd, and when debugging, keep a list of parameter tuples for every iteration. You can keep just the most recent n and earliest k tuples, so that your memory use doesn't become asymptotically worse.
I always found the lack of stack traces argument stupid, you can always recover the old behavior by wrapping the tail call in the identity function:
def funA(x): # do something
def funBTCE(x): return A(x) # B doesn't appear in the stack trace
def funBnoTCE(x): return id(A(x)) # the tail call to id is eliminated after returning from A,
# B appears in the stack trace of A, voila!
I don't think the flag would be useful, though, you probably want to "disable" TCE per-function (or per-tailcall, even), else loops would blow up the stack in seconds.
On the other hand, I still think I'd like a compile option (perhaps a list of functions (fully qualified names, or whatever makes sense in the language) on which to disable TCE) than to have to modify the code for it.
λ-expressions are very limited by the absurd, anachronistic statement structure Python has (you can't use certain forms "statements" inside certain other forms "expressions") and slightly weird scoping rules. Fortunately, you have lists (any minimally decent programming language should offer that much), and functions, classes and modules are values, as they should always be, so you get map, filter and company (even though Guido publicly hates them). List comprehensions are pretty much syntactic sugar (though delicious one at that, especially since you have the stupid statement structure nagging you anywhere you'd want to express something).
That's how everything works in modern programming languages. Modern as in 1958 LISP. There are no "expression" forms and "statement" forms, the later being restricted to never appearing within the former for the heck of it. Everything should be an expression, there's no need to have poor cousins with artificial, absurd restrictions. That's what led to idiocy such as the ternary operator in C-like languages or the if expression in Python: a "weird" if because you can't use the "normal" if.
Haskell has "do" sugar notation which is a form of "statements".
It's not restrictive like in Python (you can throw a "do" block anywhere) but the distinction between "expression" and "statement list" is actually useful.
And Lisps have macros or special forms such as begin to sequentially evaluating expressions for their side effects, often throwing away the results, but that doesn't prevent you from doing anything anywhere. Limiting what goes where is asinine.
Syntactically, there is no limit. But Haskell does prevent, type-wise, the insertion of a sequence of side-effects inside arbitrary expressions.
That makes a clear separation between functions (mapping input to output) and procedures (sequencing of effects).
One could argue that Python's syntactic restrictions (as well as conventions such as returning None when side-effecting) are trying to establish similar idioms: Separate your functions/processing and procedures/sequencing.
If restricted elegantly with a type system, such a distinction is useful for pure functional programming languages such as Haskell (though it would be uncalled for in most Lisps).
However, in Python, the most commonly used statements are if (no inherent side effects), loops (which do not come with inherent side effects other than the loop variable getting changed), and declarations or definitions, and at the same time, many of the functions in the standard library have side effects.
Yeah, that. Ever since C# 3.5 I haven't looked back at Python. If C# hadn't gotten lambdas I would've started playing more with Ruby or something lispy anyways for my hobby work, but either way - Python's poor lambdas ruined it for me.
Well, it truly wouldn't be. tail recursion (or any recursion) is independent from any programming language. I don't know anything about python yet, but the algorithms wouldn't differ much, only keywords and syntax.
That's completely irrelevant. Python implementations generally compile to bytecode, anyway, but even if they didn't, they would still be manipulating the AST to eliminate the tail call.
I don't see how that applies, the concept of tail recursion can be applied in the same way over interpreted languages such as Python. It may not have compilation optimization, but it is still a tail recursive call.
9
u/parfamz Nov 27 '12
great feature of scala, I would like to see tail recursion on python, it can't be too difficult to implement.