Menu
I saw this quote on the question: What is a good functional language on which to build a web service?
Scala in particular doesn't support tail-call elimination except in self-recursive functions, which limits the kinds of composition you can do (this is a fundamental limitation of the JVM).
Is this true? If so, what is it about the JVM that creates this fundamental limitation?
868
Java doesn't have tail call optimization for the same reason most imperative languages don't have it. Imperative loops are the preferred style of the language, and the programmer can replace tail recursion with imperative loops.
Java supports tail-recursive calls, but AFAIK it doesn't optimize them away.
Tail recursion is a compile-level optimization that is aimed to avoid stack overflow when calling a recursive method. For example, the following implementation of Fibonacci numbers is recursive without being tail-recursive. The Scala compiler has a built-in tail recursion optimization feature, but Java's one doesn't.
Tail call optimization happens when the compiler transforms a call immediately followed by a ret into a single jmp . This transformation saves one instruction, and more importantly it eliminates the implicit push/pop from the stack done by call and ret .
This post: Recursion or Iteration? might help.
In short, tail call optimization is hard to do in the JVM because of the security model and the need to always have a stack trace available. These requirements could in theory be supported, but it would probably require a new bytecode (see John Rose's informal proposal).
There is also more discussion in Sun bug #4726340, where the evaluation (from 2002) ends:
I believe this could be done nonetheless, but it is not a small task.
Currently, there is some work going on in the Da Vinci Machine project. The tail call subproject's status is listed as "proto 80%"; it is unlikely to make it into Java 7, but I think it has a very good chance at Java 8.
171
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
