Tail call optimization in Java JDK 8?

[Tarek Chammah]

Thanks for the detailed exposition into what is required to get TCO
into the virtual machine.

I'm not aware of anyone looking to change the Java language, merely
the VM, for this.

Most people, including myself, who are clamoring for this do so for
the benefits traditionally derived for when functional languages have
been implemented with proper tail call support.  Arnold Schwaighofer
indicated this in his thesis.  Matthias Felleisen mentioned the
pitfalls for what happens when code made to follow proper design is
implemented in a language (object oriented design patterns in Java, in
this case) which doesn't support TCO in his ECOOP talk, cited on the
Why Tailcalls wiki.

In this context Doug Lea's motivation for TCO in support of multi-core
and multi-tasking seems like an outlier for why many of us want it in
the JVM, but understandable in light of his work on better concurrency
facilities.

Major languages running on the JVM that would benefit from it include
Clojure, Python, Ruby, Scala, Scheme, etc.

Moving it from an implementation detail, "soft" tail calls as it were,
into the JVM proper, is I feel a requirement for first class support
for functional languages and for the Java ecosystem to better support
dynamic and scripting languages that feature rich expressiveness which
don't want to be heavily penalized depending on which JVM
implementation happens to be running.

Sincerely,

Tarek


John Rose wrote:
> 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!