FULL PRODUCT VERSION :
java version "1.4.1-beta"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1-beta-b14)
Java HotSpot(TM) Client VM (build 1.4.1-beta-b14, mixed mode)

This RFE would be useful on all OSes.

A DESCRIPTION OF THE PROBLEM :
Suppose function A calls function B, and function B, as its
last action, calls function C. The call to C is a "tail-
call" because it occurs in the "tail" position (at the end)
of function B.

When this happens, function B's call frame remains on the
stack, preventing any of B's temporary objects from being
garbage-collected, and also consuming stack space. When
function C returns, function B will simply return the same
value to A that C returned to B. The extra return also
wastes a few nanoseconds.

Thus, it would be a useful optimization for the compiler to
detect that the call to C is B's last action, and produce a
VM instruction that would go ahead and destroy B's stack
frame before the call, and set up C to return directly to
A. (It would look to function C as if A had called it -- if
C could ever tell, which it can't.)

This is tail-call optimization.

It would be useful for a few reasons.

First, it would make it possible to write programs in
a "continuation-passing" style where functions never return
but instead always end by tail-calling other functions. On
current JVMs, such programs would quickly overflow the
stack. It is not necessary that they do so.

Second, it makes it possible to express iterative functions
in a syntactically recursive way. Sometimes the recursive
version is more intuitive and easier to understand (and
easier to debug) than the iterative version.

Third, the optimization might make garbage collection more
efficient, because it allows some "dead" variables to be
converted to garbage sooner. Imagine the savings tail-call
optimization would afford if function B allocated a huge
temporary array before calling function C.

It is important to note that this change would only affect
the compiler and the Java Virtual Machine -- it would NOT
affect the Java language or API in any way at all. It would
not affect native interfaces. Existing .java files would
compile and run exactly the same as before, but possibly
with greater efficiency. Existing .class files would
continue to run on JVMs that supported the optimization,
but they would not take advantage of it. Intermixing .class
files that are compiled with and without the optimization
would do no harm. However, code compiled with the
optimization would not run on old JVMs.

Basically, statements of the form "return obj.functionCall
(...);" would be deemed tail-calls if they are legal Java
and are not lexically inside of a try{} clause.

It would be necessary to document this feature so that
programmers know it is there and can take advantage of it.

.NET's MSIL has a tail-call instruction, but I don't know
if the C# compiler actually uses it.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
// Here's a simple class that would benefit from tail-call
// optimization.

class TestClass
{ public static long factorial(int x)
  { return innerFactorial(1L, x); // tail-call
  }

  private static long innerFactorial(long sofar, int x)
  { if (x<=1) return sofar;
    return innerFactorial(sofar*x, x-1); // tail-call
  }
}
---------- END SOURCE ----------

CUSTOMER WORKAROUND :
The only work-around for the absence of this feature is to
iterate instead of using function calls, or to hope the
stack is big enough.
(Review ID: 160245) 
======================================================================

N/A

I can't fix this in the compiler because there is no way to express this
in the byte codes.

What's worse, there is a conflict in two quality-of-implementation issues
that this would introduce.  An exception stack trace is supposed to give the
call stack to the point where the exception was created, but the tail call
optimization throws away many stack frames.

In any case, the byte code specification would need to be expanded to support
this.

  xxxxx@xxxxx   2002-08-05

Tail call elimination is a neat thing, more for the elegant programming
idioms it enables than the actual optimization. The issue has come up
many times before (this is almost certainly a duplicate bug).
The Scheme community has raised this issue almost since the Java platform
was introduced.

As Neal says, this has nothing to do with the front end compiler.

I guess I should add some information about the complications.

One difficulty is
the question of whether there can be any guarantee that tail call
elimination will take place.

The way Java 2 security works, you need stack frames to keep track
of protection  domains. You cannot eliminate frames that cross
protection domains unless you change how that works. 

Of course, not all Java platforms implement Java 2 security (e.g., J2ME),
so the rules would vary from platform to platform.

Reflection relies on stack crawling to keep track of accessibility.

Debuggers can be attached dyanmically and are fond of looking up stacks.
So there has to be a way of turning this optimization off on the fly.

I beleive this could be done nonetheless, but it is not a small task.


  xxxxx@xxxxx   2002-08-05

One interesting special case to consider is self tail-calls:
tail calls to the current method. In the example, the first
tail-call is not of this kind because it is calling a
different method, but the second one is. It also happens
that it is the most interesting to optimize, because it
happens many times, while the first call only happens once.

Self tail-calls would be much easier to implement. The
difference is that instead of discarding arbitrary elements
in the stack, it will only collapse multiple entries of some
method into one. This might mean that there is no security
issue at all: if I understand correctly, security properties
can depend on the presence or absence of methods on the
stack, but not on the _number_ of occurences of a given method. 

When a stack trace is printed or inspected, it would still
look different if self tail calls were optimized. One
possibility is to declare that this is legal, maybe when a
certain property is set, to leave the choice to the users.
Another option would be to "fix" dynamically the stack: in
the stack frame of a method with a self tail-call, add an
integer counter for the number of nested calls. At each
call, increment that counter, set the local variables to the
arguments of the call, then jump to the method entry.
Additionally, catch all exceptions thrown during the
execution of this method, modify their stack trace by using
the value of the counter, then rethrow them. With this
behaviour, I believe the optimization would not incur any
visible change (appart from the speed-up and the absence of
some stack overflows). Of course modifying the stacks would
have some performance impact, but that should be smaller
than the speed-up (by not gorwing the stack, there will be
less cache misses).

General tail call optimizations would be great to have, but
self tail-call optimizations would already be good, so maybe
this is a good first step to take.

self-tail-call elimination can be done in the front end
(javac) with no help from the VM.  Anything much more
complex requires help from the VM.

Yes, self-tail-calls could be handled by javac. On the other
hand, there are many more compiler to bytecode than there
are JVM implementations (I write one, self-interest conflict
here :-), so it would be more economical to do it in the
JVM. Additionally, it would probably be natural to do so
during the native compilation phase anyway, and this would
lay the ground for a possible handling of general tail-call
optimization at the JVM level. An additional benefit is that
old compiled programs would benefit from the optimization too.

I think this is a very interesting feature,
But  I think that all the posible solutions should be compared:
- there could be and addition of new bytecode instructions,
which would need changes in the compiler and JVM.
- there could behavior requirements on the JVM specification
in cases of  an invoke_* call at the end of a code attrbute
block.

A very common idom that results in lots of tail calls is that of the proxy object. The method ultimately reached may be trvial, and the failure to perform tail-call optimisation has a siginicant impact on the cost of using proxies.

As a side note, the issue of tail call optimisation came up (repeatedly) during dicussions on the new Java memory model. It can result in an object becoming unreachable rather sooner than the developer expected, and can result in 'premature' finalization. This can be strange impacts on the release of native resources. The program is wrong anyway if it relies on knowing when the finalization will occur in this situation, but there are no doubt programs out there that are broken this way.

Tail call optimisation would be useful even if it only applied in cases where there caller and callee are guaranteed to be in the same security domain, and there are no annotations on the caller's frame at the point of the call.

I think that exception stack traces are a non-issue. It would be possible to print "(tail call)" in the trace. Already less information is provided for JITted methods than for interpreted methods; if you want to see full stack trace information when debugging a reproducible bug, you can run with the JIT turned off.

I don't see why changes to the byte code, or to front-end compilers, would be needed. The VM has enough information to tell whether any of the existing 'invoke' instructions are tail calls; a tail call is just an 'invoke' followed by a 'return'. (It doesn't even matter if the 'return' is separately reachable.) So there is no advantage in adding new instructions. There would be an advantage in changing the debugging *APIs* to turn off the optimisation for threads that are being debugged, though.

Clements and Felleisen has some interesting insights in
"A Tail-Recursive Machine with Stack Inspection".

<http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf>

Another common idiom that uses tail-calls is to implement automata. Although a more flexible way is to write an interpreter and encode the automaton in a data structure, in some cases hardcoding it and adding just a bit of extra logic to the standard definition of the automaton can make the code much shorter and easier to read.

Here's a very short illustration of the standard way to hardcode an automaton. For each state X you write:

Result processX() {
  i = readInput();
  switch (i) {
  outedge1: 
    produceOutput1();
    return processY1();
  outedge2:
    produceOutput2();
    return processY2();
...
  }
}