42. Resolving variables

The same line, two answers

Here is a Drip program to think hard about:

let x = "global";
{
  fn show() { print x; }
  show();
  let x = "block";
  show();
}

When show is declared, the only x it can see is the global. So both calls should print global. The line print x is written once, in one place, and lexical scope promises that where it is written decides what x means.

Now run it on the interpreter from chapter 41, where every lookup walks the scope chain. show captured the block’s environment. The first call doesn’t find x there, follows the parent link and prints global. But then let x = "block" adds x to that same block environment. The second call finds it one step earlier and prints block.

Same line, same function, two different variables, depending on when it runs. The chain lookup is answering “which x is visible right now?” when the question should be “which x did this line mean when it was written?”

Decide once, before running

Nothing about which declaration a name refers to depends on running the program. You can tell by reading the source. So Drip gets one more stage in its pipeline, between parsing and running:

const program = parse(tokens, reporter);
const locals = resolve(program, reporter);
if (reporter.hadError) return; // exit 65
interp.interpret(program, locals);

The resolver walks the whole tree once. It keeps a stack of scopes, one per block or function body it is inside. A scope is a Map from name to a flag: is this variable “ready” yet? There are no values: the resolver never runs anything.

let x = "global";
{
  fn show() { print x; }
  show();
  let x = "block";
  show();
}

For each variable it meets, the resolver searches from the innermost scope outwards, and records how many scopes it had to step out:

function resolveLocal(e: Expr, n: Token) {
  const top = scopes.length - 1;
  for (let i = top; i >= 0; i--) {
    if (scopes[i].has(n.lexeme)) {
      locals.set(e, top - i);
      return;
    }
  }
  // not found: assume it's a global
}

locals is a Map whose keys are the syntax-tree nodes themselves. Map keys can be objects, compared by identity^[2], so two different x nodes in the program get two separate entries, even though they spell the same name.

From distance to environment

The interpreter’s lookup changes from “search the chain” to “hop exactly d parents up”:

private lookUp(name: Token, e: Expr) {
  const d = this.locals.get(e);
  return d === undefined
    ? this.globals.get(name)
    : this.env.getAt(d, name.lexeme);
}

ancestor(distance: number): Environment {
  let env: Environment = this;
  for (let i = 0; i < distance; i++)
    env = env.enclosing!;
  return env;
}

getAt(d, name) is this.ancestor(d).values.get(name). Assignment gets a matching assignAt. Here is a case with real distances, from inside inner:

fn outer() {
  let a = 1;
  {
    let b = 2;
    fn inner() { print a + b; }
    inner();
  }
}

This only works because the two sides match exactly. Every place the resolver pushes a scope (a block, a function body) is a place where the interpreter creates an environment. If one side ever added a level the other didn’t, every distance past it would be off by one.

Errors for free

While it walks, the resolver knows things the parser doesn’t, so it can report mistakes before a single line runs:

{
  let a = "outer";
  {
    let a = a;
  }
}
// Error at 'a': Can't read local
// variable in its own initializer.

That’s the “not ready” flag at work: a is declared, but not yet defined, when its initializer is resolved. It also reports Already a variable with this name in this scope. for two lets of one name in one block (globals may be redeclared), and Can't return from top-level code. for a return outside any function. Try it: the print on the first line never runs, because errors stop the program before the interpreter starts.

print "first line";
{
  let a = "outer";
  {
    let a = a;
  }
}
let g = 1;
let g = 2;
return g;

Your turn

function resolveDepth(scopes, name) {
  // your code here
  return 0;
}

{
  let a = "outer";
  {
    let a = "copy of " + a;
    print a;
  }
  print a;
}

What you learned

• Looking names up by searching the chain at run time let a closure’s variable change meaning when a later declaration shadowed it.
• Static analysis learns about a program without running it. The resolver is a pass between parsing and running.
• It walks a stack of scopes and records, for each local variable node, its scope depth: how many environments up it lives. Globals get no entry.
• The interpreter hops exactly that many parents. That needs one resolver scope for every runtime environment.
• The same walk reports errors early: reading a variable in its own initializer, duplicate locals, return at top level.

Next: classes, and a new kind of environment that holds just one name: this.