Engineering Definitional Interpreters
A definitional interpreter should be clear and easy to write, but it may
run 4–10 times slower than a well-crafted bytecode interpreter.
In a case study focused on implementation choices, we explore ways of
making definitional interpreters
faster without expending much programming effort.
We implement, in OCaml,
interpreters based on three semantics for
a simple subset of Lua.
We compile the OCaml to x86 native code,
and we systematically investigate hundreds of combinations of
algorithms and data structures.
In this experimental context,
our fastest interpreters are based on natural semantics; good
algorithms and data structures make them 2–3 times faster than
interpreters.
Our best interpreter, created using only modest effort,
runs
only times slower than a mature bytecode interpreter
implemented in C.
Full and extended papers
The paper is available as
US Letter PDF (247K) and
US Letter TeX DVI (180K).
There is also an
extended version with many data tables
(PDF and
DVI).
Source code
We provide a compressed tarball containing
source code and test
infrastructure.