7 minute read

Section 2.1.3 - What Is Meant by Data?

Exercise 2.4

As the writers tell us, we can use the substitution model to verify that this works:

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

So it essentially creates an anonymous procedure that accepts two arguments and returns the first. This means that we can implement cdr as:

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

Exercise 2.5

We create a helper procedure contains and use it to implement both car and cdr:

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

(define (car z)
  (contains z 2))

(define (cdr z)
  (contains z 3))

(define (contains z n)
  (define (iter a i)
    (if (> (remainder a n) 0)
        i
        (iter (/ a n) (inc i))))
  (iter z 0))

Exercise 2.6

We will first use substitution to evaluate (add-1 zero) as the authors advise:

(add-1 zero)
(add-1 (lambda (f) (lambda (x) x)))
(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)))

So this means that zero applies zero times its argument procedure f. Each time we add 1 though, we apply the argument procedure one more time. Essentially the Church numeral is the function itself, composed $n$ times. So this means that we can define one as:

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

and two as:

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

We can then define addition as applying the composition $m + n$ times:

(define (plus m n)
    (lambda (f) (lambda (x) ((m f) ((n f) x)))))

We get our hint for the above from the way add-1 is implemented. Observe the (f ((n f) x)) part. What it essentially does is apply f once (add-1, remember?) to the result of passing consecutively f and x to the supplied function. In the case of zero, the result is x. In the case of one the result would be:

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

and so on and so forth.

Section 2.1.4 - Extended Exercise: Interval Arithmetic

Exercise 2.7

The selectors are simple to implement:

(define (lower-bound interval) (car interval))

(define (upper-bound interval) (cdr interval))

Exercise 2.8

The ordering will not change here:

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

Exercise 2.9

Assume we have intervals \(x\) and \(y\). Assume also we prefix by \(\mathrm{lb-}\) and \(\mathrm{ub-}\) the lower and upper bound respectively. The width of the sum \(x + y\) will be:

\[\begin{align*} \mathrm{width}(x + y) &= \mathrm{width}([\mathrm{lb-}x + \mathrm{lb-}y, \mathrm{ub-}x + \mathrm{ub-}y])\\ &= \frac{\mathrm{ub-}x + \mathrm{ub-}y - \mathrm{lb-}x - \mathrm{lb-}y}{2}\\ &= \frac{\mathrm{ub-}x - \mathrm{lb-}x}{2} + \frac{\mathrm{ub-}y - \mathrm{lb-}y}{2}\\ &= \mathrm{width}(x) + \mathrm{width}(y) \end{align*}\]

So the width of the sum (and similarly, the difference) of two intervals is a function only of the widths of the intevals being added.

Consider multiplication. Assume we have two intervals \(a = (1, 3)\) and \(b = (-3, -1)\). Their widths are \(\mathrm{width}(a) = 1\) and \(\mathrm{width}(b) = 1\). However, their multiplication yields the interval \(a \times b = (-9, -1)\) and \(\mathrm{width}(a \times b) = 4\). Now if instead of \(b\) we use an other interval of width 1, e.g. \(d = (5, 7)\) we would have \(a \times d = (5, 21)\) and \(\mathrm{width}(a \times c) = 8\). So width is not a function only of the widths of the intervals beeing multiplied. Division is exactly similar.

Exercise 2.10

(define (div-interval x y)
  (if (and (<= (lower-bound y) 0) (>= (upper-bound y) 0))
      (error "Cannot divide by interval that spans zero")
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))))

Exercise 2.11

In my mind this is one case where the programmer has to choose between optimization and readable code. So, if you’re starving for resources then by all means, do this.

Each interval can have its numbers both negative, one negative and one positive, or both positive. Hence three times three are the nine cases we need to examine. In each case but the one where both intervals span zero, we do not need to compare anything to arrive at the solution. Finally, in the case where both intervals span zero, we can at least use less arguments in |min| and |max| by observing that each time only two numbers will be positive and two will be negative. Here goes:

