Master Theses


Run-time byte code compilation, optimization, and interpretation for Alice

Christian Müller

Advisor: Guido Tack

Responsible Professor: Gert Smolka

On this page you can find some information about my Diplom thesis. The following picture shortly approximates the topic of my work. Read below for a more detailed description.


Conceptual Formulation


Run-time byte code compilation, optimization and interpretation for Alice


Alice is a functional programming language based on Standard ML, extended with support for concurrent, distributed, and constraint programming. It is implemented as a full-featured, open-source programming system based on a generic virtual machine library called Seam. One key feature of the system is that code is communicated in a high-level platform independent format, called the Alice Abstract Code. The system ensures efficient execution by providing run-time compilation to native code.
Run-time compilation (often called just-in-time or JIT compilation) is particularly well-suited for Alice: A static compiler can only apply moderate optimizations because components are linked dynamically. A run-time compiler can be reflective and take advantage of its greater knowledge of the current state of the system. For instance, an application of a primitive integer addition can be inlined as soon as it is known that the identifier + actually represents integer addition.
Run-time compilation to native code, on the other hand, has three severe drawbacks: Debugging of the system becomes much more complicated, porting the system to other platforms is difficult, and generating efficient code requires deep knowledge of the underlying platform. The goal of this project is hence to develop a run-time compiler that generates byte code instead of native code, and to implement a highly optimized interpreter for that byte code.

The project involves three major work packages:
  1. Design of the byte code
  2. Design and implementation of a run-time compiler
  3. Design and implementation of a byte code interpreter
The design of the byte code should be concise, well-documented and leave room for run-time optimizations. Both run-time compiler and interpreter will be implemented using the Seam architecture, which provides all the low-level services for a virtual machine as well as mechanisms for plugging in run-time compilers and interpreters.

The criteria of success are
  1. A well-documented and well-understood byte code for Alice
  2. An efficient, optimizing run-time compiler
  3. An efficient, optimized byte code interpreter
We would like to confirm our hypothesis that, given these three criteria, the resulting performance of the system will at least equal the current architecture that is based on native code. Our hope is that thanks to a clear design, a lot of optimizations can be applied at run time that allow for even better performance.

A possible direction for future work, whether within this project or as a follow-up, could be to investigate the borderline between interpreted byte code and native code. A different backend for the run-time compiler could be used to generate simple native code by inlining calls to the byte code interpreter. It should be interesting to see how different degrees of inlining affect the system performance.


Christian Müller, 03.04.2006