Ken Dyck

One solution to Exercise 2.13:

In exercise 2.12, we found a way to express a range as a tolerance.

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

Where,

(define (make-center-width c w)
(make-interval (- c w) (+ c w))) #2

Expanding #2 in #1 give us:

(define (make-center-percent c p)
(make-interval (- c (* c (/ p 100)))
(+ c (* c (/ p 100))))) #3

Now, imagine a range, x with a center cx
and a percentage tolerance px.

(define x (make-center-percent cx px)) #4

Expanding #4 out, from #3, we get:

(define x
(make-interval (- cx (* cx (/ px 100)))
(+ cx (* cx (/ px 100))))) #5

That’s a bit messy with all those divisions by 100. Let’s introduce
an absolute tolerance, tx, that is one hundreth the
size of the percentage tolerance.

(define px (* tx 100)) #6

Substituting #6 into #5, we get:

(define x
(make-interval (- cx (* cx tx))
(+ cx (* cx tx)))) #7

We’ll need another range if we are to do any multiplication. Let’s
likewise define y:

(define y
(make-interval (- cy (* cy ty))
(+ cy (* cy ty)))) #8

Another lesson we learned from exercise 2.12 is how to find the
width of a range:

(define (width i)
(/ (- (upper-bound i) (lower-bound i)) 2)) #9

A couple of relations that we are almost certain to find useful
(and I hope you’ll find obvious):

(equal u (upper-bound (make-interval l u))) #10
(equal l (lower-bound (make-interval l u))) #11

In exercise 2.11, we found that when all the numbers are positive,
we can define mul-interval as follows:

(define (mul-interval x y)
(make-interval (* (lower-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y)))) #12

We are interested in the percentage tolerance of the product of two
intervals in terms of their percentage tolerances. In other words,

(percent (mul-interval x y)) #13

You’ll recall the definition of percent from exercise
2.12:

(define (percent i)
(* (/ (width i) (center i)) 100)) #14

Expanding #13 with #14, we get:

(* (/ (width (mul-interval x y))
(center (mul-interval x y)))
100) #15

To keep things from getting too messy, let’s just focus on the
width part for now:

(width (mul-interval x y)) #16

Substituting in #12

(width (make-interval
(* (lower-bound x)
(lower-bound y))
(* (upper-bound x)
(upper-bound y)))) #17

And the definitions of x and y from #7
and #8:

(width (make-interval
(* (lower-bound (make-interval (- cx (* cx tx))
(+ cx (* cx tx))))
(lower-bound (make-interval (- cy (* cy ty))
(+ cy (* cy ty)))))
(* (upper-bound (make-interval (- cx (* cx tx))
(+ cx (* cx tx))))
(upper-bound (make-interval (- cy (* cy ty))
(+ cy (* cy ty))))))) #18

Boy, this is getting messy. We can rely on relations #10 and #11 to
tidy things up a bit.

(width (make-interval
(* (- cx (* cx tx))
(- cy (* cy ty)))
(* (+ cx (* cx tx))
(+ cy (* cy ty))))) #19

Expanding out the products:

(width (make-interval
(- (+ (* cx cy) (* cx tx cy ty))
(+ (* cx cy ty) (* cy cx tx)))
(+ (* cx cy) (*cx tx cy ty)
(* cx cy ty) (* cy cx tx)))) #20

Substituting into #9

(/ (- (upper-bound
(make-interval
(- (+ (* cx cy) (* cx tx cy ty))
(+ (* cx cy ty) (* cy cx tx)))
(+ (* cx cy) (*cx tx cy ty)
(* cx cy ty) (* cy cx tx))))
(lower-bound
(make-interval
(- (+ (* cx cy) (* cx tx cy ty))
(+ (* cx cy ty) (* cy cx tx)))
(+ (* cx cy) (*cx tx cy ty)
(* cx cy ty) (* cy cx tx)))))
2) #21

Another mess. But we can call on #10 and #11 again to clean things
up.

(/ (- (+ (* cx cy) (*cx tx cy ty)
(* cx cy ty) (* cy cx tx))
(- (+ (* cx cy) (* cx tx cy ty))
(+ (* cx cy ty) (* cy cx tx))))
2) #22

Let’s rearrange the terms to see what, if anything, cancels out.

(/ (+ (- (* cx cy) (* cx cy))
(- (*cx tx cy ty) (*cx tx cy ty))
(* cx cy ty) (* cx cy ty)
(* cy cx tx) (* cy cx tx))
2) #23

