Comp210 Lecture 14

local

Consider the path-to-mona function.

;; path-to-mona: FamTree --> list-of-symbol, or false
;; Return a series of names leading from a-ft back
;; to an ancester named 'mona, or false if no such ancester.
;; (If multiple ancestors with that name,
;; a path to any is okay.)
;;
(define (path-to-mona a-ft)
   (cond [(unknown? a-ft)   false]
         [(child?   a-ft)   
          (cond [(symbol=? (child-name a-ft) 'mona)
                 (cons 'mona empty)]
                [(cons? (path-to-mona (child-ma a-ft)))
                 (cons (child-name a-ft)
                       (path-to-mona (child-ma a-ft)))]
                [(cons? (path-to-mona (child-pa a-ft)))
                 (cons (child-name a-ft)
                       (path-to-mona (child-pa a-ft)))]
                [else false])]))

(path-to-mona marge-tree) = false
(path-to-mona bart-tree) = (cons 'bart (cons 'home (cons 'mona empty)))

There's something unsatisfying about this program: we may often compute (path-to-mona (child-ma a-ft)) twice. Writing the same expression twice is unsatifying for several reasons:

If we write an expression only once, then if we have to change it, we only need to change it in one place. This is called having a single point of control.
If the expression is long and tedious, we would rather not write (or read) it more than once.
It induces a lot of redundant computation. How much? Just considering the maternal side: we check the mother's side twice. But each of these two checks looks at the grandmother twice: so that's four times. But each of those four checks of grandma checks great-grandma twice: that's eight times. My nth-mother is checked 2ⁿ times!

Therefore, we want to be able to call path-to-mona only once for the mothers side. Today, we introduce another piece of Scheme syntax (your first in a month) to help with this situation: it's called local. Here's how path-to-mona would appear using local. (To use this, you'll need to start using the Intermediate language level in DrScheme.)

;; path-to-mona: FamTree --> list-of-symbol, or false
;; Return a series of names leading from a-ft back
;; to an ancester named 'mona, or false if no such ancester.
;; (If multiple ancestors with that name,
;; a path to any is okay.)
;;
(define (path-to-mona a-ft)
   (cond [(unknown? a-ft)   false]
         [(child?   a-ft)
          (local [(define mona-ma (path-to-mona (child-ma a-ft)))
                  (define mona-pa (path-to-mona (child-pa a-ft)))]
             (cond [(symbol=? (child-name a-ft) 'mona) (cons 'mona empty)]
                   [(cons? mona-ma) (cons (child-name a-ft) mona-ma)]
                   [(cons? mona-pa) (cons (child-name a-ft) mona-pa)]
                   [else false]))]))

Why are there two parentheses between local and define? Local takes a list of definitions, each in proper Scheme definition format. The outer pair of parentheses enclose the list of definitions, which in the above case has only one element.

Exercise: Use local to get rid of the redundancy:

;; max-of-list : non-empty-list-of-numbers -> num
;; Return the largest number in nums.
;; (max-of-list doesn't make sense for empty lists.
;; Possible discussion -- use -inf.0 as sentinel?  Why good or bad?)
;;
(define (max-of-list nums)
  (cond [(empty? (rest nums)) (first nums)]
	[(cons? (rest nums))
	 (cond [(> (first nums) (max-of-list (rest nums)))
		(first nums)]
	       [else (max-of-list (rest nums))])]))

local is also handy when you have many sub-expressions building up your answer.

;; earth-pull: given a mass which is "height" meters above the ground,
;; return the force of gravity between it and the earth.
;;
(define (earth-pull m height)
  (local [(define G ...)           ; Universal gravitational constant.
          (define earth-mass   ..) ; in kg
          (define earth-radius ..) ; in m
          (define dist-from-center (+ earth-radius height))]
     (/ (* G earth-mass m) (square dist-from-center))))



(define (quadratic-roots a b c)
  (local [(define discriminant (- (square b) (* 4 a c)))]
    (cond [(negative? discriminant)  'no-real-roots]
          [(zero?     discriminant)  (/ (- b) (* 2 a))]
          [(positive? discriminant) 
           (local [(define root/2a  (/ (sqrt discriminant) (* 2 a)))
                   (define neg-b/2a (/ (- b) (* 2 a)))
                   (define r1 (+ neg-b/2a root/2a))
                   (define r2 (- neg-b/2a root/2a))]
             (cons r1 (cons r2 empty)))])))

Here's an example that uses two function definitions:

(define (expt5 x)
  (local [(define (cube z) (* z (squayre z)))
          (define (squayre y) (* y y))]
    (* (squayre x) (cube x))))

What happens if we put this definition into the Definitions window and evaluate (expt5 2) in the interactions window? We get 32, as expected. What if we evaluate (cube 3) in the interactions window? We get an error. Why?

The definitions inside of a local are only visible within the parentheses that enclose the local. Since the multiplication is inside the local, it can use the functions square and cube. Once we pass the parenthesis that closes (local, we can no longer use those definitions.

This raises an important issue in programming languages known as scoping. Scoping tells us where a definition is visible. You've been dealing with scoping all along, but perhaps without realizing it. Consider what happens if you type x at the DrScheme prompt. Unless you've done a (define x ...), DrScheme complains that x is an undefined identifier. However, if you write (define (f x) (+ x 3)), DrScheme doesn't complain because the x in (+ x 3) is within a function that has x as a parameter.

Whenever you write a definition (define or define-struct), you are telling DrScheme where it can use your definition. Consider the following example

(define x 17)

(define (double x)
  (+ x x))

(define (some-math x)
  (local ((define (squayre y) (* y y))
	  (define (cube y) (* y (squayre y))))
    (+ (squayre x) (cube x)
       (local ((define z (- (cube x) 3)))
         (squayre (double z))))))

What this program computes is irrelevant. What is relevant is where each variable and definition is visible. Double is visible everywhere, because it is not inside of a local. The programs squayre and cube are only visible inside of the first local. The identifier z is only visible inside the second local. The text contains several examples of drawing boxes around the parts of a program where a definition is visible. Look at those and make sure you see how to draw similar boxes on this example.

Finally, we need to discuss how DrScheme evaluates a local, so that you know what programs using local actually do. Let's return to our earlier example expt5:

(define (expt5 x)
  (local ((define (squayre y) (* y y))
	  (define (cube z) (* z (squayre z))))
    (* (squayre x) (cube x))))

Evaluate (+ (expt5 2) 3). What does this become according to our evaluation rules?

(+ (local ((define (squayre y) (* y y))
	   (define (cube z) (* z (squayre z))))
     (* (squayre 2) (cube 2)))
   3)

Now, DrScheme evaluates

(local ((define (squayre y) (* y y))
	(define (cube z) (* z (squayre z))))
  (* (squayre 2) (cube 2)))

At this point, DrScheme copies your local definitions as if they were in the definitions window (you don't see them appear there, but it is as if a little person inside the machine moved them there). However, in order to keep someone from using them outside of their scope, DrScheme renames them (and changes the names in your program to reflect the new names). You don't see any of these changes in the text of your program -- this all goes on behind the scenes when DrScheme evaluates your program.

Now, DrScheme can finish evaluating your program normally, to yield the answer 35. To summarize:

Syntax of local:
```
   (local [definition-1
           ...
           definition-n]
     body-expr)
```
where each definition is a define or define-struct form, and body-expr is any expression (presumably involving placeholders just defined).

Semantics of local (Law of Scheme):

   ...top-level definitions..
   (local [defs]
    body)

becomes:

   ..top-level definitions..
   ..defs..                      ; (renamed for uniqueness)
   body                          ; (with renaming)

Some Pragmatics of local:
- Give names to individual parts of a computation, for clarity.
- To avoid re-computation!
- To hide the name of helper functions.
- Can avoid re-mentioning a static argument.
(That's in approximate order of importance.) (We haven't shown examples of all of these.)