Names, Binding, and Scope

A name (or identifier) is a piece of syntax — a string like `x`, `total`, or `computeArea` — that appears in source code. On its own, a name carries no meaning; meaning comes from a binding, which is an association between a name and a denotable entity: a variable (really, a storage location or value), a function, a type, a module, a label, or a constant. The act of creating a binding is called a declaration (or binding occurrence) of the name. Every other appearance of that name within its region of validity is a use occurrence, referring back to the entity established by the declaration. The scope of a binding is the region of the program text (for statically scoped languages) or the region of execution time (for dynamically scoped languages) in which that binding is active — that is, where a use of the name resolves to that particular binding rather than some other one. Scopes are typically nested: a function body is nested inside a module, a block is nested inside a function, a loop body is nested inside a block. When scopes nest and an inner scope declares a name that was already bound in an outer scope, the inner binding shadows the outer one for the remainder of the inner scope; the outer binding is not destroyed, merely inaccessible until the inner scope ends. This is different from overloading, where multiple entities share a name but are distinguished by other information (such as argument types), and from aliasing, where two different names are bound to the same entity simultaneously. A crucial refinement is the hole rule: in most block-structured languages, the scope of a declaration is the entire enclosing block except for any nested region where the same name is redeclared — a "hole" carved out of the scope. This is why ``` let x = 1 in let x = x + 1 in x ``` evaluates to `2`: the inner `x` refers to the outer `x` during its own initializing expression (because the hole starts after the `=`, not before), then shadows it afterward. Scope rules therefore interact subtly with the exact syntactic point at which a binding becomes active — a detail that trips up both language designers and their users.

Name resolution is the process by which a compiler or interpreter maps each use occurrence of a name to its binding. The standard mechanism is a symbol table (or environment), a dictionary from names to their bound entities, organized as a stack of scopes that mirrors the nesting of the source program. Entering a new scope pushes a fresh table; leaving it pops that table off, restoring whatever was visible before. Looking up a name searches from the innermost table outward, stopping at the first match — this search order is precisely what implements shadowing. Two different design axes are worth separating clearly: 1. When is a binding made? — at compile time (static binding, e.g., most variable declarations in C), at link time (linking a function call to a compiled object file), or at run time (dynamic binding, e.g., virtual method dispatch, or `eval`-introduced variables). Earlier binding generally enables more optimization and earlier error detection; later binding generally enables more flexibility (polymorphism, dynamic loading, reflection). 2. How is scope determined? — lexical (static) scoping looks up names according to the textual nesting of scopes in the source, so the binding for a use can be determined without running the program. Dynamic scoping looks up names according to the chain of currently active function calls at run time, so the same use occurrence can resolve to different bindings on different calls. Lexical scoping is used by nearly all modern general-purpose languages (C, Java, Python, Rust); dynamic scoping appears in some Lisp dialects (historically), shell variable scoping in some contexts, and special-purpose mechanisms like Common Lisp's "special variables." The following pseudocode sketches how a compiler's scope resolution pass works over an abstract syntax tree, using a stack of symbol tables — this is the standard algorithm implementing lexical scoping with shadowing and the hole rule. ``` function resolve(node, scopeStack): match node: case Block(statements): push(scopeStack, newEmptyTable()) for stmt in statements: resolve(stmt, scopeStack) pop(scopeStack) case Declaration(name, initExpr):

# Hole rule: resolve the initializer BEFORE the new

# binding is installed, so `x = x + 1` sees the outer x. resolve(initExpr, scopeStack) table = top(scopeStack) if name in table: error("duplicate declaration of " + name + " in this scope") table[name] = freshEntity(node) case FunctionDef(name, params, body): table = top(scopeStack) table[name] = freshEntity(node) # function bound in enclosing scope push(scopeStack, newEmptyTable()) for p in params: top(scopeStack)[p] = freshEntity(p) resolve(body, scopeStack) pop(scopeStack) case NameUse(name): for table in reverse(scopeStack): # innermost first if name in table: bind(node, table[name]) # record the resolved binding return error("undeclared identifier: " + name) case BinaryExpr(left, right): resolve(left, scopeStack) resolve(right, scopeStack)

# ... other node kinds recurse structurally ``` The key invariant maintained throughout is: at the moment `NameUse(name)` is resolved, `scopeStack` contains exactly the tables for scopes lexically enclosing this point, innermost last, and each table contains exactly the names declared (and not yet shadowed-over) in that scope up to this point in a single left-to-right, outer-to-inner pass. Because the algorithm pushes on scope entry and pops on scope exit, and because it installs a declared name only after resolving its own initializer, this invariant is preserved by every case, which is precisely what a structural induction on the AST would show.

