Hacker News Reader

Comment by exceptione | Hacker News Reader

Sorry to hijack, but since you are involved, can you explain why tail call optimization would incur a run time perf penalty, as the docs mention? I would expect tail call optimization to be a job for the compiler, not for the runtime.

View on HN

We have to emulate tail calls using trampolines. This means that in some cases we have to represent stack frames as objects on the heap. Fortunately, in the common case where a recursive function simply calls itself in tail position, we can rewrite the call to a bytecode level loop and there is no overhead.

Thanks for explaining that term. That sounds really bad indeed. Maybe this is way too technical, but representing them as stack pointers was unfeasible?

The JVM (and other VMs for that matter) do not grant direct access to the stack.

But the good news is that the common case incurs no overhead.

TCO (tail call optimization) is often confused with TCE (tail call elimination), the latter is a runtime guarantee whereas the former is a compiler's best effort attempt to statically optimize tail calls.

Thanks! So you are implying that `TCO :: Maybe TCE`?

I am trying to think of a situation where a functional language compiler does not have enough information at compile time, especially when effects are witnessed by types.

I'm not a compiler dev, but I know that many functional programming languages struggle with this in the same manner if the target platform does not support TCE itself, and therefore require trampolining.

Reply on news.ycombinator.com