6 ms·
I can't answer fully for Clojure's reasons for not supporting TCO, but it will at least be fundamentally rooted in the fact that the JVM, as a platform, does NO
by rit 13y ago
I can't answer fully for Clojure's reasons for not supporting TCO, but it will at least be fundamentally rooted in the fact that the JVM, as a platform, does NOT support TCO.
Scala is usually the language brought up as a counter argument here, but Scala has the same limitations as Clojure - the JVM can't do the TCO. Scala's compiler tries, with certain types of tail calls, to optimize via (I believe) a trampoline – it reduces those calls into a loop, so they are no longer a function call.
But, only certain types of calls (specifically, the last line of code in a recursive function must be a call to the hosting function) can be TCO in Scala. There is an annotation, scala.annotation.tailrec, which can be placed above a method you want to tail recurse.
@tailrec does not, however, "force" the compiler to do TCO – it simply forces compilation to fail if the method in question cannot be Tail Call Optimized. It's a developer hook for saying "I realize the compiler tries to do TCO where possible, but I require this method to be trampolined". If it can't be, you'll get a compilation error with details on why the TCO failed.
- fhars 13y agoScala compiles direct tail recursion the a jump to the start of the function (jumps within a method are possible on the JVM) without any trampoline. So @tailrec tells the compiler to compile this call to an unconditional jump.
- derleth 13y ago> the JVM, as a platform, does NOT support TCO. And the x86, as a platform, does? What, specifically, does the JVM do to make TCO more difficult than it would be in the machine code of your choice?
- smosher 13y ago> And the x86, as a platform, does? "It's complicated." http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations http://stackoverflow.com/questions/105834/does-the-jvm-preve...
- kragen 13y agoYes, the x86 instruction that implements TCO is called JMP. The JVM doesn't have an equivalent instruction; you can only jump around inside a single method, not to the beginning of another method.
- derleth 13y ago> The JVM doesn't have an equivalent instruction; you can only jump around inside a single method, not to the beginning of another method. OK, why do functions in the source language have to translate directly into methods at the JVM level? Purely for debugging?
- kragen 13y agoThe JVM also doesn't (I'm fairly sure) have an indirect JMP instruction, which means you can't compile a polymorphic source-language method call into a JMP inside of a single generated method. Instead you have to use a call to a method. That means that tail-calls to functions passed as parameters (rather than functions that can be statically bound at compile time) can't use JMP.
- happy_dino 13y agoThe “JVM” can use any instruction it wants to use. If you want a runtime with proper tail calls, use a implementation which supports it.
- kragen 13y agoI'm talking about the bytecode instructions standardized in the "JVM" specification. The "JVM" has to implement the semantics of the instructions found in your bytecode program, or your program won't run. Your bytecode program can only use bytecodes defined in the "JVM" specification, or it won't run on the "JVM".
- happy_dino 13y ago