Interpreter Architecture
Table of Contents
Definition
An interpreter is a program that directly executes another program, expressed in some source language, by evaluating its meaning. The standard architecture for a tree-walking interpreter has two stages:
- Parsing :: Converts surface syntax (character stream or s-expression) into an Abstract Syntax Tree (AST) — a structured, typed internal representation.
- Interpretation :: Recursively evaluates the AST, returning a value.
In tolk and PLAI the two stages are the parse and interpret (/ interp)
functions, composed by execute.
The Pipeline in PLAI and Tolk
| Stage | PLAI (plai-typed) | Tolk (Common Lisp) |
|---|---|---|
| Surface syntax | s-expression / read |
s-expression / CL reader |
| AST type | define-type variants |
defclass hierarchy |
| Parse | parse : s-exp → ArithC |
defgeneric parse |
| Interpret | interp : ArithC → number |
defgeneric interpret |
| Compose | manual | defgeneric execute |
Design principles
- Separation of concerns
- Parser and interpreter are separate functions. The parser handles syntax; the interpreter handles semantics. This allows the interpreter to be tested independently of parsing.
- Recursive structure
- Both parser and interpreter mirror the recursive structure of the AST. Each recursive AST constructor has exactly one case in each function. See trivia for the pattern-matching used in tolk's parsers.
- The template method
- From HtDP: the structure of the recursive function is given by the structure of the data type. Write the skeleton first; fill in the blanks.
- Semantics is a choice
- The meaning of an operator (e.g.
+) is not determined by its syntax. The interpreter can implement any semantics; naively delegating to the host language imports the host's semantics.
In This Cluster
| Page | Role |
|---|---|
| Abstract Syntax Tree | Internal representation of programs |
| Parsing | Surface syntax → AST |
| Interpreter | AST → value |
| Semantics | Meaning assigned to syntax |