04 — Depth Annotations: O(1) Environment Lookups

After the resolver runs, every local variable reference has an integer depth stored in interp_.locals_. This step shows how the interpreter uses that information to avoid chain walking.

The `getAt` and `setAt` methods

Value& Environment::getAt(int depth, const std::string& name) {
    Environment* e = this;
    for (int i = 0; i < depth; ++i) e = e->parent_.get();
    return e->vars_.at(name);
}

void Environment::setAt(int depth, const std::string& name, Value v) {
    Environment* e = this;
    for (int i = 0; i < depth; ++i) e = e->parent_.get();
    e->vars_[name] = std::move(v);
}

The loop here is O(depth), but depth is a small compile-time constant for each site. More importantly, it avoids calling vars_.count() at every intermediate scope — the lookup is direct.

`lookUpVariable` and `assignVariable`

Value Interpreter::lookUpVariable(VarExpr& e) {
    auto it = locals_.find(&e);
    if (it != locals_.end())
        return env_->getAt(it->second, e.name);
    return globals_->get(e.name);  // fallback to globals
}

void Interpreter::assignVariable(AssignExpr& e, Value v) {
    auto it = locals_.find(&e);
    if (it != locals_.end())
        env_->setAt(it->second, e.name, std::move(v));
    else
        globals_->set(e.name, std::move(v));
}

The locals_ map key is the pointer to the AST node, not the variable name. This is intentional: two different uses of x in the source (two VarExpr nodes) can refer to bindings at different depths, and the pointer uniquely identifies which AST node is being evaluated.

Why pointer keying is correct

let x = 1;
fn f() {
    let x = 2;
    print x;  // VarExpr node A — depth 0 in f's scope
}
print x;      // VarExpr node B — depth 0 in globals

Both uses are named x, but they are different AST nodes. The resolver annotated A as depth=0 and B as not-in-locals (global). The interpreter uses the pointer to distinguish them.

If the key were the name string, both would map to the same entry and one would be wrong.

Measuring the improvement

Without annotations, getAt is O(depth) and calls find at every intermediate scope. With annotations, it's still O(depth) for the loop but does only one find at the target scope. The real saving is correctness (dynamic-scope bug eliminated) more than raw speed.

For a program with average nesting depth 3:

Without annotations: 3 × (hash_lookup + parent_deref) per variable use.
With annotations: 3 × parent_deref + 1 × hash_lookup.

At scale this matters. The JVM and V8 both keep variable annotations in bytecode for the same reason — not because they need O(1) vs O(3), but because the slot index is also used for register allocation and inlining.

Environment structure with slots

Production VMs go one step further: instead of named maps, each scope is a slot array and each variable use has a slot index. getAt(depth, slot) is just pointer arithmetic:

// production VM sketch
env[depth].slots[slot]

cp-03/04 uses named maps for clarity. cp-06+ introduces bytecode with explicit stack slots, which is the array-indexed equivalent.

Compilers & Parser Engineer