# Notes and excercises from *Structure and Interpretation of Computer Programs*

The book is [available online on MIT's site](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html), there are also [recorded lectures on MIT's OCW](https://www.youtube.com/playlist?list=PLE18841CABEA24090).

I'm using the [Calysto Scheme](https://github.com/Calysto/calysto_scheme) notebooks.

```python
pip install calysto_scheme
```

## Chapter 2. Building Abstractions with Data

### `cons` vs `list`

```scheme
(list <a1> <a2> ... <an>)
```

is equivalent to

```scheme
(cons <a1>
      (cons <a2>
            (cons ...
                  (cons <an>
                        nil) ...)))
```


```scheme
;; math functions missig from Calysto Scheme

(import "math")

(define sin math.sin)
(define cos math.cos)
(define tan math.tan)
(define atan math.atan)
(define log math.log)
```


```scheme
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(define (square x) (* x x))

(define (approx x y) (< (abs (- x y)) 0.01))
```


```scheme
;; Representing rational numbers

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))
(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))
(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

(define (make-rat n d) (cons n d))

(define (numer x) (car x))

(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))
```


```scheme
(define one-half (make-rat 1 2))
(define one-third (make-rat 1 3))

(print-rat one-half)
(print-rat (add-rat one-half one-third))
(print-rat (mul-rat one-half one-third))
(print-rat (add-rat one-third one-third))
```

    
    1/2
    5/6
    1/6
    6/9

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

(print-rat (add-rat one-third one-third))


```scheme
;; For example, an alternate way to address the problem of reducing rational numbers to lowest terms is to perform
;; the reduction whenever we access the parts of a rational number, rather than when we construct it. This leads
;; to different constructor and selector procedures:

(define (make-rat n d)
  (cons n d))

(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))

(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

(define one-half (make-rat 1 2))
(define one-third (make-rat 1 3))

(print-rat one-half)
(print-rat (add-rat one-half one-third))
(print-rat (mul-rat one-half one-third))
(print-rat (add-rat one-third one-third))
```

    
    1/2
    5/6
    1/6
    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:


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


```scheme
(define (make-point x y)
  (cons x y))

(define (x-point p) (car p))

(define (y-point p) (cdr p))

(assert = (x-point (make-point 1 2)) 1)
(assert = (y-point (make-point 1 2)) 2)

(print-point (make-point 1 2))
```

    
    (1,2)


```scheme
(define (make-segment start-segment end-segment)
  (list start-segment end-segment))

(define (midpoint-segment segment)
  (define (midpoint selector)
    (/ (+
        (selector (car segment))
        (selector (cadr segment)))
       2))
  (make-point
   (midpoint x-point)
   (midpoint y-point)))

(assert = (car (midpoint-segment (make-segment (make-point 1 2) (make-point 3 0)))) 2)
(assert = (cdr (midpoint-segment (make-segment (make-point 1 2) (make-point 3 0)))) 1)
```




    ok



**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? 


```scheme
(define (rectangle l w) (cons l w))
(define (get-length rectangle) (car rectangle))
(define (get-width rectangle) (cdr rectangle))

(define (rectangle-area rectangle)
  (* (get-length rectangle)
     (get-width rectangle)))

(assert = (rectangle-area (rectangle 1 1)) 1)
(assert = (rectangle-area (rectangle 2 2)) 4)
(assert = (rectangle-area (rectangle 2 5)) 10)

(define (rectangle-perimeter rectangle)
  (* 2 (+ (get-length rectangle)
          (get-width rectangle))))

(assert = (rectangle-perimeter (rectangle 1 1)) 4)
(assert = (rectangle-perimeter (rectangle 2 2)) 8)
(assert = (rectangle-perimeter (rectangle 2 5)) 14)
```




    ok




```scheme
;; Euclidean distance between two points
(define (distance p q)
  (sqrt
   (+ (square (- (x-point p) (x-point q)))
      (square (- (y-point p) (y-point q))))))

(assert approx (distance (make-point 1 3) (make-point 4 13)) 10.44)
(assert approx (distance (make-point 4 13) (make-point 1 3)) 10.44)
```




    ok




```scheme
;;         w
;;   p1 ------- p3
;;   |          |
;; l |          | 
;;   |          | 
;;   p2 ------- p4
;;
;; p_i = (x_i, y_i)

;; Lousy way of storing it, by storing all the four points
(define (rectangle p1 p2 p3 p4) (list p1 p2 p3 p4))

(define (get-length rectangle)
  ;; |p3 - p1|
  (distance (car rectangle) (cadr rectangle)))

(define (get-width rectangle)
  ;; |p2 - p1|
  (distance (car rectangle) (caddr rectangle)))

;; (0,1) (2,1)
;; (0,0) (2,0)
(assert = (get-length (rectangle (make-point 0 1) (make-point 0 0) (make-point 2 1) (make-point 2 0))) 1)
(assert = (get-width (rectangle (make-point 0 1) (make-point 0 0) (make-point 2 1) (make-point 2 0))) 2)

;; (0,1) (1,1)
;; (0,0) (0,0)
(assert = (rectangle-area (rectangle (make-point 0 1) (make-point 0 0) (make-point 1 1) (make-point 1 0))) 1)
(assert = (rectangle-perimeter (rectangle (make-point 0 1) (make-point 0 0) (make-point 1 1) (make-point 1 0))) 4)

;; (2,4) (5,4)
;; (2,2) (5,2)
(assert = (rectangle-area (rectangle (make-point 2 4) (make-point 2 2) (make-point 5 4) (make-point 5 2))) 6)
(assert = (rectangle-perimeter (rectangle (make-point 2 4) (make-point 2 2) (make-point 5 4) (make-point 5 2))) 10)

;; Rotated:
;; (2,4) (5,7)
;; (4,2) (7,5)
(assert approx (rectangle-area (rectangle (make-point 2 4) (make-point 4 2) (make-point 5 7) (make-point 7 5))) 12)
(assert approx (rectangle-perimeter (rectangle (make-point 2 4) (make-point 4 2) (make-point 5 7) (make-point 7 5))) 14.14)
```




    ok



**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$.

```scheme
(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.)


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

(assert = (λ-car (λ-cons 1 2)) 1)
(assert = (λ-cdr (λ-cons 1 2)) 2)
```




    ok



**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`.

$$
2^a 3^b = \underbrace{2 \cdot 2 \cdot \dots \cdot 2}_{a ~\times} \cdot \underbrace{3 \cdot 3 \cdot \dots \cdot 3}_{b ~\times}
$$

so $(2^a 3^b) \,/\, 3 = 2^a 3^{b-1} $ etc.


```scheme
(define (arith-cons a b)
  (* (expt 2 a)
     (expt 3 b)))

(define (arith-car x)
  (define (iter x count)
    (if (= 0 (remainder x 2))
        (iter (/ x 2) (+ 1 count))
        count))
  (iter x 0))

(define (arith-cdr x)
  (define (iter x count)
    (if (= 0 (remainder x 3))
        (iter (/ x 3) (+ 1 count))
        count))
  (iter x 0))

(assert = (arith-car (arith-cons 0 0)) 0)
(assert = (arith-cdr (arith-cons 0 0)) 0)
(assert = (arith-car (arith-cons 1 1)) 1)
(assert = (arith-cdr (arith-cons 1 1)) 1)
(assert = (arith-car (arith-cons 5 7)) 5)
(assert = (arith-cdr (arith-cons 5 7)) 7)
(assert = (arith-car (arith-cons 3 2)) 3)
(assert = (arith-cdr (arith-cons 3 2)) 2)
(assert = (arith-car (arith-cons 3 0)) 3)
(assert = (arith-cdr (arith-cons 0 2)) 2)
```




    ok



**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

```scheme
(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 $\lambda$-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`). 


```scheme

```


```scheme
;; 2.1.4  Extended Exercise: Interval Arithmetic

(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)
  (mul-interval x 
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))
```

https://en.wikipedia.org/wiki/Interval_arithmetic#Interval_operators

$$\begin{align}
[x_1, x_2] + [y_1, y_2] &= [x_1+y_1, x_2+y_2] \\
[x_1, x_2] - [y_1, y_2] &= [x_1-y_2, x_2-y_1] \\
[x_1, x_2] \cdot [y_1, y_2] &= [\min \{x_1 y_1,x_1 y_2,x_2 y_1,x_2 y_2\}, \max\{x_1 y_1,x_1 y_2,x_2 y_1,x_2 y_2\}] \\
\frac{[x_1, x_2]}{[y_1, y_2]} &= [x_1, x_2] \cdot \frac{1}{[y_1, y_2]}
\end{align}$$

**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:


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

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


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

(assert = (lower-bound (make-interval 1 2)) 1)
(assert = (upper-bound (make-interval 1 2)) 2)
(assert = (car (add-interval (make-interval 1 2) (make-interval 3 4))) 4)
(assert = (cdr (add-interval (make-interval 1 2) (make-interval 3 4))) 6)
```




    ok



**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`.


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

(assert = (lower-bound (sub-interval (make-interval 10 20) (make-interval 1 2))) 8)
(assert = (upper-bound (sub-interval (make-interval 10 20) (make-interval 1 2))) 19)
```




    ok



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


```scheme
(define (width interval)
  (/ (- (upper-bound interval)
        (lower-bound interval))
     2))

(assert = (width (make-interval 0 10)) 5)
```




    ok



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


```scheme
(define (raises-error? expr)
  (try (begin
        (eval expr)
        #f)
       (catch 'error #t)))

(assert eq? (raises-error? '(raise "Oh no!")) #t)
(assert eq? (raises-error? '(lambda () (+ 2 2))) #f)
```




    ok




```scheme
(define (div-interval x y)
  (if (> (width y) 0)
      (mul-interval x 
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))
      (raise "Cannot divide by interval with span = 0")))

(assert eq? (raises-error? '(div-interval (make-interval 0 1) (make-interval 1 2))) #f)
(assert eq? (raises-error? '(div-interval (make-interval 0 1) (make-interval 1 1))) #t)
```




    ok



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


```scheme
;; small+ * small+ = small+
;; large+ * large+ = large+
;; small+ * large- = moderate-
;; large+ * small- = moderate-
;; large+ * small- = moderate-
;; small+ * large- = moderate-
;; small- * small- = small-
;; large- * large- = large-


(define (mul-interval-light x y)
    (let ((lx (lower-bound x))
          (ux (upper-bound x))
          (ly (lower-bound y))
          (uy (upper-bound y)))
      (cond
       ((and (> lx 0) (> ux 0) (> ly 0) (> uy 0))
        (make-interval (* (min lx ux) (min ly uy))
                       (* (max lx ux) (max ly uy))))
       
       
       )))
```

After debugging her program, Alyssa shows it to a potential user, who complains that her program solves the wrong problem. He wants a program that can deal with numbers represented as a center value and an additive tolerance; for example, he wants to work with intervals such as $3.5\pm 0.15$ rather than $[3.35, 3.65]$. Alyssa returns to her desk and fixes this problem by supplying an alternate constructor and alternate selectors:


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

Unfortunately, most of Alyssa's users are engineers. Real engineering situations usually involve measurements with only a small uncertainty, measured as the ratio of the width of the interval to the midpoint of the interval. Engineers usually specify percentage tolerances on the parameters of devices, as in the resistor specifications given earlier.

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


```scheme
(define (make-center-percent c p)
  (let ((w (* c p)))
      (make-interval (- c w) (+ c w))))

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

(assert = (width (make-center-percent 10 0.1)) 1)
(assert = (lower-bound (make-center-percent 10 0.1)) 9)
(assert = (upper-bound (make-center-percent 10 0.1)) 11)

(assert = (lower-bound (make-center-width 10 1)) (lower-bound (make-center-percent 10 0.1)))
(assert = (lower-bound (make-center-width 10 1)) (lower-bound (make-center-percent 10 0.1)))
(assert = (upper-bound (make-center-width 1 0.1)) (upper-bound (make-center-percent 1 0.1)))
(assert = (upper-bound (make-center-width 1 0.1)) (upper-bound (make-center-percent 1 0.1)))
```




    ok



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


```scheme

```

After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways:

$$
\frac{R_1 R_2}{R_1 + R_2}
$$

and

$$
\frac{1}{1/R_1 + 1/R_2}
$$

He has written the following two programs, each of which computes the parallel-resistors formula differently:


```scheme
(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))

(define (par2 r1 r2)
  (let ((one (make-interval 1 1))) 
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))
```

Lem complains that Alyssa's program gives different answers for the two ways of computing. This is a serious complaint.

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


```scheme
(print (par1 (make-center-percent 10 0.1) (make-center-percent 10 0.1)))
(print (par2 (make-center-percent 10 0.1) (make-center-percent 10 0.1)))
(print (par1 (make-center-percent 10 0.1) (make-center-width 1 0.1)))
(print (par2 (make-center-percent 10 0.1) (make-center-width 1 0.1)))
(print (par1 (make-center-percent 10 0.5) (make-center-width 1 0.5)))
(print (par2 (make-center-percent 10 0.5) (make-center-width 1 0.5)))
```

    (3.681818181818182 . 6.722222222222221)
    (4.5 . 5.5)
    (0.6694214876033058 . 1.2222222222222223)
    (0.8181818181818181 . 1.0)
    (0.15151515151515152 . 4.090909090909091)
    (0.45454545454545453 . 1.3636363636363638)


**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?


```scheme

```

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


```scheme

```

4431610dae8da1b8c01092c69de6db4a42fb185f
ipynb
Jupyter Notebook
Scheme/SICP-Ch2.ipynb
twolodzko/Learning
e5af2bdf6f65648c3c159343e14d63c157384009
MIT
Scheme/SICP-Ch2.ipynb
twolodzko/Learning
e5af2bdf6f65648c3c159343e14d63c157384009
MIT
Scheme/SICP-Ch2.ipynb
twolodzko/Learning
e5af2bdf6f65648c3c159343e14d63c157384009
MIT
Qwen/Qwen-72B
1. YES
2. YES