7.1 Name Resolution and Scope: Who Does a Name Actually Point To?

This chapter starts with name binding, adds type and control-flow information, and lowers the tree into an intermediate representation suitable for analysis.

The AST confirms that x + 1 has a valid syntactic structure, but it doesn’t yet know whether x is a local variable, a function parameter, a module member, or simply an undefined name. Name resolution binds ordinary variable uses to declarations. An overloaded function name may first resolve to a candidate set, with the final target selected once type information is available.

Learning Objectives

• Distinguish between declarations, definitions, and name usages;
• Implement definition and lookup within lexical scoping;
• Handle name shadowing, duplicate declarations, and forward references;
• Assign stable symbol identities for subsequent type checking.

1. Names Are Not String Equality

let x = 1;
{
    let x = 2;
    print(x);
}
print(x);

The two print calls both contain the string x, yet they refer to distinct declarations. The compiler must rewrite or annotate AST name nodes as stable symbol IDs:

outer x → Symbol#17
inner x → Symbol#23

Later phases use IDs instead of repeatedly resolving strings. An ID stays stable for its compilation and object lifetime; reuse across edits or caches requires a separate identity scheme, not merely an incrementing integer. Optimizations and renames should preserve bindings even when display names change.

2. Scope Trees Rather Than Hash Table Stacks

Simple single-pass languages maintain a scope stack: push when entering a block, pop when exiting, and look up from inner to outer. A full compiler typically represents scopes as a tree, enabling features such as:

• IDEs to query visible symbols at any point in the code;
• Deferred analysis of function bodies;
• Module imports and incremental compilation;
• Closure capture and escape analysis;
• Diagnosis of conflicting declarations and their origins.

ModuleScope
└── FunctionScope(add)
    ├── parameter a
    ├── parameter b
    └── BlockScope
        └── local result

Each scope records its parent and local declaration map. If a name is not visible throughout the block, retain its visibility range and filter by query position; a tree alone does not answer every IDE lookup. Lookups proceed upward along the parent chain from the current scope. Module-level, type-member, and inheritance hierarchies may employ different lookup rules and cannot all be forced into a single lexical parent chain.

3. Definition and Lookup Interfaces

A declaration introduces a name and type information; a definition also supplies the entity. In C, extern int count; declares an object and int count = 0; defines it. A function prototype differs from a definition with a body. The language determines which repeated declarations are permitted. This C data-model fragment requires <stdint.h> and host definitions for the other IDs, Map, and Span:

typedef uint32_t SymbolId;

typedef struct Symbol {
    SymbolId id;
    StringId name;
    SymbolKind kind;
    AstNodeId declaration;
    TypeId declared_type;
    Span span;
} Symbol;

typedef struct Scope {
    struct Scope *parent;
    Map declarations; // StringId -> SymbolId
} Scope;

define checks the current scope for conflicting declarations. lookup checks the current scope and then its ancestors. Using lookup to reject duplicates would also reject valid shadowing.

This complete Python example tests block-local definitions and parent-chain lookup: inner shadowing is allowed, local duplicates are rejected. Parent references must form an acyclic lexical scope tree. Forward references and visibility ranges are not implemented here:

from dataclasses import dataclass
from itertools import count

_ids = count()

@dataclass(frozen=True)
class Symbol:
    id: int
    name: str

class Scope:
    def __init__(self, parent=None):
        self.parent = parent
        self.declarations = {}

    def define_current(self, name):
        if name in self.declarations:
            raise ValueError(f"duplicate declaration: {name}")
        symbol = Symbol(next(_ids), name)
        self.declarations[name] = symbol
        return symbol

    def lookup_visible(self, name):
        scope = self
        while scope is not None:
            if name in scope.declarations:
                return scope.declarations[name]
            scope = scope.parent
        return None

outer = Scope()
first = outer.define_current("x")
inner = Scope(outer)
second = inner.define_current("x")
assert inner.lookup_visible("x") is second
assert outer.lookup_visible("x") is first
assert first.id != second.id
assert inner.lookup_visible("missing") is None
try:
    inner.define_current("x")
except ValueError as error:
    print(error)  # duplicate declaration: x
