adrianwong programmer · retired coal miner

SICP section 2.1 - introduction to data abstraction

Selected exercises

Exercise 2.04

In section 2.1.3, the authors state that:

In general, we can think of data as defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfil in order to be a valid representation.

Thus, any implementation of cons, car and cdr can be used as a basis for implementing pairs, as long as they satisfy the condition that: for any x and y, if z is (cons x y), then (car z) is x, and (cdr z) is y.

So hey, why not implement cons, car and cdr using lambdas?

(define (cdr z)
  (z (lambda (p q) q)))

Verifying that cdr works using the substitution model:

(cdr (cons x y))
(cdr (lambda (m) (m x y)))
((lambda (m) (m x y)) (lambda (p q) q))
((lambda (p q) q) x y)
y

Exercise 2.05

To retrieve the pair’s first value, we count the number of times the product is evenly divisible by \(2\); to retrieve the second value, we count the number of times the product is evenly divisible by \(3\).

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

(define (num-divs n d)
  (define (div n count)
    (if (= (remainder n d) 0)
        (div (/ n d) (+ count 1))
        count))
  (div n 0))

(define (car z)
  (num-divs z 2))

(define (cdr z)
  (num-divs z 3))

Exercise 2.06

This exercise shows us how a language that can manipulate procedures is able to do away with natural numbers by implementing \(0\) and \(+ 1\) using lambda notation. This representation is known as Church numerals.

Defining one and two directly:

; one
(add-1 zero)
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))

; two
(add-1 (add-1 zero))
(add-1 (lambda (f) (lambda (x) (f x))))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
(lambda (f) (lambda (x) (f (f x))))

(lambda (f) (lambda (x) x))
(lambda (f) (lambda (x) (f x)))
(lambda (f) (lambda (x) (f (f x))))

…we can observe that one takes an input procedure f and returns a procedure that applies it once. two also takes an input procedure f, but it returns a procedure that applies it twice.

The pattern is obvious: for a given natural number \(n\), its Church numeral equivalent takes an input procedure f, and returns a procedure that applies it \(n\) times.

We can use this knowledge to help us define +. To add two values \(a\) and \(b\), all we need is to wrap \(b\) with \(a\) applications of f:

; +
(+ a b)
(lambda (f) (lambda (x) ((a f) ((b f) x))))

Exercise 2.07

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

(define (lower-bound i) (car i))

(define (upper-bound i) (cdr i))

Exercise 2.08

The minimum value the difference can be is the upper-bound of \(y\) subtracted from the lower-bound of \(x\), and the maximum value it can be is the lower-bound of \(y\) subtracted from the upper-bound of \(x\).

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

Exercise 2.09

Time for some math. Given:

$$\begin{align*} int_1 = [a, b], \quad width(int_1) = \frac{(b - a)}{2} \\ int_2 = [c, d], \quad width(int_2) = \frac{(d - c)}{2} \\ \end{align*}$$

We can prove that the width of the sum of two intervals is a function only of the widths of the intervals being added:

$$\begin{align*} add(int_1, int_2) &= [a + c, b + d] \\ width([a + c, b + d]) &= \frac{(b + d) - (a + c)}{2} \\ &= \frac{(b - a)}{2} + \frac{(d - c)}{2} \\ &= width(int_1) + width(int_2) \end{align*}$$

Proving that this is not true for multiplication:

(define a (make-interval 0 2))
(define b (make-interval 10 12))
(define c (make-interval 1 5))

(mul-interval a c) ; [0, 10]
(mul-interval b c) ; [10, 60]

a and b have the same width, but when both are multiplied by c, the resulting intervals have different widths. The width of the product of two intervals is therefore not a function of the widths of the intervals being multiplied.

Exercise 2.10

(define (div-interval x y)
  (mul-interval
   x
   (make-interval (/ 1.0 (upper-bound y)) ; This doesn't work with 0-spanning intervals
                  (/ 1.0 (lower-bound y)))))

If the denominator interval \(y\) spans 0, we end up constructing an invalid interval where the lower-bound has a higher value than the upper-bound.

Modifying the procedure so it signals an error if this occurs:

(define (div-interval x y)
  (if (and (<= (lower-bound y) 0)
           (>= (upper-bound y) 0))
      (error "Denominator interval cannot span 0")
      (mul-interval
       x
       (make-interval (/ 1.0 (upper-bound y))
                      (/ 1.0 (lower-bound y))))))

