Chapter 1 of Structure and Interpretation of Compupter Programs.

1.1 The elements of programming

1.1.1 Expressions

It may be somewhat confusing at first because it departs significantly from the customary mathematical convention. Prefix notation has several advantages, however.

  • It can accommodate procedures that may take arbitrary number of arguments, as in the following examples:

    (+ 35 21 12)
(* 23 43 12)

    No ambiguity can arise.

  • It extends in a straightforward way to allow combinations to be nested.

1.1.2 Naming and environment

A critical aspect of a programming language is the means it provides for …

Here are further examples of the use of define:

(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))

Name-object can be created incrementally in successive interactions. This feature encourages the incremental development and testing of programs.

1.1.3 Evaluating combinations

1.1.4 Compound procedures

1.1.5 The substitution model for procedure application

  • normal-order evaluation: fully expand and then reduce
  • applicative-order evaluation: evaluate the arguments and then apply

1.1.6 Coditional Expressions and predicates

Exercise 1.5

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

(test 0 (p))

If the interpreter uses applicative-order, the last call will lead to an infinite recusion because the second parameter will always be evaluated. If the interpreter uses normal-order the last call will just return 0.

1.1.7 Example: square roots by Newton’s method

Newton’s method describes the way to find the root of a function \(f(x)\), i.e., such a \(x\) such that \(f(x) = 0\).

We can derive the Newton’s method as the following:

\[\begin{align} f(x) &\approx f(x_0) + f'(x_0)(x - x_0) = 0\quad \text{(Taylor expansion)} \\ &\Rightarrow x = x_0 - \frac{f(x_0)}{f'(x_0)} \end{align}\]

If we want to find the square root of \(z\), i.e., \(x^2 = z\) we would have \(f(x) = x^2 -z\), assuming we have an initial guess \(x_0\) then according to the above drivation we can get the next better value as

\[x = x_0 - \frac{x_0^2 - z}{2x_0} = \frac{x_0 + \frac{z}{x_0}}{2}.\]

If the change \(\frac{x_0^2 - z}{2x_0} = \frac{x_0 - z/x_0}{2}\) is very small we can terminate the iteration process.

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

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (- guess (/ x guess))) 0.00001))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

Excercise 1.6

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

At this time new-if is a function so every time we call it we need to evaluate all its three parameters, which may lead to an infinite recusion because the third parameters will always be evaluted.

Excercise 1.7

Terminating the iteration process when the change \(\frac{x_0^2 - z}{2x_0} = \frac{x_0 - z/x_0}{2}\) is small enough.

(define (good-enough? guess x)
  (< (abs (- guess (/ x guess))) 0.00001))

1.1.8 Procedure as Black-Box abstractions

(define (my-sqrt x)
  (define (improve guess)
    (average guess (/ x guess)))
  (define (good-enough? guess)
    (< (abs (- guess (/ x guess))) 0.00001))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess)
                   x)))
  (sqrt-iter 1.0))

1.2 Procedures and the process they generate

1.2.1 Linear recursion and iteration

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))
  • Recursive process. The substitution model reveals a shape of expansion followed by contraction. The expansion occurs as the process builds up a chain of deferred operations. The contraction occurs as the operations are actually performed.
  • Iteration process. Iteration process in Lisp is characterized by recursive procedure. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process evolves.

Exercise 1.9

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

The first process is a recursive process as it involves the deferred operation inc, while the second process is an iterative process since at any give time its state can be summarized by the variables a, b.

Exercise 1.10

Ackermann’s function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

(A 0 n); 2n
(A 1 n); 2^n
(A 2 n); 2^2^2...^2

1.2.2 Tree Recursive

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Let the number of leaves of Fib(n) be L-Fib(n) then we can conclude that L-Fib(n) = L-Fib(n-1) + L-Fib(n-2) as well as L-Fib(1) = L-Fib(0) = 1, which implies L-Fib(n) = Fib(n+1).

