SICP Study

1.3 Formulating Abstractions with Higher-Order Procedures⁠ 

(define (cube x) (* x x x))

1.3.1 Procedures as Arguments⁠

Mathematicians long ago created an abstraction for summations:

∑n=abf(n)=f(a)+⋯+f(b).\sum_{n=a}^b f(n) = f(a) + \dots + f(b).

We can do the same in Scheme using a higher-order procedure:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (inc n) (+ n 1))
(define (sum-cubes a b) (sum cube a inc b))
(sum-cubes 1 10) => 3025

(define (identity x) x)
(define (sum-integers a b) (sum identity a inc b))
(sum-integers 1 10) => 55

(define (pi-sum a b)
  (define (pi-term x) (/ 1.0 (* x (+ x 2))))
  (define (pi-next x) (+ x 4))
  (sum pi-term a pi-next b))
(* 8 (pi-sum 1 1000)) ~> 3.139592655589783

The definite integral of a function ff between limits aa and bb can be approximated numerically using the formula

∫abf≈[f(a+dx2)+f(a+dx+dx2)+f(a+2dx+dx2)+⋯ ]dx\int_a^bf\approx\left[ f\left(a+\frac{dx}{2}\right) + f\left(a+dx+\frac{dx}{2}\right) + f\left(a+2dx+\frac{dx}{2}\right) + \cdots \right]dx

for small values of dx.dx\htmlClass{math-punctuation}{\text{.}} We can express this directly as a procedure:

(define (integral f a b dx)
  (define (add-dx x)
    (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(integral cube 0 1 0.01) ~> .24998750000000042
(integral cube 0 1 0.001) ~> .249999875000001

Exercise 1.29⁠

Simpson’s rule provides a more accurate method of numerical integration:

∫abf≈h3[y0+4y1+2y2+4y3+2y4+⋯+2yn−2+4yn−1+yn]dxwhereh=b−anandyk=f(a+kh).\begin{gathered} \int_a^bf\approx\frac{h}{3}\left[ y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + \cdots + 2y_{n-2} + 4y_{n-1} + y_n \right]dx \\ \text{where}\quad h = \frac{b-a}{n} \quad\text{and}\quad y_k = f(a+kh). \end{gathered}

The even integer nn controls the accuracy of the approximation.

(define (simpson f a b n)
  (let ((h (/ (- b a) n)))
    (define (term k)
      (* (f (+ a (* k h)))
         (if (or (= k 0) (= k n))
             1
             (+ 2 (* 2 (remainder k 2))))))
    (* h 1/3 (sum term 0.0 inc n))))

Simpson’s rule gives an exact answer for ∫01x3dx\int_0^1x^3dx when n=2:n=2\htmlClass{math-punctuation}{\text{:}}

(simpson cube 0 1 2) => 0.25

Exercise 1.30⁠ 

(define (sum term a next b)
  (define (iter a acc)
    (if (> a b)
        acc
        (iter (next a) (+ acc (term a)))))
  (iter a 0))

Exercise 1.31⁠

  1. Recursive:

    (define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

  2. Iterative:

    (define (product term a next b)
  (define (iter a acc)
    (if (> a b)
        acc
        (iter (next a) (* acc (term a)))))
  (iter a 1))

Calculating factorials and approximating π\pi using product:

(define (factorial n)
  (product identity 1 inc n))

(factorial 5) => 120
(factorial 7) => 5040

(define (approx-pi n)
  (define (term k)
    (let ((r (remainder k 2)))
      (/ (+ k 2 (- r))
         (+ k 1 r))))
  (* 4 (product term 1.0 inc n)))

(approx-pi 00010) ~> 3.2751010413348065
(approx-pi 00100) ~> 3.1570301764551654
(approx-pi 01000) ~> 3.1431607055322552
(approx-pi 10000) ~> 3.1417497057380084

Exercise 1.32⁠

  1. Recursive:

    (define (accumulate combine id term a next b)
  (if (> a b)
      id
      (combine (term a)
               (accumulate combine id term (next a) next b))))

  2. Iterative:

    (define (accumulate combine id term a next b)
  (define (iter a acc)
    (if (> a b)
        acc
        (iter (next a) (combine (term a) acc))))
  (iter a id))

Implementing sum and product in terms of accumulate:

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (product term a next b)
  (accumulate * 1 term a next b))

(sum identity 1 inc 10) => 55
(product identity 1 inc 10) => 3628800

Exercise 1.33⁠ 

(define (filtered-accumulate combine pred? id term a next b)
  (define (iter a acc)
    (cond ((> a b) acc)
          ((pred? a)
           (iter (next a) (combine (term a) acc)))
          (else (iter (next a) acc))))
  (iter a id))

  1. Sum of squares of primes in the interval from a to b:

    (define (sum-squared-primes a b)
  (filtered-accumulate + prime? 0 square a inc b))

(sum-squared-primes 10 15) => 290

  2. Product of positive integers below n relatively prime to n:

    (define (product-rel-prime n)
  (define (rel-prime? i)
    (= (gcd i n) 1))
  (filtered-accumulate * rel-prime? 1 identity 1 inc (- n 1)))

(product-rel-prime 10) => (* 3 7 9)

1.3.2 Constructing Procedures Using Lambda⁠ 

((lambda (x y z) (+ x y (square z))) 1 2 3) => 12

Exercise 1.34⁠ 

(define (f g) (g 2))

(f square) => 4
(f (lambda (z) (* z (+ z 1)))) => 6

If we try evaluating the combination (f f), we get the process (f f) => (f 2) => (2 2). This fails because 2 is not a procedure:

(f f) =!> "2"

1.3.3 Procedures as General Methods⁠

1.3.3.1 Finding roots of equations by the half-interval method 

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

(define tolerance 0.001)
(define (close-enough? x y) (< (abs (- x y)) tolerance))

Half interval method: Θ(log⁡(∣a−b∣/t))Θ(\log(\abs{a-b}/t)) time where tt is tolerance.

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error 'half-interval-method
                  "values are not of opposite sign"
                  a b)))))

