6.13 Chapter Summary

Binding is a relationship from one entity to another in a programming language or program (e.g., the variable a is bound to the data type int). The establishment of this relationship takes place either before run-time or during run-time. In the context of programming languages, the adjective static placed before a noun phrase indicates that the binding takes place before run-time; the adjective dynamic indicates that the binding takes place at run-time. For instance, the binding of a variable to a data type (e.g., int a;) takes place before run-time—typically at compile time—while the binding of a variable to a value takes place at run-time— typically when an assignment statement (e.g., a = 1;) is executed. Binding is one of the most foundational concepts in programming languages because other language concepts involve binding. Scope is a language concept that can be studied as a type of binding.

Identifiers in a program appear as declarations [e.g., in the expressions (lambda (tail) ··· ) and (let ((tail ··· )) ··· ) the occurrences of tail are as declarations] and as references [e.g., in the expression (cons head tail), cons, head, and tail are references]. There is a binding relationship—defined by the programming language—between declarations of and references to identifiers in a program. Each reference is statically or dynamically bound to a declaration that has limited scope. The scope of a variable declaration in a program is the region of that program (a range of lines of code) within which references to that variable refer to the declaration (Friedman, Wand, and Haynes 2001). In programming languages that use static scoping (e.g., Scheme, Python, and Java), the relationship between a reference and its declaration is established before runtime. In a language using dynamic scoping, the determination of the declaration to which a reference is bound requires run-time information, such as the calling sequence of procedures.

Languages have scoping rules for determining to which declaration a particular reference is bound. Lexical scoping is a type of static scoping in which the scope of a declaration is determined by examining the lexical layout of the blocks of the program. The procedure for determining the declaration to which a reference is bound in a lexically scoped language is to search the blocks enclosing the reference in an inside-out fashion (i.e., from the innermost block to the outermost block) until a declaration is found. If a declaration is not found, the variable reference is free (as opposed to bound). Bound references to a declaration can be shadowed by inner declarations using the same identifier, creating a scope hole.

Lexically scoped identifiers are useful for writing and understanding programs, but are superfluous and unnecessary for evaluating expressions and executing programs. Thus, we can replace each reference to a lexically scoped identifier in a program with its lexical depth and position; this pair of non-negative integers serves to identify the declaration to which the reference is bound. Depth indicates the block in which the declaration is found, and position indicates precisely where in the declaration list of that block the declaration is found; they use zero-based indexing from inside-out relative to the reference and left-to-right in the declaration list, respectively. The functions occurs-free? and occurs-bound? each accept a λ-expression and an identifier and determine whether the identifier occurs free or bound, respectively, in the expression. These functions are examples of programs that process other programs, which we increasingly encounter and develop as we progress toward the interpreter-implementation part of this text (i.e., Chapters 10–12).

The concept of scope is only relevant in the presence of nonlocal references. Resolving nonlocal references in the presence of first-class functions creates a challenge called the FUNARG problem: Which environment should be used to supply the value of a nonlocal reference in the body of a passed or returned function? There are three options: deep binding (uses the environment at the time the passed function was created), shallow binding (uses the environment of the expression that invokes the passed function), and ad hoc binding (uses the environment of the invocation expression in which the procedure is passed as an argument). The FUNARG problem illustrates the relationship between scope and closures—functions that remember the lexical environment in which they were created. Closures and combinators—λ-expressions with and without free variables, respectively—are useful programming constructs that we will continue to encounter.