Fib(n) is the closest integer to \(\phi^n / \sqrt{5}\) where \(\phi = (1 + \sqrt{5})/2\).

\[\phi^2 = \phi + 1\]

The space required grows linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation, i.e., the space required is proportional to the maximum depth of the tree.

Iterative process, let \(a, b = 1, 1\) then repeatedly apply the simultaneous transformations

\[\begin{align} & a \leftarrow a+ b \\ & b \leftarrow a \end{align}\] 
(define (fib n)
  (define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ b a) a (- count 1))))
  (fib-iter 1 0 n))

Counting Change

The number of ways to change amount \(a\) using \(n\) kinds of coins equals

  • the number of ways to change amount \(a\) using all but the first kind of coins, plus
  • the number of ways to change amount \(a-d\) using all \(n\) kinds of coins, where \(d\) is the denomination of the first kind of coin.

Recursively reducing the problem into smaller ones:

  • If \(a\) is exactly 0, we should count that as 1 way to make change.
  • If \(a\) is less than 0, we should count that as 0 way to make change.
  • If \(n\) is 0, we should count that as 0 way to make change.
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (count-change amount)
  (cc amount 5))

Exercise 1.11

\[f(n) = \begin{cases} n, \quad n < 3\\ f(n-1) + 2f(n-2) + 3f(n-3), \quad n \geq 3 \end{cases}\] 
;; recursive process
(define (f n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1))
                 (* 2 (f (- n 2)))
                 (* 3 (f (- n 3)))))))

;; iterative process
(define (f-iter n)
  (define (iter a b c counter)
    (cond ((= counter 0) a)
          (else (iter (+ a (* 2 b) (* 3 c))
                      a
                      b
                      (- counter 1)))))
  (cond ((< n 3) n)
        ((iter 2 1 0 (- n 2)))))

Exercise 1.12

(tri-num n m) computes the m-th element in n row.

(define (tri-num n m)
  (cond ((or (= n 1) (= m 1) (= m n)) 1)
        (else (+ (tri-num (- n 1) (- m 1))
                 (tri-num (- n 1) m)))))

Exercise 1.13

1.2.3 Orders of Growth

Exercise 1.1.5

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

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

a. Three times.

b. Both the space and time complexity are \(O(\log(a))\).

1.2.4 Exponentiation

\[\begin{align} b^n = (b^{n/2})^2 \quad &\text{if $n$ is even} \\ b^n = b\cdot b^{n-1} \quad &\text{if $n$ is odd} \end{align}\] 
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

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

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

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

Exercise 1.16

(define (fast-expt-iter b n)
  (define (iter a base counter)
    (cond ((= counter 0) a)
          ((even? counter) (iter a
                                 (* base base)
                                 (/ counter 2)))
          (else (iter (* a base)
                      base
                      (- counter 1)))))
  (iter 1 b n))

a absorbs base into it only when counter is odd otherwise raising base.

Exercise 1.19

\(T_{pq}\) transforms the pair \((a, b)\) according to \(a \leftarrow bq + aq + ap\) and \(b \leftarrow bp + aq\).

Applying \(T_{pq}\) and get

\[\begin{align} a_1 &\leftarrow b_0 q + a_0 q + a_0 p \\ b_1 &\leftarrow b_0 p + a_0 q \end{align}\]

Applying \(T_{pq}\) again and get

\[\begin{align} a_2 &\leftarrow b_0 (q^2 + 2pq) + a_0 (q^2 + 2pq) + a_0 (p^2 + q^2) \\ b_2 &\leftarrow b_0 (p^2 + q^2) + a_0 (q^2 + 2pq) \end{align}\]

which equals to applying the transformation \(T_{p'q'}\) of the same form with \(p' = p^2 + q^2\) and \(q' = q^2 + 2pq\).

(define (fast-fib n)
  (fast-fib-iter 1 0 0 1 n))

