Exploring the Implementation Space of Abstract Syntax Tree and Bytecode Interpreters

Programming language interpreters are often the first choice when implementing a new language, and many well-established dynamic language implementations rely on them, such as Java, JavaScript, Ruby, and Python. Interpreters run code by compiling it to some program representation, then executing this representation at the software level.

Out of all possible interpreter designs, bytecode (BC) interpreters are often considered the fastest thanks to their compact and linear representation. This often overlooks other designs, such as abstract syntax tree (AST) interpreters, and the variety of hybrid designs that are neither clearly AST nor BC. Interpreter design is influenced by several constraints and opportunities, such as the mechanisms provided by the host language (in which the interpreter is written), the requirements of the guest language (the language being executed), but also available engineering effort, or hardware constraints. Overall, when implementing an interpreter, the number of viable design decisions may appear more limited than it truly is.

Therefore, this thesis endeavors to explore the implementation space of interpreters, to help provide a stronger understanding of the available high-level designs, design decisions, as well as their engineering and performance benefits. We focus on the design and performance of AST interpreters and BC interpreters for the SOM language, implemented on top of meta-compilation frameworks, and written in the Rust system-level language. We also describe approaches that lie somewhere in between ASTandBC,andweidentify key design dimensions for designing and discussing interpreters. Our results find that in terms of run-time performance, AST designs can rival BC designs on top of meta-compilation frameworks, and are not far behind in interpreters using the Rust language. We also find that the meta-compilation context can push BC designs closer to AST designs, while relying on Rust can push AST designs to be closer to BC instead. We synthesize our analysis by providing recommendations for interpreter design, based on the requirements, constraints, and opportunities of the runtime system in question. We hope this work encourages language implementers to explore a wider range of designs, and assists in opting for design decisions that best meet their specific needs and requirements.