A VM in Java with tail-calls and continuations

Friday, July 01, 2005

So... what does it do?

Another Virtual Machine!? What for?

Well, read the proposal yourself:

The goal of my project (it doesn't have a name yet, unfortunately) is the implementation of a JVM bytecode interpreter in Java. This interpreter, hereby called the “Secondary JVM”, will be executed by the JVM itself, hereby called the “Primary JVM”.

The “Secondary JVM” will not need to implement all the features of a standard JVM, since it can rely on the “Primary JVM” for things like class loading, bytecode verification, garbage collection and heap management. The “Secondary JVM” will however manage its own stack. This will allow the “Secondary JVM” to provide two popular features the Java Platform currently lacks: general tail call elimination and serializable continuations.

Tail call elimination (or optimization) is important since it opens up the possibility of a functional/recursion-oriented programming style. Continuations are even more fundamental, since it can be proved that all control structures can be implemented with continuations.

Having these two features implemented “at the VM level” (the “Secondary JVM” in this case) greatly simplifies the implementation of compilers for “functional” languages like Scheme or Ruby targeting the JVM, as well as the creation of web-application frameworks like Cocoon or RIFE.

The following web page, at IBM developerWorks, supports the idea of using continuations for the development of complex web-applications (Use continuations to develop complex Web applications); and, there's a long-standing RFE at Sun's Bug Database asking for the implementation of tail call elimination at the JVM level (Bug ID: 4726340 RFE: Tail Call Optimization).

The “Secondary JVM” will be just a regular Java object, probably implementing the Runnable interface. It will itself take a Runnable as a parameter on construction. Upon calling its run method, the “Secondary JVM” will interpret the run method of the Runnable it was constructed with. This interpretation will probably rely on some form of JIT compilation, but the “Secondary JVM” will keep its own stack. It will be possible to create multiple “Secondary JVMs”, and run them on separate threads.

Tail call elimination will be done by the “Secondary JVM”, and it will be possible to capture the execution state through the creation of Continuation objects - which will be serializable.

It will be important, though challenging, to respect the Java class-loading semantics.

Only methods tagged as “interpretable” will be run by the “Secondary JVM”, other methods will be delegated to the “Primary JVM” for execution. This tagging will probably be done through the use of annotations, and can be seen as somewhat similar to marking a method as native. There will be some restrictions on what methods can be tagged as “interpretable” - static constructors can't, and neither can native methods, obviously - it is not yet clear, however, the extent of these restrictions, though most methods will certainly qualify.

Programs using this library can be seen as a combination of methods specified to run on the “Primary” or “Secondary JVMs”. The execution of a Java program will always start on the “Primary JVM”, which may then create a “Secondary JVM” to run certain methods, benefiting from the provided features. The “Secondary JVM” can then delegate certain methods that do not require those features back to “Primary JVM” for performance.

The idea for this library came from the need to support these features (tail calls and continuations) in yet another Scheme-to-JVM compiler I might be creating next year for school. Thinking this might be equally useful to someone creating a Ruby-to-JVM compiler, for instance, I decided to code it as a separate library, and make it freely available. Google's “Summer of Code” may just be the incentive I need to have it finished during this summer. Irrespectively of the approval of this application, I will go forward with the project, which I intend to release under either the BSD or the Apache licenses.

Prototyping work on this project has already begun, and more intensive work will follow as soon as the examinations season at my University ends, in mid-July. At that time, I will probably apply for hosting at Sourceforge, or a similar site. By September, there must already exist a stable interface for all features, as well as a usable implementation. Whatever the state of the project in September, work on it will not stop by then. I intend to maintain the project, further improving it both performance- and feature-wise.

So, that's it! Keep tuned!

No comments: