Engineering Definitional Interpreters

Jan Midtgaard and Norman Ramsey and Bradford Larsen

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.