adrianwong programmer · retired coal miner

SICP section 1.3 - formulating abstractions with higher-order procedures

Selected exercises

Exercise 1.32

The generalised form of sum and product can be defined (recursively) as follows:

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))

Redefining sum and product using 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))

The iterative version of accumulate uses an internal procedure with two state variables - one tracks the value of \(a\); the other accumulates the result, which is returned when the terminating condition \(a > b\) is met.

(define (accumulate-iter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

Exercise 1.33

filtered-accumulate is a generalised version of accumulate that only combines terms that satisfy a given condition. Its implementation is similar to accumulate, with an added conditional.

(define (filtered-accumulate combiner null-value term a next b filter)
  (define (next-fa)
    (filtered-accumulate combiner null-value term (next a) next b filter))
  (if (> a b)
      null-value
      (if (filter a)
          (combiner (term a)
                    (next-fa))
          (next-fa))))

Using filtered-accumulate to define a procedure that computes the sum of the squares of prime numbers:

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

…and a procedure that computes the product of integers less than \(n\) that are relatively prime to \(n\):

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

(define (identity n) n)

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

Exercise 1.34

Attempting to evaluate (f f) produces the following error:

mit-scheme : The object 2 is not applicable.

dr-racket  : application: not a procedure;
             expected a procedure that can be applied to arguments
             given: 2
             arguments...:

We can use the substitution model to get a clearer picture of the error:

(define (f g) (g 2))

(f f)
(f 2)
(2 2)

The second invocation of f attempts to apply \(2\), which is not a procedure, to \(2\). No bueno.

Exercise 1.37

For this exercise, I found that rewriting the k-term finite continued fraction as a single line helped me see more clearly how to implement it as a recursive process:

$$f = N_1 / (D_1 + (N_2 / (D_2 + (N_3 / (D_3 + (... + (N_k / D_k)))))))$$
(define (cont-frac n d k)
  (define (frac x)
    (if (= x k)
        (/ (n x) (d x))
        (/ (n x) (+ (d x) (frac (+ x 1))))))
  (frac 1))

To obtain an approximation of \(1/φ\) accurate to 4 decimal places, \(k = 10\).

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           10)

The iterative version of cont-frac decrements a counter \(x\) that begins with \(k\), accumulates the result in \(acc\), and returns the result when \(x = 0\):

(define (cont-frac-iter n d k)
  (define (frac x acc)
    (if (= x 0)
        acc
        (frac (- x 1) (/ (n k) (+ (d k) acc)))))
  (frac k 0))

Exercise 1.38

For this fraction, we know that all values of \(N_i\) are \(1\). \(D_i\) however, is slightly less straightforward. The (convoluted) pattern I derived from the \(D_i\) series is \(2(i + 1)/3\) if \((i + 1) \bmod 3 = 0\), for all \(i > 1\).

(define (d i)
  (cond ((= i 1) 1)
        ((not (= (remainder (+ i 1) 3) 0)) 1)
        (else (/ (* 2 (+ i 1)) 3))))

(+ (cont-frac (lambda (i) 1.0)
              d
              10)
   2)

Exercise 1.39

Fairly obvious patterns in both series: \(N_i = -x^2\) for \(i > 1\), and \(D_i = 2i - 1\).

(define (tan-cf x k)
  (define (n k) (if (= k 1) x (- (square x))))
  (define (d k) (- (* 2.0 k) 1))
  (cont-frac n d k))

Exercise 1.41

double can be defined as follows:

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

Applying the substitution model shows us that the procedure makes \(2^4\) inc calls, which gives us the answer \(5 + 16 = 21\).

(((double (double double)) inc) 5)
(((double (lambda (x) (double (double x)))) inc) 5)
(((lambda (x) (double (double (double (double x))))) inc) 5)
((double (double (double (double inc)))) 5)
((double (double (double (lambda (x) (inc (inc x)))))) 5)
... ; Expands to 16 `inc` calls
21

Exercise 1.42

Procedure composition!

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

Exercise 1.43

Using compose from the previous exercise:

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

Exercise 1.44

…and using repeated from the previous exercise:

(define dx 0.00001)

(define (smooth f)
  (lambda (x) (/ (+ (f (- x dx))
                    (f x)
                    (f (+ x dx)))
                 3.0)))

(define (n-fold-smooth f n x)
  ((repeated (smooth f) n) x))

Exercise 1.45

Analysis:

Root | Damps
   2 |     1
   3 |     1
   4 |     2
   5 |     2
   6 |     2
   7 |     2
   8 |     3
   9 |     3
  10 |     3
  11 |     3
  12 |     3
  13 |     3
  14 |     3
  15 |     3
  16 |     4

From this table, we can determine that \(average\_damps = log_2 (root)\), rounded down to the nearest integer.

Scheme does not have a log procedure that allows us to specify a base. To get around this, we can use the log change-of-base formula: \(log_b n = log_a n / log_a b\).

(define (average x y) (/ (+ x y) 2.0))

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

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

(define (log-b2 n)
  (/ (log n) (log 2)))

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

Exercise 1.46

As specified in the exercise, the procedure that iterative-improve should return is one that keeps improving the guess until it is good enough, indicating that it needs to be a procedure that repeatedly calls itself.

For a procedure to call itself, it needs a name - which is why we define an internal procedure and return it. If there is a way to solve this exercise using a lambda, I have not figured out how.

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

Using iterative-improve to redefine sqrt:

(define (average x y) (/ (+ x y) 2))

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

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

…and fixed-point:

; Fixed point
(define tolerance 0.00001)

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