Comment by tombert
18 hours ago
I'm a pretty big functional programming nerd and I want to like tail recursion, but I honestly kind of feel like I agree with Guido on it, which is that it kind of breaks the typical stack-trace patterns.
I have kind of grown to prefer Clojure's loop/recur construct, since it gives you something more or less akin to tail recursion but it doesn't pretend to be actually recursive.
Clojure does it this way because the JVM stupidly doesn't support tail call optimization.
It is true that TCO messes up your stack traces. It is also true that loops mess up your stack traces, because they don't even create a stack trace. In many languages that support TCO, TCO can be turned off for debugging and enabled for production, so Guido's characterization of the issue is ridiculous.
I know that's the origin of why Clojure does its manual loop/recur thing, but I've grown to kind of prefer its explicitness. There's no ambiguity on whether it will TCO; it simply won't compile if it's not tail-call.
I don't agree that being able to turn off TCO in debugging is enough to call Guido's characterization "ridiculous". I often have to debug running production systems, and those are (hopefully) not deployed with debug compilations.
You're not wrong about loops not creating a stack trace; I guess what bothers me (and maybe Guido) is that with loops there's no expectation of a stack trace, while with a function call there is.
> It is also true that loops mess up your stack traces
No, because an indirect tail-call eliminates the calling frame. After, it looks like the caller of that function called a function it did not call. In fact, with tail-calls a whole pile of steps gets telescoped down to nothing[1]. This is not the case with a loop, it doesn't jump to itself indirectly. Loops don't jump into the middle of other loops in other functions. We can still follow the chain of control flow from the start of the main function, through (non-tail) calls, i.e. the stack, through the start of the loop, and then from some backedge in the loop body we're looking at.
Tail-calls are absolutely harder to debug in general than loops.
[1] In the limit, if the entire program was transformed into CPS with tail-calls everywhere, the original execution stack is now strewn throughout the heap as a chain of closures.
I certainly can jump from one loop to the middle of another when writing Python code with Async and/or generators.
> Tail-calls are absolutely harder to debug in general than loops.
I like TCO because I often prefer the expressiveness of recursion over loops. When I need to debug, I turn off TCO. (I'm talking about Common Lisp.)
I agree TCO definitely makes the compiled code not look like the source, and this lossage doesn't happen with either regular recursion or with loops. But various other kinds of optimizations also have that problem.
If you're looking at the assembler output you'll see JMPs where there would have been JSRs without the optimization. So knowing that helps a bit. You just lose the automatic history preservation the stack gave you for free.
Time travel debugging might be an answer here but of course that can be much more expensive than simply keeping JSRs in place.
Although, a correctly shown stack trace for a recursive function is also pretty “messed up” in some sense. Who wants an O(n) stack trace? I guess most tools are not going to display it nicely, haha.
> ..kind of breaks the typical stack-trace patterns.
The expectation that iterative recursion ought to have a call stack is the problem here and wouldn't be up for debate if people had done their due diligence and read their SICP.