AST, Bytecode and the In Between: An Exploration of Interpreter Design Tradeoffs

Programming language interpreters usually interpret either an abstract syntax tree (AST) or bytecode (BC). An AST can be a tree of objects, which may be slow to interpret, while bytecode is a compact encoding that can give better run-time performance.

However, defining the key characteristics of both interpreter designs is not straightforward. If the AST is encoded using an array instead of a pointer-based structure, is it still an AST interpreter? If bytecodes are represented as objects instead of compact bytes, is it still a bytecode interpreter?

In this paper, we explore the different design dimensions for the implementation of interpreters and discuss their tradeoffs and how they relate to AST and bytecode-based designs. They create a spectrum from benefiting from the host language to minimizing distance with the target machine. From the discussion, we derive guidelines for interpreter designs that enable implementers to navigate the tradeoff space between performance, engineering, tooling support, and language needs.

Finally, we discuss common optimizations that are independent of the program representation to demonstrate the performance of an optimized AST interpreter and bytecode interpreter implemented in Rust. While the bytecode interpreter is slightly faster, the difference is small, and we find the discussed optimizations to be more relevant for performance than the program representation, which we argue gives implementers more freedom in choosing a point in the design than generally assumed.