Why Object-Oriented Languages Need Tail Calls (2011)
eighty-twenty.org
Why Object-Oriented Languages Need Tail Calls (2011)
1–10 of 72 posts
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#2This 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.
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#3This 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 t…
Probably 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.
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#4This 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 t…
Probably 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.
TCO also applies when you have multiple levels of indirection between the caller and the ultimate callee that actually responds to the request.
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#5There are a number of problems with this argument, but the biggest one is that most such calls will not actually be tail-recursive. The very specific `adjoin` example that has been provided only works with `contains` not being in a tail position because `or` is assumed to use short-circuit evaluation, and because the author is apparently willing to live with a set membership test that has linear time complexity. We can see that the `contains` method for `UnionObject` is not tail-recursive, for example, no matter how you cut it.
The primes example effectively constructs a linked list with 78,498 elements; any unsuccessful search will iterate over all those elements, and successful searches will (depending on how the search arguments are distributed) also easily traverse tens of thousands of elements. Handwaving performance issues away with "we know lots of ways this code can be optimized, but let us please focus on the behavior of the constructed set" is wrong, simply because efficient and actually usable implementations may exhibit totally different requirements w.r.t. tail recursion and what should be in an interface.
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#6They don't need tail calls, unless you're planning on doing idiomatic functional programming in an OO language, which, Why??
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#7This 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 t…
> 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.
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#8This 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 t…
> 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…
Not 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.
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#9They don't need tail calls, unless you're planning on doing idiomatic functional programming in an OO language, which, Why??
Some languages, such as Scala, have a mix of FP and OO concepts. Some FP features make use of TCO, so this helps to make them a first class citizen.
Re: Why Object-Oriented Languages Need Tail Calls (2011)
#10This 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 t…
> 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…
I 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.