(define (fast-fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fast-fib-iter a
                        b
                        (+ (* p p) (* q q))
                        (+ (* q q) (* 2 p q))
                        (/ count 2)))
        (else (fast-fib-iter (+ (* b q) (* a q) (* a p))
                             (+ (* b p) (* a q))
                             p
                             q
                             (- count 1)))))

1.2.5 Greatest Common Divisors

The idea of the algorithm is based on the observation, if \(r\) is the remainder when \(a\) is divided by \(b\), then the common divisors of \(a\) and \(b\) are precisely the same as the common divisors of \(b\) and \(r\).

\[a = k \cdot b + r \Rightarrow \text{GCD}(a, b) = \text{GCD}(b, r)\] 
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

If the Euclid’s Algorithm requires \(k\) steps to compute the GCD of some pair, then the smaller number in the pair must be greater than or equal to the \(k\)th Fibonacci number.

Exercise 1.20

When using the normal-order evaluation rule, in the \(i\)th time calling gcd the depth of remainder will be \(i\) which looks like (remainder 6 (remainder 40 (remainder 206 40))). If the entire process requires \(k\) steps, then the total number of remainder operations is \(\sum_{i=1}^k i = \Theta(k^2)\).

When using the applicative-order evaluation rule, the remainder operations required is just \(\Theta(k)\).

1.2.6 Example: Testing for Primality

Searching for divisors

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond [(> (square test-divisor) n) n]
        [(divides? test-divisor n) test-divisor]
        [else (find-divisor n (+ test-divisor 1))]))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

The Fermat test

If \(n\) is a prime number and \(a\) is any positive number less than \(n\), then \(a^n \equiv a\ (\text{mod}\ n)\).

(define (expmod base exp m)
  (cond [(= exp 0) 1]
        [(even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m)]
        [else
         (remainder (* base (expmod base (- exp 1) m))
                    m)]))

(define (expmod-iter base exp m)
  (define (iter a b counter)
    (cond [(= counter 0) a]
          [(even? counter)
           (iter a (square b) (/ counter 2))]
          [else
           (iter (remainder (* a b) m) b (- counter 1))]))
    (iter 1 base exp))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond [(= times 0) #t]
        [(fermat-test n) (fast-prime? n (- times 1))]
        [else #f]))

Exercise 1.25

Integer overflows.

Exercise 1.26

At each step when exp is even, the procedure grows out two branches from the current node. And the tree corresponding to the first call will have depth \(\log(n)\), thus the number of leaves in the tree is around \(2^{\log(n)} = n\).

1.3 Formulating abstractions with higher-order procedure

1.3.1 Procedures as Arguments

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

(define (sum-cubes a b)
  (sum cube a inc b))

(define (sum-integers a b)
  (sum (lambda (x) x) a inc b))

(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))
\[\int_a^b f = \left[ f(a + dx/2) + f(a +dx + dx/2) + f(a + 2dx + dx/2) + \ldots \right] dx\]

Exercise 1.29

Simpson’s Rule

\(\int_a^b f = \frac{h}{3}[y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + \ldots + 2y_{n-1} + 4y_{n-1} + y_n]\) where \(h = (b-a)/n\), for some even integer \(n\), and \(y_k = f(a+kh)\).

(define (simpson-integral f a b n)
  (define (simpson-sum acc f v k h)
    (cond [(= k (+ n 1)) acc]
          [(or (= k 0) (= k n))
           (simpson-sum (+ acc (f v))
                        f
                        (+ v h)
                        (+ k 1)
                        h)]
          [(even? k)
           (simpson-sum (+ acc (* 2 (f v)))
                        f
                        (+ v h)
                        (+ k 1)
                        h)]
          [else
           (simpson-sum (+ acc (* 4 (f v)))
                        f
                        (+ v h)
                        (+ k 1)
                        h)]))
  (define h (/ (- b a) n))
  (* (simpson-sum 0 f a 0 h)
     (/ h 3)))

Exercise 1.30

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

1.3.2 Constructing procedure using lambda

(lambda (x) (+ x 4))

Using let to create local variables

The general form of a let expression (in Racket) is

(let ([<var1> <exp1>]
      [<var2> <exp2>]
      [<var3> <exp3>]
      ...
      [<varn> <expn>])
  <body>)

which is interpreted as an alternate syntax for

((lambda (<var1> ... <varn>)
   <body>)
 <exp1>
 ...
 <expn>)

The variables’ values are computed outside the let. For example, if the value of x is 2, the expression

(let ([x 3]
      [y (+ x 2)])
  (* x y))

will have value 12.

However, if we want to use the local variables defined in previously, we can use let* in Racket such as

(let* ([x 3]
       [y (+ x 2)])
  (* x y))

the value is 15.

Exercise 1.34

(f f) =>
(f 2) =>
(2 2) => "application: not a procedure;"

Procedures as General Methods

Finding roots of equations by the half-interval method

(define (search f neg-point pos-point)
  (define (close-enough? x y)
    (< (abs (- x y)) 0.001))
  (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 (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 "Values are not of opposite sign" a b)])))

