6.1.0.3

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:
(define (f x) (+ (* x x) 25))
(define (g x) (+ (f (+ x 1)) (f (- x 1))))
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
(define (f x) (+ (* x x) 25))
(define (g x) (+ (f (+ x 1)) (f (- x 1))))
changes only two occurrences of x:
(define (f y) (+ (* y y) 25))
(define (g x) (+ (f (+ x 1)) (f (- x 1))))

Exercise 247. Here is a simple ISL+ 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))))
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.

Exercise 248. Here is a simple ISL+ function:
; [List-of X] -> [List-of X]
; creates 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 249. Recall that each occurrence of a variable receives its value from the corresponding binding occurrence. Consider the following definition:

(define x (cons 1 x))

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.,

(lambda (x-1 ...  x-n) exp)

is short for
(local ((define (a-new-name x-1 ... x-n) exp))
  a-new-name) ; if a-new-name does not occur in exp.
The short-hand explanation suggests that

(lambda (x-1 ...  x-n) exp)

introduces x-1 ... x-n as binding occurrences and that the scope of parameters is exp, e.g.,

Of course, if exp contains further binding constructs (say, a nested local expression), then the scope of the variables may have a hole.

Exercise 250. Draw arrows from the shaded occurrences of x to their binding occurrences in each of the following three lambda expressions:
  1. (lambda (x y)
      (+ x (* x y)))
  2. (lambda (x y)
      (+ x
         (local ((define x (* y y)))
           (+ (* 3 x)
              (/ 1 x)))))
  3. (lambda (x y)
      (+ x
         ((lambda (x)
            (+ (* 3 x)
               (/ 1 x)))
          (* y y))))
Also draw a box for the scope of each shaded x and holes in the scope as necessary.