Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

22. Names resolve lexically, not by runtime search (narrows 0011)

  • Status: Accepted
  • Date: 2026-09-04

Context

ADR 0011 gave Korrin bare assignment and the nearest-binding rule: x = value looks for an existing binding of x in the current function scope, then each enclosing scope, out to global. Found means update it; not found means create x in the current scope. Reads use the same search. This is what removes the need for global / nonlocal keywords, and it is deliberate.

The tree-walking interpreter implements that search at run time, over a chain of Rc<RefCell<HashMap<String, Value>>> scopes (Environment::assign_existing). A bytecode VM wants the opposite: names resolved once, at compile time, to integer slots, so the inner loop indexes an array instead of hashing a string. Milestone 3 has to reconcile the two.

Reading ADR 0011 is not enough to know what needs reconciling, so the current interpreter was measured directly. Four facts, each from a program run against korrin run:

  1. Assigning to a name that exists in an outer scope updates that outer binding. A function containing count = count + 1, with count a global, increments the global. This is the rule working as designed and it is load-bearing.

  2. An assignment in a branch that never executes creates nothing. With a global g, a function whose only g = 999 sits under if false: reads the global.

  3. Assignments to names that exist nowhere else stay local and do not leak to the global scope when the call returns.

  4. The same assignment in the same function can mean different things on different calls. Given

    fn f():
    x = 1
    print(x)

f()        # no global `x` yet: creates a local, global untouched
x = 5
f()        # a global `x` exists now: writes it, so `x` becomes 1

    the first call creates a local and the second writes the global.

Fact 4 is the problem. Under ADR 0011 as implemented, whether an assignment targets a local or an enclosing binding is not a property of the program text at all. It is a property of the state of the scope chain at the moment the assignment runs, and it can differ between two calls of the same function. No compiler can assign that name a slot, because there is no answer to give.

Nor is this a corner case that could be quarantined and accepted as a difference between the two engines: fact 1 is the same mechanism, and it is the documented, intended behaviour that makes global unnecessary.

Decision

Name resolution becomes lexical. Which binding a name refers to is fixed by the program text, at compile time, and is the same on every execution of that line. For a name n appearing in function f, in order:

  1. If n is a parameter of f, it is f's local.
  2. Otherwise, if n is lexically bound in an enclosing function (see below), it is that function's binding, reached as an upvalue.
  3. Otherwise, if n is lexically bound at module top level, or is a name the prelude installs (a builtin, or Error), it is a module global.
  4. Otherwise, if n is assigned anywhere in f's body, it is f's local.
  5. Otherwise it is a module global, and reading it before anything binds it is E0301, as today.

"Lexically bound in a scope" means the name appears anywhere in that scope's own body, in any position that introduces a binding: an assignment target, a for loop variable, an except binding, a parameter, or the name of a fn, class, or import ... as. Position within the body does not matter, only membership.

The nearest-binding rule survives unchanged: an assignment still targets the nearest binding of that name, and still creates one locally when there is no other. What changes is that "is there another one?" is answered by looking at the enclosing text rather than at the live scope chain.

Two supporting consequences of slotting locals:

  • A local slot begins each call uninitialized, which is distinct from nil. Reading a local before its first assignment in that call is E0301, matching the interpreter's "not found in this call yet".
  • Globals stay a name-keyed table, not slots. Module globals are created in execution order, the REPL adds to them between chunks, and modules each have their own; a hash lookup is the right shape for that and is what every comparable language does.

The tree-walking interpreter is not changed to match. It keeps its runtime search, and the differential test suite carries one documented exception for the programs where the two disagree (below). Rewriting the interpreter's scoping would compromise the very thing it is being kept for: being a simple, independently-written implementation that was not derived from the VM.

Consequences

  • Locals become array slots, which is the single change that makes a bytecode VM worth building. Reads and writes of a local are an index, not a string hash and a chain walk.

  • Facts 1, 2 and 3 above are all preserved exactly. Assigning to a global from inside a function still writes the global, with no keyword, which was ADR 0011's point.

  • The narrow divergence. The engines disagree only when a function assigns a name that is also bound at module top level (or in an enclosing function), and the function runs before that outer binding has been created, and the program observes the outer name in between. Under the interpreter the early call creates a throwaway local; under the VM it creates the outer binding. The smallest program that can tell:

    fn f():
    x = 1

f()
print(x)     # interpreter: E0301. VM: 1
x = 5

    Note that fact 4's program above, despite being built to expose the order-dependence, prints the same under both rules, because nothing observes x during the window. Reaching the difference takes a program that reads an outer name after a call that would have created it and before the text that does.

  • This is pinned as a golden test rather than left to be re-discovered: a future differential-fuzz failure of this shape must be recognised in seconds, not investigated as a new bug.

  • A consequence Korrin already had, now made lexically visible: assigning to a builtin's name inside a function clobbers the builtin for the whole program (str = "hi" in any function leaves str(42) failing with E0302). The rule above does not introduce this, but it does make it something a compiler can see, and so something a future lint could warn about.

  • The specification's execution-model section needs rewriting. Its claim that name resolution "searches the current scope, then each enclosing scope" describes the mechanism rather than the language, and is now only true of one engine.

  • Compilation gains a pre-pass per function body to collect binding sites before emitting code, since rule 4 needs the whole body before the first statement can be compiled.

Alternatives considered

  • Static locals, Python's rule: a name assigned anywhere in f is a local of f, full stop. This is what the Milestone 3 plan originally proposed, on the assumption that the interpreter's dynamic behaviour was a narrow corner. Fact 1 shows it is not: this would silently break every function that updates a global, and recovering that would require the global / nonlocal keywords ADR 0011 explicitly refused. It is a different language, not a different implementation of this one.
  • Implement the runtime search faithfully in the VM. Correct by construction and preserves fact 4, but then no name in a function body can be slotted, because any of them might resolve outward on any given call. The VM would still beat the tree-walker on dispatch and call overhead, and would lose most of the reason to exist.
  • A hybrid: slot only names that provably cannot be outer bindings, keep the dynamic path for the rest. Sound, and it preserves fact 4 exactly. Rejected because the set of "possible globals" is every top-level binding in the module, so adding an unrelated global named i would silently deoptimise every function in the file that uses i as a loop variable. Performance that depends on invisible name collisions is worse than a rule people can hold in their heads.
  • Changing the interpreter to match the VM. Would remove the divergence entirely, and was rejected because the interpreter's value as an oracle comes from being an independent implementation. Two engines that share a scoping implementation cannot catch each other's scoping bugs.