Time complexity. For a program of size $n$ (number of AST nodes, roughly proportional to source length), the resolution pass visits each node once, doing $O(1)$ work to push or pop a table and $O(d)$ work per name lookup, where $d$ is the current scope nesting depth. Since $d = O(n)$ in the worst case (deeply nested blocks) but is typically $O(\log n)$ or a small constant in real code, the pass runs in $O(n \cdot d)$ time in the worst case, which is $O(n^2)$ pathologically but effectively $O(n)$ in practice. Using hash tables for each scope's symbol table keeps per-scope insertion and lookup at expected $O(1)$, so the dominant cost really is the depth of the outward search on each use occurrence. A refinement used in real compilers avoids the repeated linear search: instead of scanning a stack of tables at each use, the compiler pre-computes, during the same traversal, a direct pointer from each use occurrence to its declaration (as the pseudocode's `bind(node, ...)` call does). This costs the same asymptotic time to build but makes every later compiler phase (type checking, code generation) do $O(1)$ binding lookups instead of re-searching scopes, which matters because those phases each revisit every node.

Space complexity. The scope stack holds at most $O(d_{\max})$ tables, each of size at most the number of names declared in that scope, so total auxiliary space is $O(n)$ in the worst case (every name distinct, all scopes open simultaneously along the deepest path), which is asymptotically optimal since the symbol table must at least record each declaration once.

Correctness argument. The resolution algorithm is correct with respect to the informal definition of lexical scope if it satisfies two properties, both provable by structural induction on the AST: 1. Soundness of shadowing — at any use occurrence, the algorithm returns the entity from the innermost enclosing declaration of that name. This follows because tables are searched innermost-first (`reverse(scopeStack)`), and a table for scope $S$ contains name $x$ exactly when $x$ was declared directly in $S$ before this point in the traversal (by the invariant established above), so the first match encountered is necessarily the most deeply nested one. 2. Correct hole placement — a declaration's initializer expression sees the outer binding of a name being shadowed, not the new one, because the algorithm resolves `initExpr` before mutating `table[name]`. This matches the standard "no self-reference unless the language explicitly permits recursive `let`" semantics found in languages like ML's non-recursive `let`, and is exactly why the example `let x = x + 1` above type-checks and evaluates sensibly instead of referring to itself.

Tradeoffs. Lexical scoping's chief benefit is that name resolution — and hence much of type checking — can be done entirely at compile time without running the program, which is essential for ahead-of-time optimization and for tools like IDEs to offer reliable "go to definition." Its cost is reduced runtime flexibility: you cannot, for instance, let a callee dynamically override a variable's meaning based on who called it, a feature dynamic scoping provides "for free" but which introduces correctness hazards, because a function's behavior then depends on its caller's local variable names rather than solely on the code visible at its definition site.

Consider this small program in a C-like pseudo-language, annotated with line numbers, tracing exactly how the resolver from the pseudocode above processes it. ``` 1: int total = 100; 2: 3: int scale(int total, int factor) { 4: int result = total * factor; 5: { 6: int total = result + 1; 7: result = total; 8: } 9: return result; 10: } ``` Trace of the scope stack (innermost table shown last) and each name resolution decision:

The interesting resolution is at line 7: the assignment `result = total` inside the inner block refers to the block-local `total` declared at line 6, not the function parameter `total`, because the search order is innermost-first and the block's table is on top of the stack at that point. Once the block ends (line 8), its table is popped, so the `return` statement at line 9 can no longer see the block-local `total` at all — it was never visible outside its own hole. This demonstrates shadowing (parameter `total` hidden by block `total`) and scope termination (block bindings vanish at the closing brace) in a single trace, exactly the mechanics the pseudocode's push/pop discipline enforces.

The clean separation between names, bindings, and scopes emerged gradually as languages moved beyond simple assembly-style symbol tables toward block-structured, higher-order programming. Algol 60 introduced lexically scoped, block-structured naming to the mainstream, establishing the "stack of scopes" discipline that nearly every subsequent language inherited. Lisp's early implementations initially used dynamic scoping for simplicity of implementation, and the tension this created — where a function's meaning depended on its caller rather than its textual context — motivated decades of research into closures and static scoping, culminating in Scheme's insistence on lexical scoping as a design principle.

Every compiler front end — for C, Java, Python, Rust, or any general-purpose language — implements some version of the scope-resolution algorithm described here, typically as one of the earliest passes after parsing, feeding directly into type checking and code generation. Interactive development tools such as IDE "go to definition," rename-refactoring, and autocomplete are direct applications of correctly resolved bindings: a rename tool must find every use occurrence bound to the exact declaration the user selected, which is only possible if scope resolution is sound. Interpreters for dynamically scoped languages (older Lisp dialects, certain configuration and templating languages, and shell scripting environments) must instead search the live call stack at run time, which is why such languages historically paid a performance penalty for variable lookup and why most general-purpose languages migrated to lexical scoping. Understanding binding and scope also underlies Environments (the runtime data structure implementing a chain of scopes during execution), the distinction between Static vs Dynamic Scope, and the closure semantics essential to functional and reactive programming, as well as the design of module systems, namespaces, and hygiene rules in macro systems that must avoid accidental name capture.

Ask the tutor: How do environments (the runtime data structure) implement lexical scope during actual program execution, and how do they support closures?