6.7 Dynamic Scoping

In a dynamically scoped language, the determination of the declaration to which a reference is bound requires run-time information. In a typical implementation of dynamic scoping, it is the calling sequence of procedures, and not their lexical relationship to each other, that is used to determine the declaration to which each reference is bound. While Scheme uses lexical scoping, for the purpose of demonstration, we use the following Scheme expression to demonstrate dynamic scoping:

In this expression we see nonlocal references to x and y in the definition of proc2 on line 2, which does not provide declarations for x and y. Therefore, to resolve those references so that we can evaluate the cons expression, we must determine to which declarations the references to x and y are bound.

While static scoping involves a search of the program text, dynamic scoping involves a search of the run-time call stack. Specifically, in a lexically scoped language, determining the declaration to which a reference is bound involves an outward search of the nested blocks enclosing the block where the reference is made. In contrast, making such a determination in a dynamically scoped language involves a downward search from the top of the stack to the bottom.

Due to the invocation of the read function on line 5 (which reads and returns an integer from standard input), we are unable to determine the call chain of this program without running it. However, given any two procedures, we can statically determine which has access to the other (i.e., the ability to call) based on the program’s lexical layout. Different languages have different rules specifying which procedures have access (i.e., permission to call) to other procedures in the program based on the program’s lexical structure. By examining the program text from the preceding example we can determine the static call graph, which indicates which procedures have access to each other (Figure 6.2). The call chain (or dynamic call graph) of an expression depicts the series of functions called by the program as they would appear on the run-time call stack. From the static call graph in Figure 6.2 we can derive three possible run-time call chains:

Since proc2 is the function containing the nonlocal references, we only need to consider the two call chains ending in proc2.Figure 6.3 depicts the two possible run-time stacks at the time the cons expression on line 2 is evaluated (corresponding to these two call chains). The left side of Figure 6.3 shows the stack that results when a 0 is given as run-time input, while the right side shows the stack resulting from a non-zero run-time input.

Since there is no declaration of x or y in the definition of proc2, we must search back through the call chain. When a 0 is input, a backward search of the call chain reveals that the first declarations to x and y appear in proc1 (see the left side of Figure 6.3), so the output of the program is . When a nonzero integer is input, the same search reveals that the first declarations to x and y appear in the lambda expression (see the right side of Figure 6.3), so the output of the program is .

Shadowed declarations and, thus, scope holes can exist in dynamically scoped programs, too. However, with dynamic scoping, the hole is created not by an intervening declaration (in a block nested within the block containing the shadowed declaration), but rather by an intervening activation record (sometimes called a stack frame or environment frame) on the stack. For instance, when the runtime input to the example program is 0, the declarations of x and y in proc1 on line 3 shadow the declarations of x and y in the lambda expression on line 1, creating a scope hole for those declarations in the body of proc1 as well as any of the functions it or its descendants call.

The lexical graph of a program illustrates how the units or blocks of the program are spatially nested, while a static call graph indicates which procedures have access to each other. Both can be determined before run-time. The lexical graph is typically a tree, whereas the static call graph is often a non-tree graph. The call chain of a program depicts the series of functions called by the program as they would appear on the run-time call stack and is always linear—that is, a tree structure where every vertex has exactly one parent and child except for the first vertex, which has no parent, and the last vertex, which has no child. While all possible call chains can be extracted from the static call graph, every process (i.e., program in execution) has only one call graph, but it cannot always be determined before run-time, especially if the execution of the program depends on run-time input.

Do not assume dynamic scoping when the only run-time call chain of a program matches the lexical structure of the nested blocks of that program. For instance, the run-time call chain of the program in Section 6.4.1 mirrors its lexical structure exactly, yet that program uses lexical scoping. When the call chain of a program matches its lexical structure, the declarations to which its references are bound are the same when using either lexical or dynamic scoping. Note that the lexical structure of the nested blocks of the lambda expression in the example program containing the call to read (i.e., ) does not match any of its three possible run-time call chains; thus, the resolutions of the nonlocal references (and output of the program) are different using lexical and dynamic scoping.

Similarly, do not assume static scoping when you can determine the call chain and, therefore, resolve the nonlocal references before run-time. Consider the following Scheme expression:

The only possible run-time call chain of the preceding expression is , even though the static call graph (Figure 6.2) permits more possibilities. Therefore, even if this program uses dynamic scoping, we know before run-time that the references to x and y in proc2 on line 2 will be bound (at run-time) to the declarations of x and y in proc1 on line 3. The program does not use lexical scoping because the nonlocal references on line 2 are bound to declarations nested deeper in the program, rather than being found from an inside-to-out search of its nested blocks from the point of the references. Dynamic scoping is a history-sensitive scoping method, such that the evaluation of nonlocal references depends on where you have been.