SICP Section 2.1 Introduction to Data Abstraction

Exercise 2.1. Define a better version of make-rat that handles both positive and negative arguments. Make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

Answer:
(define (make-rat n d) (let ((g (gcd n d)) (ratio (/ n d))) (if (> ratio 0.0) (cons (/ n g) (/ d g)) (cons (- (abs (/ n g))) (abs (/ d g))))))
Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:
(define (print-point p) (newline) (display "(") (display (x-point p)) (display ",") (display (y-point p)) (display ")"))
Answer:
;; Point (define (make-point x y) (cons x y)) (define (x-point p) (car p)) (define (y-point p) (cdr p)) ;; Line segment (define (make-segment start end) (cons start end)) (define (start-segment seg) (car seg)) (define (end-segment seg) (cdr seg)) (define (print-point p) (display "(") (display (x-point p)) (display ",") (display (y-point p)) (display ")")) (define (midpoint-segment seg) (let ((start (start-segment seg)) (end (end-segment seg))) (let ((x1 (x-point start)) (y1 (y-point start)) (x2 (x-point end)) (y2 (y-point end))) (make-point (average x1 x2) (average y1 y2))))) ;; (define seg (make-segment (make-point 0 1) (make-point 2 1))) ;; (print-point (midpoint-segment seg)) ;; (1,1)
Exercise 2.3. Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

Answer:
(define (make-rect p1 p2 p3 p4) (cons (cons p1 p2) (cons p3 p4))) (define (length-seg seg) (let ((start (start-segment seg)) (end (end-segment seg))) (let ((x1 (x-point start)) (y1 (y-point start)) (x2 (x-point end)) (y2 (y-point end))) (sqrt (+ (square (- x2 x1)) (square (- y2 y1))))))) (define (rect-length r) (let ((p1 (car (car r))) (p2 (cdr (car r)))) (let ((side (make-segment p1 p2))) (length-seg side)))) (define (rect-breadth r) (let ((p1 (car (car r))) (p4 (cdr (cdr r)))) (let ((side (make-segment p1 p4))) (length-seg side)))) (define (perimeter r) (* 2 (+ (rect-length r) (rect-breadth r)))) (define (area r) (* (rect-length r) (rect-breadth r))) ;; (define r (make-rect ;; (make-point 0 0) ;; (make-point 0 1) ;; (make-point 2 1) ;; (make-point 2 0))) ;; (perimeter r) ;; 6 ;; (area r) ;; 2
Exercise 2.4. Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p)))
What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

Answer:
(define (cons1 x y) (lambda (m) (m x y))) (define (car1 z) (z (lambda (p q) p))) ;; cdr (define (cdr1 z) (z (lambda (p q) q))) ;; (car1 (cons1 2 1)) ;; 2 ;; (cdr1 (cons1 2 1)) ;; 1
Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a 3b. Give the corresponding definitions of the procedures cons, car, and cdr.

Answer:
(define (count-powers-of-n number n) (define (iter count number) (if (and (= (remainder number n) 0) (>= number n)) (iter (+ 1 count) (/ number n)) count)) (iter 0 number)) (define (count-powers-of-2 number) (count-powers-of-n number 2)) (define (count-powers-of-3 number) (count-powers-of-n number 3)) (define (n-cons a b) (* (expt 2 a) (expt 3 b))) (define (n-car z) (count-powers-of-2 z)) (define (n-cdr z) (count-powers-of-3 z)) ;; (n-car (n-cons 10 11)) ;; 10 ;; (n-cdr (n-cons 10 11)) ;; 11
Exercise 2.6. In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

