4 ms·

How is this supposed to work given the JVM does not support tail calls?

• moondowner 14y ago
  Maybe someone who knows Scala or Clojure internals can answer this question..
  • fhars 14y ago
    scala doesn't optimize general tail calls, either (only direct tail recursion of final methods). If you want to optimize tail calls on the JVM, you must use trampolining, which adds some overhead to every call. So most languages choose fast calls without tail call elimination over slower calls with tail call elimination (i.e., speed over correctness).
    • happy_dino 14y ago
      Support for tail calls pretty much depends on the actual runtime implementation. If it is important to you (it certainly is to me), use an implementation which supports proper tail calls. I'm doing it and I have never looked back.
      • cantankerous 14y ago
        Out of curiosity, which implementation are you using?
        • happy_dino 14y ago
          Have a look at http://oss.readytalk.com/avian/ http://oss.readytalk.com/avian/.
          • cantankerous 14y ago
            This is very cool. Thank you!
  • justinhj 14y ago
    Clojure has a loop/recur construct which makes the tail recursion explicit so doesn't need to be done by the JVM. In other words regular recursive calls should not be used for loops if you want performance.
    • riffraff 14y ago
      I think rail recursion can be handled automatically by the compiler without any support from the jvm (scala does it). The issue is different for general tail call elimination.
    • pohl 14y ago
      Scala has a similar explicit @Tailrec annotation for its compiler, too: "A method annotation which verifies that the method will be compiled with tail call optimization. If it is present, the compiler will issue an error if the method cannot be optimized into a loop." http://www.scala-lang.org/api/current/index.html#scala.annotation.tailrec http://www.scala-lang.org/api/current/index.html#scala.annot...
  • i_s 14y ago
    Someone has made TCO possible in Clojure already: https://github.com/cjfrisz/clojure-tco https://github.com/cjfrisz/clojure-tco
    • kvb 14y ago
      That's very cool. But note that as far as I can tell it only handles mutual recursion, not arbitrary tail calls (e.g. calls to a function argument).
• clhodapp 14y ago
  In general speech, I can get behind the idea that you shouldn't correct someone if you understand what they mean. In programming, however, I think it's important to be pedantic. You must mean tail call optimization/elimination here. Clearly, the JVM supports tail calls.
  • tomp 14y ago
    I think everyone knows what he meant. In programming, everything supports everything anyhow, as long as it's Touring complete.
    • clhodapp 14y ago
      This isn't really fair: some implementations really do rule out certain optimizations. Turing-Completeness only refers to what is computable, not what actual algorithms and optimization techniques are possible.
      • groovy2shoes 14y ago
        And to be more specific, Turing completeness refers to what is computable with an unbounded amount of memory and time. This is why we have complexity theory layered on top of computability theory. Some things are theoretically computable but practically infeasible. Compiler optimizations can help greatly in some of those cases.
  • reeses 14y ago
    Plus, as it is relatively simple to perform tail call elimination with iteration instead of reusing the frame in many (most?) cases, static analysis can classify those cases and hygienically rewrite those functions. Most attempts I've seen to exploit TCO either aren't optimizations or can be dealt with via another control mechanism. My suspicion is that it is largely a solution in search of a problem for the programmer attempting to employ the technique, much like using AOP to add logging information for every "enter" and "return" from a method/function. Mind you, I am in no way dismissing tail-call elimination as an important tool. Just that some of its practitioners (such as whichever idiot who wrote some of the barely-readable code in old programs of mine!) are a bit zealous in its use.
• nicolast 14y ago
  Can't you lambda-lift & fully CPS-convert the code somewhere throughout compilation, then use a trampoline at runtime?
  • lysium 14y ago
    I'd say that's a huge performance hit (return, check, call instead of jump). Plus, your JIT might not like it.