Does the Jvm Prevent Tail Call Optimizations

Does the JVM prevent tail call optimizations?

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.

Why does the JVM still not support tail-call optimization?

Diagnosing Java Code: Improving the Performance of Your Java Code (alt) explains why the JVM does not support tail-call optimization.

But although it is well known how to automatically transform a tail-recursive function into a simple loop, the Java specification doesn't require that this transformation be made. Presumably, one reason it is not a requirement is that, in general, the transformation can't be made statically in an object-oriented language. Instead, the transformation from tail-recursive function to simple loop must be done dynamically by a JIT compiler.

It then gives an example of Java code that won't transform.

So, as the example in Listing 3 shows, we cannot expect static compilers to perform transformation of tail recursion on Java code while preserving the semantics of the language. Instead, we must rely on dynamic compilation by the JIT. Depending on the JVM, the JIT may or may not do this.

Then it gives a test you can use to figure out if your JIT does this.

Naturally, since this is an IBM paper, it includes a plug:

I ran this program with a couple of
the Java SDKs, and the results were
surprising. Running on Sun's Hotspot
JVM for version 1.3 reveals that
Hotspot doesn't perform the
transformation. At default settings,
the stack space is exhausted in less
than a second on my machine. On the
other hand, IBM's JVM for version 1.3
purrs along without a problem,
indicating that it does transform the
code in this way.

Does Java 8 have tail call optimization?

As far as I know Java 8 does not have tail call optimization. Afaik it isn't related to the actual compiler trick, because that one is simple, but to preserve a callstack for security purposes. But I guess it would be possible with a bytecode rewriter.

Tail Call Optimisation in Java

Why can't Java use the same approach ?

I can't say which approach will be used, but it's better-explained in Project Loom's proposal:

As adding the ability to manipulate call stacks to the JVM will undoubtedly be required, it is also the goal of this project to add an even lighter-weight construct that will allow unwinding the stack to some point and then invoke a method with given arguments (basically, a generalization of efficient tail-calls). We will call that feature unwind-and-invoke, or UAI. It is not the goal of this project to add an automatic tail-call optimization to the JVM.

As far as I've heard, work has not yet begun on tail calls, as Fibers and Continuations seem to currently be a higher priority.

Does java support and optimize away tail-recursive calls?

Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)

But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.

Look at this:

int sum(List<Integer> integers) {
    return sum(integers, 0);
}

int sum(List<Integer> integers, int sumSoFar) {
    if (integers.isEmpty())
        return sumSoFar;
    else
        return sum(
                integers.subList(1, integers.size()),
                sumSoFar + integers.get(0)
        );
}

See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.

In your snippet the stack frame would probably have to exist as long as the recursive call..

Why can't tail calls be optimized in JVM-based Lisps?

Real TCO works for arbitrary calls in tail position, not just self calls, so that code like the following does not cause a stack overflow:

(letfn [(e? [x] (or (zero? x) (o? (dec x))))
        (o? [x] (e? (dec x)))]
  (e? 10))

Clearly you'd need JVM support for this, since programs running on the JVM cannot manipulate the call stack. (Unless you were willing to establish your own calling convention and impose the associated overhead on function calls; Clojure aims to use regular JVM method calls.)

As for eliminating self calls in tail position, that's a simpler problem which can be solved as long as the entire function body gets compiled to a single JVM method. That is a limiting promise to make, however. Besides, recur is fairly well liked for its explicitness.

I get a StackOverFlowException on this code because my JVM doesn't support tail call optimizaion, right?

No JVM that I'm aware of supports tail call optimization. This is not an oversight. Apparently this optimization has significant consequences for Java reflection and Java security managers.

References:

• "Tail calls in the VM" by John Rose @ Oracle.
• Bug 4726340 - RFE: Tail Call Optimization

F# has tail call elimination?

The problem with Proper Tail Calls in Scala is one of engineering trade-offs. It would be easily possible to add PTCs to Scala: just add a sentence to the SLS. Voilà: PTCs in Scala. From a Language Design perspective, we are done.