(define (mul-interval x y)
  (let ((lbx (lower-bound x))
        (lby (lower-bound y))
        (ubx (upper-bound x))
        (uby (upper-bound y)))
    (cond ((and (> lbx 0) (> lby 0) (> ubx 0) (> uby 0))
           ;; 1) all positive
           (make-interval (* lbx lby) (* ubx uby)))
          ((and (< lbx 0) (< lby 0) (< ubx 0) (< uby 0))
           ;; 2) all negative
           (make-interval (* ubx uby) (* lbx lby)))
          ((and (< lbx 0) (> lby 0) (< ubx 0) (> uby 0))
           ;; 3) x all negative, y all positive
           (make-interval (* lbx uby) (* ubx lby)))
          ((and (> lbx 0) (< lby 0) (> ubx 0) (< uby 0))
           ;; 4) x all positive, y all negative
           (make-interval (* ubx lby) (* lbx uby)))
          ((and (> lbx 0) (< lby 0) (> ubx 0) (> uby 0))
           ;; 5) only lower bound of y negative
           (make-interval (* ubx lby) (* ubx uby)))
          ((and (< lbx 0) (> lby 0) (> ubx 0) (> uby 0))
           ;; 6) only lower bound of x negative
           (make-interval (* lbx uby) (* ubx uby)))
          ((and (< lbx 0) (< lby 0) (< ubx 0) (> uby 0))
           ;; 7) only upper bound of y positive
           (make-interval (* lbx uby) (* lbx lby)))
          ((and (< lbx 0) (< lby 0) (> ubx 0) (< uby 0))
           ;; 8) only upper bound of x positive
           (make-interval (* ubx lby) (* lbx lby)))
          ((and (< lbx 0) (< lby 0) (> ubx 0) (> uby 0))
           ;; 9) lower bounds negative, upper bounds positive
           (let ((neg1 (* lbx uby))
                 (neg2 (* ubx lby))
                 (pos1 (* lbx lby))
                 (pos2 (* ubx uby)))
             (make-interval (min neg1 neg2) (max pos1 pos2)))))))

Exercise 2.12

(define (make-center-percent c p)
  (let ((w (* p c)))
    (make-center-width c w)))

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

Exercise 2.13

Assume for intervals \(a = (x, p_1)\) and \(b = (y, p_2)\), where \(p_i\) is the tolerance of the interval. We could rewrite $a$ in terms of bounds as:

\[\begin{align*} (x - p_1x, x + p_1)\\ (x(1 - p_1), x(1 + p_1)) \end{align*}\]

and similarly \(b\) is \((y(1 - p_2), y(1 + p_2))\). Since all numbers are positive, the lower bound of their product will be the multiplication of their lower bounds and similarly for the upper bounds. Let’s work it out:

\[\begin{align*} (x(1 - p_1)y(1 - p_2), x(1 + p_1)y(1 + p_2))\\ (xy(1 - (p_1 + p_2 - p_1p_2)), xy(1 + (p_1 + p_2 + p_1p_2))) \end{align*}\]

Assuming small percentage tolerances, e.g. \(10^{-2}\), their products will be very small (e.g. \(10^{-4}\)) and can be ignored. So we can assume that the approximate percentage tolerance of the product of two intervals would be \(p_1 + p_2\).

Exercise 2.14

We can demonstrate that Lem is right by choosing intervals \(R_1 = (1, 3)\) and \(R_2 = (3, 6)\). We have:

> (par1 (make-interval 1 3) (make-interval 3 6))
=>
(mcons 0.3333333333333333 4.5)
;; and
> (par2 (make-interval 1 3) (make-interval 3 6))
=>
(mcons 0.75 2.0)

The issue here is that for algrebraic operations to work correctly (and thus for the two formulas to be equivalent), some equations such as \(A/A = 1\) must be respected in our system. However, this is not true for intervals where width is of the same order of magnitude as the center value. As this changes, the value gets closer to one. Observe:

> (div-interval (make-interval 1 2)(make-interval 1 2))
=>
(mcons 0.5 2.0)
;; while
> (div-interval (make-interval 10000 10001)(make-interval 10000 10001))
=>
(mcons 0.9999000099990002 1.0001)

Using center-percent form, we can at least make sure that as the percentage is small, the operations get closer to correctness. Keep in mind, that we designed our system as a way to specify ranges of values, representing error (or tolerance). This value is supposed to be small. But even in real world scenarios such as the resistor of 6.8ohms with 10\% tolerance, our system does not work correctly:

> (div-interval (make-center-percent 6.8 0.1)(make-center-percent 6.8 0.1))
=>
(mcons 0.8181818181818182 1.222222222222222)

Exercises 2.15 & 2.16

Eva Lu Ator has a point. When a variable introduces uncertainty, our system by design transfers this uncertainty to any other variable with which it operates. If we push uncertainty to the edges (i.e. have as few operations as possible) then we should get better results.

Having said that, an interval-arithmetic package should provide general operations. One option would be to limit operations to variables with small error percentages. However, as we saw with the capacitors, a 10\% error is pretty common. This would render our package useless.

In order for our package to be generic enough so it can be useful, it should respect algebraic axioms such as \(0a = 0\), \(a/a = 1\), \(a(b + c) = ab + ac\), etc. This is what makes the problem difficult.

Updated: