Lexical Scope and Block Structure

The introduction of local requires some additional terminology concerning the syntax of Scheme and the structure of functions. Specifically, we need words to discuss the usage of names for variables, function, and structures. For a simple example, consider the following two definitions:

(define (f   ) (+ (*      ) 25))

(define (g x) (* 12 (expt x 5))) 

At the same time, the first occurrence of x is different from the others. When we apply f to a number n, this occurrence completely disappears; in contrast, the others are replaced with n. To distinguish these two forms of variable occurrences, we call the one to the right of the function name BINDING occurrence of x and those in the body the BOUND occurrences of x. We also say that the binding occurrence of x binds all occurrences of x in the body of f, and from the discussion above, the body of f is clearly the only textual region of the function where the underlined binding occurrence of x can bind other occurrences. The name of this region is x's LEXICAL SCOPE. We also say that the definitions of f and g (or other definitions in the Definitions window) have GLOBAL SCOPE. On occasion, people also use the word FREE OCCURRENCE. The description of an application of f to a number n suggests the following pictorial representation of the definition:

The bullet over the first occurrence indicates that it is a binding occurrence. The arrow that originates from the bullet suggests the flow of values. That is, when the value of a binding occurrence becomes known, the bound occurrences receive their values from there. Put differently, when we know which is the binding occurrence of a variable, we know where the value will come from during an evaluation.

Along similar lines, the scope of a variable also dictates where we can rename it. If we wish to rename a parameter, say, from x to y, we search for all bound occurrences in the scope of the parameter and replace them with y. For example, if the function definition is the one from above:

(define (f x) (+ (* x x) 25))

(define (f y) (+ (* y y) 25))

Obviously function definitions also introduce a binding occurrence for the function name. If a definition introduces a function named f, the scope of f is the entire sequence of definitions:

That is, the scope of f includes all definitions above and below the definition of f.

Exercise 18.2.1

Here is a simple Scheme program:

(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)))) 

Copy the function and rename the parameter x of p1 to a and the parameter x of p3 to b.

Check the results with DrScheme's Check Syntax button. Solution

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, is only bound in the function's body and nowhere else:

Since the scope of a function name or a function parameter is a textual region, people often draw a box to indicate some 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: the inner box, which is the scope of the inner definition of f.

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 the function f and for 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.

Here is a simple Scheme function:

;; sort : list-of-numbers -> list-of-numbers
(define (sort alon) 
  (local ((define (sort alon) 
            (cond 
              [(empty? alon) empty] 
              [(cons? alon) (insert (first alon) (sort (rest alon)))])) 
          (define (insert an alon) 
            (cond 
              [(empty? alon) (list an)] 
              [else (cond 
                      [(> an (first alon)) (cons an alon)] 
                      [else (cons (first alon) (insert an (rest alon)))])]))) 
    (sort alon))) 

Exercise 18.2.3

Recall that each occurrence of a variable receives its value from the corresponding binding occurrence. Consider the following definition:

(define x (cons 1   ))