Comp 210 Lab 7: local

Index: review a simple natnum-processing program, which will help us review local syntax and examples, followed by the law-of-scheme for local .

review: natnum processing

Write the function nums-down, as described below: (What template does it use?)

;; positive?: real --> boolean
;; Is n > 0?
;; (A useful predicate for natnum-processing functions.)
;;
(define (positive? n) (> n 0))




;; nums-down: natnum --> list-of-number
;; Return (list n n-1 ... 3 2 1).
;;
(define (nums-down n)
  ...)


; Examples of calling nums-down:
;
(nums-down 0)
empty 

(nums-down 1)
(list 1)

(nums-down 3)
(list 3 2 1)

Exercise: `min-of-list`

Before we use local in our programs, we (quickly) review a problem which doesn't use it.
(Labbies: Have students copy/paste from this page.)

Consider the function min-of-list, which takes a non-empty list of numbers and returns the largest one. Note that this function does not take in a list; we'll need a new data-definition for non-empty-list:

;; A non-empty-list is:
;; - (cons num empty), or
;; - (cons num non-empty-list).

This gives rise to a template: the only of local. Thus our template is

(define (min-of-list a-nelon)
   (cond [(empty? (rest a-nelon)) ...]
         [else  ..(first a-nelon).. ..(min-of-list (rest a-nelon)).. ]))

There is a small hitch about what question to ask to distinguish these two cases; (empty? (rest a-nelon)) does it. (If you prefer, you can encapsulate this in a function named length=1?.)

Run your code on some test cases:

(= 1 (min-of-list (list 1)))

(= 1 (min-of-list (list 1 3)))
(= 1 (min-of-list (list 3 1)))

(= 1 (min-of-list (list 1 1)))

(= 1 (min-of-list (list 5 3 1)))
(= 1 (min-of-list (list 1 3 5)))
(= 1 (min-of-list (list 5 1 3)))

(= 1 (min-of-list (list 1 1 1 1 3 1)))

(= 1 (min-of-list (nums-down 20)))
    ; Labbie: have different parts of the room use
    ; different lengths, and raise their hand when their
    ; code finishes.

Hmmm, for a list of ..30.. items, this function takes a long time to return. Why? Let's use our noggins, to think through what the hand-evaluation is doing:

How many calls to the function are made, for (list 1)?

How many for (list 2 1)?

How many for (list 3 2 1)? (Hint: it's twice as many as for (list 2 1). This corresponds to the code's two recursive calls.)

For a list of 4 descending objects? n? (What is this when n=10? 20? 30?)

This isn't good news, when we might often have a list of a million items! (Consider in your gamestation -- there is a list of a million polygons which make up all the surfaces of Mario's castle; the program needs to know which one is closest to Mario so it can be drawn quickly!)

Is there anything about the writing of this function you don't like? (Hint: You don't like having the same code repeated in different places -- it is extra typing, and is not a single point-of-control.) As a matter of fact, this stylistic ugliness is what is is also giving to the ugly running-time.

`local` to the rescue

We've already saw local in lecture. To make it real, type in and evaluate the simple snippet from lecture:

(define x 5)
x

(local {(define x 7)}
   x)   ; An exceedingly simple body for a local.

x

Explain the results.

That example used just one definition; in general you can have several local defines; You could also have define-structs.
Question (for a volunteer at the whiteboard): What is the official syntax for local? That is, what exactly are you allowed to type?
(soln)

Okay, let's use local to help out min-of-list1. Just make the recursive call once, giving the result a define'd name, and we'll refer to that name repeatedly.

Stylistically, the first version violates our rule against duplicating code. Using local will give us a nice way to avoid this, improving code legibility.

(define (min-of-list2 a-nelon)
   (cond [(empty? (rest a-nelon))  (first a-nelon)]
         [else (local {(define min-rest (min-of-list2 (rest a-nelon)))}
                  (cond [(> (first a-nelon) min-rest) (first a-nelon)]
                        [else min-rest]))]))

Here, we compute the minimum of the rest of the list once before the cond and remember the result by giving it a name. In the cond, we just use this value instead of recomputing it. This is an improvement in both style and efficiency.

To do: Use this code on the same examples as before. Compare your results.

Q: Observe that each call to min-of-list2 makes at most one natural recursive calls. Can you describe at most how many times min-of-list2 is called in total in relation to the length of a-nelon? Why is it more than twice as fast?

