Intermezzo: Scope
The introduction of local and lambda requires some
additional terminology. In particular, we need words to refer to specific
uses of names for variables, functions, and structure types. For a simple
example, consider the following two definitions:
Clearly, the occurrences of x in f are completely
unrelated to the occurrences of x in the definition of
g. We could systematically replace the shaded occurrences
with y and the function would still compute the exact same
result. In short, the shaded occurrences of x mean something
only in the definition of f and nowhere else.
At the same time, the first occurrence of x in f is different from the others. When we apply f to a number n, this occurrence completely disappears while the others are replaced with n. To distinguish these two kinds of variable occurrences, we call the x in the function header a binding occurrence and those in the function’s body the bound occurrences. We also say that the binding occurrence of x binds all occurrences of x in the body of f. Indeed, people who study programming languages even have a name for the region where a binding occurrence works, namely, its lexical scope.
The definitions of f and g bind two more names: f and g. Their scope is called top-level scope because we think of scopes as nested (see below).
The word free occurrence applies to a variable without any
binding occurrence. It is a name without definition, i.e., neither the
language nor its libraries nor the program associates it with some value.
For example, if you were to put the above program into a definitions area
by itself and run it, entering f, g, and h at
the prompt of the interactions are shows that the first two are defined
and the last one is not:
> f f
> g g
> h h: this variable is not defined
The description of lexical scope suggests the following pictorial
representation of f’s definition: DrRacket’s
“Check Syntax” functionality draws these diagrams.
Here is an arrow diagram for top-level scope:
Note that the scope of f includes all definitions above and
below its definition. The bullet over the first occurrence indicates that
it is a binding occurrence. The arrows from the binding occurrence to the
bound occurrences suggest the flow of values. When the value of a binding
occurrence becomes known, the bound occurrences receive their values from
there.
Along similar lines, these diagrams also explain how renaming works. If you
wish to rename a function parameter, you search for all bound occurrences
in scope and replace them. For example, renaming f’s x
to y in the program above means
changes only two occurrences of x:
(define (p1 x y) (+ (* x y) (+ (* 2 x) (+ (* 2 y) 22)))) (define (p2 x) (+ (* 55 x) (+ x 11))) (define (p3 x) (+ (p1 x 0) (+ (p1 x 1) (p2 x)))) Draw arrows from p1’s x parameter to all its bound occurrences. Draw arrows from p1 to all bound occurrences of p1. Check the results with DrRacket “Check Syntax” functionality.
In contrast to top-level function definitions, the scope of the definitions
in a local are limited. Specifically, the scope of local
definitions is the local expression. Consider the
definition of an auxiliary function f in a local
expression. It binds all occurrences within the local expression
but none that occur outside:
The two occurrences outside of local are not bound by the local
definition of f. As always, the parameters of a function
definition, local or not, are only bound in the function’s body.
Since the scope of a function name or a function parameter is a textual
region, people also draw box diagrams to indicate scope. More precisely,
for parameters a box is drawn around the body of a function:
In the case of a local definition, the box is drawn aorund the entire
local expression:
In this example, the box describes the scope of the definitions
of f and g.
Using a box for a scope, we can also easily understand what it means to
reuse the name of function inside a local expression:
The inner box describes the scope of the inner definition of
f; the outer box is the scope of the outer definition of
f. Accordingly, all occurrences of f in the inner box
refer to the inner local; all those in the outer box refer to the
definition in the outer local. In other words, the scope of the
outer definition of f has a hole, namely, the inner box.
Holes can also occur in the scope of a parameter definition. Here is an
example:
In this function, the parameter x is used twice: for f
and g. The scope of the latter is nested in the scope of the
former and is thus a hole for the scope of the outer use of x.
In general, if the same name occurs more than once in a function, the boxes that describe the corresponding scopes never overlap. In some cases the boxes are nested within each other, which gives rise to holes. Still, the picture is always that of a hierarchy of smaller and smaller nested boxes.
; [List-of X] -> [List-of X] ; create a version of the given list that is sorted in descending order (define (insertion-sort alon) (local ((define (sort alon) (cond [(empty? alon) empty] [else (add (first alon) (sort (rest alon)))])) (define (add an alon) (cond [(empty? alon) (list an)] [else (cond [(> an (first alon)) (cons an alon)] [else (cons (first alon) (add an (rest alon)))])]))) (sort alon))) Draw a box around the scope of each binding occurrence of sort and alon. Then draw arrows from each occurrence of sort to the matching binding occurrence. Now repeat the exercise for the following variant:
(define (sort alon) (local ((define (sort alon) (cond [(empty? alon) empty] [else (add (first alon) (sort (rest alon)))])) (define (add an alon) (cond [(empty? alon) (list an)] [else (cond [(> an (first alon)) (cons an alon)] [else (cons (first alon) (add an (rest alon)))])]))) (sort alon))) Do the two functions differ other than in name?
Exercise 246. Recall that each occurrence of a variable receives its value from the corresponding binding occurrence. Consider the following definition:Where is the shaded occurrence of x bound? Since the definition is a constant definition and not a function definition, we need to evaluate the right-hand side if we wish to work with this function. What should be the value of the right-hand side according to our rules?
As discussed in lambda, Technically, a lambda expression is just a
short-hand for a local expression, i.e.,
is short for
The short-hand explanation suggests that
Of course, if exp contains further binding constructs (say, a
nested local expression), then the scope of the variables may
have a hole.
Exercise 247. Draw arrows from the shaded occurrences of x to their binding occurrences in each of the following three lambda expressions:Also draw a box for the scope of each shaded x and holes in the scope as necessary.