Appendix A — Rust for Interpreter Writers

You do not need prior Rust to use this book. Each construct is introduced where the book first needs it, and the AST chapter sets the pattern with enum and match. This appendix is the alternative for a reader who would rather learn the required basics in one go. It covers the parts of Rust the book actually uses.

Milestone M0 is a warm-up exercise that goes with this chapter: a small program (a coin purse) that puts everything below to work. Read a section here, then proceed to the exercise.

Every example below has a play button: run it, change it, run it again to help you learn.

enum and match

An enum is a value that is one of a fixed set of variants, and each variant can carry its own data. It is the single most important type in this book: a grammar production becomes an enum variant, and a runtime value’s shape becomes one too.

enum Shape {
    Circle(f64),        // a radius
    Rect(f64, f64),     // a width and a height
}

fn area(s: &Shape) -> f64 {
    match s {
        Shape::Circle(r) => 3.14159 * r * r,
        Shape::Rect(w, h) => w * h,
    }
}

fn main() {
    let s = Shape::Rect(3.0, 4.0);
    println!("{}", area(&s));   // 12
}

match takes an enum apart: each arm names a variant and binds the data that variant carries (r, or w and h), and the arm’s body is what that case evaluates to. A match satisfies two properties:

• It is an expression: it produces a value, letting you compute a value as let x = match … { … }.
• It is exhaustive: the arms must cover every variant, or the program does not compile. Delete the Rect arm above and run it: the compiler names the case you left out. When a new variant is added to an enum, the compiler lists every match that now has a gap, which is what makes a program built on enums safe to grow.

A pattern can go deeper than one level, match several values at once by pairing them in a tuple, and fall through with _, the wildcard that matches anything:

fn describe(pair: (i64, i64)) -> &'static str {
    match pair {
        (0, 0) => "origin",
        (x, 0) => if x > 0 { "east" } else { "west" },
        (0, _) => "on the y-axis",
        _      => "somewhere else",
    }
}

fn main() {
    println!("{}", describe((3, 0)));   // east
    println!("{}", describe((1, 1)));   // somewhere else
}

An arm may also carry a guard, an if that further restricts when it fires:

fn sign(n: i64) -> &'static str {
    match n {
        0 => "zero",
        n if n > 0 => "positive",
        _ => "negative",
    }
}

fn main() { println!("{}", sign(-4)); }   // negative

A fieldless enum — variants that carry no data — is the natural way to name a small fixed set of options. To compare, copy, print, or use one as a hash-map key, derive the traits it needs:

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum Coin { Penny, Nickel, Dime, Quarter }

fn cents(c: Coin) -> u64 {
    match c {
        Coin::Penny => 1,
        Coin::Nickel => 5,
        Coin::Dime => 10,
        Coin::Quarter => 25,
    }
}

fn main() {
    println!("{}", cents(Coin::Quarter));   // 25
    println!("{:?}", Coin::Dime);           // Dime  (from Debug)
}

#[derive(…)] asks the compiler to write the obvious implementation of a trait for you: Debug for {:?} printing, PartialEq/Eq for ==, Hash to use the type as a map key, Clone/Copy to duplicate it freely. Coin is the enum M0 is built on.

struct

Where an enum is a value that is one of several shapes, a struct is a value that bundles several fields together, each with its own name. Methods live in an impl block:

struct Purse {
    pennies: u64,
    nickels: u64,
}

impl Purse {
    fn new() -> Purse {             // an associated function: Purse::new()
        Purse { pennies: 0, nickels: 0 }
    }

    fn value(&self) -> u64 {        // a method: p.value()
        self.pennies * 1 + self.nickels * 5
    }
}

fn main() {
    let mut p = Purse::new();
    p.pennies = 3;
    p.nickels = 2;
    println!("{}", p.value());      // 13
}

An impl block collects the functions that work on a type. One taking &self (or &mut self) is a method, called with dot syntax (p.value()); one without a self parameter is an associated function, called through the type (Purse::new()) and used the way other languages use a constructor. A fixed struct like this is one of the representations M0 offers for its purse.

Collections: Vec and HashMap

Where a value holds a variable number of parts, it reaches for a collection. A Vec<T> is a growable array, taken apart by iterating rather than by a fixed pattern:

fn sum(xs: &Vec<i64>) -> i64 {
    let mut total = 0;
    for x in xs {
        total = total + x;
    }
    total
}

fn main() { println!("{}", sum(&vec![1, 2, 3, 4])); }   // 10

A HashMap<K, V> maps keys to values. entry(k).or_insert(d) hands back a mutable slot for key k, inserting the default d first if the key was absent — the idiom for tallying:

use std::collections::HashMap;

fn main() {
    let coins = ["penny", "dime", "penny", "penny", "dime"];
    let mut tally: HashMap<&str, u64> = HashMap::new();
    for c in coins {
        *tally.entry(c).or_insert(0) += 1;
    }
    println!("{}", tally["penny"]);   // 3
    println!("{}", tally["dime"]);    // 2
}

