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
.
Dostları ilə paylaş: |