Laboratory: Analyzing Procedures
Exercise 1: Manual Analysis
a. Add the following line to the beginning of list-append
(immediately after the line containing the lambda).
(write (list 'list-append front back)) (newline)
b. Determine how many times list-append is called when
reversing a list of length seven using list-reverse-1.
c. Add the following line to the kernel of list-reverse-2
(again, immediately after the line containing the lambda).
(write (list 'kernel remaining reversed)) (newline)
d. Determine how many times the kernel
is called when reversing a list of length seven using
list-reverse-2.
e. Comment out the lines that you just added by prefixing them with
a semicolon.
Exercise 2: Automatic Analysis
a. Replace the define for
list-reverse-1 with define$,
as in the following.
(define$ list-reverse-1
(lambda (lst)
...))
b. Find out how many times list-append is called
in reversing a list of seven elements by entering the following command
in the interactions pane.
> (analyze (list-reverse-1 (list 1 2 3 4 5 6 7)) list-append)
c. Did you get the same answer as in the previous exercise? If not,
why do you think you got a different result?
d. One potential issue is that we haven't told the analyst to
include the recursive calls in list-append.
We can do so by replacing define
with define$ in the definition of
list-append.
e. Once again, find out how many times list-append
is called in reversing a list of seven elements by entering the
following command in the interactions pane.
> (analyze (list-reverse-1 (list 1 2 3 4 5 6 7)) list-append)
f. Did you get the same answer as in exercise 1? If not, what
difference do you see?
g. Replace the define in
list-reverse-2 with define$.
h. Find out how many times kernel is called in reversing
a list of seven elements by entering the following command in the
interactions pane.
> (analyze (list-reverse-2 (list 1 2 3 4 5 6 7)) kernel)
i. Did you get the same answer as in exercise 1? If not, what difference
do you see?
Exercise 3: Additional Calls
In the previous exercise, you considered only a single
procedure in each case (list-append for
list-reverse-1, list-reverse-2-kernel
for list-reverse-2). Suppose we incorporate all of
the other procedures. What effect does it have?
a. Find out how many total procedure calls are done in reversing a list
of length seven, using list-reverse-1, with the following.
> (analyze (list-reverse-1 (list 1 2 3 4 5 6 7)))
b. How does that number of calls seem to relate to the number of
calls to list-append?
c. Are there any procedures you're surprised to see?
d. Find out how many total procedure calls are done in reversing a list
of length seven, using list-reverse-2, by entering the
following command.
> (analyze (list-reverse-2 (list 1 2 3 4 5 6 7)))
e. How does that number of calls seem to relate to the number of
calls to kernel?
f. Are there any procedures you're surprised to see?
Exercise 4: Predicting Calls
a. Fill in the following chart to the best of your ability.
| List Length |
rev1: Calls to list-append |
rev1: Total calls |
rev2: Calls to kernel |
rev2: Total calls |
| 2 |
| | | |
| 4 |
| | | |
| 8 |
| | | |
| 16 |
| | | |
b. Predict what the entries will be for a list size of 32.
c. Check your results experimentally.
d. Write a formula for the columns, to the best of your ability.
Exercise 5: The Brightest Color, Revisited
Here is a third version of rgb-brightest, which should already
be in your program.
(define rgb-brightest-3
(lambda (colors)
(let kernel ((brightest-so-far (car colors))
(remaining-colors (cdr colors)))
(if (null? remaining-colors)
brightest-so-far
(kernel (rgb-brighter brightest-so-far (car remaining-colors))
(cdr remaining-colors))))))
a. Find out how many steps this procedure takes on lists of length 2,
4, 8, and 16 in which the elements are arranged from lightest to darkest.
(You may want to review the reading to see how we built lists of colors
arranged from lightest to darkest.)
b. Find out how many steps this procedure takes on lists of length 2,
4, 8, and 16 in which the elements are arranged from darkest to lightest.
(You can reverse the lists from the previous step to create these lists.)
c. Find out how many steps this procedure takes on lists of length 2,
4, 8, and 16 in which the elements are in no particular order.
d. Predict the number of steps this procedure will take on each kind of
list, where the length is 32.
For Those with Extra Time
Extra 1: The Effects of Preconditions
Consider rgb-brightest-4, a variant of an efficient
version of rgb-brightest that has additional error
checking added.
(define rgb-brightest-4
(lambda (colors)
(when (not (all-rgb? colors))
(error "rgb-brightest: expects a list of colors; received" colors))
(if (null? (cdr colors))
(car colors)
(rgb-brighter (car colors)
(rgb-brightest-4 (cdr colors))))))
a. Predict the number of calls to rgb-brightest-4
in finding the brightest in a list of eight colors.
b. Check your hypothesis.
c. Predict the number of calls to all-rgb? in
finding the brightest in a list of eight colors.
d. Check your hypothesis.
Extra 2: Precondition Checking, Revisited
Rewrite rgb-brightest-4 so that it continues to
check preconditions, but precondition checking does not exact such a
heavy penalty.
