Tail call optimization in Java JDK 8?

[John Rose]

On Oct 5, 2010, at 12:59 PM, Tarek Chammah wrote:

> One particular feature I was thinking of under the ++ column is
> support for tail call optimization.  This particular Da Vinci
> sub-project is apparently not fully engineered and spec'ed at the
> moment.  But I was thinking with the recent rearrangement of the
> releases, if it could be developed for the JDK 8 release?

Three things are needed to make tailcall part of Java:  Engineering, design, standardization.  All of those things require cooperation, time, and sustained effort.

The first two have been strongly started by Arnold Schwaighofer for his thesis.  (This was an outstanding example of community contribution to the OpenJDK.)  This is the code in the patch repository.  The third (standardization) has not been started.  The JSR 292 EG is occupied with other problems (notably invokedynamic), and probably cannot take up tailcall.  

The standardization work is tricky, since it seems to need an Expert Group with power and expertise to change both the VM (tailcall prefix) and language ("goto" keyword or whatever).  This is a broad area to change.  Perhaps just the JVM changes could be done with language changes "to follow sometime", as with invokedynamic; that would be a political compromise.

I think a new EG needs to form to push all three fronts, including (uniquely) standardization.  The EG would have to include implementors of at least two major JVMs, plus implementors of at least two major languages that propose to use the new feature.

In order to form such an EG (as the JCP is structured), several JCP members need to agree that this is a problem worth spending time on, approve (vote for) the formation of the EG, and look favorably on its work product when the time comes to approve of the standard.  Note that JCP members are mostly corporate.  So this means having a few companies like IBM, Oracle, and Google agree that this is a good thing, and no other big players raising serious objections.

Regarding engineering:  Arnold's patch, needs re-integration with JDK 7, especially after method handles, which provide highly non-trivial new invocation paths that would need to maintain the new stackless invariants.  Not impossible, but tricky.  Also, productizing it will require one or more engineers with at least a year or two experience on the respective JVMs.  Such engineers are (sadly) in short supply.  Learning a JVM (such as HotSpot) is something that takes many months of coaching.

Regarding design:  Arnold's thesis probably needs an update relative to JSR 292, and some critical examination.  I don't think it's wrong, but the security aspects need expert community review.

The important thing is for people to articulate the motivations and use cases for tailcalls, not just as a Cool Thing, but as a useful and needful thing on the JVM.  Here are some comments along those lines which I collected from this year's JVM Language Summit:
  http://wiki.jvmlangsummit.com/Why_Tailcalls

Such motivations and use cases need to be communicated to the decision makers of our various organizations, and business-oriented (economic) justifications need to be made.  Probably the most powerful motivation is the prospect that tailcalls can make massively multitasked code scale better, by somewhat loosening the entanglement between a task and the thread it rides on.  

(Complete disentanglement seems to require moveable coroutines, but probably this is not necessary in most cases.  Tasks can be designed in most cases to return quickly and not make recursive requests.)

Doug Lea has pointed out (at this year's JVM Language Summit) that task schedulers do not want to recursively call their tasks, but rather delegate to them.  This allows control to pass symmetrically between a task (at least, its top-level structure!) and the scheduler that administers a thread/CPU.  That cannot be done without hard tail calls.  And, the lack of such an ability, according to Doug, distorts the API itself.  It's an instance of what Mattias Felleisen pointed out in 2004, that many design patterns (in this case, workers/tasks) don't actually work in an OO fashion unless you have hard tail calls.  How do they fail?  Well, they work fine in the lab, but as soon as you hand them a large data set, they tangle the stack up into an overflow.  It's a scaling problem.

Here's a fuller discussion of the connections between tail calls and OO patterns, with a comment from Mattias:
  http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion

Best wishes,
-- John

P.S. Not to dilute the present thread, but:  Some of these same points apply to other JVM ideas aimed at increasing scalability of large systems.  Such ideas include value types (tuples, structs, whatever), hybrid arrays, coroutines, and typestate.

P.P.S.  Disclaimer:  The JSR 292 EG and I are trying to close down invokedynamic and method handles for JDK 7, so I'm not going to be very responsive to this thread.  Sorry in advance!