Does the JVM prevent tail call optimizations?

Question

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?

Answer 1

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.

Answer 2

The fundamental limitation is simply that the JVM does not provide tail calls in its byte code and, consequently, there is no direct way for a language built upon the JVM to provide tail calls itself. There are workarounds that can achieve a similar effect (e.g. trampolining) but they come at the grave cost of awful performance and obfuscating the generated intermediate code which makes a debugger useless.

So the JVM cannot support any production-quality functional programming languages until Sun implement tail calls in the JVM itself. They have been discussing it for years but I doubt they will ever implement tail calls: it will be very difficult because they have prematurely optimized their VM before implementing such basic functionality, and Sun's effort is strongly focused on dynamic languages rather than functional languages.

Hence there is a very strong argument that Scala is not a real functional programming language: these languages have regarded tail calls as an essential feature since Scheme was first introduced over 30 years ago.

Answer 3

Scala 2.7.x supports tail-call optimization for self-recursion (a function calling itself) of final methods and local functions.

Scala 2.8 might come with library support for trampoline too, which is a technique to optimize mutually recursive functions.

A good deal of information about the state of Scala recursion can be found in Rich Dougherty's blog.

Answer 4

In addition to the paper linked in Lambda The Ultimate (from the link mmyers posted above), John Rose from Sun has some more to say about tail call optimization.

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

I have heard that it might be implemented on the JVM someday. Tail call support amongst other things are being looked at on the Da Vinci Machine.

http://openjdk.java.net/projects/mlvm/

Answer 5

All sources point to the JVM being unable to optimize in the case of tail recursion, but upon reading Java performance tuning (2003, O'reilly) I found the author claiming he can achieve greater recursion performance by implementing tail recursion.

You can find his claim on page 212 (search for 'tail recursion' it should be the second result). What gives?