Lambda the Ultimate

There's an unofficial list of the proposals for the next version of Java and the JVM. TCO isn't on the list. This is particularly strange since one of the hot topics for Java 7 is closures which, if implemented, will naturally lead people to experiment with functional control structures.

Apparently Scala solves the tail call issue in its actors by using exception throwing under the hood as a form of trampolining.

Actors that Unify Threads and Events -

When the receiving closure terminates, control is returned to the sender by throwing a special exception that unwinds the receiver’s call stack.

However, that doesn't solve the general problem. In my ongoing tutorial on monads in Scala I ported Haskell's IO monad but got burned by the lack of TCO. That's solvable, but messy.

In other Lisps, SISC uses its own heap based stack (with a performance penalty) and Kawa optionally uses a trampolining system (also with a performance hit).

Actually James, tail-call optimization has been discussed and is on the list, just a bit hidden under the JSR 292 invokedynamic category, which is kind of serving as a catch-all for JVM enhancements.

John Rose at Sun is leading the charge in this area. He's blogged about tail calls in the past as well. Actually, he's started a new OpenJDK project called the Multi-Language VM project, which will be used specifically to flesh out new ideas for JSR 292 such as invokedynamic and tail call optimization. You can read a little more here or in this mailing list post.

Oops, didn't think read beyond the title "invokedynamic." Thanks for the pointer.

It'd be interesting to know what's planned related to the security issue connected to TCO (Java's security policy apparently depends on stack inspection). There was previously some discussion of this in connection with Clements & Felleisen's A Tail-Recursive Machine with Stack Inspection.

After chasing all the links that puredanger posted I found very little substantiative in the way of plans. In fact, JSR 292 is still only about invokedynamic. Tail calls are only unofficially discussed in other spots. The appearance is that at best this is in the very early stages and at worst it's not a real contender for the next version.

I have seen discussions of two alternatives:

1) Implement a system like the paper you reference. This likely means a significant overhaul of the security code in the JVM.
2) Implement something more along the lines of what the CLR does: only optimize away stack frames that don't have security implications.

I wouldn't be surprised if the near term answer is #2 since that's likely a much more conservative change to the JVM code base. However, it does lead to some real difficulty in determining why one piece of tail calling code still causes stack growth and overflow while a another apparently similar bit of code is well behaved.

Not sure if it's worth mentioning that Neil Gafter has a prototype implementation of Java closures available. On my list of things to check out.

Clojure does support mutual recursion in top-level functions, but not letrec, although I might yet add it. I posted an idiomatic version in Clojure.

I posted an idiomatic version in Clojure.

It's surprisingly clean especially given that you didn't define new macros to do it. I haven't studied Clojure yet it's pretty clear and probably clear to anybody with any Lisp experience.

Clojure does support mutual recursion in top-level functions

When you say top level functions can be mutually recursive, do you mean that they can be mutually recursive without growing the stack, or do you just mean they can be defined in terms of each other without confusion? If the former, how did you implement it?

Just the latter I'm afraid. As discussed above, Clojure shares with Java a lack of TCO.

IIUC, OpenQuark compiles to JVM bytecodes and implements TCO with no special constructs in the language.

The docs say:

In addition, the CAL runtime has the following optimizations:

• compiles tail recursive functions as loops

Which is not the same thing as global tail call optimization.

Of course it's possible to do TCO on the JVM, providing one is willing to superimpose some language-specific trampoline/CPS/heap-based-stack/interpretive/etc mechanism on top of the native calling mechanism of the JVM. This may involve tradeoffs with performance and/or interoperability.

For languages which use the native call mechanism, TCO will have to come from the JVM itself. I await it eagerly!