The root between 2 and 4 of \(\sin x = 0\):

(half-interval-method sin 2.0 4.0)

\(x^3 - 2x - 3 = 0\) between 1 and 2:

(half-interval-method (lambda (x) (- (cube x) (* 2 x) 3)) 1.0 2.0)

Finding fixed points of functions

A number \(x\) is called a fixed point of a function \(f\) if \(x\) satisfies the equation \(f(x) = x\).

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ([next (f guess)])
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

Defining sqrt using fixed points method:

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

in which we used \(y \mapsto \frac{1}{2}(y + x/y)\).

Exercise 1.35

\(\phi\) is the root of equation \(x^2 - x - 1 = 0\) which implies the transformation \(x \mapsto x + 1/x\)

(define (gold-ratio)
  (fixed-point (lambda (x) (+ 1 (/ 1 x)))
               1.0))

Exercise 1.36

(define (logxx)
  (fixed-point (lambda (x) (/ (log 1000) (log x)))
               2.0))

(define (logxx-average)
  (fixed-point (lambda (x) (average (/ (log 1000) (log x)) x))
               2.0))

Exercise 1.37

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


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

\(k\) should be 5 to get an approximation that is accurate to 4 decimal places.

(cont-frac (lambda (i) 1.)
           (lambda (i) 1.)
           100)

(cont-frac-iter (lambda (i) 1.)
                (lambda (i) 1.)
                1000)

Exercise 1.38

(define (approximate-e k)
  (define (d i)
    (if (= (remainder (+ i 1) 3) 0)
        (* 2
           (/ (+ i 1) 3))
        1.))
  (+ 2
     (cont-frac-iter (lambda (i) 1.)
                  d
                  k)))

Exercise 1.39

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

1.3.4 Procedures as returned values

\(f(x)\) is a differentiable function, then a solution of the equation \(f(x) = 0\) is a fixed point of the function

\[x \mapsto x - \frac{f(x)}{f(x)'}\] 
(define (deriv f)
  (lambda (x)
    (/ (- (f (+ x dx)) (f x))
       dx)))

(define dx 0.00001)

(define (newton-transform f)
  (lambda (x)
    (- x (/ (f x) ((deriv f) x)))))

(define (newtons-method f guess)
  (fixed-point (newton-transform f) guess))

(newtons-method (lambda (x) (- (square x) 2)) 1.0)

Exercise 1.40

(define (cubic a b c)
  (lambda (x)
    (+ (* x x x) (* a x x) (* b x) c)))

Exercise 1.41

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

(((double (double double)) 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)
  (define (f-i i)
    (if (= i 1)
        f
        (compose f (f-i (- i 1)))))
  (f-i n))

(define (repeated-iter f n)
  (define (iter i r)
    (if (= i 1)
        r
        (iter (- i 1) (compose f r))))
  (iter n f))

((repeated-iter square 2) 5); -> 625