(half-interval-method sin 2.0 4.0)
~> 3.14111328125
(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3)) 1.0 2.0)
~> 1.89306640625
(half-interval-method cos -1 1)
=!> "values are not of opposite sign: -1 1"

1.3.3.2 Finding fixed points of functions 

(define tolerance 0.00001)
(define (close-enough? x y) (< (abs (- x y)) tolerance))

(define (fixed-point f first-guess)
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point cos 1.0) ~> 0.7390822985224023

Without average damping, it does not converge:

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))

(sqrt 2) =>...

With average damping, it converges:

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y))) 1.0))

(sqrt 2) ~> 1.4142135623746899

Exercise 1.35⁠

Theorem. The golden ratio φ\varphi is a fixed point of the transformation x↦1+1/x.x\mapsto 1+1/x\htmlClass{math-punctuation}{\text{.}}

Proof. We will show that for any x>1x>1 and y=1+1/x,y=1+1/x\htmlClass{math-punctuation}{\text{,}} we have ∣y−φ∣<∣x−φ∣,\abs{y-\varphi}<\abs{x-\varphi}\htmlClass{math-punctuation}{\text{,}} meaning each iteration brings the value closer to φ.\varphi\htmlClass{math-punctuation}{\text{.}} Recall from Exercise 1.13 the golden ratio equation φ+1=φ2,\varphi+1=\varphi^2\htmlClass{math-punctuation}{\text{,}} or equivalently φ=1+1/φ:\varphi=1+1/\varphi\htmlClass{math-punctuation}{\text{:}}

