The Abstract Syntax Tree

Syntax and semantics separated the abstract structure of a program from the concrete syntax that disambiguates it: three spellings of an addition collapse to one tree. In this chapter, we detail the concrete implementation of the AST structure of Bridger programs that the parser provided with this book will have you use in the implementation Milestones. Specifically, this chapter details three Rust types: Expr for the expressions at the core of Bridger, Program for whole top-level declarations, and Ty for expressing types. For complete details on the concrete syntax of Bridger see Appendix B: concrete syntax.

The shape of expressions

Run down the grammar and an expression is always one of a fixed set of shapes: a literal, a variable, an operator applied to smaller expressions, a conditional, a call, and so on. A type whose values are “one of the following” is a sum type, and in Rust it is written as an enum: one variant per shape, each carrying exactly the pieces that shape is built from. The productions of a grammar and the variants of a sum type line up one for one, which is what makes the enum the natural representation of an AST.

That correspondence is old enough to have shaped which languages interpreters get written in. McCarthy’s LISP (1960) represented programs as the very lists the language processed — code as data — so a function that transformed a program was an ordinary list-processing function. The ML family later made the shapes explicit as algebraic data types and took them apart with pattern matching, a fit close enough that interpreters and compilers have been written in ML-family languages ever since. Rust inherits both halves: the enum names the shapes, and match (below) takes them apart.

A tree records structure and drops the surface detail the parser has already used up — the parentheses, the whitespace, the fact that * binds tighter than +. What survives is how the pieces fit together, and that is what the type below captures.

Bridger’s Expressions in Rust

The core of Bridger’s syntax is made up of recursively constructable expressions. This section details the components that make up such expressions and how the Book’s companion parser represents the expressions it parses. For convenience in error reporting, every parsed expression includes a span which records where in the source text the expression is located.

struct Span { src: SrcId, start: usize, end: usize }

The src says which loaded source the bytes belong to — the prelude is one source and the program another — so a span names a node uniquely even across files.

A Literal is represented by the following Lit enum. A numeric literal is represented as a 64-bit signed integer in Rust (i.e., all numeric values in Bridger are between $-2^{63}$ and $2^{63}-1$); a Boolean literal is simply a Rust bool type; a string literal is simply a Rust String, and a unit literal is the singleton value () left implicit in the Lit enum.

enum Lit { Int(i64), Bool(bool), Str(String), Unit }

Before detailing how we represent expressions, we detail several auxiliary types. The enum UnOp represents all unary operators in Bridger. Similarly, BinOp all binary operators. Finally, all names (identifiers and variables) are represented as a String.

enum UnOp { Neg, Not, Ref, Deref }

enum BinOp {
    Add, Sub, Mul, Div, Mod,      // arithmetic
    Eq, Ne, Lt, Le, Gt, Ge,       // comparison
    And, Or,                      // boolean
    Concat,                       // ++
    Cons,                         // ::  (prepend to a list)
}

type Name = String;

With each of the auxiliary data types defined, we represent Bridger expressions with the recursive enum Expr.

enum Expr {
    // a literal value: 5, true, "hi", ()
    Lit(Lit, Span),
    // a variable reference, or the receiver `self`
    Var(Name, Span),
    // a prefix operator: -e, not e, ref e, deref e
    Unary(UnOp, Box<Expr>, Span),
    // a binary operator: e + e, e == e, e and e, e ++ e, e :: e
    Binary(BinOp, Box<Expr>, Box<Expr>, Span),
    // a conditional: if e { … } else { … }, the else optional
    If(Box<Expr>, Box<Expr>, Option<Box<Expr>>, Span),
    // a block: statements and an optional trailing value
    Block(Vec<Stmt>, Option<Box<Expr>>, Span),
    // assignment through a reference: e := e
    Assign(Box<Expr>, Box<Expr>, Span),
    // a function call: e(e, …)
    Call(Box<Expr>, Vec<Expr>, Span),
    // a method call: e.m(e, …)
    Method(Box<Expr>, Name, Vec<Expr>, Span),
    // a lambda: |x, …| e, each parameter optionally annotated x: T
    Lambda(Vec<LambdaParam>, Box<Expr>, Span),
    // a pattern match: match e { arm, … }
    Match(Box<Expr>, Vec<Arm>, Span),
    // a while loop: while e { … }
    While(Box<Expr>, Box<Expr>, Span),
    // a for loop over a list: for x in e { … }
    For(Name, Box<Expr>, Box<Expr>, Span),
    // a for loop over a relation's solutions: for R(a, ?x) { … }
    ForQuery(Query, Box<Expr>, Span),
    // an early return from a function: return e
    Return(Box<Expr>, Span),
    // error propagation: e?  (sugar over match and return)
    Try(Box<Expr>, Span),
    // a tuple: (e, e, …), two or more elements
    Tuple(Vec<Expr>, Span),
    // a list: [e, …]
    List(Vec<Expr>, Span),
    // struct field access: e.f
    Field(Box<Expr>, Name, Span),
    // tuple projection by index: e.0
    Proj(Box<Expr>, u32, Span),
    // constructor application: C(e, …)
    Ctor(Name, Vec<Expr>, Span),
    // struct literal: S { f: e, … }
    Struct(Name, Vec<(Name, Expr)>, Span),
    // a relations operation: add q / clear R / solutions q / query
    Relation(Rel, Span),
}