else:
    raise AssertionError("duplicate declaration accepted")

The declaration table should store the span of each declaration to enable precise error messages indicating both the new and original locations:

line 9:5: `count` declares a duplicate in the current scope
line 3:5: The previous declaration was here

4. Declaration Visibility Timing Belongs to Language Specification

Consider:

let x = x + 1;

The right-hand side x may refer to the outer variable, the currently being initialized variable, or be invalid, depending on the language's choice.

When analyzing declarations, the compiler may:

1. Resolve names in the initializer first, then add the name to the current scope;
2. Add the declared-but-uninitialized state first, then analyze the initializer;
3. Collect declarations across the scope first, then analyze bodies and check initialization dependencies according to the specification.

The third approach supports mutual recursion and forward references. Collecting declarations does not execute initializers or automatically allow reading uninitialized values. Duplicate declarations, initialization order, and IDE visibility still follow the language rules. Never let traversal order accidentally define language semantics.

5. Namespaces May Be More Than One

Some languages separate type names, value names, labels, and macros into different namespaces, allowing the same spelling to exist simultaneously across different categories. Other languages use a single, unified namespace.

The symbol table key might be:

(name, namespace) → SymbolId

Member lookup also depends on the receiver type: the x in point.x should not be resolved from the current lexical scope. Qualified names package.module.name must be parsed segment by segment, with visibility and import aliases properly handled.

6. Shadowing, Capture, and Closures

Shadowing occurs when an inner declaration temporarily hides a similarly named outer declaration. Whether this is allowed, warned about, or prohibited depends on the language and symbol type.

When an inner function references an outer local variable, capture takes place:

fn outer() {
    let count = 0;
    fn next() { count = count + 1; }
}

Name resolution first binds count to the outer Symbol; the language determines capture-by-value or capture-by-reference behavior and whether closures share mutable variables. Closure conversion chooses a representation that preserves those semantics, while escape analysis may determine whether heap allocation is needed. Correct name binding is a prerequisite for subsequent layout decisions.

7. Modules and Imports Bring Graph Structure

Module dependencies can form cycles. Common strategies include:

• Collect exported interfaces in the first pass, analyze implementations in the second;
• Distinguish between allowed cyclic declaration dependencies and prohibited cyclic initialization dependencies;
• Establish explicit priorities for imports to detect ambiguity in wildcard imports;
• Cache module interface summaries to enable incremental builds.

Relying solely on recursive "analyze all dependencies" leads to infinite recursion on cyclic dependencies. Use unseen / visiting / done states to detect cycles. If cycles are allowed, coordinate analysis through interface precollection or strongly connected components. Merely skipping a visiting node does not make its unfinished interface available.

8. Using Placeholders for Error Recovery

An unchecked null result for an unresolved name can cause cascading diagnostics or a crash. Instead, create an error symbol:

unknownName → ErrorSymbol#...

This error symbol carries the error type, allowing subsequent operations to propagate the error while suppressing derived diagnostics. A single root cause error should not spawn dozens of "inferred type unavailable" messages.

Common Misconceptions

• The symbol table is just name → type: It must also include symbol identity, declaration location, type, visibility, and state.
• Searching from inner to outer scopes resolves all names: Members, imports, overloads, and inheritance each follow distinct rules.
• Adding a declaration when traversal reaches it is sufficient: Forward references and recursion require explicit visibility timing.
• Stopping immediately on unresolved names is optimal: IDEs and batch diagnostics often need error symbols to continue analysis.

Exercise

1. Implement define_current and lookup_visible for nested blocks, testing valid shadowing and repeated declarations.
2. Design two passes of name collection for mutually recursive functions.
3. Distinguish lexical name lookup from member lookup for object.member.
4. Design an error symbol to ensure that unknown variables are reported only once with their root cause.

Summary

Name resolution binds source spellings to stable, declared identities. Scope, visibility timing, namespace, imports, and captures are part of language semantics and cannot be arbitrarily determined by the order of a single AST traversal.

The next lesson examines types in terms of binding: what inputs each operation accepts, when conversions are permitted, and how errors propagate forward.