Values and Runtime Errors

In the previous chapter, we covered the AST of Bridger as provided by the accompanying Rust parser. The provided code base also includes a Rust enum type Value representing the possible values a Bridger expression may evaluate to. Throughout this book, you will work through the milestones to create an interpreter that evaluates an Expr (and whole programs) to a Value. This chapter details the Value type you will be working with. It also covers what the interpreter should produce when an expression has no value at all (a runtime error). The mathematical value grammar and the semantic rules that define the meaning of Bridger programs are detailed in Appendix D: language reference.

The space of values

Evaluation produces a value, and every value a Bridger program can compute is one of a fixed set of shapes: an integer, a boolean, a string, unit; a tuple or a list built from smaller values; a constructor value or a struct value; a location into the store; a closure. The reference writes the set as a grammar:

$$\begin{array}{rlrl}v::=& n\mid b\mid s\mid ()& & \text{integer, boolean, string, unit}\\ \mid & (v,\dots ,v)& & \text{tuple}\\ \mid & []\mid v::v& & \text{empty list, list cons (non-empty list)}\\ \mid & C(v,\dots ,v)\mid S\{f=v,\dots \}& & \text{constructor value, struct value}\\ \mid & \ell & & \text{location}\\ \mid & ⟨\lambda x,\dots ,x.e,\rho ⟩& & \text{closure}\\ \mid & R\mid T& & \text{relation, type name}\end{array}$$

The last two stand for names rather than data — a declared relation, and a struct or type named as the receiver of an associated call — and nothing compares, prints, or stores them.

The above set of values represents the result of running any Bridger program or expression to completion. We describe each in detail in future chapters: integers, booleans, and strings in the tree-walking evaluation as the result of evaluating simple arithmetic, boolean, and string expressions; tuples and lists in that same chapter, as compound expressions built from smaller values; unit, the value of statements and blocks, with control flow; locations with mutable references; closures with functions; and constructor and struct values with algebraic data types and structs later still.

Bridger’s values in Rust

The set of value shapes is a sum type, the same correspondence the AST turned on: one variant per shape, each carrying what that shape is built from. The Value enum, provided with this book alongside the AST, holds them. It reuses type Name = String from the AST chapter for the names in Ctor and Struct.

enum Value {
    Int(i64),                          // 5
    Bool(bool),                        // true
    Str(Rc<str>),                      // "hi"
    Unit,                              // ()
    Tuple(Rc<[Value]>),                // (v, v, …), two or more
    List(List),                        // [] or a cons cell v :: v, see below
    Ctor(Name, Rc<[Value]>),           // a constructor value: C(v, …)
    Struct(Name, Rc<[(Name, Value)]>), // a struct value: S { f = v, … }
    Ref(Loc),                          // a location in the store (Part IV)
    Closure(Rc<Closure>),              // a function + its captured env (Part V)
    Relation(Name),                    // a declared relation, by name (Part VII)
    Type(Name),                        // a type name, receiver of `T.m()` (Part IX)
}

The comment on each variant gives an example of the kind of value it holds, and the variants line up with the grammar above one for one. The string, tuple, constructor, and struct payloads sit behind Rc, as the types in the AST chapter do: a value is copied whenever it is read from a variable or a cell, and a reference-counted pointer makes that copy a pointer bump rather than a walk of the payload. The Value enum is to a running program what Expr is to a parsed one: the type every part of the interpreter agrees on for the thing it passes around. Where Expr is what the evaluator takes apart, Value is what it builds.

One representation choice is visible in List. The reference models a list as either the empty list $[]$ or a cons $v_h::v_t$, a head joined to a tail, and the List type holds exactly that: the empty list, or a cell with a head, a tail, and the length so far, the tail shared with any other list that ends the same way. Sharing is what makes the rules’ shape a good representation and not only a good notation. Prepending with ::, taking a list apart with the pattern h :: t, and head and tail each touch one cell, whatever the list’s length, so a function that recurses down a list does work proportional to the list. An array would make ::, tail, and the tail of h :: t copy the whole list. A list literal and ++ cost the left operand’s length, since its cells are rebuilt onto the shared right operand, and len reads the count each cell stores. What the array would give back, reading the nth element in one step, Bridger has no operation for.