A Vec<Coin> records every coin individually; a HashMap<Coin, u64> records each kind with a count. Both, and the fixed struct above, are representations M0 lets you choose between.

Ownership, borrowing, and mutability

Rust has no garbage collector and no manual free. Instead every value has a single owner, and when the owner goes out of scope the value is released. This is the part of Rust that most often surprises a newcomer, and getting a feel for it is much of what M0 is for.

Assigning or passing a value moves it: ownership transfers, and the old name can no longer be used. For the small Copy types — i64, bool, char, and simple enums that derive Copy — the value is copied instead, so both names stay valid. To use a value without taking ownership, you borrow it with a reference:

• &T is a shared reference — read-only, and you may hold many at once.
• &mut T is an exclusive reference — you may write through it, and while it exists no other reference to the same value may.

fn total(xs: &Vec<i64>) -> i64 {       // borrows: caller keeps the Vec
    xs.iter().sum()
}

fn push_zero(xs: &mut Vec<i64>) {      // borrows exclusively: may mutate
    xs.push(0);
}

fn main() {
    let mut v = vec![1, 2, 3];
    println!("{}", total(&v));   // 6   — shared borrow
    push_zero(&mut v);           //     — exclusive borrow
    println!("{:?}", v);         // [1, 2, 3, 0]
}

Two rules do most of the work. A binding is immutable unless you write let mut, so a value can be changed only where mutation is asked for by name. And a value may have many readers or one writer, never both at once — the compiler enforces it, ruling out a whole class of aliasing bugs before the program runs. A lifetime — occasionally written 'a — is the compiler’s name for how long a borrow stays valid; it exists to guarantee a reference never outlives the value it points at, and in the code this book asks you to write it rarely has to be named.

M0’s combine leans on the move rule directly: taking its two purses by value consumes them, so Rust then stops you from reusing a purse you have already emptied into another. An operation that changes the purse borrows it as &mut; one that only reads it borrows as &.

Shared ownership with Rc

Single ownership fits a value with one clear home. Some structures instead need a value reachable from several places at once, with no one holder entitled to free it while another still points at it. Rc<T> — a reference-counted pointer — is the standard library’s answer. Rc::new(v) places v on the heap behind a shared handle; Rc::clone(&h) hands back another handle to the same v without copying it and adds one to a count of live holders, and v is released only when the last handle is dropped and the count reaches zero. An Rc<T> gives shared, read-only access (&T) to what it holds, so it does not by itself allow mutation — the many-readers-or-one-writer rule stays intact.

use std::rc::Rc;

fn main() {
    let a = Rc::new(vec![1, 2, 3]);
    let b = Rc::clone(&a);                 // same Vec, one more holder
    println!("{} {}", a.len(), b.len());   // 3 3
    println!("{}", Rc::strong_count(&a));  // 2
}

Option and Result

Two enums from the standard library carry the possibility of “no value” in the value itself, so a caller cannot ignore it:

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

Option<T> models a value that might be absent; Result<T, E> a computation that might fail, carrying why in the E. Both are ordinary enums — you take them apart with match:

fn checked_div(a: i64, b: i64) -> Option<i64> {
    if b == 0 { None } else { Some(a / b) }
}

fn main() {
    match checked_div(10, 2) {
        Some(q) => println!("quotient {}", q),   // quotient 5
        None    => println!("undefined"),
    }
    println!("{:?}", checked_div(10, 0));         // None
}

The ? operator

Threading a failure through several steps by hand nests match inside match. The ? operator does it in one character: applied to a Result, e? unwraps Ok(v) to v and, on Err(x), returns Err(x) from the enclosing function at once. The happy path then reads top to bottom:

fn checked_div(a: i64, b: i64) -> Result<i64, String> {
    if b == 0 {
        return Err("divide by zero".to_string());
    }
    Ok(a / b)
}

fn eval(a: i64, b: i64, c: i64) -> Result<i64, String> {
    let x = checked_div(a, b)?;   // an Err bubbles straight out here
    let y = checked_div(x, c)?;
    Ok(y)
}

fn main() {
    println!("{:?}", eval(100, 5, 2));   // Ok(10)
    println!("{:?}", eval(100, 0, 2));   // Err("divide by zero")
}

This is the exact shape an interpreter takes: evaluate a subexpression, and if it failed, propagate that failure — its message and the source it points at intact — without the surrounding code having to mention the failure at all. Values and runtime errors is where the book puts this pattern to work.

A handful of combinators are worth knowing, each a shorthand for a match that appears constantly:

• opt.unwrap_or(d) — the value inside, or d if it is None.
• opt.map(f) / res.map(f) — apply f to the value inside, leaving None / Err untouched.
• res.ok() — turn a Result into an Option, discarding the error.

Reach for match when the cases do different things, and a combinator when one line says it more plainly.

Where to go next

Practice your rust skills in Milestone M0: a coin purse built from the enum, struct, collection, and borrowing pieces above. When its tests pass, the tools run and the language is familiar enough to start the interpreter at Milestone M1.

To go deeper into Rust itself — well past what this book needs — the 100 Exercises to Learn Rust work through the language one small, test-driven step at a time.