notes-ch2-1.md

Section 2.1

Introduction

Meeting 03-30-2025

Hindley–Milner style types.
LISPs implement memory safety during runtime
Type safety isn't just about [...]?
Runtime issue: generalized form of the halting problem;
Halting problem: https://en.wikipedia.org/wiki/Rice%27s_theorem and https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem -- relevant if we ask what static things we can say about a program (without running it)
Rust is guaranteed to not have false negatives about memory safety [?]
Type safety
https://nature-of-computation.org/ -- https://en.wikipedia.org/wiki/Christos_Papadimitriou has some interesting has some interesting, approachable books.
https://hbpms.blogspot.com/
https://hackernewsbooks.com/
https://people.eecs.berkeley.edu/~bh/sicp.html

Exercises

Exercise 2.1

Define a better version of make-rat that handles both positive and negative arguments. Make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

Solution

code/ex2-1.rkt

#lang sicp

(define (make-rat n d)
  (if (< d 0) (make-rat (- n) (- d))
    (let ((g (gcd n d)))
      (cons (/ n g) 
            (/ d g)))))

(make-rat 10 15)
(make-rat 10 -15)
(make-rat -10 15)
(make-rat -10 -15)

Output:

(2 . 3)
(-2 . 3)
(-2 . 3)
(2 . 3)

Exercise 2.2

Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the $x$ coordinate and the $y$ coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

Solution

code/ex2-2.rkt

#lang sicp
(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))
(define (make-segment a b) (cons a b))
(define (start-segment seg) (car seg))
(define (end-segment seg) (cdr seg))
(define (make-point x y) (cons x y))
(define (x-point pt) (car pt))
(define (y-point pt) (cdr pt))
(define (midpoint-segment seg)
  (let ((x1 (x-point (start-segment seg)))
        (y1 (y-point (start-segment seg)))
        (x2 (x-point (end-segment seg)))
        (y2 (y-point (end-segment seg))))
        (make-point (/ (+ x1 x2) 2) (/ (+ y1 y2) 2))))

(print-point (midpoint-segment (make-segment 
                                  (make-point 0 0) 
                                  (make-point 3 3))))

Output:

(3/2,3/2)

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?

Solution

Super tedious! I guess this is the 1980's version of "implement these getter functions" -.-

I was tempted to implement a programmatic way to switch between rect1 or rect2 based on a flag passed in, but I think that's overengineering the problem.

code/ex2-3.rkt

#lang sicp

(define (make-point x y) (cons x y))
(define (x-point pt) (car pt))
(define (y-point pt) (cdr pt))
(define (print-point p)
  (newline) (display "(") (display (x-point p)) (display ",")
  (display (y-point p)) (display ")"))

;; One representation
(define (make-rect1 pos widthheight)
  (cons pos widthheight))
(define (rect-width1 rect)
  (x-point (cdr rect)))
(define (rect-height1 rect)
  (y-point (cdr rect)))
(define (rect-perimeter1 rect)
  (* 2 (+ (rect-width1 rect) (rect-height1 rect))))
(define (rect-area1 rect)
  (* (rect-width1 rect) (rect-height1 rect)))

;;Second representation using "top-left" and "bottom-right"
;;constraint: tl.x<br.x, tl.y<br.y
(define (make-rect2 tl br)
  (cons tl br))
(define (rect-width2 rect)
  (- (x-point (cdr rect)) (x-point (car rect))))
(define (rect-height2 rect)
  (- (y-point (cdr rect)) (y-point (car rect))))
(define (rect-perimeter2 rect)
  (* 2 (+ (rect-width2 rect) (rect-height2 rect))))
(define (rect-area2 rect)
  (* (rect-width2 rect) (rect-height2 rect)))

(display "Representation 1 (perimeter, height):")
(newline)
(let ((r1 (make-rect1 (make-point 0 0) (make-point 2 2))))
  (display (rect-perimeter1 r1)) (display ", ") 
  (display (rect-area1 r1)) (newline))

(display "Representation 2 (perimeter, height):")
(newline)
(let ((r2 (make-rect2 (make-point -1 -1) (make-point 1 1))))
  (display (rect-perimeter2 r2)) (display ", ") 
  (display (rect-area2 r2)) (newline))

Output:

Representation 1 (perimeter, height):
8, 4
Representation 2 (perimeter, height):
8, 4

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

Solution

First, let's check how car works:

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

So the corresponding definition of cdr will just have (lambda (p q) q) instead.

code/ex2-4.rkt

#lang sicp
(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)))
(let ((arg (cons 1 2)))
  (display (car arg))
  (newline)
  (display (cdr arg)))

Output:

1
2

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^a 3^b}$. Give the corresponding definitions of the procedures cons, car, and cdr.

Solution

code/ex2-5.rkt

#lang sicp
(define (pow n m) (if (< m 1) 1 (* n (pow n (- m 1)))))

;; Find how many powers of two the number has
;; Might be fun to optimize once I know more scheme.
(define (npowers base n)
  (define (npowers-iter product k)
    (if (= (gcd product n) product) 
      (npowers-iter (* product base) (+ k 1))
      k))
  (npowers-iter base 0))
(define (cons a b) (* (pow 2 a) (pow 3 b)))
(define (car z) (npowers 2 z))
(define (cdr z) (npowers 3 z))

(let ((arg (cons 10 13)))
  (display "2^a 3^b is: ") (display arg) (newline)
  (display "a is: ") (display (car arg)) (newline)
  (display "b is: ") (display (cdr arg)) (newline))

Output:

2^a 3^b is: 1632586752
a is: 10
b is: 13

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

Solution

How topical! The video "What is PLUS times PLUS?" just came out.

;; (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 (((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))))
;; (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
(add-1 one)
(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))))

addition:

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

Testing: Yooo it works first try, nice.

To future-me/future-readers: the idea behind church-add is to first unwrap a and b so that they're simple functions that apply f some number of times, then apply both to x.

code/ex2-6.rkt

#lang sicp

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

(define (inc a) (+ a 1))
(define (church-convert a) ((a inc) 0))
(display "zero = ") (display (church-convert zero)) (newline)
(display "one = ") (display (church-convert one)) (newline)
(display "two = ") (display (church-convert two)) (newline)
(display "one + zero = ") (display (church-convert (church-add one zero))) (newline)
(display "one + one = ") (display (church-convert (church-add one one))) (newline)
(display "one + two = ") (display (church-convert (church-add one two))) (newline)
(display "two + two = ") (display (church-convert (church-add two two))) (newline)

Output:

zero = 0
one = 1
two = 2
one + zero = 1
one + one = 2
one + two = 3
two + two = 4

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.

Solution

(define (make-interval a b) (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))

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.

Solution

Write our two intervals as $A$ and $B$. The lower bound should be

$$\mathrm{inf}_{x\in A, y\in B}(x-y)=A_{\textrm{min}}-B_{\textrm{max}}$$

The upper bound should be

$$\mathrm{sup}_{x\in A, y\in B}(x-y)=A_{\textrm{max}}-B_{\textrm{min}}$$

(define (sub-interval A B)
  (make-interval (- (lower-bound A) (upper-bound B)) 
                 (- (upper-bound A) (lower-bound B))))

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.

Solution

Addition:

$$\begin{align*} \textrm{Width}_{A+B} &= \mathrm{sup}_{x\in A, y\in B}(x+y)-\mathrm{inf}_{x\in A, y\in B}(x+y)\\ &=A_{\textrm{max}}+B_{\textrm{max}} - (A_{\textrm{min}}+B_{\textrm{min}})\\ &=\textrm{Width}_A+\textrm{Width}_B \end{align*}$$

Subtraction:

$$\begin{align*} \textrm{Width}_{A-B} &= \mathrm{sup}_{x\in A, y\in B}(x-y)-\mathrm{inf}_{x\in A, y\in B}(x-y)\\ &=A_{\textrm{max}}-B_{\textrm{min}} - (A_{\textrm{min}}-B_{\textrm{max}})\\ &=\textrm{Width}_A+\textrm{Width}_B \end{align*}$$

Counterexamples:

code/ex2-9.rkt

#lang sicp
(define (make-interval a b) (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(define (sub-interval A B)
  (make-interval (- (lower-bound A) (upper-bound B))
                 (- (upper-bound A) (lower-bound B))))
(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)))))
(define (width-interval int)
  (- (upper-bound int) (lower-bound int)))