Exercise 2.11

This one was a slog. The only case which requires more than two multiplications is when \(x_L <= 0\), \(x_H >= 0\), \(y_L <= 0\) and \(y_H >= 0\).

(define (mul-interval x y)
  (let ((xL (lower-bound x))
        (xH (upper-bound x))
        (yL (lower-bound y))
        (yH (upper-bound y)))
    (cond ((and (>= xL 0)
                (>= xH 0)
                (>= yL 0)
                (>= yH 0))
           (make-interval (* xL yL) (* xH yH)))
          ((and (<= xL 0)
                (>= xH 0)
                (>= yL 0)
                (>= yH 0))
           (make-interval (* xL yH) (* xH yH)))
          ((and (<= xL 0)
                (<= xH 0)
                (>= yL 0)
                (>= yH 0))
           (make-interval (* xL yH) (* xH yL)))
          ((and (<= xL 0)
                (<= xH 0)
                (<= yL 0)
                (>= yH 0))
           (make-interval (* xL yH) (* xL yL)))
          ((and (<= xL 0)
                (>= xH 0)
                (<= yL 0)
                (>= yH 0))
           (make-interval (min (* xL yH) (* xH yL))
                          (max (* xL yL) (* xH yH))))
          ((and (>= xL 0)
                (>= xH 0)
                (<= yL 0)
                (>= yH 0))
           (make-interval (* xH yL) (* xH yH)))
          ((and (>= xL 0)
                (>= xH 0)
                (<= yL 0)
                (<= yH 0))
           (make-interval (* xH yL) (* xL yH)))
          ((and (<= xL 0)
                (>= xH 0)
                (<= yL 0)
                (<= yH 0))
           (make-interval (* xH yL) (* xL yL)))
          ((and (<= xL 0)
                (<= xH 0)
                (<= yL 0)
                (<= yH 0))
           (make-interval (* xH yH) (* xL yL))))))

Exercise 2.12

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

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

(define (percent i)
  (* (/ (width i) (center i)) 100.0))

Exercise 2.13

Let \(c\) be the center, and \(t\) be the tolerance. Therefore:

$$\begin{align*} x &= [c_x(1 - t_x), c_x(1 + t_x)] \\ y &= [c_y(1 - t_y), c_y(1 + t_y)] \end{align*}$$

Compute \(z = x * y\). We can assume that all numbers are positive, therefore \(z_L = x_L * y_L\) and \(z_H = x_H * y_H\).

$$\begin{align*} z = [c_xc_y(1 - t_x - t_y + t_xt_y), c_xc_y(1 + t_x + t_y + t_xt_y)] \end{align*}$$

We can disregard \(t_xt_y\), because the value will be very small. Therefore:

$$\begin{align*} z &= [c_xc_y(1 - t_x - t_y), c_xc_y(1 + t_x + t_y)] \\ z &= [c_xc_y(1 - (t_x + t_y)), c_xc_y(1 + (t_x + t_y))] \\\\ z &= [c_z(1 - t_z), c_z(1 + t_z)] \therefore t_z = t_x + t_y \end{align*}$$

Exercise 2.14

(define a (make-center-percent 100 1))
(define b (make-center-percent 200 2))

(par1 a b) ; (63.61967213114754, 69.84406779661016)
(par2 a b) ; (65.77627118644067, 67.55409836065574)

(center (div-interval a a))  ; 1.0002000200020003 <-- Division by self != 1
(percent (div-interval a a)) ; 1.9998000199980077

(center (div-interval a b))  ; 0.5003001200480192
(percent (div-interval a b)) ; 2.9994001199760016

Exercise 2.15

Proving that the two parallel resistor formulae are algebraically equivalent:

$$\begin{align} \frac{1}{1/R_1 + 1/R_2} &= \frac{1}{1/R_1 + 1/R_2} * \frac{R_1}{R_1} * \frac{R_2}{R_2} \\ &= \frac{R_1R_2}{R_1 + R_2} \end{align}$$

To arrive at \((2)\), we multiply equation \((1)\) by \(R_1 / R_1\) and \(R_2 / R_2\). Perfectly valid, as those divisions should equal \(1\). Or do they?

The problem is that \(R_1\) and \(R_2\) are intervals. As can be seen in exercise 2.14, the division of an interval by itself does not yield a value of \(1\).

This means Eva is correct - we can get tighter error bounds when no variable that represents an uncertain number is repeated in our formula, as each repetition introduces error.