Answer:
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x))))) ;; one (define one (lambda (f) (lambda (x) (f x)))) ;; two (define two (lambda (f) (lambda (x) (f (f x))))) ;; + (define (church+ m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
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.

Answer:
;; selectors (define (lower-bound interval) (car interval)) (define (upper-bound interval) (cdr interval))
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.

Answer:
(define (sub-interval x y) (make-interval (- (lower-bound x) (upper-bound y)) (- (upper-bound x) (lower-bound y))))
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.


(define (spans-zero? interval) (and (< (lower-bound interval) 0) (> (upper-bound interval) 0))) (define (div-interval x y) (if (spans-zero? y) (error "Denominator interval spans zero" y) (mul-interval x (make-interval (/ 1.0 (upper-bound y)) (/ 1.0 (lower-bound y))))))
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.

Answer:
(define (above-zero? interval) (and (> (lower-bound interval) 0) (> (upper-bound interval) 0))) (define (below-zero? interval) (and (< (lower-bound interval) 0) (< (upper-bound interval) 0))) (define (mul-interval x y) (let ((l1l2 (* (lower-bound x) (lower-bound y))) (l1u2 (* (lower-bound x) (upper-bound y))) (u1l2 (* (upper-bound x) (lower-bound y))) (u1u2 (* (upper-bound x) (upper-bound y)))) (cond ((and (above-zero? x) (above-zero? y)) (make-interval l1l2 u1u2)) ((and (above-zero? x) (spans-zero? y)) (make-interval u1l2 u1u2)) ((and (spans-zero? x) (above-zero? y)) (make-interval l1u2 u1u2)) ((and (above-zero? x) (below-zero? y)) (make-interval u1u2 l1l2)) ((and (below-zero? x) (above-zero? y)) (make-interval u1u2 l1l2)) ((and (below-zero? x) (spans-zero? y)) (make-interval l1u2 l1l2)) ((and (spans-zero? x) (below-zero? y)) (make-interval u1l2 l1l2)) ((and (below-zero? x) (below-zero? y)) (make-interval u1u2 l1l2)) ((and (spans-zero? x) (spans-zero? y)) (make-interval (min l1u2 u1l2) (min l1l2 u1u2))))))
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.

Answer:
(define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2)) (define (make-center-percent c p) (let ((p-value (/ (* c p) 100))) (make-interval (- c p-value) (+ c p-value))))
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.

Answer: Let x and y be two intervals and dx and dy their respective tolerances. Their product can be calculated as (x + dx) * (y + dy). Expanding this we get xy + xdy + ydx + dxdy. As dx and dy are small to begin with their product will be very small and can be ignored without losing much accuracy. The equation then becomes xy + xdy + ydx.

If we call the product z, with a tolerance dz, then z + dz = xy + xdy + ydx. Separating z and dz, we get dz = xdy + ydx. This is the relation between the tolerance of the product the individual tolerances.

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

Answer: Lem's hypothesis is easily proven right. Take the example below.
(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))))) (define x (make-center-percent 3 0.1)) (define y (make-center-percent 7 0.1)) (par1 x y) ;; (2.0937083916083914 . 2.1063084084084083) (par2 x y) ;; (2.0979 . 2.1021)
The problem stems from the fact that the formulae do not take intervals into consideration whereas the code does. For instance the interval one implicitly assumes that R1/R1 = R2/R2 = 1. However this is only true when intervals are not involved. Hence the two formulae give two different results.

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?

Answer: Eva is correct. As we are operating with intervals rather than whole numbers it is better to reduce the "occurrence" of intervals in any given formula to a minimum. This reduces the number of ways in which errors can creep in and thereby produces tighter bounds. As the second formula has fewer occurrences of the intervals it will produce tighter bounds.

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

Answer: The answer is similar those of the two previous questions. The main reason is the difference between using whole numbers and intervals. Normal properties and rules of algebra that apply to whole numbers do not hold true when intervals are used. For instance, while x/x = 1 when x and y are non zero whole numbers this is not so for cases when x is an interval. Likewise x - x need not be zero and so on.

It *might* be possible to develop a package provided such concepts as inverse can be defined for an interval. I am not sure how to go about the definitions though.