SICP Study

2.1 Introduction to Data Abstraction⁠

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

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

Exercise 2.3⁠ 

(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

2.1.3 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 fundamental theorem of arithmetic, 2a3b2^a3^b will always produce a unique product given a unique pair of integers aa and b.b\htmlClass{math-punctuation}{\text{.}}

(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

2.1.4 Extended Exercise: Interval Arithmetic⁠ 

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

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⁠ 

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

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

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

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

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 ii and j,j\htmlClass{math-punctuation}{\text{,}} represented both in lower-upper bound form and in center-tolerance form:

i=[ai,bi]=[ci(1−ti),ci(1+ti)],j=[aj,bj]=[cj(1−tj),cj(1+tj)].\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

ij=[aiaj,bibj]=[cicj(1−ti)(1−tj),cicj(1+ti)(1+tj)]=[cicj(1−ti−tj+titj),cicj(1+ti+tj+titj)].\begin{aligned} ij &= [a_ia_j,b_ib_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 tit_i and tjt_j are small, their product titjt_it_j is negligible, so we can approximate:

ij≈[cicj(1−(ti+tj)),cicj(1+(ti+tj))]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⁠ 

(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 in 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.