SICP « Dan's Thoughts

28Jul/090

Exercise 2.12 of SICP

Exercise 2.12: Define a constructor make-center-percent that takes a center and a percentage tolerance and produces the desired interval. You must also define a selector percent that produces the percentage tolerance for a given interval. The center selector is the same as the one shown above.

(define (make-center-percent value p)
  (make-center-width value (* value (/ p 100.0))))
(define (percent int)
  (* 100 (/ (width int) (center int))))
 
(define (make-interval a b) 
  (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))
(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 (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)
  (define (spans-zero? i)
    (and 
      (not (> (lower-bound i) 0)) 
      (not (< (upper-bound i) 0)))) 
  (if (spans-zero? y)
    (error "The dividing interval cannot span 0.")
    (mul-interval x 
                  (make-interval (/ 1.0 (upper-bound y))
                                 (/ 1.0 (lower-bound y))))))
 
(define (sub-interval2 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 (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))
 
(define (print int)
  (newline)
  (display "[")
  (display (lower-bound int))
  (display ",")
  (display (upper-bound int))
  (display "]")
  (newline))

> (print (make-center-percent 10 12))
[8.8,11.2]
> (percent (make-center-percent 10 12))
11.999999999999993

Filed under: lisp, SICP No Comments

27Jul/090

Exercise 2.11 of SICP

Exercise 2.11: In passing, Ben also cryptically comments: "By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only one of which requires more than two multiplications.'' Rewrite this procedure using Ben's suggestion.

The assumption made here is that for any interval $[x_1,x_2]$ : $x_1 \le x_2$
Using this assumption here are the 9 valid signs combinations.


[+,+]  [+,+]
[+,+]  [-,+]
[-,+]  [-,+]
[-,+]  [+,+]
[+,+]  [-,-]
[-,-]  [+,+]
[-,-]  [-,+]
[-,+]  [-,-]
[-,-]  [-,-]

Notice that the case of 3 will need a little extra logic since it is possible for the two negative lower bounds to multiply together and become larger than the two positive upper bounds.

(define (mult-interval x y)
  (define (positive? a)
    (if (not (< a 0))
      #t
      #f))
  (define (negative? a)
    (if (not (< a 0))
      #f
      #t))
  (define (1-positives? a)
    (positive? a))
  (define (2-positives? a b)
    (and (positive? a) (positive? b)))
  (define (3-positives? a b c)
    (and (positive? a) 
         (positive? b)
         (positive? c)))
  (define (4-positives? a b c d)
    (and (positive? a) 
         (positive? b)
         (positive? c)
         (positive? d)))
  (define (1-negatives? a)
    (not (1-positives? a)))
  (define (2-negatives? a b)
    (and (negative? a)
         (negative? b)))
  (define (3-negatives? a b c)
    (and (negative? a)
         (negative? b)
         (negative? c)))
  (define (4-negatives? a b c d)
    (and (negative? a)
         (negative? b)
         (negative? c)
         (negative? d)))
  (let ((x1 (lower-bound x))
        (x2 (upper-bound x))
        (y1 (lower-bound y))
        (y2 (upper-bound y)))
    (cond ((4-positives? x1 x2 y1 y2) (make-interval (* x1 y1) (* x2 y2))) ;1
          ((4-negatives? x1 x2 y1 y2) (make-interval (* x2 y2) (* x1 y1))) ;9
          ((and (3-positives? x1 x2 y2) ;2
                (1-negatives? y1))
             (make-interval (* x2 y1) (* x2 y2)))
          ((and (3-positives? x2 y1 y2) ;4
                (1-negatives? x1))
             (make-interval (* x1 y2) (* x2 y2)))
          ((and (3-negatives? x1 x2 y1) ;7
                (1-positives? y2))
           (make-interval (* x1 y2) (* x1 y1)))
          ((and (3-negatives? x1 y1 y2) ;8
                (1-positives? x2))
           (make-interval (* x2 y1) (* x1 y1)))
          ((and (2-positives? x1 x2) ;5
                (2-negatives? y1 y2))
           (make-interval (* y1 x2) (* x1 y2)))
          ((and (2-positives? y1 y2) ;6
                (2-negatives? x1 x2))
           (make-interval (* x1 y2) (* y1 x2)))
          ((and (2-positives? x2 y2) ;3
                (2-negatives? x1 y1))
           (cond ((< x1 y1) (make-interval (* x1 y2) (* x2 y2)))
                 ((< y1 x1) (make-interval (* y1 x2) (* x2 y2))))))))

> (print (mul-interval (make-interval 1 2) (make-interval 3 4)))
[3,8]
> (print (mult-interval (make-interval 1 2) (make-interval 3 4)))
[3,8]
> (print (mult-interval (make-interval -2 -1) (make-interval -4 -3)))
[3,8]
> (print (mul-interval (make-interval -2 -1) (make-interval -4 -3)))
[3,8]
> (print (mul-interval (make-interval -2 1) (make-interval -4 -3)))
[-4,8]
> (print (mult-interval (make-interval -2 1) (make-interval -4 -3)))
[-4,8]

I suspect this problem is given not because it's an expert systems programmer's way of solving it but for the interval arithmetic to sync in about always maximizing the width of the new interval whenever possible.

Filed under: lisp, SICP No Comments

26Jul/090

Exercise 2.10 of SICP

Exercise 2.10: Ben Bitdiddle, an expert systems programmer, looks over Alyssa's shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Modify Alyssa's code to check for this condition and to signal an error if it occurs.

If an interval I = [-2,2] spans 0, the inverse, I^-1=[0.5,-0.5] which is wrong since the lower limit cannot be greater than the upper limit.

(define (div-interval x y)
  (define (spans-zero? i)
    (and 
      (not (> (lower-bound i) 0)) 
      (not (< (upper-bound i) 0)))) 
  (if (spans-zero? y)
    (error "The dividing interval cannot span 0.")
    (mul-interval x 
                  (make-interval (/ 1.0 (upper-bound y))
                                 (/ 1.0 (lower-bound y))))))

> (div-interval (make-interval 1 1) (make-interval -2 2))
*** ERROR IN (console)@76.1 -- The dividing interval cannot span 0.

Filed under: lisp, SICP No Comments

25Jul/090

Exercise 2.9 of SICP

Exercise 2.9: The width of an interval is half of the difference between its upper and lower bounds. The width is a measure of the uncertainty of the number specified by the interval. For some arithmetic operations the width of the result of combining two intervals is a function only of the widths of the argument intervals, whereas for others the width of the combination is not a function of the widths of the argument intervals. Show that the width of the sum (or difference) of two intervals is a function only of the widths of the intervals being added (or subtracted). Give examples to show that this is not true for multiplication or division.

$(a-\epsilon_1,a+\epsilon_1) \pm (b-\epsilon_2,b+\epsilon_2)$
$w_a=\frac{1}{2}(a+\epsilon_1-(a-\epsilon_1))=\epsilon_1$
$w_b=\frac{1}{2}(b+\epsilon_2-(b-\epsilon_2))=\epsilon_2$

Addition:

$(a-\epsilon_1,a+\epsilon_1)+(b-\epsilon_2,b+\epsilon_2)$
$\left((a+b)-(\epsilon_1+\epsilon_1),(a+b)+(\epsilon_1+\epsilon_1))\right)$
$w_{a+b}=\epsilon_1+\epsilon_2=w_a+w_b$

Subtraction:

$(a-\epsilon_1,a+\epsilon_1)-(b-\epsilon_2,b+\epsilon_2)$
$\left((a-b)-(\epsilon_1+\epsilon_2),(a-b)+(\epsilon_1+\epsilon_2)\right)$
$w_{a-b}=\epsilon_1+\epsilon_2= w_a+w_b$

Multiplication:

$(a-\epsilon_1,a+\epsilon_1) \cdot (b-\epsilon_2,b+\epsilon_2)$

$(a+\epsilon_1)\cdot(b+\epsilon_2)=ab+a\epsilon_2+b\epsilon_1+\epsilon_1\epsilon_2$
$(a+\epsilon_1)\cdot(b-\epsilon_2)=ab-a\epsilon_2+b\epsilon_1-\epsilon_1\epsilon_2$
$(a-\epsilon_1)\cdot(b+\epsilon_2)=ab+a\epsilon_2-b\epsilon_1-\epsilon_1\epsilon_2$
$(a-\epsilon_1)\cdot(b-\epsilon_2)=ab-a\epsilon_2-b\epsilon_1+\epsilon_1\epsilon_2$

If any of the four intervals expressions are used as interval endpoints their width formula will not give the tidy results of addition/subtraction.

Division:

$(a-\epsilon_1,a+\epsilon_1) \cdot (\frac{1}{b+\epsilon_2},\frac{1}{b-\epsilon_2})$

$(a-\epsilon_1)\cdot\frac{1}{b+\epsilon_2}=\frac{a-\epsilon_1}{b+\epsilon_2}$
$(a+\epsilon_1)\cdot\frac{1}{b+\epsilon_2}=\frac{a+\epsilon_1}{b+\epsilon_2}$
$(a-\epsilon_1)\cdot\frac{1}{b-\epsilon_2}=\frac{a-\epsilon_1}{b-\epsilon_2}$
$(a+\epsilon_1)\cdot\frac{1}{b-\epsilon_2}=\frac{a+\epsilon_1}{b-\epsilon_2}$

Examples:

w₁=0.68
w₂=0.235
w_total=0.915
> (print (add-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[10.585,12.415]
w_actual=0.915

w₁=0.68
w₂=0.235
w_total=0.915
> (print (sub-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[1.1850000000000005,3.0150000000000006]
w_actual=0.915 (ignoring the floating point number errors)

w₁=0.68
w₂=0.235
w_{naive_total}=0.15980
Of course this doesn't make sense since accuracy cannot be magically gained by multiplying two interval together. More on this in the division example.
> (print (mul-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[1.1850000000000005,3.0150000000000006]
w_actual=4.794

w₁=0.68
w₂=0.235
w_{naive_total}=2.89361702127659574468
> (print (div-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[1.2401215805471126,1.6752519596864504]
w_actual=.2175651895696689
How is it that w_actual is smaller than each w₁, w₂? w_{naive_total} is just plain wrong and should be discarded.

The answer is that w_actual isn't smaller. It's actually larger. The percentage of error that w_actual represents, for it's interval, is actually greater than either w₁=10% and w₂=5%. w_actual = 14.9%.
$6.8 \pm 0.68$
$0.68 = \frac{0.68}{6.8}=10\%$
$4.7 \pm 0.235$
$0.235 = \frac{0.235}{4.7}=5\%$
$0.2175651895696689 = \frac{.2175651895696689}{\left(\frac{1}{2}\cdot(1.2401215805471126+1.6752519596864504)\right)}=14.9\%$

As expected the error is actually higher even though the aggregate number for w_actual looks smaller.

Filed under: lisp, math, SICP No Comments

24Jul/090

Exercise 2.8 of SICP

Exercise 2.8: Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

In the resistor example, the resistor is measured at 6.8 ohm with a tolerance of 10%. This means the actual value is $6.8 \pm 0.68$ , which makes the interval [6.12 , 7.48]. The other resistor is $4.7 \pm 0.235$ with the interval of [4.465 , 4.935]. Naively subtracting the two intervals would give, [1.655 , 2.545]. Which doesn't seem wrong but it is. It is wrong because we are biasing the tolerance in one direction for both measurements. We assume that the first value is $6.8-0.68$ and second $4.7-0.235$ . There is no basis to assume that the following case isn't just as valid: $6.8-0.68$ and $4.7+0.235$ .
It's even clearer with the interval of $3 \pm 1$ [2 , 4] and $2 \pm 1$ [1 , 3]. Naively subtracting these terms yields an interval of 0 length, [1,1] or $1 \pm 0$ which is nonsense.
In order to make sure no tolerance bias exists that makes calculations seem more accurate than is possible, the worst case measurement error must be assumed. The intervals will become as wide as possible to not give a false sense of accuracy.

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))
(define (make-interval a b) (cons a b))
 
(define (lower-bound inter) (car inter))
(define (upper-bound inter) (cdr inter))
 
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(define (div-interval x y)
  (mul-interval x 
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-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 (print int)
  (newline)
  (display "[")
  (display (lower-bound int))
  (display ",")
  (display (upper-bound int))
  (display "]")
  (newline))

> (print (sub-interval (make-interval 6.12 7.48) (make-interval 4.465 4.935)))
[1.1850000000000005,3.0150000000000006]

Filed under: lisp, math, SICP No Comments

23Jul/090

Exercise 2.7 of SICP

Exercise 2.7: Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:

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

Define selectors upper-bound and lower-bound to complete the implementation.

(define (make-interval a b) (cons a b))
 
(define (lower-bound inter) (car inter))
(define (upper-bound inter) (cdr inter))
 
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(define (div-interval x y)
  (mul-interval x 
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-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 (print int)
  (newline)
  (display "[")
  (display (lower-bound int))
  (display ",")
  (display (upper-bound int))
  (display "]")
  (newline))

Filed under: lisp, SICP No Comments

22Jul/090

Exercise 2.6 of SICP

Exercise 2.6: In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

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

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

This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

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

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

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

(add-1 one)
(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))))

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

In order to check these I will use the fact that Church numerals appear to be repeated function composition.
If I use the familiar inc function and pass an argument of 0 I should get the number I am looking for:

(define (inc n) (+ n 1))

> ((one inc) 0)
1
> ((two inc) 0)
2
> (((add-1 two) inc) 0)
3

Now that I am convinced that my functions work it's time to move on and create an addition function.

(define (add M N)
  (lambda (f)
    (lambda (x)
      ((M f) ((N f) x)))))

(add one one)
(add (lambda (f) (lambda (x) (f x))) (lambda (f) (lambda (x) (f x))))
(lambda (f)
  (lambda (x)
    (((lambda (f) (lambda (x) (f x))) f) (((lambda (f) (lambda (x) (f x))) f) x))))
(lambda (f)
  (lambda (x)
    ((lambda (x) (f x)) ((lambda (x) (f x)) x))))
(lambda (f)
  (lambda (x)
    ((lambda (x) (f x)) (f x))))
(lambda (f)
  (lambda (x)
    (f (f x))))

Now to check that it works properly:
> (((add one one) inc) 0)
2
> (((add two one) inc) 0)
3
> (((add two two) inc) 0)
4

Just for fun multiply looks like this:

(define (mult m n)
  (lambda (f)
      (m (n f))))

Filed under: lisp, SICP No Comments

21Jul/090

Exercise 2.5 of SICP

Exercise 2.5: Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

The discrete log procedure is a cousin of discrete-log from 1.45.

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))
 
(define (car x)
  (discrete-log x 2))
 
(define (cdr x)
  (discrete-log x 3))
 
(define (discrete-log n base)
  (if (not
        (= 0 (remainder n base)))
    0
    (+ 1 (discrete-log (/ n base) base))))

Filed under: lisp, SICP No Comments

20Jul/090

Exercise 2.4 of SICP

Exercise 2.4: Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.

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

What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

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

> (car (cons 1 2))
1
> (cdr (cons 1 2))
2

The reason this works is because upon execution of cons the function that is returned is used in a clever way by car and cons. Car and cdr pass a function via the m parameter in the cons. That function then receives as arguments x and y. In the case of cdr the second parameter is returned. The thing to note is that x and y get stored in the lambda function when the cons procedure is called.

(car (cons 1 2))
(car (lambda (m) (m 1 2)))
((lambda (m) (m 1 2)) (lambda (p q) p))
((lambda (p q) p) 1 2)
(lambda (1 2) 1)
1

Filed under: lisp, SICP No Comments

19Jul/090

Exercise 2.3 of SICP

Exercise 2.3: Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

I have decided to use a diagonal segment for representation of make-rectangle and a point with both dimensional magnitudes for make-rectangle2.

(define (make-segment p1 p2)
  (cons p1 p2))
(define (start-segment s)
  (car s))
(define (end-segment s)
  (cdr s))
(define (average a b) (/ (+ a b) 2.0))
(define (make-point x y)
    (cons x y))
(define (x-point p)
  (car p))
(define (y-point p)
  (cdr p))
(define (midpoint-segment s)
  (make-point
    (average
        (x-point (start-segment s))
        (x-point (end-segment s)))
    (average
        (y-point (start-segment s))
        (y-point (end-segment s)))))
 
(define (dimension direction r)
  (- (direction (end-segment r))
     (direction (start-segment r))))
 
(define (width r) (dimension y-point r))
(define (length r) (dimension x-point r))
 
(define (make-rectangle s) s)
 
(define (make-rectangle2 p length width)
  (make-segment p
                (make-point
                  (+ (x-point p) length)
                  (+ (y-point p) width))))
 
(define (area r)
  (* (length r)
     (width r)))
 
(define (perimeter r)
  (* 2 (+ (length r)
          (width r))))

(define R
  (make-rectangle (make-segment
                    (make-point 0 0)
                    (make-point 4 4))))

> (area R)
16
> (perimeter R)
16

(define R2 (make-rectangle2
             (make-point 0 0)
             4 4))

> (area R2)
16
> (perimeter R2)
16

(define R
  (make-rectangle (make-segment
                    (make-point 2 1)
                    (make-point 5 4))))

> (area R)
9
> (perimeter R)
12

(define R2 (make-rectangle2
             (make-point 2 1)
             3 3))

> (area R)
9
> (perimeter R)
12

Filed under: lisp, math, SICP No Comments

« Newer Entries Older Entries »

Dan's Thoughts Thinking somewhat carefully

Exercise 2.12 of SICP

Exercise 2.11 of SICP

Exercise 2.10 of SICP

Exercise 2.9 of SICP

Exercise 2.8 of SICP

Exercise 2.7 of SICP

Exercise 2.6 of SICP

Exercise 2.5 of SICP

Exercise 2.4 of SICP

Exercise 2.3 of SICP

Pages

Categories

Blogroll

Archive

Meta