(define (disp-interval int)
  (display "[") (display (lower-bound int)) (display ", ") 
  (display (upper-bound int)) (display "]"))
(define (disp-interval-op a b c d func character)
  (let ((i1 (make-interval a b))
        (i2 (make-interval c d)))
    (disp-interval i1) (display character) (disp-interval i2) (display " = ")
    (disp-interval (func i1 i2)) (newline)))

(display "Multiplication of two width 2 intervals result in a width 3 interval:") (newline)
(disp-interval-op -0.5 1.5 -1.5 0.5 mul-interval " * ")

(display "Multiplication of two width 2 intervals result in a width 4 interval:") (newline)
(disp-interval-op 0 2 0 2 mul-interval " * ")

(display "Division of two width 1 intervals creates a tiny interval:") (newline)
(disp-interval-op 2 3 10 11 div-interval " / ")

(display "Division of two width 1 intervals creates a huge interval:") (newline)
(disp-interval-op 2 3 0.1 1.1 div-interval " / ")

Output:

Multiplication of two width 2 intervals result in a width 3 interval:
[-0.5, 1.5] * [-1.5, 0.5] = [-2.25, 0.75]
Multiplication of two width 2 intervals result in a width 4 interval:
[0, 2] * [0, 2] = [0, 4]
Division of two width 1 intervals creates a tiny interval:
[2, 3] / [10, 11] = [0.18181818181818182, 0.30000000000000004]
Division of two width 1 intervals creates a huge interval:
[2, 3] / [0.1, 1.1] = [1.8181818181818181, 30.0]

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.

Solution

code/ex2-10.rkt

#lang sicp
(define (make-interval a b) (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))
(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 (contains? interval x)
  (and (<= (lower-bound interval) x) (<= x (upper-bound interval))))
(define (div-interval x y)
  (if (not (contains? y 0))
      (mul-interval x (make-interval (/ 1.0 (upper-bound y))
                                     (/ 1.0 (lower-bound y))))
      (error "div-interval called with interval containing zero")))
(define (disp-interval int)
  (display "[") (display (lower-bound int)) (display ", ") 
  (display (upper-bound int)) (display "]"))
(define (disp-interval-op a b c d func character)
  (let ((i1 (make-interval a b))
        (i2 (make-interval c d)))
    (disp-interval i1) (display character) (disp-interval i2) (display " = ")
    (disp-interval (func i1 i2)) (newline)))

(display "Division by an interval containing zero:") (newline)
(disp-interval-op 2 3 -1 1.1 div-interval " / ")

Output:

Division by an interval containing zero:
[2, 3] / [-1, 1.1] = 
Error (exit code 1):
div-interval called with interval containing zero
  context...:
   /home/physbuzz/sicp/src/ch2/code/ex2-10.rkt:22:0: disp-interval-op
   body of "/home/physbuzz/sicp/src/ch2/code/ex2-10.rkt"

Exercise 2.11

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

Solution

So, let's see. The goal here is to reduce the number of multiplications down from 4. We have four numbers $x_\ell,x_u,y_\ell,y_u.$ If we go case-by-case whether each number is greater than or equal to zero, we don't have sixteen cases because we also have to enforce $x_\ell\lt x_u$. I guess it's easier to list this out by cases.

case 1111: The positive case 1111 is easy:

$$x*y=[x_\ell y_\ell,x_u y_u]$$

case 1101: If all numbers are positive except $y_\ell$ (case 1101) the lower bound is $x_u y_\ell:$ $x*y=[x_u y_\ell,x_u y_u]$
case 0111: By symmetry, if all numbers are positive except $x_\ell,$ then $x*y=[x_u y_\ell,x_u y_u]$

Anyways, proceeding in this way we get the list of sixteen cases:

