Java Chases Its Tail Calls

John Rose talks about implementing support for tail call optimization in the JVM. I've been waiting for this one, as in my mind, it has long been one of the biggest holes in the leaky dike of Java's implementation.

The optimization can be illustrated very succinctly. Imagine a function Max() that returns the maximum value in a given list. Remembering that Head() returns the first value of a list, Tail() returns the rest of the list minus the first value, and Length() returns its length, we would likely end up with something like this:

function Max(list, current_max)

   if Length(list) == 0 do
      return current_max
   end

   if current_max 

At each step, we can see that the return value of the current call can be gained directly from the value returned from the recursive call. With this observation, it's straightforward to see that recursion can be turned into iteration, doing away with the need to allocate stack space for each inner function call. A possible tail call optimization might be along the lines of:


function Max(list, current_max)

   while Length(list) > 0 do
      if current_max 

In modern programming languages, this can all occur under the hood of the compiler. It gives
programmers the luxury of functional problem solving: thinking in terms of recursion without
any cause for performance anxiety. The lack of support for this optimization has been a serious
roadblock for implementing dynamic functional languages on the JVM. Nobody would seriously
consider building a Scheme-like recursive language if the call-stack of the underlying platform
was going to be gobbled up by tail calls; this enhancement paves the way for language developers
as well as new extensions and improvements to the Java language itself.

It's fantastic that Sun seem to be serious about pushing Java to it's full
potential. I've been waiting a long time to see J2EE die, and Java start to be treated as a means
to an end, rather than an end in itself.