Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #7: `local` and scope

Quick Review of Scope

A function definition

     (define (parameters...)
        body)

introduces a new local scope -- the parameters are defined within the body.

A local definition

     (local [definitions...]
        body)

introduces a new local scope -- the names in the definitions are defined within both within the bodies of the definitions and within the local's body.

In order to use local and to use functions as data (also just introduced in class), you need to set the DrScheme language level to "Advanced". Unfortunately, DrScheme's stepper doesn't work beyond the Beginner level.

Exercises

Finding the maximum element of a list
Let's consider the problem of finding the maximum number in a list. To simplify the problem for today's goal, assume the maximum number in an empty list is 0. (Previously, we've examined ways of writing this function only for non-empty lists.) Develop the function without using `local`. For the purposes of this exercise, do not use any helper functions, nor the built-in Scheme function `max`. Also, don't use an accumulator. Stylistically what don't (or shouldn't) you like about this code? Develop the function using `local`. Again, don't use a helper function, `max`, or an accumulator. Try running each version on the following input (or longer ones): (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) What difference do you see? For each version, determine how many calls to your function is made for the input (list 1 2 3 ... `n`) for various values of `n`. For each version, can you write a mathematical equation that describes this number of calls?

Using local doesn't let us write programs which were impossible before, but it does let us write them better.

How to avoid `local`?
How can you take any program written with `local`, and turn it into an equivalent program that doesn't use `local`? Hint: What other construct introduces a new scope and placeholder names? Your answer will show that even without using an accumulator or `local`, functions the the previous example can be written efficiently.

List of descending numbers exercises
We'll return to an example seen in a previous lab. We'll develop functions returning the list of positive numbers 1...`n` (left-to-right), given `n` as input. Develop a function that, given `n` and `i` normally returns the list of length `i` of numbers up to `n`: (list `n`-(`i`-1) ... `n`-1 `n`) More concretely, e.g., (nums-upto-help 5 0) ⇒ empty (nums-upto-help 5 2) ⇒ (list 4 5) (nums-upto-help 5 5) ⇒ (list 1 2 3 4 5) (nums-upto-help 6 5) ⇒ (list 2 3 4 5 6) (nums-upto-help 7 5) ⇒ (list 3 4 5 6 7) For simplicity, you may assume that `i`≤`n`. This should just follow the template for natural numbers on `i`. Your `nums-upto-help` repeatedly passed one argument unchanged to its recursive call. I.e., it's an invariant argument. Rewrite your function, adding a helper, hidden by `local`, which avoids having an invariant argument. Don't forget to include a contract and purpose for this new local function, too. Develop the function we really want: (nums-upto 5) ⇒ (list 1 2 3 4 5) Use your `nums-upto-help` to do most of the work. Edit your code to use `local` to hide the helper `nums-upto-help` inside your main function `nums-upto`.

Advice on when to use `local`

These examples point out the reasons why to use local:

Avoid code duplication. I.e., increase code reuse.

As in the maximum element of a list example.
Avoid recomputation.

Sometimes provides dramatic benefits, as with the maximum element of a list example.
Avoid re-mentioning an unchanging argument.

As in the ascending numbers list example.

To hide the name of helper functions.

As in the ascending numbers list example.

An Aside
While important conceptually, most programming languages (including Scheme) provide alternate mechanisms for this which scale better to large programs. These mechanisms typically have names like modules or packages. As this one example shows, even small programs can get a bit less clear when hiding lots of helpers.

Name individual parts of a computation, for clarity.

A side benefit in the maximum element of a list example.

On the other hand, don't get carried away. Here are two easy ways to misuse local:

       ;; max-of-list: non-empty-list --> number
       ;;
       (define (max-of-list a-nelon)
          (local [(define max-rest (max-of-list (rest a-nelon)))]
             (cond [(empty? (rest a-nelon)) (first a-nelon)]
                   [else  (cond [(< (first a-nelon) max-rest) max-rest]
                                [else (first a-nelon)])])))

Question
What's wrong with this?

Make sure you don't put a local too early in your code.

       ;; max-of-list: non-empty-list --> number
       ;;
       (define (max-of-list a-nelon)
          (cond [(empty? (rest a-nelon)) (first a-nelon)]
                [else  (local [(define max-rest (max-of-list (rest a-nelon)))
                               (define first-smaller? (< (first a-nelon) max-rest))]
                          (cond [first-smaller? max-rest]
                                [else (first a-nelon)]))]))

This isn't wrong, but the local definition of first-smaller? is unnecessary. Since the comparison is only used once, this is not a case of code reuse or recomputation. It provides a name to a part of the computation, but whether that improves clarity in this case is a judgement call.

Scope and the semantics of `local`

How does a local evaluate? The following is one way to understand it.

For each defined name in the list of definitions, rename it something entirely unique, consistently through the entire local.
Lift those defines to the top level, and erase the surrounding local, leaving only the body-expression.

Example:

     (define x 5)
     (local [(define x 7)]
        x)

Becomes:

     (define x 5)
     (local [(define x^ 7)]
        x^)

which in turn evaluates to

     (define x 5)
     (define x^ 7)
     x^

This makes it clear that there are really two independent placeholders.

Example:

     (define x 5)
     (define y x)
     (define z (+ x y))
     (local [(define x 7)
             (define y x)]
       (+ x y z))

Evaluates to:

     (define x 5)
     (define y x)
     (define z (+ x y))
     (define x^ 7)
     (define y^ x^)
     (+ x^ y^ z)