x_lower>=0? x_upper>=0? y_lower>=0? y_upper>=0? 
1111 - [x_lower*y_lower, x_upper*y_upper]
1110 - disallowed
1101 - [x_upper*y_lower, x_upper*y_upper]
1100 - [x_upper*y_lower, x_lower*y_upper]
1011 - disallowed
1010 - disallowed
1001 - disallowed
1000 - disallowed
0111 - [x_lower*y_upper, x_upper*y_upper]
0110 - disallowed
0101 - [min(x_lower*y_upper, x_upper*y_lower), max(x_lower*y_lower,x_upper*y_upper)]
0100 - [x_upper*y_lower, x_lower*y_lower]
0011 - [x_lower*y_upper, x_upper*y_lower]
0010 - disallowed
0001 - [x_lower*y_upper, x_lower*y_lower]
0000 - [x_upper*y_upper, x_lower*y_lower]

code/ex2-11.rkt

#lang sicp
(define (make-interval a b) (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))

(define (mul-interval-new x y)
  (define (bin bool) (if bool 1 0))
  (let ((xl (lower-bound x)) (xu (upper-bound x))
        (yl (lower-bound y)) (yu (upper-bound y)))
    (let ((switch 
            (+ (* 8 (bin (>= xl 0)))
               (* 4 (bin (>= xu 0)))
               (* 2 (bin (>= yl 0)))
               (bin (>= yu 0)))))
      (cond ((= switch 15) (make-interval (* xl yl) (* xu yu)))
            ((= switch 13) (make-interval (* xu yl) (* xu yu)))
            ((= switch 12) (make-interval (* xu yl) (* xl yu)))
            ((= switch 7)  (make-interval (* xl yu) (* xu yu)))
            ((= switch 4)  (make-interval (* xu yl) (* xl yl)))
            ((= switch 3)  (make-interval (* xl yu) (* xu yl)))
            ((= switch 1)  (make-interval (* xl yu) (* xl yl)))
            ((= switch 0)  (make-interval (* xu yu) (* xl yl)))
        ;; special comparison case
            ((= switch 5)  (make-interval (min (* xl yu) (* xu yl))
                                          (max (* xl yl) (* xu yu))))
            (else (error "invalid interval"))))))

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

;;Testing code
(define (myrandom lower upper nsteps)
  (+ lower (* (- upper lower) (/ (random nsteps) nsteps))))
(define (random-interval)
  (let ((a (myrandom -10 10 10000)) (b (myrandom -10 10 10000)))
    (if (< a b) (make-interval a b) (random-interval))))
(define (interval-equal? int1 int2)
  (and (= (lower-bound int1) (lower-bound int2))
       (= (upper-bound int1) (upper-bound int2))))
