Name: gm110360			Date: 08/05/2002


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) 
======================================================================