RE: [Caml-list] How to write an efficient interpreter

["Jon Harrop" <jon@ffconsultancy.com>]

If the language you are interpreting is quite declarative then piggy-backing
on OCaml's run-time either by writing an interpreter or by compiling to
OCaml code will be a big advantage. Writing a VM with a run-time as
efficient as OCaml's in this context is a *lot* of work compared to writing
an interpreter.

Unless there is a compelling reason not to, I'd stick with an interpreter
and just optimize it carefully. In particular, pay careful attention to your
data representations. When writing a term-rewriter, one of the biggest
performance gains I got was putting the value of each variable in the
variable itself so it could be looked up by dereferencing a pointer rather
than going via a hash table. Symbol tables are useful for similar reasons:
map identifiers onto small integer IDs and replace hash tables that have
identifiers as keys with an array indexed by ID. Beware the write barrier
though.

Also, when profiling I'd recommend logging the "kinds" of inputs your
interpreter sees. For example, try to spot patterns in the shapes of
expressions that your interpreter deals with and add special cases to the
expression type for those shapes and custom code to interpret them.

Cheers,
Jon.