The AST: Structure Without Syntax

The abstract syntax tree is the first data structure in the pipeline that is ours — the lexer's tokens and the source text are dictated by the language, but the shape of the tree is a design decision. Two later subsystems consume it: the tree-walking interpreter in Section 2 and the compiler in Section 3. Getting its shape right is worth an hour of thought now.

Three concepts: the tree as an intermediate representation, node design in Rust, and traversal.

Concept 1: The Tree as an Intermediate Representation

1. Concept

An abstract syntax tree records the structure of a program and discards the syntax that conveyed it. Parentheses, keywords, commas, and semicolons are gone; what remains is "an addition whose left operand is a literal and whose right operand is a multiplication."

SOURCE           (10 + 20) * 3

CONCRETE tree                     ABSTRACT tree
  Mul                               Mul
   ├── Paren                         ├── Add
   │    ├── '('                      │    ├── Int(10)
   │    ├── Add                      │    └── Int(20)
   │    │    ├── Int(10)             └── Int(3)
   │    │    ├── '+'
   │    │    └── Int(20)             The parentheses are GONE. Their entire
   │    └── ')'                      contribution was making Add a child of
   ├── '*'                           Mul instead of the other way round, and
   └── Int(3)                        that is now expressed by the shape.

2. Problem

The token stream is linear; programs are nested. Every consumer of a program — an evaluator, a compiler, a formatter, a linter — needs the nesting. Rebuilding it from tokens at each consumer would mean writing the parser again, several times, and getting different answers.

3. Mental model

The AST is a contract between the front end and everything else. The parser promises: "here is a well-formed structure, precedence already resolved, with a span on every node." Everything downstream is allowed to assume it and forbidden to re-derive it.

4. Implementation

#![allow(unused)]
fn main() {
// src/ast.rs
#[derive(Debug, Clone)]
pub enum Expr {
    Nil        { span: Span },
    Bool       { value: bool, span: Span },
    Int        { value: i64,  span: Span },
    Float      { value: f64,  span: Span },
    Str        { value: String, span: Span },
    Vararg     { span: Span },

    Name       { name: String, span: Span },
    Index      { object: Box<Expr>, key: Box<Expr>, span: Span },   // t[k] and t.k
    Call       { callee: Box<Expr>, args: Vec<Expr>, span: Span },
    Method     { object: Box<Expr>, name: String, args: Vec<Expr>, span: Span }, // t:m(...)

    Unary      { op: UnOp,  operand: Box<Expr>, span: Span },
    Binary     { op: BinOp, lhs: Box<Expr>, rhs: Box<Expr>, span: Span },
    Function   { params: Vec<String>, is_vararg: bool, body: Block, span: Span },
    Table      { fields: Vec<TableField>, span: Span },
}

#[derive(Debug, Clone)]
pub enum Stmt {
    Empty      { span: Span },
    Local      { names: Vec<String>, exprs: Vec<Expr>, span: Span },
    Assign     { targets: Vec<Expr>, exprs: Vec<Expr>, span: Span },
    ExprStat   { expr: Expr, span: Span },
    Do         { body: Block, span: Span },
    If         { arms: Vec<(Expr, Block)>, else_: Option<Block>, span: Span },
    While      { cond: Expr, body: Block, span: Span },
    NumericFor { var: String, start: Expr, stop: Expr, step: Option<Expr>,
                 body: Block, span: Span },
    GenericFor { names: Vec<String>, exprs: Vec<Expr>, body: Block, span: Span },
    Break      { span: Span },
    Return     { exprs: Vec<Expr>, span: Span },
}

#[derive(Debug, Clone, Default)]
pub struct Block { pub stmts: Vec<Stmt>, pub span: Span }
}

Six design decisions are visible here. Each is a choice, and each has a reason.

1. No Paren node. Parentheses affected the shape and are then discarded. This is what "abstract" means. (Lua needs one exception — (f()) truncates multiple returns to one value — and Ember adds a Paren node in Lab 17 for exactly that. Note it as a divergence when it happens: it is a case where syntax genuinely carries semantics.)
2. Index covers both t.k and t[k]. t.k is desugared at parse time to Index { object: t, key: Str("k") }. One node, one code path in the compiler, one place for the metatable lookup in Section 4. The span still points at the original syntax, so error messages are unaffected.
3. If holds Vec<(Expr, Block)> rather than a nested else: If. elseif chains are flat in the source and flat in the tree, so the compiler emits a jump table over a Vec rather than recursing. It also means an if/elseif chain a thousand arms long does not nest a thousand deep.
4. Every node has a span, and it is the whole subtree's extent. Binary's span is lhs.span().merge(rhs.span()), not the operator's span.
5. Method is separate from Call. t:m(x) means t.m(t, x) — evaluating t once. Desugaring it in the parser would require a temporary the AST cannot express. Keep it explicit and let the compiler handle it.
6. Local and Assign hold Vecs of both sides. local a, b = f() is one statement, and the multiple-return adjustment rules in Section 4 need to see both lists at once.

