Structure and Interpretation of Computer Programs (21 page)

After debugging her program, Alyssa shows it to a potential user,
who complains that her program solves the wrong problem. He
wants a program that can deal with numbers represented as a center
value and an additive tolerance; for example, he wants to work with
intervals such as 3.5± 0.15 rather than [3.35, 3.65]. Alyssa
returns to her desk and fixes this problem by supplying an alternate
constructor and alternate selectors:

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))
(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

Unfortunately, most of Alyssa's users are engineers. Real engineering
situations usually involve measurements with only a small uncertainty,
measured as the ratio of the width of the interval to the midpoint of
the interval. Engineers usually specify percentage tolerances on the
parameters of devices, as in the resistor specifications given
earlier.

Exercise 2.12.
  Define a constructor
make-center-percent
that takes a center and
a percentage tolerance and produces the desired interval. You must
also define a selector
percent
that produces the
percentage tolerance for a given interval. The
center
selector
is the same as the one shown above.

Exercise 2.13.
  Show that under the assumption of small percentage tolerances there is
a simple formula for the approximate percentage tolerance of the
product of two intervals in terms of the tolerances of the factors.
You may simplify the problem by assuming that all numbers are
positive.

After considerable work, Alyssa P. Hacker delivers her finished
system. Several years later, after she has forgotten all about it, she
gets a frenzied call from an irate user, Lem E. Tweakit.
It seems that Lem has
noticed that the formula for parallel resistors can be written in two
algebraically equivalent ways:

and

He has written the following two programs, each of which computes the
parallel-resistors formula differently:

(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))
(define (par2 r1 r2)
  (let ((one (make-interval 1 1))) 
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))

Lem complains that Alyssa's program gives different answers for
the two ways of computing. This is a serious complaint.

Exercise 2.14.
  Demonstrate that Lem is right. Investigate the behavior of the
system on a variety of arithmetic expressions. Make some intervals
A
and
B
,
and use them in computing the expressions
A
/
A
and
A
/
B
. You will
get the most insight by using intervals whose width is a small
percentage of the center value. Examine the results of the computation
in center-percent form (see exercise 
2.12
).

Exercise 2.15.
  Eva Lu Ator, another user, has also noticed the different intervals
computed by different but algebraically equivalent expressions. She
says that a formula to compute with intervals using Alyssa's system
will produce tighter error bounds if it can be written in such a form
that no variable that represents an uncertain number is repeated.
Thus, she says,
par2
is a “better” program for parallel
resistances than
par1
. Is she right? Why?

Exercise 2.16.
  Explain, in general, why equivalent algebraic expressions may lead to
different answers. Can you devise an interval-arithmetic package that
does not have this shortcoming, or is this task impossible? (Warning:
This problem is very difficult.)

As we have seen, pairs provide a primitive “glue” that we can use to
construct compound data objects.
Figure 
2.2
shows a standard way to
visualize a
pair – in this case, the pair formed by
(cons 1 2)
.
In this representation, which is called
box-and-pointer
notation
, each object is shown as a
pointer
to a box. The box
for a primitive object contains a representation of the object. For
example, the box for a number contains a numeral. The box for a pair
is actually a double box, the left part containing (a pointer to) the
car
of the pair and the right part containing the
cdr
.

We have already seen that
cons
can be used to combine not
only numbers but pairs as well. (You made use of this fact, or
should have, in doing exercises 
2.2
and 
2.3
.) As a consequence, pairs provide a universal
building block from which we can construct all sorts of data
structures. Figure 
2.3
shows two ways
to use pairs to combine the numbers 1, 2, 3, and 4.

Figure 2.2:
  Box-and-pointer representation of
(cons 1 2)
.

Figure 2.3:
  Two ways to combine 1, 2, 3, and 4 using pairs.

The ability to create pairs whose elements are pairs is the essence of
list structure's importance as a representational tool. We refer to
this ability as the
closure property
of
cons
. In general,
an operation for combining data objects satisfies the closure property
if the results of combining things with that operation can themselves
be combined using the same operation.
⁶
Closure is the key to power in
any means of combination because it permits us to create
hierarchical
structures – structures made up of parts, which
themselves are made up of parts, and so on.

From the outset of chapter 1, we've made essential use of closure in
dealing with procedures, because all but the very simplest programs
rely on the fact that the elements of a combination can themselves be
combinations. In this section, we take up the consequences of closure
for compound data. We describe some conventional techniques for using
pairs to represent sequences and trees, and we exhibit a graphics
language that illustrates closure in a vivid way.
⁷

Figure 2.4:
  The sequence 1, 2, 3, 4 represented as a chain of pairs.