Now we’re getting somewhere:

(/ (+ (* 2 cx cy ty)
(* 2 cy cx tx))
2) #24

Simplifying.

(+ (* cx cy ty) (* cy cx tx))) #25

And again.

(* cx cy (+ tx ty)) #26

So now we know what the width of a product is in terms
of the tolerances and centers. Now let’s take a look at the
center of a product.

(center (mul-interval x y)) #27

From exercise 2.12, we know the definiton of center

(define (center i)
(/ (+ (lower-bound i) (upper-bound i)) 2)) #28

Expanding #27.

(/ (+ (lower-bound (mul-interval x y))
(upper-bound (mul-interval x y)))
2) #29

Substituting #12.

(/ (+ (lower-bound (make-interval
(* (lower-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y))))
(upper-bound (make-interval
(* (lower-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y)))))
2) #30

Using #10 and #11, again.

(/ (+ (* (lower-bound x) (lower-bound y))
(* (upper-bound x) (upper-bound y)))
2) #31

Subsituting in #7 and #8:

(/ (+ (* (lower-bound (make-interval (- cx (* cx tx))
(+ cx (* cx tx))))
(lower-bound (make-interval (- cy (* cy ty))
(+ cy (* cy ty)))))
(* (upper-bound (make-interval (- cx (* cx tx))
(+ cx (* cx tx))))
(upper-bound (make-interval (- cy (* cy ty))
(+ cy (* cy ty))))))
2) #32

Can’t get enough of #10 and #11:

(/ (+ (* (- cx (* cx tx))
(- cy (* cy ty)))
(* (+ cx (* cx tx))
(+ cy (* cy ty))))
2) #33

Expanding it all out:

(/ (+ (- (* cx cy) (* cx cy ty))
(- (* cx tx cy ty) (* cy cx tx))
(* cx cy) (* cx cy ty)
(* cx tx cy ty) (* cy cx tx))
2) #34

Several terms cancel out again, leaving:

(/ (+ (* 2 cx cy)
(* 2 cx tx cy ty))
2) #35

Since we are assuming small tolerances, the second term
(* 2 cx tx cy ty) is effectively zero, leaving us
with:

(/ (* 2 cx cy)
2) #36

Or,

(* cx cy) #37

Now we can return to #15, substituting #26 and #37 in:

(* (/ (* cx cy (+ tx ty)))
(* cx cy))
100) #38

This simplifies quite nicely to:

(* (+ tx ty) 100) #39

Recall from #6 that we defined tx and ty
to eliminate the division by 100. If we switch back to percentage
notation, now, we get rid of that pesky 100 for good:

(+ px py) #40

There you have it. Assuming small tolerances, we can conclude that
the percentage tolerance of the product of two intervals is equal
to the sum of the tolerances of the multiplicands.

One solution to Exercise 2.12:

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

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


One solution to Exercise 2.11:

(define (mul-interval x y)
(let* ((lx (lower-bound x))
(ux (upper-bound x))
(ly (lower-bound y))
(uy (upper-bound y))
(pos-lx? (positive? lx))
(pos-ux? (positive? ux))
(pos-ly? (positive? ly))
(pos-uy? (positive? uy)))
(cond
; lx ux ly uy example
; ----------------------------------
; + - + + invalid interval
; + - + - invalid interval
; + - - + invalid interval
; + - - - invalid interval
((and pos-lx? (not pos-ux?))
(error "invalid interval" x))

; + + + - invalid interval
; - + + - invalid interval
; - - + - invalid interval
((and pos-ly? (not pos-uy?))
(error "invalid interval" y))

; + + + + (1.2)(2.3) = (2.6)
((and pos-lx? pos-ux? pos-ly? pos-uy?)
(make-interval (* lx ly) (* ux uy)))

; + + - + (1.2)(-2.3) = (-4.6)
((and pos-lx? pos-ux? (not pos-ly?) pos-uy?)
(make-interval (* ux ly) (* ux uy)))

; + + - - (1.2)(-2.-1) = (-4.-1)
((and pos-lx? pos-ux? (not pos-ly?) (not pos-uy?))
(make-interval (* ux ly) (* lx uy)))

; - + + + (-1.2)(2.3) = (-3.6)
((and (not pos-lx?) pos-ux? pos-ly? pos-uy?)
(make-interval (* lx uy) (* ux uy)))

; - + - + (-1.2)(-2.3) = (-4.6) *
((and (not pos-lx?) pos-ux? (not pos-ly?) pos-uy?)
(make-interval (min (* lx uy) (* ux ly))
(* ux uy)))

; - + - - (-1.2)(-2.-1) = (-4.2)
((and (not pos-lx?) pos-ux? (not pos-ly?) (not pos-uy?))
(make-interval (* ux ly) (* lx ly)))

; - - + + (-2.-1)(2.3) = (-6.-2)
((and (not pos-lx?) (not pos-ux?) pos-ly? pos-uy?)
(make-interval (* lx uy) (* ux ly)))

; - - - + (-2.-1)(-2.3) = (-6, 4)
((and (not pos-lx?) (not pos-ux?) (not pos-ly?) pos-uy?)
(make-interval (* lx uy) (* lx ly)))

; - - - - (-2.-1)(-2.-1) = (1.4)
((and (not pos-lx?) (not pos-ux?) (not pos-ly?) (not pos-uy?))
(make-interval (* ux uy) (* lx ly))))))

One solution to Exercise 2.10:

(define (spans-zero? x)
(not (or (positive? (lower-bound x))
(negative? (upper-bound x)))))

(define (div-interval x y)
(if (spans-zero? y)
(error "Divisor spans zero" y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))


A solution to Exercise 2.9:

Some preliminary definitions:

(upper-bound (make-interval a b)) = a [1]
(lower-bound (make-interval a b)) = b [2]

(width i) = (/ (- (upper-bound i) (lower-bound i)) 2) [3]

(add i1 i2) = (make-interval (+ (upper-bound i1) (upper-bound i2))
(+ (lower-bound i1) (lower-bound i2))) [4]


Rearranging [3]:

(* 2 (width i)) = (- (upper-bound i) (lower-bound i))
(+ (* 2 (width i)) (lower-bound i)) = (upper-bound i) [5]


From [3]:

(width (add i1 i2)) = (/ (- (upper-bound (add i1 i2))
(lower-bound (add i1 i2)))
2)


Simplifying with [1], [2] and [4]:

(width (add i1 i2)) = (/ (- (+ (upper-bound i1)
(upper-bound i2))
(+ (lower-bound i1)
(lower-bound i2)))
2)


Substituting in [5]:

= (/ (- (+ (+ (* 2 (width i1)) (lower-bound i1))
(+ (* 2 (width i2)) (lower-bound i2)))
(+ (lower-bound i1)
(lower-bound i2)))
2)

= (/ (- (+ (* 2 (width i1)) (* 2 (width i2))
(lower-bound i1)
(lower-bound i2))
(+ (lower-bound i1)
(lower-bound i2)))
2)


All the (lower-bound x)s cancel out, leaving:

= (/ (+ (* 2 (width i1))
(* 2 (width i2)))
2)


So do the 2s:

(width (add i1 i2)) = (+ (width i1) (width i2))

Clearly the width of the sum is a function only of the width of the operands.

A solution to Exercise 2.8:

The maximum the difference could be is difference between the upper bound of the first interval and the lower bound of the second. The minimum difference is the difference between the lower bound of the first and the upper bound of the second. This holds true even if the second interval is greater than the first or the intervals overlap.

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


A solution to Exercise 2.7:

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

One solution to Exercise 2.6:

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))

; (add-1 zero)
; (lambda (f) (lambda (x) (f ((zero f) x))))
; (lambda (f) (lambda (x) (f (((lambda (g) (lambda (y) y)) f) x))))
; (lambda (f) (lambda (x) (f ((lambda (y) y) x))))
; (lambda (f) (lambda (x) (f x)))
(define one
(lambda (f) (lambda (x) (f x))))

; (add-1 one)
;(lambda (f) (lambda (x) (f ((one f) x))))
;(lambda (f) (lambda (x) (f (((lambda (g) (lambda (y) (g (y)))) f) x))))
;(lambda (f) (lambda (x) (f ((lambda (y) (f (y))) x))))
;(lambda (f) (lambda (x) (f (f (x)))))
(define two
(lambda (f) (lambda (x) (f (f x)))))

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

; transform Church numerals to integers (for testing)
(define (to-integer n)
(define (inc x) (+ 1 x))
((n inc) 0))


Solution to Exercise 2.5:

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

(define (count-powers n d)
(define (iter i pow)
(if (zero? (remainder i d))
(iter (/ i d) (+ pow 1))
pow))
(iter n 0))

(define (car c)
(count-powers c 2))

(define (cdr c)
(count-powers c 3))


Solution to Exercise 2.4:

Substituting through…


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


The definition for cdr:

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