Now the poor compiler writers need to implement that spec. Well, compiling into a language with PTCs is easy … but unfortunately, the JVM byte code isn't such a language. Okay, so what about GOTO? Nope. Continuations? Nope. Exceptions (which are known to be equivalent to Continuations)? Ah, now we are getting somewhere! So, we could use exceptions to implement PTCs. Or, alternatively, we could just not use the JVM call stack at all and implement our own stack.

After all, there are multiple Scheme implementations on the JVM, all of them support PTCs just fine. It's a myth that you cannot have PTCs on the JVM, just because the JVM doesn't support them. After all, x86 doesn't have them either, but nonetheless, there are languages running on x86 that have them.

So, if implementing PTCs on the JVM is possible, then why doesn't Scala have them? Like I said above, you could use exceptions or your own stack to implement them. But using exceptions for control flow or implementing your own stack means that everything which expects the JVM call stack to look a certain way would no longer work.

In particular, you would lose pretty much all interoperability with the Java tooling ecosystem (debuggers, visualizers, static analyzers). You would also have to build bridges to interoperate with Java libraries, which would be slow, so you lose interop with the Java library ecosystem as well.

But that is a major design goal of Scala! And that's why Scala doesn't have PTCs.

I call this "Hickey's Theorem", after Rich Hickey, the designer of Clojure who once said in a talk "Tail Calls, Interop, Performance – Pick Two."

You would also present the JIT compiler with some very unusual byte code patterns that it may not know how to optimize well.

If you were to port F# to the JVM, you would basically have to make exactly that choice: do you give up Tail Calls (you can't, because they are required by the Language Spec), do you give up Interop or do you give up Performance? On .NET, you can have all three, because Tail Calls in F# can simply be compiled into Tail Calls in MSIL. (Although the actual translation is more complex than that, and the implementation of Tail Calls in MSIL is buggy in some corner cases.)

This poses the question: why not add Tail Calls to the JVM? Well, this is very hard, due to a design flaw in the JVM byte code. The designers wanted the JVM byte code to have certain safety properties. But instead of designing the JVM byte code language in such a way that you cannot write an unsafe program in the first place (like, say, in Java, for example, where you cannot write a program that violates pointer safety, because the language just doesn't give you access to pointers in the first place), JVM byte code in itself is unsafe and needs a separate byte code verifier to make it safe.

That byte code verifier is based on stack inspection, and Tail Calls change the stack. So, the two are very hard to reconcile, but the JVM simply doesn't work without the byte code verifier. It took a long time and some very smart people to finally figure out how to implement Tail Calls on the JVM without losing the byte code verifier (see A Tail-Recursive Machine with Stack Inspection by Clements and Felleisen and tail calls in the VM by John Rose (JVM lead designer)), so we have now moved from the stage where it was an open research problem to the stage where it is "just" an open engineering problem.

Note that Scala and some other languages do have intra-method direct tail-recursion. However, that is pretty boring, implementation-wise: it is just a while loop. Most targets have while loops or something equivalent, e.g. the JVM has intra-method GOTO. Scala also has the scala.util.control.TailCalls object, which is kind-of a re-ified trampoline. (See Stackless Scala With Free Monads by Rúnar Óli Bjarnason for a more general version of this idea, which can eliminate all use of the stack, not just in tail-calls.) This can be used to implement a tail-calling algorithm in Scala, but this is then not compatible with the JVM stack, i.e. it doesn't look like a recursive method call to other languages or to a debugger:

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
 if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcall(fib(n - 1))
    y <- tailcall(fib(n - 2))
  } yield (x + y)

fib(40).result

Clojure has the recur special form, which is also an explicit trampoline.

Opt-in tail call support in the JVM on a per-language base?

Yes, this is technically possible -- in fact there an experimental patch by Arnold Schwaighofer for OpenJDK which does just that, although it isn't easy to apply the patch and build, as it isn't kept up to date at present.

An explicit tail call instruction has advantages over transparent optimisation of function calls in tail position by the JVM, as the JVM can verify that what you have specified as a tail call really is see this tail call blog post by John Rose for an explanation of some of the verification which can by done.

I think the future of the JVM is not Java, and I hope that someone with the time and talent pushes tail calls for the JVM forward.

---

Related Topics