The comment on each variant names the Bridger form it holds, and every variant matches the abstract syntax fixed in the language reference. This chapter settles the shape of each; the chapters that follow give each its meaning. Several variants hold companion types — Stmt, Arm, Pattern, Rel, and Query — which we define after two structural choices in Expr itself.

Children sit behind Box. An Expr can contain an Expr (e.g., the two operands of a Binary operator or the condition and branches of an If) so its size would depend on itself, and no fixed size would satisfy the Rust compiler. We use Box<Expr> (a pointer to an Expr). Since a pointer has a known size, a Box<Expr> can be used to hold sub-expressions recursively. A node owns its children through the Box, and dropping a tree drops everything under it. Where a node has any number of children — a Call’s arguments, a List’s elements — a Vec<Expr> owns all of them.

Four variants hold companion types, which we define now. A block (Block) is a sequence of statements followed by an optional result expression, and each statement (Stmt) is either a local let binding or an expression evaluated for its effect. A ref x = e binding is stored as an ordinary let of a ref expression, so it needs no case of its own.

enum Stmt {
    Let(Name, Option<Ty>, Expr, Span),   // let x = e   (or   let x: T = e)
    Expr(Expr),                          // an expression evaluated for effect
}

A match expression holds a list of arms. An arm (Arm) pairs a pattern with an optional guard and the expression to evaluate when the arm is chosen.

struct Arm {
    pat: Pattern,          // the pattern this arm matches
    guard: Option<Expr>,   // an optional `if` guard
    body: Expr,            // evaluated when the arm is taken
}

A pattern (Pattern) describes the shape a match tests a value against, and mirrors the expression forms it takes apart. Like an expression, every pattern carries its span.

enum Pattern {
    Wild(Span),                                 // _
    Lit(Lit, Span),                             // a literal: 5, true, "hi"
    Var(Name, Span),                            // binds the matched value to a name
    Ctor(Name, Vec<Pattern>, Span),             // a constructor: C(p, …)
    Tuple(Vec<Pattern>, Span),                  // (p, p, …), two or more
    List(Vec<Pattern>, Option<Name>, Span),     // [p, …], with an optional ...rest
    Cons(Box<Pattern>, Box<Pattern>, Span),     // head :: tail
    Struct(Name, Vec<(Name, Pattern)>, Span),   // S { f: p, … }
    Or(Box<Pattern>, Box<Pattern>, Span),       // p | p
}

The relations sublanguage folds its four expression forms into Rel. A query (Query) names a relation and supplies arguments; each argument (QArg) is either an ordinary expression or a hole to solve for, named ?x or anonymous ?.

enum Rel {
    Add(Query),        // add R(a, …)
    Clear(Name),       // clear R
    Solutions(Query),  // solutions R(a, …)
    Query(Query),      // a bare query R(a, …)
}

struct Query { name: Name, args: Vec<QArg> }   // R(a, …)

enum QArg {
    Expr(Expr),          // a ground argument
    Hole(Option<Name>),  // a hole: ?x (named) or ? (anonymous)
}

The program that holds them

An Expr builds the core of Bridger’s structure; however, at the top-level, a Bridger program is a sequence of declarations: functions, globals, types, structs, traits, relations. The order of declarations does not matter, instead every declaration is visible to every other top-level declaration (with a requirement that all global names must be unique). As such, we represent the top level Declarations simply as a map from names to declarations, and separate trait implementations and rules which are unnamed.

struct Program {
    decls: HashMap<Name, Decl>,   // fn, global, type, struct, trait, relation
    spans: HashMap<Name, Span>,   // where each declaration was written
    impls: Vec<Impl>,             // anonymous: keyed by the type they extend
    rules: Vec<Rule>,             // any number define one relation
}

