Hacker News Reader

Comment by throwaway17_17 | Hacker News Reader

In the context of higher order functions, tail call elimination allows for the avoidance of building up intermediate stack frames and the associated calling costs of functions when doing things like composing functions, particularly when calling large chains of nested function calls. The benefits of TCO for something like mapping a function can also be pretty large because the recursive map can be turned into a while loop as you describe at the beginning of your comment.

The optimization of stack frame elision is pretty large for function calls on the JVM and the stack limits are not very amenable to ‘typical’ higher order function ‘functional programming’ style.

View on HN

> tail call elimination allows for the avoidance of building up intermediate stack frames and the associated calling costs of functions when doing things like composing functions, particularly when calling large chains of nested function calls.

This is more general than what tail-call-optimization can handle. This is true, but only in the context of recursive functions, and you don't actually save anything besides not needing to re-allocate the stackframes below your recursion point. Other optimizations such as inlining may perform some of this in the general case. Regardless, you get the same benefits by using `recur` in Clojure, it's just explicit, it still uses no extra stack space.

The downside is purely stylistic. It's functionally the same as if you did `(let recur () ...)` in Scheme.

I’m not certain, but I am pretty sure tail call optimization includes generic tail call elimination. This does not rely on the function being recursion. In effect the compiler converts all tail calls into direct jumps and allows for the reuse of stack space, limiting the total stack size for any given chain of tail called function to a statically determined finite size. This same optimization also allows for the omission of instructions which manage stack frames and their associated bookkeeping data. I know the Ocaml compiler does this, and I’m almost sure that GHC does as well.

I do not know if the above is included in what clojure does for tail calls, recursive or not, but on the JVM the elimination of those calls can and does have an impact.

> I’m not certain, but I am pretty sure tail call optimization includes generic tail call elimination.

I believe they're related, but not the same thing.

> I do not know if the above is included in what clojure does for tail calls, recursive or not, but on the JVM the elimination of those calls can and does have an impact.

As far as I know the JVM doesn't allow a program to arbitrarily modify the stack, so any support would need to be baked into the JVM itself, which it might be now, but I'm not finding any indication that it is. The `loop`/`recur` construct essentially compiles to a loop in the Java sense (to my understanding), so it is as efficient as a recursive loop with TCO. The more general tail-call elimination likely isn't possible on the JVM, but you're correct that it would likely result in a speed up.

All of this is sort of besides the point: I don't think there's much in terms of higher-order functions (which is an extremely broad category of things) that you can't do in Clojure just because it lacks TCO. At least no one has been able to give me an example or even address the point directly. Speed is not really what I'm referring to.

If you program purely and represent "state" as a function

    s -> (a,s)

Then the JVM bites you the moment you naively abstract over that. You end up having to manually "compile" stuff like traversing a list with a stateful update. For example, Scala's pure FP ecosystem is full of specialized functions for state due to this.

Reply on news.ycombinator.com