Hacker News Reader

Comment by jnordwick | Hacker News Reader

Looping is fine for imperative languages. It should be the norm for performance sensitive things since that is how the CPU works. It is just easier than trying to make a smart compiler turn your recursion into looping constructions.

However, for functional languages you really want TCO to work properly so you can write your algorithms in a properly functional way. And you don't just want self-calls to work, but full mutual recursion (A calls B that calls A etc) to be properly optimized too.

View on HN

the CPU is just doing a jump to an instruction at the end of each iteration.

When you do tail call recursion you are doing just that. The assembly jumps to a tag and in recursion you jump to a function name, which is also effectively a tag.

So it's not really about mapping better to the CPU instructions or anything like that

The added benefit is that with tail call recursion you can have mutually recursive function (function A calls function B at the end and function B calls function A at the end), which isn't possible with a simple iterative loop, so the functional style is actually more powerful than an iterative approach and still maps directly to "the way the CPU works"

You are forgetting about the function prologue, epilogue, and the maintenance of the various pointers. It certainly isn't as simple as a jump as you imply. To do proper TCO most implementation resort to function trampolines and other self-modifying trickery to get similar to loop-like performance. Within the confines of the JVM, without doing extensive source analysis, I doubt there is even a way to do it.

this is outside my field of expertise. Can you give an example of a tail call that needs "trickery"?

I'm not 100% on this, but when you have a tail call I don't think you have to remember the state of the stack frame. "function prologue, epilogue, and the maintenance of the various pointers" aren't god given rules - they're things dictated by something like the C ABI so you can resume the caller. So if you're thinking in terms of C ABI then yes, it's a compiler optimization, but in principle I think it's a zero cost abstraction (though I'd argue that the iterative loop is the actual abstraction)

In tail call recursion you're ensured the caller will never resume!

When you enter a tail-recursive function you save (as you normally would) a return pointer for the program counter and allocate registers/memory for your function arguments. At the end of the function you've done all the computation that that frame will ever do, so you are free to overwrite the argument variables when calling the next iteration/recursive-step. The return pointer doesn't need to be touched at all. Where is the complexity you're talking about?

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.

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.

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.

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.

I will have to look for mutual recursion support (or lack thereof) in clojure.

Clojure's loop/recur is a work-around for some issue with the JVM and lack of fine grained control over the stack. That said, It's not a simple loop, the keyword "loop" is effectively an anonymous function that gets called by the "recur" keyword, with parameters.

An example:

  (loop [iter 1
       acc  0]
  (if (> iter 10)
    (println acc)
    (recur (inc iter) (+ acc iter))))

I don't know if that is any different than other lisps or not. In case it's less less than clear, the bracketed portion after the "loop" keyword is an initial binding form (setting iter to 1, and acc to 0), and thereafter iter and acc are just considered parameters.

For self recursion, that seems like a fair compromise. No help at all for mutual recursion though.

I never had to use it but I recall there was a 'trampoline' fn for mutual recursion

Exactly. I once read a great article [1] written by Martin Trojer I think, it was about recursion in Clojure.

EDIT: [1] https://martintrojer.github.io/clojure/2011/11/20/tail-calls...

Reply on news.ycombinator.com