On the Design and Implementation of a Virtual Machine for Process Calculi
Luís Lopes
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150 Porto, Portugal
Dezembro de 1999
Abstract
There has been an ever growing interest in the study of
process-calculi as frameworks for concurrent, distributed,
object-oriented languages. These are of particular importance given
the adequacy of the object programming model and its widespread use in
software development and, ultimately, in Internet applications. The
asynchronous
pi-calculus is a powerful tool to reason about
concurrent process interaction. However, it is not an adequate
framework for the implementation of object-oriented languages as its
encodings of objects are quite inefficient. Efforts in the
implementation of languages based on process calculi have so far
failed in providing a unifying framework in the form of a virtual
machine specification.
This thesis introduces a virtual machine specification and its
implementation for a variant of the pi-calculus -- the TyCO
calculus. TyCO features objects and asynchronous messages. Thus,
contrary to other calculi such as pi, objects are builtin
entities and do not require computationally expensive encodings.
This work starts with the definition of a small kernel language
based on TyCO and provides its static semantics, in the form of a
type-inference system, and its dynamic semantics, in the form of an
abstract machine. This formal framework forms the basis for the
design of a virtual machine and language compiler. The virtual machine
runs TyCO programs translated into byte-code format. It is compact,
architecture independent and performs favorably when compared with
other related implementations. The machine is fine-tuned for TyCO but
may be used to implement other calculi with minor changes or
extensions to its semantics.
Finally, an orthogonal extension of the TyCO calculus is defined to
provide support for distributed computations and code mobility. In
this model, remote communication and code migration are induced by the
lexical scope of names in the base calculus. The model can be applied
without change to a wide variety of calculi that fulfill a few, very
mild, conditions.