Expressions that do not evaluate to a value

Evaluating an expression usually produces a value; however, there are two scenarios when an expression does not evaluate to a value. Evaluation can get stuck: adding a boolean to an integer, applying a value that is not a function, projecting a field off a tuple, or dividing by zero. Each such scenario has no corresponding evaluation rule (and the expression has no well-formed meaning as a value). Instead, the interpreter immediately halts on such runtime errors. On the other hand, an evaluation can choose to return early: a return e computes e and then abandons the rest of the enclosing function’s body, carrying that value out to the function’s own result. We represent both non-local exits with one type Control in our Rust interpreter.

enum Control {
    Raise(RuntimeError),  // stuck: no rule applies; the run halts
    Return(Value),        // an early return, sent to the enclosing function
}

This chapter describes the purpose of Raise in detail. Stuckness is the absence of a result rather than a special result, a notion the operational semantics the book writes its rules in makes precise, and the reference collects the full list of cases. In the untyped evaluator of Parts II through V, these stuck states are how a nonsensical program fails; they are Bridger’s runtime errors. Return carries a value that did finish computing, only not here; a return is legal only inside a function body. We will explain how return e and the Control::Return variant are treated within the interpreter we build in the Control flow chapter and functions.

The interpreter we build must handle expressions that may contain runtime errors. Rather than having our interpreter crash or have undefined behavior on runtime errors, we have the interpreter we build make use of Rust’s Result and Error types to represent such runtime errors explicitly. That means, when the interpreter encounters such runtime errors, rather than halting it stops evaluation early and returns a RuntimeError describing why the interpreter stopped evaluation.

The variants below are the ones the arms of this part and the next raise; the driver and the prelude add theirs (no main, a cycle among global initializers, a failed read from input, a range or a call depth past the machine’s bound, printing a function), and each later part its own as its constructs arrive (a missing struct field, a method with no receiver, a query inside a filter).

enum RuntimeError {
    // x not in scope
    UnboundVariable { name: Name, span: Span },
    // 1 + true, a non-bool condition, iterating a non-list, …
    TypeError { expected: Ty, found: Ty, span: Span },
    // 5 / 0 or 5 % 0
    DivByZero { span: Span },
    // .f a value lacks
    NoSuchField { field: String, span: Span },
    // applying a non-function
    NotAFunction { found: Ty, span: Span },
    // wrong number of arguments
    ArityMismatch { expected: usize, found: usize, span: Span },
    // no arm matched the value
    NonExhaustiveMatch { span: Span },
    // == on a function or relation
    NotComparable { found: Ty, span: Span },
}

Evaluation therefore does not return a bare Value. It returns a Value or a Control, and Rust spells “one or the other” with its own sum type, Result. Its companion Option spells “a value or nothing”:

enum Result<T, E> { Ok(T), Err(E) }   // a T, or an error E
enum Option<T>    { None, Some(T) }   // a T, or nothing

Both come from Rust’s standard library, and both are how a Rust program carries the possibility of failure in a value the compiler forces every caller to look at. The evaluator puts a Value on the Ok side and a Control on the Err side — a normal value, or one of the two non-local exits:

fn eval(e: &Expr) -> Result<Value, Control> {
    match e {
        Expr::Lit(Lit::Int(n), _) => Ok(Value::Int(*n)),
        Expr::Binary(BinOp::Add, l, r, span) => {
            let a = eval(l)?;                 // a Raise or Return bubbles out here
            let b = eval(r)?;
            match (a, b) {
                (Value::Int(x), Value::Int(y)) => Ok(Value::Int(x.wrapping_add(y))),
                (a, b) => {
                    let found =
                        if matches!(a, Value::Int(_)) { type_of(&b) }
                        else { type_of(&a) };
                    Err(Control::Raise(RuntimeError::TypeError {
                        expected: Ty::int(), found, span: *span,
                    }))
                }
            }
        }
        _ => todo!("the remaining forms: the next chapter"),
    }
}

