6.6 Free or Bound Variables
A variable in an expression in any programming language can appear either (1) bound to a declaration and, therefore, a value, or (2) free, meaning unbound to a declaration and, thus, a denotation or value. The qualification of a variable as free or bound is defined as follows (Friedman, Wand, and Haynes 2001, Definition 1.3.2, p. 29):
A variable v occurs free in an expression e if and only if there is a reference to v within e that is not bound by any declaration of v within e.
Avariable v occurs bound in an expression e if and only if there is a reference to v within e that is bound by some declaration of v in e.
For instance, in the expression 
, the x in the body of the lambda expression occurs bound to the declaration of x in the formal parameter list, while the argument y occurs free because it is unbound by any declaration in this expression. A variable bound in the nearest enclosing λ-expression corresponds to a slot in the current activation record.
A variable may occur free in one context but bound in another enclosing context. For instance, in the expression
the reference to y on line 2 occurs bound by the declaration of the formal parameter y on line 1.
The value of an expression e depends only on the values to which the free variables within the expression e are bound in an expression enclosing e. For instance, the value of the body (line 2) of the lambda expression in the preceding example depends only on the denotation of its single free variable y on line 1; therefore, the value of y comes from the argument to the function. The value of an expression e does not depend on the values bound to variables within the expression e. For instance, the value of the expression 
is independent of the denotation of x at the time when the entire expression is evaluated. By the time the free occurrence of x in the body of 
is evaluated, it is bound to the value associated with y.
The semantics of an expression without any free variables is fixed. Consider the identity function: 
. It has no free variables and its meaning is always fixed as “return the value that is passed to it.” As another example, consider the following expression:
The semantics of this expression, which also has no free variables, is always “a function that accepts a value x and returns ‘a function that accepts a function f and returns the result of applying the function f to the value x.”’ Expressions in λ-calculus not containing any free variables are referred to as combinators; they include the identity function 
and the application combinator 
, which are helpful programming elements. We saw combinators in Chapter 5 and encounter combinators further in subsequent chapters.
The definitions of free and bound variables given here are general and formulated for any programming language. The definitions shown in Table 6.4 apply specifically to the language of λ-calculus expressions. Notice that the cases of each definition correspond to the three types of λ-calculus expressions, except there is no symbol case in the definition of a bound variable—a variable cannot occur bound in a λ-calculus expression consisting of just a single symbol.
Table 6.4 Definitions of Free and Bound Variables in λ-Calculus (Friedman, Wand, and Haynes 2001, Definition 1.3.3, p. 31)
|
Avariable v occurs free in a λ-calculus expression e if and only if:
|
|
Avariable v occurs bound in a λ-calculus expression e if and only if:
|
Using these definitions, we can define recursive Scheme functions occurs-free? and occurs-bound? that each accept a variable var and a λ-calculus expression expr and return #t if var occurs free or bound, respectively, in expr and #f otherwise. These functions, which process expressions, are shown in Listing 6.1. The three cases of the cond expression in the definition of each function correspond to the three types of λ-calculus expressions.
The occurrence of the functions caadr and caddr make these occurs-free? and occurs-bound? functions unreadable because it is not salient that the former refers to the declaration of a variable in a lambda expression or the latter refers to its body. Incorporating abstract data types into our discussion (Chapter 9) makes these functions more readable. Nonetheless, since Scheme is a homoiconic language (i.e., Scheme programs are Scheme lists), Scheme programs can be directly manipulated using standard language facilities (e.g., car and cdr).
Programming Exercises for Section 6.6
Exercise 6.6.1 (Friedman, Wand, and Haynes 2001, Exercise 1.19, p. 31) Define a function free-symbols in Scheme that accepts only a list representing a λ-calculus expression and returns a list representing a set (not a bag) of all the symbols that occur free in the expression.
Examples:
Exercise 6.6.2 (Friedman, Wand, and Haynes 2001, Exercise 1.19, p. 31) Define afunction bound-symbols in Scheme that accepts only a list representing a λ-calculus expression and returns a list representing a set (not a bag) of all the symbols that occur bound in the expression.
Examples:
