Structure and Interpretation of Computer Programs

adding two intervals. She reasons that the minimum value the sum could be is the sum of the two

lower bounds and the maximum value it could be is the sum of the two upper bounds:

(define (add-interval x y)

  (make-interval (+ (lower-bound x) (lower-bound y))

                 (+ (upper-bound x) (upper-bound y))))

Alyssa also works out the product of two intervals by finding the minimum and the maximum of the

products of the bounds and using them as the bounds of the resulting interval. (

Min

 and 

max

 are 

primitives that find the minimum or maximum of any number of arguments.)

(define (mul-interval x y)

  (let ((p1 (* (lower-bound x) (lower-bound y)))

        (p2 (* (lower-bound x) (upper-bound y)))

        (p3 (* (upper-bound x) (lower-bound y)))

        (p4 (* (upper-bound x) (upper-bound y))))

    (make-interval (min p1 p2 p3 p4)

                   (max p1 p2 p3 p4))))

To divide two intervals, Alyssa multiplies the first by the reciprocal of the second. Note that the

bounds of the reciprocal interval are the reciprocal of the upper bound and the reciprocal of the lower

bound, in that order.

(define (div-interval x y)

  (mul-interval x 

                (make-interval (/ 1.0 (upper-bound y))

                               (/ 1.0 (lower-bound y)))))

Exercise 2.7.  Alyssa’s program is incomplete because she has not specified the implementation of the

interval abstraction. Here is a definition of the interval constructor:

(define (make-interval a b) (cons a b))

Define selectors 

upper-bound

 and 

lower-bound

 to complete the implementation. 

Exercise 2.8.  Using reasoning analogous to Alyssa’s, describe how the difference of two intervals

may be computed. Define a corresponding subtraction procedure, called 

sub-interval

. 

Exercise 2.9.  The width of an interval is half of the difference between its upper and lower bounds.

The width is a measure of the uncertainty of the number specified by the interval. For some arithmetic

operations the width of the result of combining two intervals is a function only of the widths of the

argument intervals, whereas for others the width of the combination is not a function of the widths of

the argument intervals. Show that the width of the sum (or difference) of two intervals is a function

only of the widths of the intervals being added (or subtracted). Give examples to show that this is not

true for multiplication or division. 

Exercise 2.10.  Ben Bitdiddle, an expert systems programmer, looks over Alyssa’s shoulder and

comments that it is not clear what it means to divide by an interval that spans zero. Modify Alyssa’s

code to check for this condition and to signal an error if it occurs. 

---

Exercise 2.11.  In passing, Ben also cryptically comments: ‘‘By testing the signs of the endpoints of

the intervals, it is possible to break 

mul-interval

 into nine cases, only one of which requires more

than two multiplications.’’ Rewrite this procedure using Ben’s suggestion. 

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

2

 The name 

cons

 stands for ‘‘construct.’’ The names 

car

 and 

cdr

 derive from the original

implementation of Lisp on the IBM 704. That machine had an addressing scheme that allowed one to

reference the ‘‘address’’ and ‘‘decrement’’ parts of a memory location. 

Car

 stands for ‘‘Contents of

Address part of Register’’ and 

cdr

 (pronounced ‘‘could-er’’) stands for ‘‘Contents of Decrement part

of Register.’’ 

3

 Another way to define the selectors and constructor is 

(define make-rat cons)

(define numer car)

(define denom cdr)

The first definition associates the name 

make-rat

 with the value of the expression 

cons

, which is

the primitive procedure that constructs pairs. Thus 

make-rat

 and 

cons

 are names for the same

primitive constructor.

Defining selectors and constructors in this way is efficient: Instead of 

make-rat

 calling 

cons

, 

make-rat

 is 

cons

, so there is only one procedure called, not two, when 

make-rat

 is called. On

the other hand, doing this defeats debugging aids that trace procedure calls or put breakpoints on

procedure calls: You may want to watch 

make-rat

 being called, but you certainly don’t want to

watch every call to 

cons

.

We have chosen not to use this style of definition in this book. 

4

 

Display

 is the Scheme primitive for printing data. The Scheme primitive 

newline

 starts a new

line for printing. Neither of these procedures returns a useful value, so in the uses of 

print-rat

below, we show only what 

print-rat

 prints, not what the interpreter prints as the value returned by 

print-rat

. 

---