The Ok/Err split names both outcomes at the type level: a caller of eval cannot use the value without first deciding what to do when it is an Err. The ? after eval(l) is Rust’s propagation operator — when the subexpression is an Err, ? returns it from eval at once, so whichever exit it carries — a Raise with its span, or a Return with its value — travels out through every enclosing operation untouched. One mechanism threads both: every operation propagates a Control the same way, and only a function call inspects a Return, catching it at the boundary and turning it back into the call’s value. When both operands are integers the addition proceeds; when they are not, the last arm raises a RuntimeError::TypeError naming the Ty it expected and the Ty type_of read from the offending operand, and carrying the addition’s span. The addition wraps, since the reference fixes integers as 64-bit values with arithmetic modulo $2^{64}$.

Two kinds of failure

The Err(Control::Raise(…)) an addition returns and a Bridger value like Err("file not found") read alike on the page and are different in kind. The first is the interpreter stopping: no rule applied, so there is no value, and the host Result carries that fact out to the top level, where it is printed. A Bridger program cannot observe it or recover from it; the program has already stopped. The second is an ordinary Bridger value, a constructor value Err(s) that a successful evaluation produced, which the program inspects with match and carries on from. Evaluating it is a completed derivation that yields a value; nothing is stuck.

Bridger has its own Option and Result for exactly this second kind of failure, defined in the prelude as ordinary data types and handled with match — separate from Rust’s Option and Result, which are how the interpreter is written. The recoverable failures a Bridger program models with those values, the surface that makes them convenient, and the design space of failure mechanisms (values against exceptions against a halting panic) are the subject of Error handling, once algebraic data types give the language the constructors to build them. What this chapter fixes is the boundary: a runtime type error is the host stopping, and it stays outside the values a program computes with.

That boundary is why every stuck case is stated precisely. Each carries a span and names the Ty it expected against the one it found, because for Parts II through V a runtime type error is the only report a mistake gets, and the reader debugging a program has nothing else to go on. When the type checker arrives in Part VI it rules out the type-shaped stuck cases before the program runs, trading the clear failures described here for a guarantee made ahead of time. Division by zero, a failed read from input, and the interpreter’s two bounds — on call depth and on the size of a range — cannot be ruled out statically, nor, until exhaustiveness checking arrives, can a match no arm covers.

How a value is represented

A tagged union is one way to give an interpreter a single value type, and the choice reads as a choice against the alternatives a faster or a more open interpreter reaches for.

The enum stores a tag — which variant this is — beside the payload, and every value costs the tag plus room for the largest variant. match reads the tag to choose an arm, and the compiler checks that the arms cover every variant, the same exhaustiveness the AST walk relied on. A value kind cannot be added without editing the one enum and revisiting the matches the addition now leaves incomplete.

Other interpreters and compilers optimizing for speed instead often make use of smaller, packed value representations. For instance, a production virtual machine for a dynamic language often stores every value in a single 64-bit word, reading a few spare bits as the tag: small integers are represented inline with a tag bit set. This is how OCaml represents its values. It represents its native integers with 63 bits and the low bit determines whether the 64-bit word is an integer or a pointer to a structure. These packed representations achieve faster computations due to the denser representation that leads to fewer memory reads. However, the cost is that the representation is tied to a specific word size, and such packed representations are often hard to read and understand.

An interpreter written in an object-oriented language reaches instead for a class hierarchy: each value kind a subclass of a common value class, and each operation a virtual method the runtime dispatches on the object’s class. That arrangement makes the set of value kinds open — a new kind is a new subclass, added without editing a central type — and gives up the closed, checked case analysis the enum and its match provide, where the compiler can prove every kind is handled. In this book, we make the decision to use an enum type to represent the AST and Value because it makes it clear which cases are handled and which are not and is easier to read and understand for learning purposes.

Further reading

Representing values in an interpreter: Robert Nystrom’s Crafting Interpreters (free online) gives its bytecode interpreter a tagged-union value type in its “Types of Values” chapter, the same shape as the Value here, and its later “Optimization” chapter rewrites that type as a NaN-boxed word and measures what the packing buys.

Tagged data and dispatching on it: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) builds data that carries a type tag and operations that read it, and works through both the central-table and the class-style organizations for dispatching on that tag — the two the last section set against the enum.

Concept checks