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?

Popelka

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.

Arrowwood

I did not quite follow the explanation. I thought tail-call optimization was implemented by the compiler. Assuming you have a function that could be tail-call optimized by the compiler, you could also then have an equivalent non-recursive function that implements the same functionality using a loop, correct? If so, couldn't this be done by the compiler. I am not able to follow the dependence on the JVM. How does this compare with a Scheme compiler that generated native i386 code? – Orbicular

Ok, just saw Jon's answer below. So, it's not that it cannot be implemented, its that it cannot be implemented with proper debugger support – Orbicular

@Gautham: My statement about debugging was in reference to using trampolines as a workaround for the lack of tail call elimination on the JVM. Tail call elimination can and has been implemented on the JVM (Arnold Schaighofer did in in OpenJDK, and also LLVM) so there is no question as to whether or not it can be done. Microsoft's CLR has, of course, supported tail call elimination for 10 years and the release of F# has demonstrated that it is a game changer. I think the answer is that the JVM has long since stagnated. – Bung

This is a common misconception and an oft-repeated excuse, but is incorrect. It has been well-established for a number of years that security by stack inspection (and provision of useful stack traces) is not incompatible with proper tail calls. For example, see this paper from 2004. citeseerx.ist.psu.edu/viewdoc/… Downvoting, as the answer is incorrect. – Hexagram

@JustinSheehy: What is incorrect? The question was, "Does the JVM prevent tail call optimizations?" And the answer is, "No, but it's hard." – Arrowwood

do you know if in java8 this is included? – Humanism

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.

Bung

Hence there is a very strong argument that Scala is not a real functional programming language - the argument is actually quite weak. Sure are tail calls [as] an essential feature, and nice if the underlying hardware (or virtal machine) supports it directly. But it's implementation details. – Cradlesong

@Ingo: Only if you don't consider stack overflows in your program at run-time seen by the user to be a significant problem. According to its bug tracker, even the Scala compiler itself has been plagued with stack overflows. So even the most seasoned Scala developers are still getting it wrong... – Bung

It is ok to be an advocate of, say F#. But I've noted you for a long time (even years before in usenet) for being hostile to everything that is not F#, and yet your elaborations show that you don't know what you're talking about. Like here: your argument seems to be that a language where I can write a program that aborts with stack overflow is not a functional one? But couldn't the same argument be made for languages where I can provoke heap overflow? Hence, the holy F# itself would not count as functional. – Cradlesong

@Ingo: "your argument seems to be that a language where I can write a program that aborts with stack overflow is not a functional one". On the contrary, you can write programs in almost all functional languages that stack overflow, e.g. Scheme, OCaml, F#, Haskell. – Bung

@Ingo: "But couldn't the same argument be made for languages where I can provoke heap overflow? Hence, the holy F# itself would not count as functional". By that classification, no languages would be "functional". Such classifications are not very useful. Formally, it has zero information content... – Bung

So what exactly was the difference that makes Scala alledgedly non-functional? – Cradlesong

@Ingo: Several idioms in functional programming, like mutual recursion and continuation passing style, can require tail call elimination to work. Without it, your programs will stack overflow. If a language cannot run idiomatic functional code reliably, is it functional? The answer is a judgement call, as you say, but an important distinction in practice. Martin Trojer just published an interesting blog post about this: martinsprogrammingblog.blogspot.com/2011/11/… – Bung

@Ingo: For example, when matching orders for physical commodities in financial markets you need to be able to satisfy volume requirements such as "enough crates to fill exactly one boat" which is the 0-1 knapsack problem. Zach Bray of Trayport (the market leader in European power trading) wrote this blog post describing how they used continuation passing style to solve the problem elegantly in F#: zbray.com/2011/11/02/… – Bung

still, just because the JVM (regrettably, no question) can't do tail calls this does not mean that tail call elimination is impossible. This is so as if one stated that floating point calculations are only possible on computers with FPUs. – Cradlesong

@Ingo: Absolutely. I mentioned trampolines in my answer as well as the issues surrounding them. – Bung

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.

Dragone

Can you, please, update the question on current scala status? – Philine

@Philine AFAIK, nothing has changed, neither on Scala side, nor on JVM side. – Dragone

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/

Topfull

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?

Vex

IBM has supported some form of TCO in their JVM implementation (as an optimization, so no guarantees). Maybe the authors of Java Performance tuning thought this feature would eventually be implemented by all JVMs. ibm.com/developerworks/java/library/j-diag8.html – Hydrostatic