01 — The Resolver Pass: Why and What

The interpreter in cp-03 resolves variable names at runtime, by walking the environment chain on every access. That works but has two problems:

1. Performance: O(depth) lookup on every read/write.
2. Correctness: The interpreter can silently read from the wrong scope if names shadow each other across closure boundaries.

The resolver pass is a static analysis pass that runs after parsing and before interpreting. It walks the AST once, builds a map of (VarExpr* → depth), and annotates every variable use with the exact environment depth at which its binding lives. The interpreter can then do O(1) direct-depth lookups.

The scope of the problem

var a = "global";
fn outer() {
    fn inner() { print a; }
    inner();
}
outer();

With a naive runtime-walking resolver:

• When print a runs, the interpreter looks in inner's frame, then outer's frame, then global, finds a = "global" and prints it.
• This works correctly.

But:

var a = "global";
fn showA() {
    print a;
}
fn test() {
    var a = "local";
    showA();
}
test();

Lexical scope says showA should print "global" — a in its body refers to the a visible when showA was defined, not when it's called. A runtime chain walk starting from the call site environment would incorrectly find "local" from the caller test.

The resolver fixes this: it records, at parse time, that the a in showA is 1 level up from its closure's capture point. At runtime the interpreter goes exactly 1 level up in the closure's parent chain — not the caller's.

What the resolver produces

A std::unordered_map<Expr*, int> locals_ in the interpreter:

class Resolver {
    std::vector<std::unordered_map<std::string, bool>> scopes_;
    Interpreter& interp_;  // writes into interp_.locals_
public:
    void resolve(std::vector<StmtPtr>& stmts);
private:
    void resolveLocal(Expr* e, const std::string& name);
    void beginScope();
    void endScope();
};

resolveLocal(expr, name) searches scopes_ from the innermost outward. When it finds the name, it records scopes_.size() - 1 - depth (the "distance" from the current scope) in interp_.locals_[expr].

The interpreter's lookUpVariable

Value Interpreter::lookUpVariable(const std::string& name, Expr* e) {
    auto it = locals_.find(e);
    if (it != locals_.end())
        return env_->getAt(it->second, name);  // O(1) direct depth
    return globals_->get(name);
}

Variables not found in locals_ are globals — they're not annotated because they live at depth 0 from the global environment, which the interpreter always has a direct pointer to.

When to run the resolver

After parsing the full source, before execution:

auto stmts = parser.parse();
Resolver resolver(interp);
resolver.resolve(stmts);
for (auto& s : stmts) interp.execute(*s);

The resolver pass is one linear traversal of the AST. It touches every node exactly once. After it runs, the interpreter's locals_ map is fully populated and all subsequent variable lookups are O(1).