What I would do with the open-sourced JVM
Monday December 11, 2006 by Derek Young
My first reaction to the news that Sun has open sourced java was, well, who cares?. Sun has worked hard at improving Java performance, and more recently functionality, so will this new open source license really make a difference?
One thing that I believe could change however, is the introduction of features Sun has stated they will not implement. One interesting feature I would like to see is the the introduction of tail call optimization (TCO). With TCO, If the last statement in a function (let’s say foo) is a call to another function (bar), the standard call can be replaced with a jump. The stack is adjusted so that when bar returns, it returns directly to foo’s caller. This optimization allows functions to call each other infinitely without returning, which would otherwise quickly lead to a stack overflow.
TCO allows the programmer to use recursion in place of iteration. It also allows programs to be written in Continuation Passing Style (CPS), where each function call is passed a new argument called the continuation, a function representing what to do next that is called when the function completes. With CPS, functions never return, they always call a the continuation. This is impossible without tail calls.
Neither of these uses are very exciting for Java programmers, but many interesting languages use these concepts heavily, and are impossible to translate into C style function calls. Scheme, Haskell, and ML based languages like OCaml all require tail calls, and are impossible to implement efficiently without them. These all have their own compilers or virtual machines. Some of these (like OCaml) are very fast, others (Haskell) are not. Ruby supports continuations (at least for now) . Continuations are the key to one of the most innovation web frameworks, Seaside.
Both Java and Microsoft’s .NET have spent considerable time getting garbage collection and just in time compilation right, and both produce reasonably fast code (especially when compared to virtual machines or compilers of other languages). Supporting tail call optimization would allow the JVM to be used as a runtime for a much broader set of interesting languages.
Sun has basically stated that they will not work to support tail calls in part because by messing with the stack you can no longer walk it and make security checks. Microsoft has also used this as an explanation of why their tail calls (marginally supported in .NET) are inefficient or disabled when security checks are required. They also have pointed out why tail calls are hard when using accurate garbage collection
While I understand the implementation issues are real, I don’t believe they’re insurmountable. The Sun bug I referenced early has an interesting link to a recent paper titled A Tail-Recursive Machine with Stack Inspection that starts with the following enticing abstract:
Security folklore holds that a security mechanism based on stack inspection is incompatible with a global tail call optimization policy; that an implementation of such a language must allocate memory for a source-code tail call, and a program that uses only tail calls (and no other memory-allocating construct) may nevertheless exhaust the available memory. In this article, we prove this widely held belief wrong. We exhibit an abstract machine for a language with security stack inspection whose space consumption function is equivalent to that of the canonical tail call optimizing abstract machine. Our machine is surprisingly simple and suggests that tail calls are as easy to implement in a security setting as they are in a conventional one.
If Sun is unwilling to implement TCO, does an open source JVM mean it might be possible to implement this long awaited feature without their blessing?
Toward a mouseless work environment Most useful overlooked Java APIs