∣y−φ∣=∣1+1x−φ∣=∣x+1−φxx∣=∣x+1−(1+1/φ)xx∣since φ=1+1/φ=∣φ−xxφ∣=∣x−φ∣∣xφ∣.\begin{aligned} \abs{y-\varphi} &= \abs{1+\frac{1}{x}-\varphi} \\ &= \abs{\frac{x+1-\varphi x}{x}} \\ &= \abs{\frac{x+1-(1+1/\varphi)x}{x}} & \text{since $\varphi=1+1/\varphi$} \\ &= \abs{\frac{\varphi-x}{x\varphi}} \\ &= \frac{\abs{x-\varphi}}{\abs{x\varphi}}. \end{aligned}

Since x>1x>1 and φ>1,\varphi>1\htmlClass{math-punctuation}{\text{,}} we have ∣xφ∣>1,\abs{x\varphi}>1\htmlClass{math-punctuation}{\text{,}} hence ∣y−φ∣<∣x−φ∣\abs{y-\varphi}<\abs{x-\varphi} as required. ■\blacksquare

(define golden-ratio (/ (+ 1 (sqrt 5)) 2))

golden-ratio
~> 1.6180339887498950
(fixed-point (lambda (x) (+ 1 (/ x))) 1.0)
~> 1.6180327868852458

Exercise 1.36⁠ 

(define (fixed-point-verbose f first-guess)
  (define (try guess)
    (let ((next (f guess)))
      (display next)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (f x) (/ (log 1000) (log x)))

Without average damping, it takes 28 approximations.

(hide-output (fixed-point-verbose f 5)) ~> 4.555539314360711
(string-count #\newline (capture-output (fixed-point-verbose f 5))) => 28

With average damping, it takes only 8 approximations.

(define (f-damped x) (average x (f x)))
(hide-output (fixed-point-verbose f-damped 5)) ~> 4.5555361005218895
(string-count #\newline (capture-output (fixed-point-verbose f-damped 5))) => 8

Exercise 1.37⁠

  1. Recursive process:

    (define (cont-frac n d k)
  (define (helper i)
    (if (= i k)
        0
        (/ (n i)
           (+ (d i) (helper (+ i 1))))))
  (helper 1))

  2. Iterative process:

    (define (cont-frac n d k)
  (define (iter i acc)
    (if (zero? i)
        acc
        (iter (- i 1) (/ (n i)
                         (+ (d i) acc)))))
  (iter k 0))

Approximating the inverse golden ratio using cont-frac:

(define (always-one i) 1.0)
(define (approx-igr k) (cont-frac always-one always-one k))

When k=11,k = 11\htmlClass{math-punctuation}{\text{,}} the value is accurate to 4 decimal places:

(approx-igr 01) ~> 1.0
(approx-igr 02) ~> 0.5
(approx-igr 03) ~> 0.6666666666666666
(approx-igr 04) ~> 0.6000000000000001
(approx-igr 05) ~> 0.625
(approx-igr 06) ~> 0.6153846153846154
(approx-igr 07) ~> 0.6190476190476191
(approx-igr 08) ~> 0.6176470588235294
(approx-igr 09) ~> 0.6181818181818182
(approx-igr 10) ~> 0.6179775280898876
(approx-igr 11) ~> 0.6180555555555556

(define (round4 x) (* 1e-4 (truncate (* 1e4 x))))
(round4 (approx-igr 11)) ~> (round4 (/ golden-ratio))

Exercise 1.38⁠ 

(define (approx-e k)
  (define (d i)
    (if (zero? (remainder (+ i 1) 3))
        (* 2/3 (+ i 1))
        1))
  (+ 2 (cont-frac always-one d k)))

(approx-e 1) ~> 3.0
(approx-e 2) ~> 2.6666666666666665
(approx-e 3) ~> 2.75
(approx-e 4) ~> 2.7142857142857144
(approx-e 5) ~> 2.71875
(approx-e 1000) ~> 2.7182818284590455

Exercise 1.39⁠ 

(define (tan-cf x k)
  (cont-frac
   (lambda (i) (if (= i 1) x (- (square x))))
   (lambda (i) (- (* i 2) 1))
   k))

(define quarter-pi (atan 1))

(tan-cf quarter-pi 1) ~> 0.7853981633974483
(tan-cf quarter-pi 2) ~> 0.9886892399342050
(tan-cf quarter-pi 3) ~> 0.9997876809149684
(tan-cf quarter-pi 4) ~> 0.9999978684156948
(tan-cf quarter-pi 5) ~> 0.9999999865263550
(tan quarter-pi) ~> 1

1.3.4 Procedures as Returned Values⁠ 

(define (average-damp f)
  (lambda (x) (average x (f x))))

((average-damp square) 10) => 55

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

(define (cbrt x)
  (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))

1.3.4.1 Newton’s method 

(define dx 0.00001)
(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

(define (cube x) (* x x x))
((deriv cube) 5) ~> 75.00014999664018

(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x)) 1.0))

1.3.4.2 Abstractions and first-class procedures 

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (/ x y)) average-damp 1.0))

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (- (square y) x)) newton-transform 1.0))

