Chapter 9: The Renamer

New files

src/rename.rs

src/scc.rs

src/renamed.rs

Changed files

src/names.rs

src/typecheck.rs

src/ast.rs

src/core.rs

src/elaborate.rs

src/eval.rs

src/fixity.rs

src/lib.rs

src/main.rs

src/parse.rs

src/types.rs

Motivation

Two variables can both be called x and mean entirely different things. That’s easy enough to follow in a small expression. It gets less comfortable when the compiler starts moving expressions around. We’d like to settle which binding each occurrence means once, then carry that answer through the rest of the compiler.

That’s the renamer’s first job. Its second is to free us from writing helpers before the functions that use them. Some functions even call each other, so there is no possible ordering that puts every helper first. We’ll find those groups in a dependency graph and give the type checker the whole group at once.

The Language, Now

Top-level and local declarations may refer forward within their block. These two functions belong to the same recursive component:

even n = if n == 0 then True else odd (n - 1)

odd n = if n == 0 then False else even (n - 1)

main = even 100

Each binding block is one lexical scope. A local definition shadows a global with the same spelling. Two definitions in the same block are an E0102 error. Every member of a recursive component must have a function right-hand side. Thus a = b; b = a is rejected with E0120, even if neither value is used.

Fixities also receive a scope check. A top-level fixity declaration must have a matching definition in the file (E0130). An unbound variable reports E0101 and suggests an in-scope spelling when its edit distance is at most two.

Theory

A binding identity consists of an interned spelling and a fresh integer. The spelling serves diagnostics. The unique integer separates shadowed binders. Inference and Core use these identities, so neither has to repeat lexical lookup. This is the compiler counterpart of the binding distinctions explored in Chapter 3 (Pierce 2002).

Draw an arrow from a function to each binding in its block that it uses. If even calls odd and odd calls even, we can follow arrows from either one back to the other. They belong together. A strongly connected component is a maximal group with this mutual-reachability property.

Now treat each group as one node. The resulting graph has no cycles, so we can process its dependencies first. That’s the order our type checker needs. A helper outside a recursive group can have its type generalized before its callers use it (Simon Marlow 2010).

Inside a recursive component, allocate one provisional monotype per binder and infer all bodies against them. Unify those provisional types with the results. Only then generalize the component. Outside the component, each occurrence can instantiate the resulting schemes independently. Signatures still check inferred types here. Signature-directed polymorphic recursion remains Chapter 14’s work.

Implementation

Name resolution

The surface tree retains a whole local declaration block until renaming. The renamer allocates all of that block’s identities before visiting any right-hand side. Each lambda introduces a smaller scope containing its parameter. Lookup searches scopes from the innermost outward.

#![allow(unused)]
fn main() {
pub fn rename(
    sess: &mut Session,
    program: ast::Program,
) -> Result<Program, Stop> {
    let program = crate::fixity::resolve(sess, program)?;
    for fixity in &program.fixities {
        for op in &fixity.operators {
            if !program.bindings.iter().any(|b| b.name == *op) {
                sess.emit(Diagnostic::error(
                    ErrorCode::OrphanFixity,
                    format!("fixity without a definition: {op}"),
                    fixity.span,
                ));
            }
        }
    }
    let mut primitives = Vec::new();
    let mut prelude = BTreeMap::new();
    if !sess.options.no_prelude {
        for op in [
            Op::Div,
            Op::Mod,
            Op::Add,
            Op::Sub,
            Op::Mul,
            Op::Append,
            Op::Eq,
            Op::Lt,
            Op::Le,
        ] {
            let id = sess.fresh_id(op.text());
            prelude.insert(op.text().into(), id.clone());
            primitives.push((op, id));
        }
    }
    let mut renamer = Renamer {
        sess,
        scopes: vec![prelude],
    };
    let groups = renamer.bindings(program.bindings);
    let main = renamer.lookup("main", program.span);
    renamer.sess.finish(Program {
        groups,
        primitives,
        main,
        span: program.span,
    })
}
}

The renamed tree is a separate IR. Its occurrences contain an Id, which keeps a Name and its diagnostic spelling together. Dumps display names as x#12. This small amount of repeated text keeps dumps readable after the source session has gone away. Comparisons still include the allocated identity.

Errors accumulate during the walk. An unresolved occurrence receives a fresh placeholder so other bodies can still be checked for scope errors. The driver stops after the renaming pass, before any placeholder can reach evaluation.

Dependency components

Tarjan’s search assigns each vertex an index and records the lowest reachable index still active on the search stack. When the two indices agree, the vertex is the root of a complete component, which can be popped together.