enum Decl {
    Fn(Generics, Vec<Param>, Ty, Box<Expr>),   // fn f<T: C>(x: T, …) -> T = e
    Global(Option<Ty>, Box<Expr>),             // let x = e  (or  let x: T = e)
    Type(Generics, Vec<Variant>),              // type T<U> = C(U, …) | …
    Struct(Generics, Vec<Field>),              // struct S<T> { f: T, … }
    Trait(Generics, Vec<Sig>),                 // trait Tr<T> { fn m(…); … }
    Relation(Vec<Ty>),                         // relation R : (T, …)
}

The generic-bearing forms — Fn, Type, Struct, Trait, and the impl blocks — each carry a Generics: a declaration can be parameterized by types, and a type parameter may carry a trait bound its argument must satisfy:

struct Generics { params: Vec<TyParam> }   // <T, U: Show, …>; empty if absent

struct TyParam {
    name: Name,               // T
    bound: Option<TraitRef>,  // : Show — the trait bound, if any
    span: Span,               // where it is written, for diagnostics
}

The type checker in Part VI reads them — it quantifies a declaration over its parameters, then at each use instantiates them and checks the bound — while the evaluator ignores them, since running the program is type-erased. The reference’s abstract syntax folds them into a note for the same reason; the AST the parser builds keeps them for the checker.

Every Decl bottoms out in Expr — a function’s body, a global’s initializer — so the tree the last section built is what these hold. Two forms carry no single name and stay out of the map: an impl is found by the type it extends rather than a name, and a relation is defined by any number of rules at once, so each keeps its own list. We define the companion types these declarations use — Param, Field, Variant, Sig, Method, Impl, TraitRef, and the rule forms — below.

Looking a name up is then a map lookup, and that lookup is the order-free, mutually visible scope the reference specifies made concrete: where a declaration sits in the file cannot matter, because the file order is gone once the map is built, and a name declared twice collides when the map is.

A parameter (Param) and a struct field (Field) are each a name with a type, and a constructor of a type declaration is a variant (Variant) with a name and the types of its fields. Each carries the span of its own text, so a diagnostic can point at one parameter of a signature. A lambda’s parameter (LambdaParam) differs from a function’s in one respect: its annotation is optional, because the type checker can usually infer it from how the lambda is used.

struct Param       { name: Name, ty: Ty, span: Span }            // x: T
struct LambdaParam { name: Name, ty: Option<Ty>, span: Span }    // x  or  x: T
struct Field       { name: Name, ty: Ty, span: Span }            // f: T
struct Variant     { name: Name, fields: Vec<Ty>, span: Span }   // C(T, …), or C

A trait lists method signatures (Sig); an impl supplies methods (Method), which are signatures with a body. Each records whether the method takes self, its remaining parameters, and its return type.

struct Sig {
    name: Name,
    has_self: bool,       // whether the method takes `self`
    params: Vec<Param>,
    ret: Ty,              // (), when the return type is omitted
    span: Span,
}

struct Method {           // a Sig with a body
    name: Name,
    has_self: bool,
    params: Vec<Param>,
    ret: Ty,
    body: Expr,
    span: Span,
    sig: Span,            // the signature alone, `fn m(self, x: Int) -> T`
}

An impl block (Impl) records its own generics, the trait it implements if any, the type it extends, and its methods. A trait named there is a TraitRef — a trait name with any type arguments.

struct Impl {
    generics: Generics,        // impl<T> …
    trait_: Option<TraitRef>,  // the trait implemented, if any
    ty: Ty,                    // the type being extended
    methods: Vec<Method>,
    span: Span,
    head: Span,                // the header, `impl<T> Tr for T`
}

struct TraitRef { name: Name, args: Vec<Ty>, span: Span }   // Tr, or Tr<T, …>

A rule (Rule) has a head atom and a body. The head (Atom) names a relation and lists its terms (Term), each a logic variable or a literal. The body is the rule’s and-chain split into its conjuncts, and each conjunct is an ordinary expression: edge(x, y) and is_ok(x) are the same syntax, and which of them joins against a relation and which tests already-bound variables is settled by name resolution when the rules are installed, in Part VII.

struct Rule { head: Atom, body: Vec<Expr>, span: Span }   // rule H :- B1 and …

struct Atom { name: Name, terms: Vec<Term>, span: Span }  // R(t, …)

enum Term {
    Var(Name),   // a logic variable (a lowercase name)
    Lit(Lit),    // a literal
}