(define (test-mul-interval n)
  (if (= n 0) #t
    (let ((x (random-interval)) (y (random-interval)))
      (if (interval-equal? (mul-interval x y) (mul-interval-new x y))
        (test-mul-interval (- n 1))
        #f))))
(display "Testing new code for 10000 cases. All intervals equal?")
(newline)
(display (if (test-mul-interval 10000) "true" "false"))

Output:

Testing new code for 10000 cases. All intervals equal?
true

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.

Solution

I'm going to opt to keep my tolerances as pure fractions (no multiplication by 100 to get a pure percent). I find it easiest to first write the percent function:

(define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (width i) (/ (- (upper-bound i) (lower-bound i)) 2))
(define (percent i) (/ (width i) (center i)))

Then, (make-center-percent x p) should be defined as the interval $i$ with

$$\frac{i_\ell+i_u}{2}=x,\qquad \frac{i_u-i_\ell}{i_u+i_\ell}=p$$

Which has the solution

$$i_\ell=x-px,\qquad i_u=x+px$$

which we should have known but it's nice to write it out in full!

(define (make-percent-center x p)
    (make-interval (- x (* x p)) (+ x (* x p))))

Exercise 2.13

Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

Solution

$$\begin{align*} (a+\Delta a)(b+\Delta b)&=ab+b\Delta a+a\Delta b+\Delta a\Delta b\\ &\approx ab+b\Delta a+a\Delta b\\ &=ab\left(1+\frac{\Delta a}{a}+\frac{\Delta b}{b}\right) \end{align*}$$

So the percent tolerances add.

Exercise 2.14

Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals $A$ and $B$, and use them in computing the expressions $A / A$ and $A / B$. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see Exercise 2.12).

Solution

code/ex2-14.rkt

#lang sicp
(define (make-interval a b) (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))
(define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (width i) (/ (- (upper-bound i) (lower-bound i)) 2))
(define (percent i) (/ (width i) (center i)))
(define (make-percent-center x p)
    (make-interval (- x (* x p)) (+ x (* x p))))

(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 (contains? interval x)
  (and (<= (lower-bound interval) x) (<= x (upper-bound interval))))
(define (div-interval x y)
  (if (not (contains? y 0))
      (mul-interval x (make-interval (/ 1.0 (upper-bound y))
                                     (/ 1.0 (lower-bound y))))
      (error "div-interval called with interval containing zero")))
;; (define (disp-interval int)
;;   (display "[") (display (lower-bound int)) (display ", ") 
;;   (display (upper-bound int)) (display "]"))
(define (disp-interval int)
  (display (center int)) (display "(1 ± ") (display (percent int)) 
  (display ")"))
(define (disp-interval-op i1 i2 func character)
    (disp-interval i1) (display character) (disp-interval i2) (display " = ")
    (disp-interval (func i1 i2)) (newline))

;; (A+eps dA)/(B+eps dB) = ((A + eps dA)/B)/(1+eps dB/B)
;; =((A/B + eps dA/B) (1- eps dB/B)
;; =A/B + eps (dA/B - A/B dB/B)
;; =A/B(1+eps(dA/A - dB/B))
;; So the percent uncertainties add.
(let ((A (make-percent-center 1.0 0.05))
      (B (make-percent-center 10.0 0.1)))
  (display "Division of A/A:") (newline)
  (disp-interval-op A A div-interval " / ")

  (display "Division of A/B:") (newline)
  (disp-interval-op A B div-interval " / "))

Output:

Division of A/A:
1.0(1 ± 0.050000000000000044) / 1.0(1 ± 0.050000000000000044) = 1.0050125313283207(1 ± 0.09975062344139651)
Division of A/B:
1.0(1 ± 0.050000000000000044) / 10.0(1 ± 0.1) = 0.10151515151515152(1 ± 0.1492537313432836)

This makes sense, the percent errors add (under the small error approximation).

Exercise 2.15

Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a better program for parallel resistances than par1. Is she right? Why?

Solution

Alyssa's Conjecture: Among algebraically equivalent expressions the one that minimizes the error of the result interval is the one in which no variable that represents an uncertain number is repeated, if such a form exists.

My statement: Every operation involving two intervals of width greater than zero adds to the error, so those are the things we want to minimize.

Question: is there a expression such that making a variable occur only once adds to the total number of interval operations?

Polynomials are out. Let's count (pow A 3) as the symbol A occurring multiple times.
The only expressions we can form are binary trees, the way to minimize the number of nontrivial interval operations is to ensure each symbol only occurs once, if that's possible. If we have 4 variables and 4 nontrivial leaf nodes, we'll have 3 nontrivial interval combinations. (Evaluating nodes of the tree: Every operation takes in two intervals and returns 1, so the number of nontrivial intervals can only decrease by one)
The question now is, is minimizing the number of nontrivial interval combinations the way to go?!
"Any operation between two intervals will increase errors" - I can prove this.
"The binary tree with the smallest number of nontrivial intervals as leaf nodes minimizes the number of nontrivial interval operations." - I can also prove this
The problem is + and * increase the errors by different amounts, so if I reduce the total number of operations, but introduce a * to the wrong spot, what if this blows up the error? So my concern is really about allowed transformations on the binary tree and the interplay between + and * (or -, or /). For example in this code snippet to evaluate $A/B + C/B,$ we reduce the number of divisions, but don't reduce the error.

code/ex2-15.rkt

#lang sicp
(define (make-interval a b) (cons a b))
(define (lower-bound int) (car int))
(define (upper-bound int) (cdr int))
(define (center i) (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (width i) (/ (- (upper-bound i) (lower-bound i)) 2))
(define (percent i) (/ (width i) (center i)))
(define (make-percent-center x p)
    (make-interval (- x (* x p)) (+ x (* x p))))
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(define (sub-interval A B)
  (make-interval (- (lower-bound A) (upper-bound B))
                 (- (upper-bound A) (lower-bound B))))


(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 (contains? interval x)
  (and (<= (lower-bound interval) x) (<= x (upper-bound interval))))
(define (div-interval x y)
  (if (not (contains? y 0))
      (mul-interval x (make-interval (/ 1.0 (upper-bound y))
                                     (/ 1.0 (lower-bound y))))
      (error "div-interval called with interval containing zero")))
;; (define (disp-interval int)
;;   (display "[") (display (lower-bound int)) (display ", ") 
;;   (display (upper-bound int)) (display "]"))
(define (disp-interval int)
  (display (center int)) (display "(1 ± ") (display (percent int)) 
  (display ")"))
(define (disp-interval-op i1 i2 func character)
    (disp-interval i1) (display character) (disp-interval i2) (display " = ")
    (disp-interval (func i1 i2)) (newline))

(let ((A (make-percent-center 0.1 0.8))
      (B (make-percent-center 0.001 0.8))
      (C (make-percent-center 7.0 0.1))
      (one (make-percent-center 1.0 0)))
  (display "A = ") (disp-interval A) (newline)
  (display "B = ") (disp-interval B) (newline)
  (display "C = ") (disp-interval C) (newline)
  (display "Division of A/B+C/B:") (newline)
  (disp-interval (add-interval (div-interval A B) (div-interval C B)))
  (newline)
  (display "Division of (A+C)/B:") (newline)
  (disp-interval (div-interval (add-interval A C) B))
  (newline)
  (newline)
  (display "And, just to confirm the issue:") (newline)
  (display "Division of (AB)/(A+B):") (newline)
  (disp-interval (div-interval (mul-interval A B) (add-interval A B)))
  (newline)
  (display "Division of 1/(1/A+1/B):") (newline)
  (disp-interval (div-interval one (add-interval (div-interval one A) (div-interval one B)))))

Output:

A = 0.1(1 ± 0.8000000000000002)
B = 0.001(1 ± 0.7999999999999999)
C = 7.0(1 ± 0.10000000000000002)
Division of A/B+C/B:
21455.555555555555(1 ± 0.8363542206110824)
Division of (A+C)/B:
21455.555555555555(1 ± 0.8363542206110824)

And, just to confirm the issue:
Division of (AB)/(A+B):
0.008030803080308036(1 ± 0.9972602739726029)
Division of 1/(1/A+1/B):
0.0009900990099009901(1 ± 0.8)

I'm going to leave this problem here. It's probably true, I'm just having trouble proving it.

Exercise 2.16

Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

Solution

Consider the context of problem 2.15, where we care about the expression $ab/(a+b)$.

The gold standard is to model each number as a random variable, possibly with a joint probability distribution $P(a,b)$. Then you ask what is the probability distribution $$P\left(\frac{ab}{a+b}\right)=P\left(\frac{1}{\frac{1}{a}+\frac{1}{b}}\right)$$ This can be done through monte carlo, or bootstrap and jackknife, or through linear error propagation, there's a ton of methods.
Another simpler heuristic would be to treat our expression as a function:

;; equivalent definitions
(define (f a b) (/ (* a b) (+ a b)))
(define (f a b) (/ 1 (+ (/ 1 a) (/ 1 b))))

and then the new interval would have bounds

(let ((al (lower-bound A))
      (au (upper-bound A))
      (bl (lower-bound B))
      (bu (upper-bound B)))
  (let ((x1 (f al bl))
        (x2 (f al bu))
        (x3 (f au bl))
        (x4 (f au bu)))
    (make-interval (min x1 x2 x3 x4)
                   (max x1 x2 x3 x4))))

In many cases the result will be the smallest interval possible. But we could have pathological cases with non-monotonic functions (the extreme cases can lie in the middle of the interval instead of the endpoints; so maybe "convex" is the word I'm searching for).

So anyways this is just a discussion of the possible approaches, we're not going to actually implement all this stuff.

Directory

Section 2.1

Introduction

Meeting 03-30-2025

Exercises

Exercise 2.1

Solution

Exercise 2.2

Solution

Exercise 2.3

Solution

Exercise 2.4

Solution

Exercise 2.5

Solution

Exercise 2.6

Solution

Exercise 2.7

Solution

Exercise 2.8

Solution

Exercise 2.9

Solution

Exercise 2.10

Solution

Exercise 2.11

Solution

Exercise 2.12

Solution

Exercise 2.13

Solution

Exercise 2.14

Solution

Exercise 2.15

Solution

Exercise 2.16

Solution