#![allow(unused)]
fn main() {
fn visit(&mut self, v: usize) {
    self.index[v] = Some(self.next);
    self.low[v] = self.next;
    self.next += 1;
    self.stack.push(v);
    self.active[v] = true;
    for &w in &self.edges[v] {
        if self.index[w].is_none() {
            self.visit(w);
            self.low[v] = self.low[v].min(self.low[w]);
        } else if self.active[w] {
            self.low[v] = self.low[v].min(self.index[w].unwrap());
        }
    }
    if self.low[v] == self.index[v].unwrap() {
        let mut group = Vec::new();
        loop {
            let w = self.stack.pop().unwrap();
            self.active[w] = false;
            group.push(w);
            if w == v {
                break;
            }
        }
        group.sort_unstable();
        self.result.push(group);
    }
}
}

Our edges point toward dependencies, so completed components arrive in the order inference needs. We visit source indices in a fixed order to keep dumps reproducible. A group containing just one binding is recursive only if that binding refers to itself. As a check on Tarjan’s bookkeeping, the tests also find components by the much slower but direct method of testing mutual reachability.

Inference by group

The environment contains all provisional types while a recursive component is being inferred. Generalization waits until every body has contributed constraints. Signatures are checked against the inferred schemes, and specialization propagates through the shared component before the exported schemes are finalized.

#![allow(unused)]
fn main() {
fn group(
    &mut self,
    env: &mut Vec<(Id, Scheme)>,
    group: &BindGroup,
) -> Result<(), Diagnostic> {
    self.level += 1;
    let size = env.len();
    let provisional: Vec<_> = group
        .binds
        .iter()
        .map(|b| (b.id.clone(), self.fresh()))
        .collect();
    if group.recursive {
        env.extend(
            provisional
                .iter()
                .map(|(id, ty)| (id.clone(), Scheme::mono(ty.clone()))),
        );
    }
    let inferred = group
        .binds
        .iter()
        .zip(&provisional)
        .map(|(b, (_, expected))| {
            let ty = self.infer(env, &b.rhs)?;
            if group.recursive {
                self.unify(expected, &ty, &b.rhs)?;
            }
            Ok(ty)
        })
        .collect::<Result<Vec<_>, Diagnostic>>();
    env.truncate(size);
    self.level -= 1;
    let inferred = inferred?;
    for (binding, ty) in group.binds.iter().zip(&inferred) {
        if let Some(annotation) = &binding.annotation {
            let scheme = self.generalize(ty.clone());
            self.check_signature(&scheme, annotation, &binding.rhs)?;
        }
    }
    self.level += 1;
    for (binding, ty) in group.binds.iter().zip(&inferred) {
        if let Some(annotation) = &binding.annotation {
            let declared = self.instantiate(annotation);
            self.unify(ty, &declared, &binding.rhs)?;
        }
    }
    self.level -= 1;
    for (binding, ty) in group.binds.iter().zip(inferred) {
        env.push((binding.id.clone(), self.generalize(ty)));
    }
    Ok(())
}
}

That last step matters. If f and g call one another and f has an Int -> Int signature, a shared argument type must also constrain g. Exporting an unconstrained polymorphic scheme for g would be unsound. A regression test rejects a subsequent g True call.

Recursive closures

The interpreter stores an immutable recipe for every recursive group: its lambda bodies and the outer environment. Entering one of these closures reconstructs the group’s bindings before adding the function argument. No closure needs a mutable pointer to itself, and there is no reference-counting cycle.

#![allow(unused)]
fn main() {
fn recursive_values(bindings: Rc<Vec<Bind>>, env: Rc<Env>) -> Env {
    let mut values = Vec::new();
    for binding in bindings.iter() {
        let Expr::Lam(parameter, body) = &*binding.rhs else {
            unreachable!("recursive lambda invariant")
        };
        let value = Value::Closure {
            parameter: parameter.clone(),
            body: Rc::new(*body.clone()),
            env: env.clone(),
            recursive: Some(bindings.clone()),
        };
        values.push((binding.name.clone(), value));
    }
    values
}
}

Top-level value initializers run once in dependency order. Functions are closures. Creating one does not run its body. Core lint now checks unique binder identities as well as scope, primitive saturation, and the recursive-lambda restriction.

Running It

$ cd crates/ch09_rename
$ cargo run -q -- run tests/programs/rename/mutual.fun
True
$ cargo run -q -- dump --pass=rename tests/programs/fun-forward.fun
nonrec { later#10 = 1; }
nonrec { main#9 = later#10; }
$ cargo xtask check-inherit 09
chapter 09: 101 inherited programs verified and chapter tests passed

Try moving the helper in a small program below its caller. It now works. Then make the two functions call each other and inspect the rename dump. You should see one recursive group, which tells the checker to infer them together.

Exercises

Introductory. annotate each occurrence of x in a nested-shadowing example with the binder it references. Compare with the rename dump.
Intermediate. Draw the dependency graph of a three-function recursive group with one non-recursive helper, then predict the emitted component order.
Intermediate. Add a diagnostic test with two independent misspelled names and verify that the pass reports both.
Advanced. Explain why the immutable closure recipe has no reference-counting cycle even when one of its functions returns another closure.
Advanced. Identify where signature-directed polymorphic recursion will require the current component construction and checking strategy to change.

Write You a Haskell