Skip to content

CONCEPT Cited by 1 source

AST interpreter

An AST interpreter (also tree-walking interpreter) is the simplest strategy for executing a dynamic language or expression language: parse the input into an concepts/abstract-syntax-tree, then recursively walk the tree and compute the result node by node.

Evaluate(node):
    if node is Literal:          return node.value
    if node is BinaryOp(op,l,r): return op(Evaluate(l), Evaluate(r))
    if node is FunctionCall:     ...

Properties

Strengths:

  • Trivial to implement — the interpreter mirrors the tree structure 1:1.
  • Correctness-first — one path from expression to result; no bytecode encoding to keep in sync; easy to prototype language features.
  • Flexible on operand types — recursion returns whatever the subtree computes; the interpreter dispatches on runtime type at each node.
  • Cheap for one-shot evaluation — no compile step; for a query evaluated once (e.g. constant folding in a planner), walking the AST directly beats compile + VM dispatch.

Weaknesses:

  • Slow. Recursion spills registers per node; every operator type-switches operand types at runtime; cache locality is awful.
  • Doesn't scale to hot paths. Languages whose target workload executes the same expression many times per row (SQL filter predicates, ML feature transforms, template engines) quickly outgrow AST interpretation.

Canonical transition story

Most mature dynamic languages begin life as AST interpreters and graduate to bytecode VMs when performance matters:

  • Ruby: MRI's original AST walker → YARV bytecode VM.
  • Python: transitioned to bytecode early.
  • JavaScript: every modern engine compiles to bytecode as the starting point; no serious JS engine uses AST interpretation.

When AST interpreters remain useful

Even after a bytecode VM exists, the AST interpreter often stays in the codebase for three reasons:

  1. One-shot / planner-time evaluation. Compile-then-execute on the VM is more expensive than a single tree walk for expressions evaluated exactly once (e.g. constant folding in a query planner). See systems/vitess-evalengine.

  2. VM deoptimization fallback. When a specialized VM instruction encounters a runtime condition the compile-time specialization didn't account for (classic example: -BIGINT_MIN promoting to DECIMAL instead of staying BIGINT), the VM bails out and the AST interpreter — which always type-switches at runtime — completes the evaluation.

  3. Fuzz-oracle sibling. Two interpreters for the same language, implemented independently, enable differential fuzzing: every disagreement is a bug in one interpreter, or in the reference implementation. Vitess uses this to find bugs in MySQL's own C++ expression engine.

Seen in

  • sources/2025-04-05-planetscale-faster-interpreters-in-go-catching-up-with-cpp — original Vitess evalengine was an AST interpreter over the SQL parse tree; the 2025 rewrite replaced it with a VM but kept the AST interpreter permanently as deoptimization fallback + one-shot evaluator + fuzz-oracle sibling. "The code for the AST interpreter can never be removed from Vitess. But this is, overall, not a bad thing." Canonical wiki statement of the AST-interpreter retention trade-off.
Last updated · 319 distilled / 1,201 read