5. Alternatives

6. Decision

We build an abstract tree of owned, boxed nodes (option A).

Against option C, which is what Lua does and is genuinely faster and smaller: an AST is what makes the tree-walking reference interpreter possible, and the reference interpreter is what makes differential testing possible. That single consequence outweighs the memory. Write it in docs/adr/ADR-003-keep-the-tree-walker.md — it is the same decision seen from the other end.

Against option D, which is the better engineering answer and which you should consider seriously: an arena removes the deep-Drop hazard described below, improves cache locality, and makes the tree trivially serializable. It also makes every traversal an explicit arena[id] lookup, which is noisier to read in a book. If you are building this for real rather than to learn, use D. Note it in your ADR as the rejected option with the strongest case.

7. Tradeoffs

8. Production concerns

Recursive Drop can overflow the stack, and this one surprises Rust programmers.

#![allow(unused)]
fn main() {
// This parses fine with a depth limit of 200... but consider what happens if
// the limit were absent and a 100,000-deep tree existed:
let ast = parse("1+1+1+ ... +1")?;      // right-nested Binary chain
drop(ast);                               // ← Box<Expr>'s Drop recurses ONE FRAME PER NODE
}

Box<T>'s generated Drop is recursive. Dropping a 100,000-deep tree recurses 100,000 times and aborts the process — after parsing succeeded, in a destructor, where no Result can catch it. serde_json ships a nesting limit for this reason; rustc has hit it; it is a known hazard of recursive owned data structures in Rust generally.

Two defenses, and Ember uses the first:

1. Bound the depth at parse time (MAX_PARSE_DEPTH, from the previous chapter). If the tree can never be deeper than 200, the drop can never recurse deeper than 200. One guard fixes both problems, which is a good sign the guard is at the right layer.
2. Write an iterative Drop that walks the tree with an explicit worklist. Correct, tedious, and unnecessary once (1) exists. Option D (arena) makes it moot: dropping an arena is dropping one Vec.

Tip: Add the test. #[test] fn deep_expression_does_not_abort() builds a 10,000-term expression string, asserts parse() returns an Err, and — critically — still runs the rest of the suite, which it will not do if the process aborted.

Other production concerns:

• The AST is not public API. Ember keeps ast.rs pub(crate). Exposing it means every internal refactor is a breaking change, and the AST is the module most likely to change. Engine is the public surface; the tree is an implementation detail. Revisit only if a real consumer appears.
• AST size is a memory-budget item. Section 5's memory limit must account for compilation, not just execution — a 10 MB script can produce a 100 MB tree before a single instruction runs. The budget check belongs before parsing, on source size, and after parsing, on node count.
• Keeping the printed form honest. ember ast output is a debugging tool and it will lie to you if it omits a field you later add. Derive it from the same match that every consumer uses, and let the exhaustiveness check force you to update it.

9. References

# Compare four ASTs for the same trivial program.
python3 -c "import ast; print(ast.dump(ast.parse('x = 10 + 20*3'), indent=2))"
echo 'int x = 10 + 20*3;' > /tmp/a.c && clang -Xclang -ast-dump -fsyntax-only /tmp/a.c
luac -l -l /tmp/a.lua        # Lua: there IS no AST. Bytecode straight from the parser.

• rust-lang/rust, compiler/rustc_ast/src/ast.rs — a real AST, with the NodeId/Span pattern Ember copies.
• rust-analyzer's rowan — option B. Read the design doc on why an IDE needs a lossless tree and a compiler does not.
• Python's ast module docs — a public, stable, documented AST, and a good case study in the cost of that promise.

Concept 2: Traversal

1–3. Concept, problem, mental model

Every consumer walks the tree. In an object-oriented language without sum types this needs the visitor pattern: a Visitor interface with a visit_X method per node type, and a accept method on each node that dispatches. In Rust, it needs match.

The visitor pattern exists to simulate pattern matching in languages that lack it. Rust has pattern matching. Do not port the workaround.

4. Implementation

