Introduction to Data Abstraction Exercises

2.1

Example: Arithmetic Operations for Rational Numbers

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))
(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))
(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

Pairs:

(define x (cons 1 2))
(car x) => 1
(cdr x) => 2

(define y (cons 3 4))
(define z (cons x y))
(car (car z)) => 1
(car (cdr z)) => 3

Representing rational numbers:

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

(define one-half (make-rat 1 2))
(print-rat one-half) =$> ["1/2"]

(define one-third (make-rat 1 3))
(add-rat one-half one-third) => '(5 . 6)
(mul-rat one-half one-third) => '(1 . 6)
(add-rat one-third one-third) => '(6 . 9)

Reducing to lowest terms:

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

(add-rat one-third one-third) => '(2 . 3)

Exercise 2.1

(define (sgn x)
  (cond ((positive? x) 1)
        ((zero? x) 0)
        ((negative? x) -1)))

(define (make-rat n d)
  (let ((g (gcd n d))
        (s (* (sgn n) (sgn d))))
    (cons (* s (/ (abs n) g))
          (/ (abs d) g))))

(make-rat 5 10) => '(1 . 2)
(make-rat -5 10) => '(-1 . 2)
(make-rat -5 -10) => '(1 . 2)
(make-rat 5 -10) => '(-1 . 2)

Abstraction Barriers

(define (make-rat n d) (cons n d))
(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))
(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

Exercise 2.2

(define make-point cons)
(define x-point car)
(define y-point cdr)

(define make-segment cons)
(define start-segment car)
(define end-segment cdr)

(define (midpoint-segment seg)
  (let ((a (start-segment seg))
        (b (end-segment seg)))
    (make-point
     (/ (+ (x-point a) (x-point b)) 2)
     (/ (+ (y-point a) (y-point b)) 2))))

(midpoint-segment
 (make-segment (make-point 6 5) (make-point 12 13)))
=> '(9 . 9)

Exercises 2.3

Imports: Exercise 2.2 make-point x-point y-point

(define (perimeter rect)
  (* 2 (+ (width-rect rect) (height-rect rect))))
(define (area rect)
  (* (width-rect rect) (height-rect rect)))

First representation: two corners.

(define make-rect cons)
(define p1-rect car)
(define p2-rect cdr)
(define (width-rect rect)
  (abs (- (x-point (p1-rect rect))
          (x-point (p2-rect rect)))))
(define (height-rect rect)
  (abs (- (y-point (p1-rect rect))
          (y-point (p2-rect rect)))))

(define rect (make-rect (make-point 1 2) (make-point 6 5)))
(perimeter rect) => 16
(area rect) => 15

Second representation: corner and dimensions.

(define (make-rect p w h) (cons p (cons w h)))
(define point-rect car)
(define width-rect cadr)
(define height-rect cddr)

(define rect (make-rect (make-point 1 2) 5 3))
(perimeter rect) => 16
(area rect) => 15

What is Meant by Data?

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error 'cons "argument not 0 or 1" m))))
  dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

(car (cons 'a 'b)) => 'a
(cdr (cons 'a 'b)) => 'b

Exercise 2.4

(define (cons x y) (lambda (m) (m x y)))
(define (car z) (z (lambda (x y) x)))
(define (cdr z) (z (lambda (x y) y)))

(car (cons 'a 'b)) => 'a
(cdr (cons 'a 'b)) => 'b

Exercise 2.5

Due to the fundemental theorem of arithmetic, $2^a3^b$ will always produce a unique prouct give a unique pair of integers a and b.

(define (cons x y) (* (expt 2 x) (expt 3 y)))

(define (count-divides a b)
  (define (count a n)
    (let ((q (/ a b)))
      (if (integer? q)
          (count q (+ n 1))
          n)))
  (count a 0))

(define (car z) (count-divides z 2))
(define (cdr z) (count-divides z 3))

(car (cons 7 12)) => 7
(cdr (cons 7 12)) => 12

Exercise 2.6

(define zero (lambda (f) (lambda (x) x)))
(define (add1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

(define (add a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))

(define (church->number n)
  ((n (lambda (x) (+ x 1))) 0))

(church->number zero) => 0
(church->number one) => 1
(church->number two) => 2
(church->number (add1 two)) => 3
(church->number (add one zero)) => 1
(church->number (add zero two)) => 2
(church->number (add one two)) => 3
(church->number (add two two)) => 4

Extended Exercise: Interval Arithmetic

Imports: Exercise 2.7 lower-bound make-interval upper-bound

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

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

(define (div-interval x y)
  (mul-interval
   x
   (make-interval (/ 1.0 (upper-bound y))
                  (/ 1.0 (lower-bound y)))))

Exercise 2.7

(define (make-interval a b) (cons a b))
(define (lower-bound x) (car x))
(define (upper-bound x) (cdr x))

Exercise 2.8

Imports: Exercise 2.7 lower-bound make-interval upper-bound

The difference between two intervals reaches a minimum at the minuend’s lower bound minus the subtrahend’s upper bound. It reaches a maximum at the minuend’s upper bound minus the subtrahend’s lower bound.

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))

Exercise 2.9

Imports: Extended Exercise: Interval Arithmetic add-interval div-interval mul-interval, Exercise 2.7 lower-bound make-interval upper-bound, Exercise 2.8 sub-interval

(define (width x)
  (/ (- (upper-bound x) (lower-bound x)) 2))

Consider arbitrary intervals x and y:

(define x1 (random 1000))
(define x2 (random 1000))
(define y1 (random 1000))
(define y2 (random 1000))

(define x (make-interval x1 x2))
(define y (make-interval y1 y2))

(width x) => (/ (- x2 x1) 2)
(width y) => (/ (- y2 y1) 2)

The width of the sum is the sum of the widths:

(width (add-interval x y))
=> (width (make-interval (+ x1 y1) (+ x2 y2)))
=> (/ (- (+ x2 y2) (+ x1 y1)) 2)
=> (/ (+ (- x2 x1) (- y2 y1)) 2)
=> (+ (/ (- x2 x1) 2) (/ (- y2 y1) 2))
=> (+ (width x) (width y))

The width of the difference is also the sum of the widths:

(width (sub-interval x y))
=> (width (make-interval (- x1 y2) (- x2 y1)))
=> (/ (- (- x2 y1) (- x1 y2)) 2)
=> (/ (+ (- x2 x1) (- y2 y1)) 2)
=> (+ (/ (- x2 x1) 2) (/ (- y2 y1) 2))
=> (+ (width x) (width y))

The width of a product or quotient is not a function of the widths of the intervals being multiplied or divided. Here is a counterexample:

(define x (make-interval 0 10))
(define y (make-interval 4 6))
(width x) => 5
(width y) => 1
(width (mul-interval x y)) => 30
(width (div-interval x y)) ~> 1.25

(define x (make-interval -5 5))
(define y (make-interval -1 1))
(width x) => 5
(width y) => 1
(width (mul-interval x y)) => 5
(width (div-interval x y)) ~> 5.0

In both cases the input widths are 5 and 1, but the product widths are different (30 and 5), as are the quotient widths (1.25 and 5).

Exercise 2.10

Imports: Extended Exercise: Interval Arithmetic mul-interval, Exercise 2.7 lower-bound make-interval upper-bound

(define (div-interval x y)
  (let ((y1 (lower-bound y))
        (y2 (upper-bound y)))
    (if (<= y1 0 y2)
        (error 'div-interval "can't divide by an interval spanning zero" y)
        (mul-interval x (make-interval (/ y2) (/ y1))))))

(div-interval (make-interval 1 2) (make-interval 3 4)) => '(1/4 . 2/3)
(div-interval (make-interval 1 2) (make-interval -1 1)) =!> "can't divide"

Exercise 2.11

Imports: Exercise 2.7 lower-bound make-interval upper-bound

(define (mul-interval x y)
  (let ((x1 (lower-bound x))
        (x2 (upper-bound x))
        (y1 (lower-bound y))
        (y2 (upper-bound y)))
    (cond ((> x1 0)
           (cond ((> y1 0) (make-interval (* x1 y1) (* x2 y2)))
                 ((< y2 0) (make-interval (* x2 y1) (* x1 y2)))
                 (else (make-interval (* x2 y1) (* x2 y2)))))
          ((< x2 0)
           (cond ((> y1 0) (make-interval (* x1 y2) (* x2 y1)))
                 ((< y2 0) (make-interval (* x2 y2) (* x1 y1)))
                 (else (make-interval (* x1 y2) (* x1 y1)))))
          (else
           (cond ((> y1 0) (make-interval (* x1 y2) (* x2 y2)))
                 ((< y2 0) (make-interval (* x2 y1) (* x1 y1)))
                 (else (make-interval (min (* x1 y2) (* x2 y1))
                                      (max (* x1 y1) (* x2 y2)))))))))

(mul-interval (make-interval 1 2) (make-interval 3 4)) => '(3 . 8)

Exercise 2.12

Imports: Example: Square Roots by Newton’s Method⁠ average, Exercise 2.7 lower-bound make-interval upper-bound

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

(define (make-center-percent c p)
  (make-center-width c (* c (/ p 100))))
(define (percent x)
  (* 100 (/ (width x) (center x))))

(define x (make-interval 9 11))
(width x) => 1
(center x) => 10
(percent x) => 10

Exercise 2.13

Imports: Extended Exercise: Interval Arithmetic mul-interval, Exercise 2.12 make-center-percent percent

Under the assumption of small percentage tolerances, there is a simple formula for the approximate percent tolerance of the product of two intervals in terms of the tolerances of the factors: their sum. Consider two intervals $i$ and $j$ , represented both in lower-upper bound form and in center-tolerance form.

\begin{aligned} i &= [a_i,b_i] = [c_i(1-t_i),c_i(1+t_i)], \\ j&= [a_j,b_j] = [c_j(1-t_j),c_j(1+t_j)]. \end{aligned}

Assuming all numbers are positive, their product is

\begin{aligned} ij &= [a_i a_j, b_i b_j], \\ &= [c_ic_j(1-t_i)(1-t_j),c_ic_j(1+t_i)(1+t_j)] \\ &= [c_ic_j(1-t_i-t_j+t_it_j), c_ic_j(1+t_i+t_j+t_it_j)]. \end{aligned}

Since $t_i$ and $t_j$ are small, their product $t_it_j$ is negligible, so we can approximate:

ij \approx [c_ic_j(1-(t_i+t_j)), c_ic_j(1+(t_i+t_j))]

A simple test bears out this approximation:

(define i (make-center-percent 30 1))
(define j (make-center-percent 25 3))
(define i*j (mul-interval i j))
(+ (percent i) (percent j)) => 4
(percent i*j) ~> 3.9988003598920323

Exercise 2.14

Imports: Extended Exercise: Interval Arithmetic add-interval div-interval mul-interval, Exercise 2.7 make-interval, Exercise 2.12 center make-center-percent percent

(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 is right. The resulting uncertainty is different for mathematically equivalent expressions calculated by par1 and par2:

(define r1 (make-center-percent 10000 5))
(define r2 (make-center-percent 330 10))
(percent (par1 r1 r2)) ~> 19.931607019958708
(percent (par2 r1 r2)) ~> 9.841433938087881

When we divide an interval by itself, we should get exactly one. Instead, we get an interval whose center is approximately one, with a fair amount of uncertainty.

(define i (make-center-percent 5000 2))
(define j (make-center-percent 2500 1))
(center (div-interval i i)) ~> 1.0008003201280510 ; ideally should be 1
(percent (div-interval i i)) ~> 3.998400639744109 ; ideally should be 0%
(center (div-interval i j)) ~> 2.0006000600060000 ; correct
(percent (div-interval i j)) ~> 2.999400119975999 ; correct

Exercise 2.15

Yes, Eva is right. When the expressions are written such a form that no uncertain variable is repeated, the uncertainty of the result is smaller, and this is the more correct value. When an uncertain variable is repeated, the interval arithmetic procedures have no way of knowing that they are dealing with the same value twice, so they combine uncertainties as if they were separate measurements. For example, If we manipulate an algebraic expression by dividing a value by itself, we introduce error because the interval arithmetic division does not produce exactly one.

Exercise 2.16

In general, equivalent expressions may lead to different answers because identical intervals are treated indepedently even if they represent the same measurement. This is called the dependency problem. For complicated functions, it is not always possible to eliminate repetitions of an interval in the expression, so there is an unwanted expansion in the resulting intervals. It is impossible to completely avoid this shortcoming. The best we can do is attempt to rewrite expressions so that intervals are not repeated.