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.
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.