As an equivalent way of looking at things, we can look at the original code and ask which definition corresponds to each placeholder use. The answer is simple -- it is always the closest (in terms of nestedness) enclosing binding definition. We have three forms of binding:

Parameters of a function.
Local definitions.
"Global" definitions. (This is a special case of local definitions, if we simply consider there to be an implicit local around everything.)

`local` implementation
The actual way `local` is implemented is along these lines. The interpreter keeps track of these bindings in an environment, which maps placeholder names to their values. Then, an expression is evaluated in the context of the current environment.

DrScheme provides an easy way to look at this: the Check Syntax button. Clicking on this does two things. First, it checks for syntactic correctness of your program in the definitions window. If there are errors, it reports the first one. But, if there aren't any, it then annotates your code with various colors and, when you move your cursor on top of a placeholder, draws arrows between placeholder definitions and uses.

Scoping Exercise
What does the following code do? Explain it in terms of the evaluation rule above. (define growth-rate 1.1) (define (grow n) (* n growth-rate)) (local [(define growth-rate 1.3)] (grow 10)) (grow 10) Confirm your understanding with DrScheme, with the Check Syntax button, and by evaluating the code. Is the following code essentially different from the previous example? Why or why not? (define growth-rate 1.3) (define (grow n) (local [(define growth-rate 1.1)] (* n growth-rate))) (grow 10) Once again, confirm your understanding with DrScheme. In each case, `grow` "knows" which placeholder named `growth-rate` was in scope when it was defined, because that knowledge is part of `grow`'s closure.

More scoping exercises
In each of the following, determine which definition corresponds to each placeholder usage. As a result, determine what each example produces. Then confirm by using DrScheme. (Note: Some examples give errors about unbound placeholders.) (define w 1) (define x 3) (define y 5) (local [(define w 2) (define x 4) (define z 6)] (+ w x y z)) (+ w x y) (define w 1) (define x 3) (define (test x y) (local [(define w 2) (define x 4) (define z 6)] (+ w x y z)))) (test 8 3) (test x w) (test w x) (define x 1) (define y 1) (local [(define x 2) (define y x)] (+ x y)) (+ x y) Here is an example of mutually recursive functions following the natNum template; it is motivated by the observation "a positive number n is even if n-1 is odd, a positive number n is odd if n-1 is even, and 0 is even." (local [;; my-odd?: natnum --> boolean ;; (define (my-odd? n) (cond [(zero? n) false] [(positive? n) (my-even? (sub1 n))])) ;; my-even?: natnum --> boolean (define (my-even? n) (cond [(zero? n) true] [(positive? n) (my-odd? (sub1 n))]))] ; Now, the body of the local: (my-odd? 5)) ; Outside the local: (my-odd? 5) Note that the two local functions are in each others' closure; they will always call each other, no matter how you define other placeholders with the same names `my-even?`. Also note that this is an example of mutually recursive functions, where the mutual recursion does not result from a mutually recursive data structure. (define x 1) (define y 2) (define (f x) (local [(define (g x) (+ x y)) (define y 100)] (g (g x)))) (local [(define x 30) (define y 31) (define (g x) (* x y))] (g 20)) (g 20) (f 20)

In each of the following, determine which definition corresponds to each placeholder usage. As a result, determine what each example produces. Then confirm by using DrScheme. (Note: Some examples give errors about unbound placeholders.)

         (define w 1)
         (define x 3)
         (define y 5)

         (local [(define w 2)
                 (define x 4)
                 (define z 6)]
            (+ w x y z))

         (+ w x y)

         (define w 1)
         (define x 3)
         (define (test x y)
            (local [(define w 2)
                    (define x 4)
                    (define z 6)]
               (+ w x y z))))

         (test 8 3)
         (test x w)
         (test w x)

         (define x 1)
         (define y 1)
         (local
             [(define x 2)
              (define y x)]
             (+ x y))
         (+ x y)

Here is an example of mutually recursive functions following the natNum template; it is motivated by the observation "a positive number n is even if n-1 is odd, a positive number n is odd if n-1 is even, and 0 is even."
```
         (local
            [;; my-odd?: natnum --> boolean
             ;;
             (define (my-odd? n)
                 (cond [(zero? n)     false]
                       [(positive? n) (my-even? (sub1 n))]))
         
             ;; my-even?: natnum --> boolean
             (define (my-even? n)
                 (cond [(zero? n)     true]
                       [(positive? n) (my-odd? (sub1 n))]))]

           ; Now, the body of the local:
           (my-odd? 5))

         ; Outside the local:
         (my-odd? 5)
         
```
Note that the two local functions are in each others' closure; they will always call each other, no matter how you define other placeholders with the same names my-even?.

Also note that this is an example of mutually recursive functions, where the mutual recursion does not result from a mutually recursive data structure.

         (define x 1)
         (define y 2)

         (define (f x)
           (local [(define (g x) (+ x y))
                   (define y 100)]
              (g (g x))))

         (local [(define x 30)
                 (define y 31)
                 (define (g x) (* x y))]
           (g 20))

         (g 20)
         (f 20)

Last Revised Tuesday, 24-Aug-2004 13:49:06 CDT

Comp210: Principles of Computing and Programming Fall 2004 -- Lab #7: local and scope

Quick Review of Scope

Exercises

Advice on when to use local

Scope and the semantics of local

Comp210: Principles of Computing and Programming
Fall 2004 -- Lab #7: `local` and scope

Advice on when to use `local`

Scope and the semantics of `local`