The type language

A type annotation on a let, the signature of a function, the fields of a struct, the columns of a relation, and the bound on a type parameter are all written in one small language of types, and it is a tree of its own:

struct Ty { kind: TyKind, span: Option<Span> }   // a shape, and where it was written

enum TyKind {
    Int, Bool, Str, Unit,    // Int, Bool, String, ()
    Tuple(Rc<[Ty]>),         // (T, U, …) — two or more
    List(Rc<Ty>),            // [T]
    Fn(Rc<[Ty]>, Rc<Ty>),    // fn(T, …) -> T
    Ref(Rc<Ty>),             // ref<T>
    SelfTy,                  // Self, in a trait or impl
    Named(Name, Rc<[Ty]>),   // N, or N<T, …> when applied
    Meta(u32),               // a type not yet known; the checker solves it (Part VI)
}

The children sit behind Rc, a reference-counted pointer, where the expression tree uses Box. Types are shared far more than expressions are: the checker records a type for every expression, nested expressions have nested types, and with plain boxes each level would hold its own copy of everything below it. With Rc the copies are pointers, and cloning a type costs nothing.

A type is used in two ways, and the split into Ty and TyKind serves both. A type the programmer wrote has a position, and a diagnostic can then say that a function was declared to return Int here and point at the annotation. A type the checker computes has none, so the span is optional. Two types are equal when their shapes are, wherever they came from, so a Ty compares and prints as its TyKind alone; Ty::int(), Ty::list(t) and their kin build the computed ones. TyKind is recursive for the same reason Expr is — a list of a list, a function returning a function. Named covers both a plain type name and a generic one applied to arguments, with an empty argument list for the plain case. This is the language the type checker in Part VI works over; here it is only the shape the parser records from a written type.

Matching over the tree

A function over an AST is a case analysis: one arm per variant, handling the pieces that variant carries. match is Rust’s tool for it, and pulling a node apart binds its fields in the same motion:

fn depth(e: &Expr) -> usize {
    match e {
        Expr::Lit(..) | Expr::Var(..) => 1,
        Expr::Unary(_, inner, _) => 1 + depth(inner),
        Expr::Binary(_, l, r, _) => {
            1 + depth(l).max(depth(r))
        }
        Expr::If(c, t, e, _) => {
            let branches = match e {
                Some(els) => depth(t).max(depth(els)),
                None => depth(t),
            };
            1 + depth(c).max(branches)
        }
        _ => 1, // remaining forms: Part II onward
    }
}

The recursion in the type becomes recursion in the function, and the shape of each arm is dictated by the shape of its variant. match is also exhaustive: drop the _ arm and the compiler names every variant still unhandled, so a new form added to Expr cannot silently fall through a pass that predates it. That guarantee — the type system enforcing that every case is considered — is why tree-walking interpreters read so cleanly in this style, and it is the single most useful piece of Rust for the chapters ahead.

The trees a compiler keeps

The AST here is shaped for a book that walks it directly. A production compiler keeps different trees, and the differences are worth knowing so the choices above read as choices.

A compiler usually holds more than one tree. This one is untyped: it is the parser’s output, and nothing in it records what an expression’s type is. Part VI’s type checker leaves the tree as it is and records each expression’s type in a side table keyed by the expression’s span — which is why a span must name a node uniquely — so a later stage can consult a type without recomputing it. Names, kept here as String, are often interned to small integers so that comparing two of them is one machine instruction rather than a character-by-character scan. And a tree stored with Box scatters its nodes across the heap; a compiler that cares about locality keeps them in an arena — one contiguous block — and replaces every Box<Expr> with an integer NodeId index into it, which also lets the side tables (types, uses) key off a small integer rather than a span. Each of these buys speed or a place to hang more information, at the cost of a tree that is heavier to build and read. A first interpreter wants neither cost, so it takes the Box, the String, and the one untyped tree.

Further reading

Building an interpreter around an AST: Robert Nystrom’s Crafting Interpreters (free online) builds two interpreters for the same language, the first a tree-walker over an AST much like this one, and it is unusually concrete about the shape of the tree and the walk over it. Its “Representing Code” and “Evaluating Expressions” chapters cover the same ground as this one and the next, in Java rather than Rust.

The trees a compiler keeps instead: Andrew Appel’s Modern Compiler Implementation in ML (Cambridge University Press, 1998) develops the typed and lowered intermediate representations named in the last section — separate trees for parsing, type checking, and code generation — and shows what each stage reads off the tree the stage before it produced.

Concept checks