5 ms·

Tail calls, tailrec and trampolines (2009)

• sorokod 9y ago
  >Unfortunately for Scala programmers, the JVM doesn't perform this optimisation. Kotlin performs tailrec optimisation and is compiled to jvm.
  • iainmerrick 9y ago
    A little further down it says “Luckily, even without JVM support, the Scala compiler can perform tail-call optimisation in some cases.”
    • jonalmeida 9y ago
      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.
      • iainmerrick 9y ago
        If it’s done right, there would be no observable difference.
  • oweiler 9y ago
    In Kotlin the compiler is doing the TCO similar to Scala.
• Shoothe 9y ago
  Maybe it would be useful to mention that debugging can be more difficult when using tail calls as previous stack frames are not available.
  • adwf 9y ago
    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...
  • srean 9y ago
    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.
    • pdpi 9y ago
      > 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.
      • srean 9y ago
        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.
  • wruza 9y ago
    Debugging is already difficult since all returned stack frames are not available. Sometimes I miss softice’s trace mode (printf habit helps).
• eklavya 9y ago
  Maybe 2009 should be added to the title.
  • sctb 9y ago
    Updated. Thanks!
• jvican 9y ago
  Note that there is a compiler plugin for mutual recursion in Scala. https://github.com/wheaties/TwoTails/blob/master/README.md https://github.com/wheaties/TwoTails/blob/master/README.md
• avodonosov 9y ago
  It's a pity scala didn't get continuations in the end.
  • sifoo 9y ago
    The language is better off without them. Few features mess up a language implementation to the same extent as full continuations. It's a CS pipe dream; just because everything may be modeled theoretically using continuations, that doesn't mean it's a practical approach in the real world. Map and terrain, they're not the same thing.
• xiaq 9y ago
  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 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 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".)
  • sedachv 9y ago
    > 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.lisp#L79 https://github.com/vsedach/Eager-Future2/blob/master/future.... https://github.com/vsedach/Vacietis/blob/master/compiler/implementation.lisp#L179 https://github.com/vsedach/Vacietis/blob/master/compiler/imp...
  • richdougherty 9y ago
    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 https://github.com/tc39/proposal-ptc-syntax
• taylodl 9y ago
  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-javascript-tail-call-optimization-and-trampolines/ https://taylodl.wordpress.com/2013/06/07/functional-javascri...
  • k__ 9y ago
    Doesn't JavaScript core optimize it?
    • richdougherty 9y ago
      Here's the state of tail-call optimisation in JavaScript: https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) https://kangax.github.io/compat-table/es6/#test-proper_tail_... Discussion on this (apparently controversial!) feature: https://github.com/kangax/compat-table/issues/819 https://github.com/kangax/compat-table/issues/819
      • k__ 9y ago
        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.