From Interpreter to Compiler and Virtual Machine: A Functional
Derivation
Mads Sig Ager
March 2003 |
Abstract:
We show how to derive a compiler and a virtual
machine from a compositional interpreter. We first
illustrate the derivation with two evaluation
functions and two normalization functions. We obtain
Krivine's machine, Felleisen et al.'s CEK machine,
and a generalization of these machines performing
strong normalization, which is new. We observe that
several existing compilers and virtual
machines--e.g., the Categorical Abstract Machine
(CAM), Schmidt's VEC machine, and Leroy's Zinc
abstract machine--are already in derived form and
we present the corresponding interpreter for the CAM
and the VEC machine. We also consider Hannan and
Miller's CLS machine and Landin's SECD
machine.
We derived Krivine's machine via a call-by-name CPS transformation and the CEK machine via a call-by-value CPS transformation. These two derivations hold both for an evaluation function and for a normalization function. They provide a non-trivial illustration of Reynolds's warning about the evaluation order of a meta-language. Available as PostScript, PDF, DVI. |