3 ms·
This is an old debate. On the one hand with tail calls you can write recursive code and find that it runs fast without excessive memory. On the other hand whe
by btilly 9y ago
This is an old debate.
On the one hand with tail calls you can write recursive code and find that it runs fast without excessive memory.
On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object.
- dualogy 9y agoProbably could be a user option in compilers for debug builds to either disable TCO or include "faked stack" in the tco-generated loop --- in many-maybe-most cases, wouldn't a cleanly recursive stack trace just consist of ever-the-same-callee repeated a gazillion times? Not all and not the more intricate scenarios of course.
- pdpi 9y agoTCO also applies when you have multiple levels of indirection between the caller and the ultimate callee that actually responds to the request.
- steego 9y ago> On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object. Is that really a concern? If you're writing a loop, do you expect your tools to show you a trace of every iteration in the loop? Of course not, because that would be silly. If you really want to trace each iteration, you can add your own tracing. I think of tail-recursion as parameterized gotos that are wonderfully constrained and are useful for describing state transformations in a predictable way. It's not a regular function call, so the stack trace is probably a very bad idea.
- tuukkah 9y agoNot all calls in tail position are recursive and when they are, they may be mutually recursive. This means it's not possible to detect and optimize recursive calls only.
- bunderbunder 9y agoI think it probably depends on how you think of the abstraction. Everyone readily thinks of loops, in the abstract, as "GOTO line X and do everything over again, but using all the state that has changed since the last time we were at line X." Ideally, you can think of recursion as nearly the same thing: "GOTO line X and do this stuff again, but using these very clearly stated changes to the data." If you think of recursion that way, then it's fairly self-evidently easier to reason about. In practice, though, I've met few developers who think that way and haven't spent significant time doing functional programming. I'm guessing it's because you need to spend a fair bit of time with both abstractions before you can really grok either of them. Without that, they're just kind of intimidating. Recursion more so, because everyone's taught from a young age to think imperatively.
- sbmassey 9y agoTail recursion optimisation gets rid of all tail calls in functions, not just those that might lead to loops - you cannot in general detect those calls that might be loops. This can put a lot of holes in your stack trace.
- tsuraan 9y agoGHC does non-strict evaluation as well as tail call optimization, and it offers pretty decent stack traces. The team that implemented them wrote a paper on how they did it, including how they fold mutually recursive calls in the call stack representation so that a normal Haskell program won't cause unbounded growth of the stack representation: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/DebugTraces.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... I wouldn't expect the same from an OO language, but I'm not sure that it's impossible either.
- goialoq 9y agoThe OP addresses that concern with a link to https://www2.ccs.neu.edu/racket/pubs/cf-toplas04.pdf https://www2.ccs.neu.edu/racket/pubs/cf-toplas04.pdf
- btilly 9y agoThat is a different concern. That paper is about implementing security models based on what is supposed to be in the stack. My concern is about emitting a debugging stack backtrace on error. If you are concerned with a security model, it is nice to know that you can remove the stack and prove that the security model is satisfied. But you can't provide a programmer with a record of stack frames that you do not have.