Interpreters
Interpretation Strategies
Tree-Walking
Evaluate the AST directly: expressions compute values, statements perform effects, control flow recurses into child nodes. Simplest to build (five steps from Crafting Compilers get a runner in a day) and trivial to debug, since the tree is your call stack.
Source-to-Source
Translate the DSL into a host language (Python, SQL, C) and let the host run it. Zero runtime code of your own; the cost is mapping host errors back onto DSL text — which is why a thin error column matters.
Bytecode (Preview)
Compile to an instruction list and loop over it (Bytecode & Codegen + Virtual Machines). Faster and more predictable, but you now maintain a VM — the chapter after next.
Evaluation Core
Environments Again
The semantics from Semantics & Scoping become one class: Env holds a dict plus a link to its parent, and lookup(name) walks parents. Everything — variables, functions, DSL tables — is data in scopes.
Statements and Effects
Expressions return values; statements change state. A tiny dispatcher on the node type (print, let, if, loop) keeps the interpreter readable, and one RuntimeError type carries user-level failures to the error reporter from Errors & Diagnostics.
The REPL Loop
read (lex+parse) → eval (with one persistent environment) → print result → loop. A REPL is the cheapest teaching tool a DSL can have, and it costs one small function on top of the evaluator.
Interpreter Performance
When to Optimize
Tree-walking pays an indirection per node; that is fine for interactive and config-scale DSLs. When profiling says otherwise, the fix order is: cache resolved lookups, then compile to bytecode (next two topics) — never hand-optimize the walker before measuring.
Example: A Tree-Walker
The interpretive heart of the mini-language from Crafting Compilers, in one commented class.
evaluator.py (commented)
# evaluator.py — evaluate the AST from the parsing chapter
class Evaluator:
def __init__(self): self.env = {} # one flat scope is fine for mini
def eval(self, node):
# dispatch on the node kind, exactly like an interpreter switch
kind = node[0]
if kind == "num": return node[1]
if kind == "binop": # recurse into children, apply the operation
left = self.eval(node[1])
right = self.eval(node[2])
op = node[0][1]
return {"+": add, "-": sub, "*": mul}[op]( left, right)
if kind == "print": print(self.eval(node[1])); return None
if kind == "let": self.env[node[1]] = self.eval(node[2]); return None
if kind == "name": return self.env[node[1]] # resolved earlier
raise SyntaxError(f"unknown node {node!r}")How to Read It
One dispatch per node kind, recursion where the grammar recursed: this is the entire semantics of the language in fifty lines, readable top to bottom — the property that makes interpreters the right first runtime.
Next Steps
Continue Phase 2
Interpretation is immediate; compilation is scalable. Move the same language to a compiled form: Bytecode & Codegen, then Virtual Machines & Runtimes.