6.11 Deep, Shallow, and Ad Hoc Binding

The presence of first-class procedures makes the determination of the declaration to which a nonlocal reference binds more complex than in languages without support for first-class procedures. The question is: 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

• ad hoc binding uses the environment of the invocation expression in which the procedure is passed as an argument

Consider the following Scheme expression:

The function that is bound to f on line 4 contains a free variable y. This function is passed to the function g on line 13 in the expression and invoked (as x) on line 10 in the expression .

The question is: To which declaration of y does the reference to y on line 4 bind? In other words, from which environment does the denotation of y on line 4 derive? There are multiple options:

• the y declared on line 1

• the y declared on line 6

• the y declared on line 7

• the y declared on line 11

6.11.1 Deep Binding

Scheme uses deep binding. The following Scheme expression is the preceding Scheme expression annotated with comments that indicate the denotations of the identifiers involved in the determination of the declaration to which the y on line 4 is bound:

Deep binding evaluates the body of the passed procedure in the environment in which it is created. The environment in which f is created is . Therefore, when the argument f is invoked using the formal parameter x on line 10, which is passed the argument y bound to 6 (because the reference to x on line 13 is bound to the declaration of x on line 8; i.e., static scoping), the return value of on line 10 is . This expression equals 36, so the return value of the call to g (on line 13) is , which equals 216. The next three Scheme expressions are progressively annotated with comments to help illustrate the return value of 216 with deep binding:

6.11.2 Shallow Binding

Evaluating this code using shallow binding yields a different result. Shallow binding evaluates the body of the passed procedure in the environment of the expression that invokes it. The expression that invokes the passed procedure in this expression is on line 10, and the environment at line 10 is

Thus, the free variable y on line 4 is bound to 4 on line 6. Evaluating the body, , of the passed procedure f in this environment results in , which equals 48. Thus, the return value of the call to g (on line 13) is , which equals 288. The next three Scheme expressions are progressively annotated with comments to help illustrate the return value of 288 with shallow binding:

6.11.3 Ad Hoc Binding

Evaluating this code using ad hoc binding yields yet another result. Ad hoc binding uses the environment of the invocation expression in which the procedure is passed as an argument to evaluate the body of the passed procedure. The invocation expression in which the procedure f is passed is on line 13, and the environment at line 13 is

Thus, the free variable y on line 4 is bound to 2 on line 11. Evaluating the body, , of the passed procedure f in this environment results in , which equals 24. Thus, the return value of the call to g (on line 13) is , which equals 144. The next three Scheme expressions are progressively annotated with comments to help illustrate the return value of 144 with ad hoc binding:

The terms shallow and deep derive from the means used to search the runtime stack. Resolving nonlocal references with shallow binding often results in only searching a few activation records back in the stack (i.e., a shallow search). Resolving nonlocal references with deep binding (even though we do not think of searching the stack) often involves searching deeper into the stack—that is, going beyond the first few activation records on the top of the stack.

Deep binding most closely resembles lexical scoping not only because it can be done before run-time, but also because resolving nonlocal references depends on the nesting of blocks. Conversely, shallow binding most closely resembles dynamic scoping because we cannot determine the calling environment until run-time. Ad hoc binding lies somewhere in between the two. However, deep binding is not the same as static scoping, and shallow binding is not the same as dynamic scoping. A language that uses lexical scoping can also use shallow binding for passed procedures. Even though we cannot determine the calling environment until runtime (i.e., shallow binding), that environment can contain bindings as a result of static scoping. In other words, while we cannot determine the point in the program where the passed procedure is invoked until run-time (i.e., shallow binding), once it is determined, the environment at that point can be determined before run-time if the language uses static scoping. For instance, the expression that invokes the passed procedure f in our example Scheme expression is on line 10, and we said the environment at line 10 is

That environment, at that point, is based on lexical scoping. Thus, in general, scoping and environment binding are not the same concept even though the rules for each in a particular language indicate how nonlocal references are resolved. Both the type of scoping method used and the type of environment binding used have implications for how to organize an environment data structure most effectively to facilitate subsequent search of it in a language implementation. See Table 6.7; Section 9.8; Chapters 10–11; and Sections 12.2, 12.4, 12.6, and 12.7, where we implement languages.

Table 6.7 Scoping Vis-à-Vis Environment Binding

When McCarthy and his students at MIT were developing the first version of Lisp, they really wanted static scoping, but implemented pure dynamic scoping by accident, and did not address the FUNARG problem. Their implementation of the second version of Lisp attempted to rectify this. However, what they implemented was ad hoc binding, which, while closer to static scoping than what they originally conceived, is not static scoping. Scheme was an early dialect of Lisp that sought to implement lexical scoping.

As stated at the beginning of this chapter, binding is a universal concept in programming languages, and we are by no means through with our treatment of it. This chapter covers the binding of references to declarations—otherwise known as scope. The universality of binding is a theme that recurs frequently in this text.

Conceptual Exercises for Section 6.11

Exercise 6.11.1 Consider the following Scheme program:

(a) Draw the sequence of procedures on the run-time stack (horizontally, where it grows from left to right) when e is invoked (including e). Clearly label local variables and parameters, where present, in each activation record on the stack.

(b) Using dynamic scoping and shallow binding, what value is returned by e?

(c) Using dynamic scoping and ad hoc binding, what value is returned by e?

(d) Using lexical scoping, what value is returned by e?

Exercise 6.11.2 Give the value of the following JavaScript expression when executed using (a) deep, (b) shallow, and (c) ad hoc binding:

The (args) => (body) syntax in JavaScript, which defines an anonymous/ λ-function, is the same as the (lambda (args) (body)) syntax in Scheme. The ... on line 3, called the spread operator, is syntactic sugar for inserting the output of the following expression [e.g., proc2()] into the list in which it appears.

Exercise 6.11.3 Reconsider the last Scheme example in Section 6.10.5. In that example, an anonymous function is passed on line 8: (lambda () (cons x (cons y (cons (+ x y) ’())))). Since that function is created in the same environment in which it is passed, the result using deep or ad hoc binding is the same: (5 100 101 201). Will the evaluation of any program using deep or ad hoc binding always be the same when every function passed as argument in the program is an anonymous/literal function? If so, explain why. If not, give an example where the two binding strategies lead to different results.

Programming Exercises for Section 6.11

Exercise 6.11.4 ML, Haskell, Common Lisp, and Python all support first-class procedures. Convert the Scheme expression given at the beginning of Section 6.11 to each of these four languages, and state which type of binding each language uses (deep, shallow, or ad hoc).

Exercise 6.11.5 Give a Scheme program that outputs different results when run using deep, shallow, and ad hoc binding.