Tail calls, tailrec and trampolines (2009) | Hacker News Reader

Tail calls, tailrec and trampolines (2009)

blog.richdougherty.com

83 pointspilingual22 comments

Tail call optimization is a neat idea, but I have always felt that it is too magical. You cannot opt out of it. Clojure's approach strikes a good balance: Clojure doesn't do TCO, but it gives you "recur" as an explicit way to do tail recursions that don't consume stack space: https://clojuredocs.org/clojure.core/recur

Clojure has also had "trampoline" in core since 1.0, which was released in the same year this article was written: https://clojuredocs.org/clojure.core/trampoline. I have no idea how well it performs though.

If your language has "goto", it is very easy to manually optimize mutually recursive functions. One of the few valid use cases of "goto" today. (As someone who writes a lot of Go, I have always suspected this use case is why Go still has "goto".)

> One of the few valid use cases of "goto" today.

Manually rewriting recursive algorithms is one of the least valid use case of GOTO. You need GOTO for low-level concurrency, IO multiplexing, and transpiling:

https://github.com/vsedach/Eager-Future2/blob/master/future....

https://github.com/vsedach/Vacietis/blob/master/compiler/imp...

JavaScript is considering syntactic support for tail calls instead of automatic support. Automatic optimisation is currently in the spec but is apparently controversial.

https://github.com/tc39/proposal-ptc-syntax

JavaScript doesn't optimize tail recursion. I wrote about this, and how to use trampolines, a few years back: https://taylodl.wordpress.com/2013/06/07/functional-javascri...

Doesn't JavaScript core optimize it?

Here's the state of tail-call optimisation in JavaScript:

https://kangax.github.io/compat-table/es6/#test-proper_tail_...

Discussion on this (apparently controversial!) feature:

https://github.com/kangax/compat-table/issues/819

Yes, I know about the controverse.

People say it blows up the stack traces, so it should be opt-in.

But it seems that Node.js and Safari have it, and as far as I know Safari uses JavaScript Core, which is also used for React-Native.

Maybe it would be useful to mention that debugging can be more difficult when using tail calls as previous stack frames are not available.

But isn't the whole point of tail recursion not to have those stack frames ? Iterative alternative would not have those stack frames either. I don't hear that complain for iterations or the complain that the previous version of the iteration variable has been overwritten. Tail recursions have the same thing, the 'stack variables' get overwritten.

With time travelling debuggers it might be possible to look at those, but that's a whole new topic.

> But isn't the whole point of tail recursion not to have those stack frames

Sure. But a recursive function can have errors happen in one call that are only detected a few levels down. Given a full call stack, you have a trace of the execution thus far that gives you information about where, exactly, things went wrong. With TCO, you're just left with the original call at the top, and the failed state at the bottom, and no snapshot of what happened in the meanwhile.

What you say is indeed true, but only partly so. The state of affairs would be no different in the corresponding iterative solution. I say 'partly' because you could put a break point at the entry point or before the call. One would be able to debug the recursion just as one would debug the corresponding loop.

The general solution to that is to have a debug compiler setting to turn off TCO when debugging.

Of course this leads to its own problem if your now unoptimised recursive blows the stack...

Debugging is already difficult since all returned stack frames are not available. Sometimes I miss softice’s trace mode (printf habit helps).

Note that there is a compiler plugin for mutual recursion in Scala. https://github.com/wheaties/TwoTails/blob/master/README.md

It's a pity scala didn't get continuations in the end.

>Unfortunately for Scala programmers, the JVM doesn't perform this optimisation.

Kotlin performs tailrec optimisation and is compiled to jvm.

A little further down it says “Luckily, even without JVM support, the Scala compiler can perform tail-call optimisation in some cases.”

I'd say the full quote to be, "Luckily, even without JVM support, the Scala compiler can perform tail-call optimisation in some cases. The compiler looks for certain types of tail calls and translates them automatically into loops."

This wouldn't be actual TCO in that case.

If it’s done right, there would be no observable difference.

In Kotlin the compiler is doing the TCO similar to Scala.

Maybe 2009 should be added to the title.

Updated. Thanks!

Reply on news.ycombinator.com