Environment Representations and Lookup

The previous chapter settled what an environment has to provide: lookup, which reads the value a name is currently bound to, and extend, which produces a new environment binding a name to a value — the two operations Bridger’s lexical scope is built from. A running program reads a variable at nearly every step and enters or leaves a block at many of them, so lookup and extend run constantly, and the way the environment is represented sets what they cost. This chapter opens the representation the Bridger starter repository provides: what the scope chain is made of, and what a lookup costs as the chain deepens. It is the environment your interpreter uses in Milestone M2 to evaluate variables, let bindings, and blocks.

The chain of scopes

In the previous chapter, we learned how to read the value a name was bound to by following lexical scoping rules. How do we make that mechanical? The general intuition we used in lexical scoping was that the value a name was bound to was defined by the innermost let binding for that name next to the occurrence being read. We use that intuition to represent the environment as an immutable linked list of bindings whose head is the innermost binding and whose tail is the outermost binding. Consider the following block of code:

let x = 1;
{
  let y = 2;
  {
    let z = 3;
    x + z
  }
}

On line 6, when we evaluate x + z, the scope has an environment with the bindings x = 1, y = 2, and z = 3. Pictorially, the linked list of bindings would appear as a chain with the innermost binding being z = 3, then y = 2, then x = 1, and finally any environment containing the block of code (e.g., the global/root environment). If we wanted to look up the value of x in the environment, we would walk from the innermost binding (z = 3) rightward until we found a binding for x, or reached the end of the list and reported that x is unbound.

The figure traces that walk for x: a miss at z’s scope, a miss at y’s, and a hit at the third. That walk is E-Var — a name is read by starting at the innermost scope and following the links outward, taking the first binding it finds — and running off the end of the chain without a match is the UnboundVariable case. Because the walk stops at the first match, an inner binding is reached before an outer one of the same name: the walk is what makes shadowing resolve to the innermost binding.

Each extend produces one such scope — a binding and a link to the scope enclosing it — and leaves its parent untouched, because the environment is read-only. A parent is therefore shared by every scope built on top of it, and leaving a block discards only the innermost scope and exposes the chain below it unchanged: a name bound inside a block is out of scope the moment the block ends, because nothing was written that has to be undone.

In Rust, a scope is a small record — a name bound to a value, and a link to its parent:

// A scope: one binding, and a link to the scope that encloses
// it. `Rc` lets a scope be shared — several scopes can hold the
// same parent, and a value can keep a scope alive after the
// block that built it has returned.
struct Scope {
    name:   Name,
    val:    Value,
    parent: Option<Rc<Scope>>,
}

// `extend` puts a new scope in front and leaves its parent as
// it was — the read-only environment of the previous chapter.
fn extend(parent: &Rc<Scope>, x: Name, v: Value) -> Rc<Scope> {
    Rc::new(Scope { name: x, val: v, parent: Some(Rc::clone(parent)) })
}

// `lookup` walks outward: this scope, then its parent, and on
// until the name matches or the chain runs out — a run-out is
// the `UnboundVariable` of the previous chapter.
fn lookup(scope: &Rc<Scope>, x: &Name) -> Option<Value> {
    let mut cur = scope;
    loop {
        if cur.name == *x {
            return Some(cur.val.clone());
        }
        match &cur.parent {
            Some(p) => cur = p,
            None => return None,
        }
    }
}

The parent link is an Rc, a reference-counted shared pointer. A plain owned pointer — one scope owning its parent outright — would be enough while a scope lives no longer than the block that built it and is freed when that block ends. It stops being enough once a value can carry a scope away from its block: a function value keeps the scope it was defined in so it can read its free names when it later runs, and that scope has to stay alive after the block that created it has returned (the subject of Part V). Shared ownership lets the carried-away scope and the chain both hold it, and it lives as long as either does. The reason the chain is refcounted rather than owned lands with closures; the representation is chosen here so that it can.

Each scope holds a single binding because Bridger adds one scope per let, so the chain grows by a link at every binding. A common alternative gives each block one scope holding all of its bindings in a map; a lookup then walks scope to scope and probes the map at each. The distance a lookup travels is measured in bindings one way and in scopes the other, and the walk is otherwise the same.

What a lookup costs