Exercise 1.40⁠ 

(define (cubic a b c)
  (lambda (x)
    (let ((xx (square x)))
      (+ (* x xx)
         (* a xx)
         (* b x)
         c))))

(newtons-method (cubic a b c) 1.0) approximates a zero of x3+ax2+bx+c:x^3+ax^2+bx+c\htmlClass{math-punctuation}{\text{:}}

(define f (cubic -3 1 1))
(f (newtons-method f 1.0)) ~> 0

Exercise 1.41⁠ 

(define (double f)
  (lambda (x)
    (f (f x))))

(((double (double double)) inc) 5)
=> (((double (lambda (f) (double (double f)))) inc) 5)
=> (((lambda (f) (double (double (double (double f))))) inc) 5)
=> ((double (double (double (double inc)))) 5)
=> ((double (double (double (lambda (x) (inc (inc x)))))) 5)
=> ((double (double (lambda (x) (inc (inc (inc (inc x))))))) 5)
=> ((double (lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc x)))))))))) 5)
=> ((lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc
      (inc (inc (inc (inc x))))))))))))))))) 5)
=> (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc
     (inc 5))))))))))))))))
=> 21

Exercise 1.42⁠ 

(define (compose f g)
  (lambda (x)
    (f (g x))))

((compose square inc) 6) => 49

Exercise 1.43⁠ 

(define (repeated f n)
  (if (= n 1)
      f
      (compose (repeated f (- n 1)) f)))

((repeated square 2) 5) => 625

Exercise 1.44⁠ 

(define dx 0.1)
(define (smooth f)
  (lambda (x)
    (/ (+ (f (- x dx))
          (f x)
          (f (+ x dx)))
       3)))

((smooth square) 2) ~> 4.006666666666667
(((repeated smooth 5) square) 2) ~> 4.033333333333333

Exercise 1.45⁠

We need to average-damp ⌊log⁡2n⌋\lfloor\log_2n\rfloor times.

(define (nth-root x n)
  (fixed-point
   ((repeated average-damp
              (floor (/ (log n) (log 2))))
    (lambda (y) (/ x (expt y (- n 1)))))
   1.0))

(nth-root 4 2) ~> 2.000000000000002
(nth-root 256 8) ~> 2.0000000000039666
(nth-root 1048576 20) ~> 1.999999063225966

Exercise 1.46⁠ 

(define (iterative-improve good-enough? improve)
  (define (iter guess)
    (if (good-enough? guess)
        guess
        (iter (improve guess))))
  iter)

(define (sqrt x)
  ((iterative-improve
    (lambda (guess)
      (< (abs (- (square guess) x)) tolerance))
    (lambda (guess)
      (average guess (/ x guess))))
   1.0))

(sqrt 2) ~> 1.4142156862745097

(define (fixed-point f first-guess)
  ((iterative-improve
    (lambda (guess)
      (< (abs (- guess (f guess))) tolerance))
    f)
   first-guess))

This is slightly different from the original fixed-point because it returns guess when it’s good enough, not next (so the original always does one more improvement).

(fixed-point cos 1.0) ~> 0.7390893414033928