Avoiding repetition, local, Don't get carried away, Efficiency, Scope
All of these code examples are in /home/comp210/public_html/Labs/lab06/examples.ss, except for the scope examples, which are in separate files.
(Note to labbies: you can quickly skim this section.)
In some of our programs, we have calculated the same thing multiple times because we needed to use the result multiple times. For example, consider the following code:
(define repeat-and-double-each-number1
(lambda (l)
(cond ((null? l) null)
(else (cons (* 2 (car l))
(cons (* 2 (car l))
(repeat-and-double-each-number1 (cdr l))))))))
;> (repeat-and-double-each-number1 (list 1 2 3 4))
;(2 2 4 4 6 6 8 8)
It's a silly, but short, example.
Notice that the expression (* 2 (car l)) is repeated.
Wouldn't it be nice if we could avoid, or at least reduce such repetition? It would save us time typing, and it should make the code shorter and thus easier to understand. We'll examine another major benefit later.
Somehow, we need to name the intermediate result of (* 2 (car l)). Let's look at how we could do this, given what we know about Scheme so far.
We could write
(define double (lambda (n) (* 2 n)))
(define repeat-and-double-each-number2
(lambda (l)
(cond ((null? l) null)
(else (cons (double (car l))
(cons (double (car l))
(repeat-and-double-each-number2 (cdr l))))))))
or even
(define double-first-element (lambda (ll) (* 2 (car ll))))
(define repeat-and-double-each-number3
(lambda (l)
(cond ((null? l) null)
(else (cons (double-first-element l)
(cons (double-first-element l)
(repeat-and-double-each-number3 (cdr l))))))))
This approach let's us have a single helper function, double
or double-first-element, that does most of the work for us.
We still have repeated subexpressions that use the helper function,
but the repetitions are smaller.
Another way to use a helper function would be the following:
(define repeat-first-element
(lambda (n ll)
(cons n (cons n ll))))
(define repeat-and-double-each-number4
(lambda (l)
(cond ((null? l) null)
(else (repeat-first-element
(* 2 (car l))
(repeat-and-double-each-number4 (cdr l)))))))
I.e., the helper function does the repetition, not the "real work" of doubling.
(Of course, we could combine the two approaches, too.)
Note that we now have a name for the repeated computation's value:
n, in the helper function.
We don't need to name our helper function, here repeat-first-element. We could have written something like
(define repeat-and-double-each-number5
(lambda (l)
(cond ((null? l) null)
(else ((lambda (n ll) (cons n (cons n ll)))
(* 2 (car l))
(repeat-and-double-each-number5 (cdr l)))))))
I.e., we just stuck the definition of the helper function where we used to
call it.
Note: To try this example, you'll need to use the Advanced language level. Because of that, this function is commented out in the source file provided.
The helper function is now an anonymous function, i.e., we just don't give it a name. In particular, it's an anonymous function which we aren't passing around anywhere, but we're simply applying it immediately. We've seen this before a few times, but now we see a real benefit from it.
Unfortunately, code like this can be awkward to read. This pattern is so common, that Scheme has several ways of writing this idea in a more readable way. For this class, we show one of these:
(define repeat-and-double-each-number6
(lambda (l)
(cond ((null? l) null)
(else (local [(define n (* 2 (car l)))
(define ll (repeat-and-double-each-number6 (cdr l)))]
(cons n (cons n ll)))))))
Compare some of these, especially repeat-and-double-each-number1 and repeat-and-double-each-number6 in Donkey.
As its name implies, the keyword local allows us to introduce local variables. (Why are these variables called "local"? We'll see why later.)
A local expression has the form
(local [def1
...
defn]
exp)
where each of def1 to defn are definitions, i.e.,
a define or define-structure expression.
These definitions are effective only in the expression
exp.
(This is part of the reason these variables are "local" -- they are
local to exp.)
As more fully explained in class, this local is equivalent to
There are two easy ways to misuse local:
We can use it "too early", e.g.,
(define repeat-and-double-each-number7
(lambda (l)
(local [(define n (* 2 (car l)))
(define ll (repeat-and-double-each-number7 (cdr l)))]
(cond ((null? l) null)
(else (cons n (cons n ll)))))))
Here, the problem is that we try to select the parts of list l
before we see that it isn't null!
Or a completely different example:
(define double-even-numbers
(lambda (l)
(cond ((null? l) null)
(else (local [(x (double-even-numbers (cdr l)))]
(cond
((even? (car l)) (cons (double (car l)) x))
((odd? (car l)) (cons (car l) x))))))))
There's nothing really wrong with this, but notice that
even without the local, we'd only call
double-even-numbers once each iteration, not twice, because
each use is in a separate branch of a conditional.
Here's the use of local is optional, and is a question of style
and clarity.
There's another major reason why avoiding repetition is important. In our original several versions of repeat-and-double-each-number, the program performed the doubling of each element twice. In our last versions, the program performed the doubling of each element only once, named the result of the doubling, and used that value twice. The original versions require (about) twice as much time, since they do the same work twice.
Here, doubling takes a negligible amount of time, but we could easily change our program so that, instead of doubling each number, we calculate some big hairy function of each number.
With those examples, we can see that using local variables can reduce the amount of computation by some constant fraction, but it it can be much more important than that. Consider our lecture's example where a function contains repeated code which recursively calls the same function:
(define max-list1
(lambda (l)
(cond ((null? l) 0)
(else (if (> (car l) (max-list1 (cdr l)))
(car l)
(max-list1 (cdr l)))))))
and
(define max-list2
(lambda (l)
(cond ((null? l) 0)
(else (local [(define m (max-list2 (cdr l)))]
(if (> (car l) m)
(car l)
m))))))
Try stepping through these in Donkey, e.g.,
(max-list1 (list 4 8 2 10)) (max-list2 (list 4 8 2 10))And this is for just a list of four elements!
max-list1 can be twice as bad for list of
length 5.
In DrScheme (not Donkey), how long a list of
ascending numbers can max-list1 process in, say, a minute?
How about when using max-list2?
(What about a list of descending numbers?
A randomly-scrambled list?)
Variables in declared in a local really are "local". They are only accessible inside the local, in both the final "body" expression, and also in each of the local definitions.
The following are some examples illustrating the scope of local variables. "Scope" refers to where the value of the variable is accessible. Or stated another way, if you have a local variable and a global variable of the same name, scope tells you which one you are using. Try these examples in DrScheme and Donkey. In DrScheme, use Check Syntax, and then observe the arrows it draws between variable uses and their definitions. In Donkey, observe the renaming of variables (as described in class) as you step through evaluation.
File: /home/comp210/public_html/Labs/lab06/scope1.ss:
(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)
File: /home/comp210/public_html/Labs/lab06/scope2.ss:
(define w 1)
(define x 3)
(define test
(lambda (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)
File: /home/comp210/public_html/Labs/lab06/scope3.ss:
(define x 1)
(define y 1)
(local
[(define x 2)
(define y x)]
(+ x y))
(+ x y)
File: /home/comp210/public_html/Labs/lab06/scope4.ss:
(local
[(define Odd?
(lambda (n) (if (zero? n) #f (Even? (- n 1)))))
(define Even?
(lambda (n) (if (zero? n) #t (Odd? (- n 1)))))]
(Odd? 5))
(Odd? 5)
File: /home/comp210/public_html/Labs/lab06/scope5.ss:
(define x 1)
(define y 2)
(define z 3)
(define test
(lambda (x)
(local
[(define y 5)]
(+ (local
((define x (lambda (x y) (* x y)))
(define y 5))
(x y z))
x))))
(test 7)
Ok, so this one is pretty bizarre, but you should be able to figure
it out.