A lookup costs its walk: the number of scopes visited before the binding is found. A name bound in the current block is a step away; a name from an enclosing block is as many steps as the scopes between the use and the binding; a prelude name read from deep inside nested blocks is the length of the whole chain. extend adds a single scope at the front, and discarding a scope drops the innermost link, so growing and shrinking the environment are each a constant-time operation and the cost of the representation sits on lookup.

A different representation moves that cost. A single map from every name currently in scope to its value answers a lookup in one probe, with no walk at all. What it does not get for nothing is the coming and going of scopes: entering a block has to record every name the block shadows, and leaving the block has to put the shadowed values back, so the map carries a stack of shadowed bindings per name, or a snapshot restored on exit. The bookkeeping the chain spends on a lookup, the flat map spends at every scope boundary instead. Which representation costs less depends on whether a program reads variables more often than it opens scopes, or the reverse.

Resolving names before the run

Lexical scope settles which binding an occurrence refers to before the program runs, so the walk’s outcome is fixed ahead of time too: for a given occurrence of a name, the number of scopes to skip before its binding is found is the same on every run, because the nesting of scopes at that point is the nesting of the enclosing blocks, and the text fixes that. Because each scope holds one binding, that count is the whole answer. A name can then be replaced, before the run, by the number of scopes the walk would have crossed, and the reference read by stepping out that many scopes — with no name compared along the way.

That single number is what Nicolaas de Bruijn introduced in 1972: drop the names entirely and write each variable as the distance to its binder — the count of enclosing binders to cross — so a term carries no variable names at all (de Bruijn, 1972). Two terms that differ only in their choice of names become the same term, and shadowing is just a larger distance, so the renaming questions that surround names do not arise. A scope that holds several bindings — the block representation, where one scope carries a whole block’s names — needs a second coordinate on top of the distance: which scope to stop at, and which binding within it. That pair is called lexical addressing, and over a single-binding chain its second coordinate is always zero, leaving de Bruijn’s lone index.

It is the same chain, with x’s spelling replaced by its distance. Because the target is fixed by the text, computing that distance is a pass over the program made before it runs, and once done the run-time lookup steps out a fixed number of scopes, with no name searched for.

Bridger keeps names. Resolving references to coordinates is a pass a tree-walker can do without, and the speed it buys is not what a tree-walker is for; against it, a name is what an error reports. UnboundVariable names the variable, and so do the type errors of Part VI, while a coordinate has no name to hand back. The chain stays keyed by name, and a lookup stays a walk.

The design space

Several choices sit behind the environment, and Bridger has taken a point in each.

Where a lookup’s cost falls. A chain of scopes puts it on the walk and keeps extension and exit cheap; a flat map spends it on save-and-restore at each scope boundary and keeps a lookup a single probe. A program that reads variables far more often than it opens scopes is served by the first; a program dominated by scope changes over shallow lookups by the second.

By name or by position. Keyed by name, a reference is searched for by spelling at run time and every name survives into the running program, where an error can report it. Resolved to a position — a de Bruijn index over the single-binding chain, or the ⟨scope, binding⟩ pair of lexical addressing once a scope holds several — a reference is found without a search, at the price of a resolution pass and of the names an error might have used. This choice is open only because scope is lexical: a language deciding bindings while running could not resolve them before it.

Owned or shared. A singly owned chain is enough while a scope dies with its block. Sharing — Bridger’s Rc — is forced once a value outlives its defining block and has to carry that block’s scope with it, which is what a closure does. Bridger shares from the start, so the chain a block builds can be captured without copying it (Part V).

The one scope not built by an extend is the root, which holds the prelude and the top-level functions. Because those functions may call one another regardless of the order they are written in, the root is assembled by the interpreter’s provided setup before any of them runs, rather than grown a binding at a time the way a block’s scopes are.

Further reading

Nameless variable representations: N. G. de Bruijn’s Lambda calculus notation with nameless dummies (Indagationes Mathematicae, 1972) represents each variable by the distance to its binder, so that terms differing only in their choice of names coincide and renaming is unnecessary — the representation an interpreter borrows when it resolves references to positions.

Lexical addressing: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) works through resolving a variable reference to a coordinate — which enclosing scope, and which binding within it — in its treatment of compilation, so that a name is found by position rather than searched for by spelling.

Concept checks