Hacker News Reader

Comment by senex | Hacker News Reader

When TCO is "lexically scoped" like loop/recur, the compiler can handle it.

When HoF are involved, you may have a case where a procedure calls a procedure-parameter, which calls another, and another... Something about the runtime has to recognize this or else the compiler has to accept more constrains.

See, for example, how Gambit-C implements tail calls by compiling modules to single C functions and how there is a trade off for procedure calls across module boundaries versus Chicken Scheme's approach to essentially garbage-collecting the call stack.

View on HN

Okay, but at that point you're talking about things that are way beyond the capabilities of an iterative loop. I think my point still stands - that implementing a tail recursion in place of a loop is not something you will have to pay for. Both structures will map to the same instructions.

Yep, you're absolutely right. I guess that maybe if you care about inventing new kinds of loops (e.g. a DSL that wants to loop as a specialized kind of `fold` construct), there's more flexibility with TCO.

But Clojure shows that there's tons of mileage and composability that can happen by using runtime protocols and tasteful language-design decisions even without TCO.

Capturing continuations is another interesting theoretical outcome of TCO, although as various scheme implementations show: the approach to supporting TCO also imposes some performance constraints on call/cc.

The difficulty with tail recursion optimization is related to calling conventions. Some calling conventions expect the caller to do some cleanup after the callee returns, which effectively means that no function calls actually occur in tail position. For example, in the C calling convention the caller caller is responsible for allocating and freeing the stack memory dedicated for the callee's function parameters. This system makes vararg functions like printf easy to implement but makes it hard to do TCO. Another example is Rust, where having destructors automatically run when a variable got out of scope prevented them from implementing TCO in a clean manner. I'm not familiar with the JVM internals but I think the limitations are going to be similar to the ones I mentioned here.

It's not just that, it's that last time there was serious talk of it, LLVM's musttail wasn't properly supported across important platforms for us. So it got put by the wayside, and there's always so much to do, nobody has worked through the semantics now that support is better.

We did reserve a "become" keyword for this purpose though. Instead of "return", you say "become", and TCO is guaranteed. That's the basic idea anyway, we'll see what happens.

Reply on news.ycombinator.com