Using local doesn't let us write programs which were impossible before, but it does let us write them better (more clearly, as well as w/o an exponential slowdown).
To think about for those who are working ahead: How can you take any program written with local, and turn it into an equivalent program that doesn't use local? Hint: your answer will show that even without using an accumulator or local, our min-of-list function can be written efficiently.

Another Use of `local` (optional)

Write the function nums-up (analagous to nums-down). Well, it's easy if we just use reverse and nums-down. But suppose these functions weren't already written. We'd start the template, and realize that the recursive call doesn't really give us what we want. To solve (nums-up 17), we know that our first number will be 1, but we want a recursive call which will be returning (list 2 3 4 ... 16 17). How to do this? The recursive call needs to be told to make a list that's 16 elements long, and ends at 17. (And in turn, it's recursive call will want a list that's 15 long, ending at 17.) Aha, sounds like what we want is really:

;; nums-up-from: num, natnum --> num
;; Return a list of i ascendingn numbers, ending at top.
;; E.g. a list from top-(i-1) up through top-0.
;;  
(define (nums-up-from top i)
  (cond [(zero? i)     ...]
        [(positive? i) ...])

(nums-up-from 17 3)
(list 15 16 17)

(nums-up-from 17 1)
(list 17)

(nums-up-from 17 0)
empty



(nums-up-from 3 3)
(list 1 2 3)

To do:

Complete nums-up-from.
Now write the "real" nums-up, which uses nums-up-from as (an accumulator-style) helper.
Users of your code (e.g. other programmers, or yourself in a few weeks) will want to call nums-up, but should not be calling the helper nums-up-from directly. Use local so that this helper function is not global, but is local to nums-up.
Having done this, let's go one more step: Realize that the argument top stays the same in every call. We don't really need it as a function-argument. How can we use (the existing) local to factor out this argument? (Could we have factored this out before we made the helper function local to nums-up? Why or why not?)

These examples illustrate some of the Pragmatics of local (when and why to use it). Summarizing, (in approximate order of importance),

Give names to individual parts of a computation, for clarity. (Think back on the gravity example from lecture.)
To avoid re-computation!
Can avoid re-mentioning a static argument.
To hide the name of helper functions.
(This is important conceptually, although in practice, most functions are visible in the entire file, and other mechanisms are used to export the functions for use in other programs.)

Don't get carried away [optional]

There are two easy ways to misuse local:

We can put the local "too early" in our function, e.g.,

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

What's wrong with this?
We make our recursive call even before checking if we're in the base case! In particular, if the a-nelon had only one item, (rest a-nelon> would be empty, and the recursive call would break the contract of non-empty-list (and, cause an error)!

Or a completely different example:

;; min-of-list: non-empty-list --> number
;;
(define (min-of-list a-nelon)
   (cond [(empty? (rest a-nelon)) (first a-nelon)]
         [else  (local {(define min-rest (min-of-list (rest a-nelon)))
                        (define first-bigger? (> (first a-nelon) min-rest))}
                   (cond [first-bigger? min-rest]
                         [else (first a-nelon)]))]))

This isn't strictly wrong, but notice that we only compare (first a-nelon) to the result of the recursive call once; giving a name to that sub-result may or may not be making the entire code clearer. Here's the use of local is optional; it is a judgement call about clarity.

Semantics

The Law of Scheme, for local:

For each defined name in the list of definitions, rename it something entirely unique, 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, how there are really two independent placeholders happenin'.

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)

To discuss: What does this code do?

(define growth-rate 1.1)

(define (grow n)
  (* n growth-rate))

(local
  {(define growth-rate 1.3)}
  (grow 10))

(grow 10)

Can you explain the result in terms of the Law of Scheme? We say that grow has (the first, top-level copy of) growth-rate in its "closure"; no matter where you use grow, that funciton knows its closure.

Is the following essentially different?

(define growth-rate 1.3)

(define (grow n)
  (local {(define growth-rate 1.1)}
    (* n growth-rate)))

(grow 10)

Exercises: What do each the following yield? (Note: some of them give errors about unbound placeholders.)
Hint: You can paste these in, and use the "check syntax" button. If in doubt, just apply the Law of Scheme!

(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?.

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

DrScheme's Check-Syntax button is pretty handy in this one! It's bizarre, but still just follows the law-of-scheme.