Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Object-Oriented Languages Need Tail Calls (2011)

eighty-twenty.org

Post reply on HN
Print view View original

11–20 of 72 posts

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#11

Post by sbmassey »

steego wrote: post #7
btilly wrote: post #2

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

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

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#12

Post by samth »

jacinabox wrote: post #6

They don't need tail calls, unless you're planning on doing idiomatic functional programming in an OO language, which, Why??

The answer to your question is the entire point of the blog post, which was written by Guy Steele, who worked on the original design of Java.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#13

Post by willtim »

sbmassey wrote: post #11
steego wrote: post #7

Earlier quoted context omitted.

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

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

It's an optimisation. It can be turned off when debugging with stack traces. If you need stack traces in production code, you have too many partial functions.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#14

Post by Rusky »

willtim wrote: post #13
sbmassey wrote: post #11

Earlier quoted context omitted.

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

It's an optimisation. It can be turned off when debugging with stack traces. If you need stack traces in production code, you have too many partial functions.

But you can't ever turn it off if you rely on it for loops, which defeats the whole point.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#15

Post by mikeash »

Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive.

If you had to explicitly request it, say by doing `tailcall f()` instead of just `f()`, that would mostly fix these problems. Control flow will be a lot less confusing since it'll be explicit in the code (but you still lose information from the optimized-out stack frames, no way around that) and you'll get an explicit error if someone tries to add something that can no longer be tail call optimized, like `tailcall f() + 1`.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#16

Post by catnaroek »

mikeash wrote: post #15

Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive…

I understand the case for adding O(1) overhead for the sake of debuggability, but not having proper tail calls (it's not an optimization, goddammit) is way more than O(1) overhead.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#17

Post by willtim »

Rusky wrote: post #14
willtim wrote: post #13

Earlier quoted context omitted.

It's an optimisation. It can be turned off when debugging with stack traces. If you need stack traces in production code, you have too many partial functions.

But you can't ever turn it off if you rely on it for loops, which defeats the whole point.

You can turn it off, you just can't process large data sets, as you'd run out of stack space. But who wants to debug with large data sets?

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#18

Post by cr__ »

mikeash wrote: post #15

Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive…

This is how Clojure does it.

https://clojuredocs.org/clojure.core/recur

https://clojuredocs.org/clojure.core/trampoline

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#19

Post by tsuraan »

btilly wrote: post #2

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 t…

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

I wouldn't expect the same from an OO language, but I'm not sure that it's impossible either.

Re: Why Object-Oriented Languages Need Tail Calls (2011)

#20

Post by to3m »

mikeash wrote: post #15

Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive…

We even already have a common keyword suitable for this: 'goto'.
Post reply on HN