Lexical Scope

The environment is a runtime object: it is built as a program runs, growing by a binding each time evaluation meets a let and reverting to what it was when a block ends. Which value a name reads therefore depends on how far the program has run. Yet the question this chapter asks has an answer that does not wait for the program to run at all. In the following code block,

{
    let x = 1;
    let y = { let x = 2; x + 10 };
    x + y
}

the name x inside the inner block reads 2 and the x on the last line reads 1, and that interpretation is settled by determining which binding each reference to x refers to by reading the braces, without evaluating anything. Every use of a name in a program refers to one definite binding, and that binding is fixed by where the use is written. Determining a name’s binding from the shape of the program text, ahead of running it, is lexical scope (also called static scope), since the binding is settled before, and independently of, any execution.

Free and bound occurrences

For every occurrence of a name (one location where the name is written and read), we say the occurrence is bound in an enclosing block of code when that block contains a let binding for the name somewhere before the occurrence; otherwise, the occurrence is free in that block. In the following block of code,

{ let x = 2; x + 10 }

the occurrence of x in x + 10 is bound: the let x = 2 that precedes it in the same block is the binder that x is bound to. However, in the following block of code without the let binding,

x + 10        // x is free here — nothing in this fragment binds it

the occurrence of x is free, because the region under consideration no longer contains the let that bound x. Whether an occurrence is free or bound is relative to the region you are reading. A let binding reaches inward over the text it encloses, and an occurrence of a name is bound exactly when it falls inside the reach of a binder that binds its name.

The scope of a binding

The scope of a binding is the region of program text over which its name refers to it. For a let binding, the rule E-Let already fixed that region: a let extends its scope over the rest of its block, so the binding’s scope runs from just after the let binding to the closing brace of the block that holds it. This notion of lexical scope was introduced by Algol 60 in what it named block structure — a name declared inside a region means something there and nowhere else — and it is what gives a block-structured program its nesting of scopes, each one the text between a binder and the brace that closes over it.

Scopes nest because blocks nest. An occurrence lies within the scope of a binding when it falls inside that binding’s region — the text from the let to the closing brace of its block, nested sub-blocks included. An occurrence can lie within the scopes of several bindings of the same name, one nested inside another; it is then bound by the innermost binding (the binding whose scope is the smallest) of the same name.

In the margin, each binding’s scope is drawn as a bar in its own colour. let x = 1 reaches over the rest of the outer block, but its bar breaks along the x + 10 line, where the inner let x = 2 binds x, its scope drawn by the orange bar. That break is a hole in the outer binding’s scope. We say that the innermost binding of x shadows the outer binding of x. The x in x + 10 lies inside both blocks and resolves to the orange binding; on the x + y line, past the inner block, the outer (blue) binding is in force again, so that x reads 1. let y reaches only the final line x + y, the one place y can be read, so its green bar covers just that row.

The rule for reading a program is uniform. An occurrence of a name refers to the binding of the nearest binder that encloses it — nearest meaning the smallest enclosing region that contains both the occurrence and a binder for the name. When no binder encloses it, the occurrence is free, and a name still free at the top of a program has no binding to resolve to: evaluating it results in an UnboundVariable error. None of this appeals to a value, an input, or how far the program has run. The binding each occurrence refers to is a function of the program text alone, which is why it can be read from the program’s text itself (without ever executing the program) — and why the word for the discipline is lexical, from the arrangement of the text itself.

Lexical scoping as a property

In Bridger, nothing new is added to the evaluator to enforce lexical scoping; instead, lexical scoping of let bindings is a property of the Milestone M2 semantic rules that were already described in the previous chapter. The E-Let rule extends the environment over the textual remainder of the block, and E-Var reads whatever environment has been threaded to the point of the occurrence: so the binding a variable finds at run time is the one the enclosing text put there.

The two views line up because the environments built at run time take the shape of the text. Each block is evaluated by extending the environment it was entered in, and a block is entered from the environment of the text that surrounds it, so at any point during the run the environments form a chain of children whose nesting matches the blocks that enclose that point in the source. Looking a name up — reading the current environment, then its parent, and outward — visits the same bindings, in the same order, as reading outward from the occurrence through the blocks that enclose it. The run-time lookup and the reading off the page cannot disagree, because they walk the same nesting. How that chain is represented, and what walking it costs as scopes deepen, is the topic of the next chapter.

Settling a name’s binding before the program runs is what later work builds on. Resolving every occurrence to a fixed position in the enclosing scopes — so a name need not be searched for by spelling at all — is the subject of the next chapter. And because a name’s binding is fixed by its definition, the type of what it holds can be too, which is what lets the checker in Part VI decide a program’s types without running it.

The design space

A name that is free in a fragment must ultimately resolve somewhere, and there are two disciplines for where. Under lexical scope (the scoping rules that Bridger uses), a free occurrence resolves in the environment that textually encloses it: the environment present where the code is written. Under dynamic scope, it resolves in the environment present where the code runs, the environment active at the moment control reaches the occurrence, which is decided by the execution order of the program.

In a language whose only way to enter a new environment is to enter a block, the code that runs in an environment is precisely the code written inside it, so the two disciplines choose the same binding for every occurrence, and nothing a program can do distinguishes them. They come apart only once a region of code can be carried away from where it was written and run somewhere else (i.e., via a function call from a separate part of the program). A function body mentions names it does not itself bind, and the two disciplines answer differently once its body runs under a call rather than where it was defined. That is where the choice becomes observable, and where Bridger’s commitment to lexical scope is made executable and weighed against the alternative (dynamic scoping); it is the subject of Part V.

Further reading

Block structure: the Report on the Algorithmic Language ALGOL 60 (1960) is where a name declared inside a region of a program is given a region of validity determined by the program’s own nesting — the arrangement this chapter reads scopes off of.

The environment model of scope: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) develops evaluation as the extension of environments, and works through how a name is looked up by searching outward through the enclosing scopes.

Concept checks