#![allow(unused)]
fn main() {
// src/interp/eval.rs — the whole traversal strategy, in one shape
fn eval_expr(&mut self, e: &Expr) -> Result<Value> {
    match e {
        Expr::Int { value, .. }   => Ok(Value::Integer(*value)),
        Expr::Float { value, .. } => Ok(Value::Float(*value)),
        Expr::Nil { .. }          => Ok(Value::Nil),
        Expr::Binary { op, lhs, rhs, span } => {
            let l = self.eval_expr(lhs)?;      // POST-ORDER: children first.
            let r = self.eval_expr(rhs)?;      // This IS the evaluation order.
            self.binary_op(*op, l, r, *span)
        }
        Expr::Unary { op, operand, span } => {
            let v = self.eval_expr(operand)?;
            self.unary_op(*op, v, *span)
        }
        // ... one arm per variant. If you add a variant and forget an arm,
        // the compiler tells you — in EVERY consumer. That is the whole point.
    }
}
}

Post-order is the evaluation order. Children are evaluated before the parent, left before right. That is not an implementation detail; it is a language semantic, it is observable through side effects, and Section 3's compiler must emit bytecode that reproduces it exactly or the differential tests fail. Write it down in docs/architecture.md: Ember evaluates operands left to right.

Note: Lua's manual explicitly does not guarantee evaluation order for many expressions. Ember guarantees left-to-right, because determinism is a product requirement for a policy engine. That is a divergence, it is deliberate, and it goes in appendix/lua-differences.md.

5–7. Alternatives, decision, tradeoffs

Decision: A. Ember has two tree consumers — the interpreter and the compiler — and two is below the threshold where a visitor pays for itself. The duplicated shape is a feature at this size: each consumer's match is a readable table of "what this pass does with each node". Revisit at four consumers.

8. Production concerns

• Recursion depth again. eval_expr recurses once per node, so the evaluator has the same stack hazard as the parser and needs its own depth counter — a separate one, because the tree walker also recurses on script function calls. This is Lab 7.
• Exhaustiveness is your migration tool. When Lab 13 adds Expr::Table, cargo check lists every place that must handle it. Never write _ => unreachable!() in a tree match; you are turning a compile error into a runtime panic, and the compile error was the valuable one.

9. References

• Crafting Interpreters, chapter 5 — implements the visitor pattern in Java and explains exactly why: Java has no sum types. Reading it makes the Rust simplification vivid.
• The Gang of Four's Visitor chapter, for the historical framing.
• rustc_ast::visit — what a visitor looks like when you genuinely have dozens of consumers.

The Trace: local x = 10 + 20

After Lab 2 this is what ember ast prints. Spans are byte offsets into the source.

$ ember ast -e 'local x = 10 + 20'
Block                                        @0..17
└── Local                                    @0..17
    ├── names: ["x"]
    └── exprs:
        └── Binary(Add)                      @10..17
            ├── Int(10)                      @10..12
            └── Int(20)                      @15..17

Three things to check, every time you print a tree:

1. The root span covers the whole input. If it does not, some node forgot to merge.
2. Child spans are inside the parent's. A child whose span escapes its parent is a merge bug and will produce a caret in the wrong place.
3. The shape matches the precedence table. For 10 + 20 * 3, Add is the root and Mul is its right child. If they are swapped, your binding powers are wrong — and nothing else in the system will ever tell you.

Things to Notice

• The AST is where syntax dies. After this point nothing knows about parentheses, keywords, or commas. That is a feature: it means the compiler cannot accidentally depend on syntax.
• Every design decision in the node definitions is a decision about what a later pass must do. Desugaring t.k to Index moves work from the compiler to the parser. Keeping Method separate moves work the other way. Neither is wrong; both must be conscious.
• Exhaustive match is a superpower Rust gives language implementers, and it is the single clearest place where Rust makes this work easier than C. The corresponding place where it makes it harder is the object graph in Section 4.
• Recursive owned trees have a Drop hazard. This is Rust-specific, it is not obvious, and one depth limit fixes it along with the parser's stack overflow.

Validation / Self-check

1. What does "abstract" mean in "abstract syntax tree"? Give something concrete that is discarded and say how its meaning survives.
2. Name three of the six design decisions in Ember's node definitions and the downstream pass each one serves.
3. Why does Index cover both t.k and t[k], and why is Method not desugared the same way?
4. Give the four AST strategies and a real implementation of each. Which does Lua use, and what does Ember get by rejecting it?
5. Explain the deep-Drop hazard, why Result cannot catch it, and which single guard prevents it.
6. Why is the visitor pattern unnecessary in Rust? When would you add one anyway?
7. What is the evaluation order of f() + g() in Ember, where is it decided, and how is it documented?
8. Three checks to run on any printed AST. What bug does each catch?

Next: Spans and Source Maps.