Chapter 1 — Building Abstractions with Procedures

In Scheme, #f is interpreted as false, and #t (or any other value other than #f) is true.

(> 1 2)                                 ; #f
(< 1 2)                                 ; #t

(define (abs x)
  (cond [(> x 0) x]
        [(= x 0) 0]
        [(< x 0) (- x)]))
(define (abs x)
  (cond [(< x 0) (- x)]
        [else x]))

else is a special symbol that can be used as the final predicate of cond. In fact, any value other than #f can be used in place of else.

and and or are special forms, as not all operands are necessarily evaluated. However, not is an ordinary procedure, as it only takes and evaluates one operand.

and returns the value of the first expression that evaluates to a false value, or the value of the last expression, if all expressions evaluate to true values.

(and (= 2 2) (> 2 1))                   ; #t
(and (= 2 2) (< 2 1))                   ; #f
(and 1 2 'c '(f g))                     ; (f g)
(and)                                   ; #t

Similarly, or returns the first expression that evaluate to a true value, or the value of the last expression (#f), if all expressions evaluate to false values.

(or (= 2 2) (> 2 1))                    ; #t
(or (= 2 2) (< 2 1))                    ; #t
(or #f #f #f)                           ; #f
(or 123 (/ 3 0))                        ; 123

Note that (/ 3 0) is not evaluated.

A number \(x\) is called a fixed point of a function \(f\) if \(f(x) = x\). For some function \(f\) we can locate a fixed point by beginning with an initial guess and applying \(f\) repeatedly, \[ f(x), \quad f(f(x)), \quad f(f(f(x))), \quad \ldots \] until the value does not change very much.

(define (fixed-point f initial-guess)
  (define tolerance 0.001)
  (define (close-enough? a b)
    (< [abs (- a b)] tolerance))
  (define (try guess)
    (let ([next (f guess)])
      (if (close-enough? guess next)
          next
          (try next))))
  (try initial-guess))

To find \(\sqrt{x}\) means finding the fixed point of the function \(f(y) = x/y\). However, consider an initial guess \(y_1\). The next guess is \(y_2 = f(y_1) = x / y_1\), and the next one \(y_3 = f(y_2) = x / (x / y_1) = y_1\). The guesses will oscillate between \(y_1\) and \(y_2\), never converging.

Applying the technique of average damping can solve this problem. Here average-damp is a procedure that takes a procedure f and returns another procedure—the average damped version of f.

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

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

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

(sqrt 9)                                ; 3.000000001396984

Notice that cube root is the fixed point of the function \(f(y) = x / y^2\):

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

(cube-root 27)                          ; 2.9998228753561564

If \(g(x)\) is a differentiable function, then a solution of \(g(x)=0\) is a fixed point of the function \(f(x)\), where \[ f(x) = x - \frac{g(x)}{g'(x)}. \]

First we expression the idea of a derivative: \[ g'(x) = \frac{g(x + dx) - g(x)}{dx}. \] Just like average damping, deriv transforms a function into another function:

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

With the aid of deriv, we can express Newton's method as a fixed-point process. Here newton-transform converts the problem of finding \(g(x) = 0\) to finding \(f(x) = x\).

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

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

Thus we can calculate \(\sqrt{x}\):

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

(sqrt 9)                                ; 3.0000000174227237

Note that the resulting lambda expression in newton-transform calculates the derivative of \(g\) every time it is called, since it does not save the result of (deriv g). This is very inefficient. Using a local variable dg to hold the result so deriv is called only once:

(define (newton-transform g)
  (let ([dg (deriv g)])
    (lambda (x)
      (- x (/ (g x)
              (dg x))))))

We calculated sqrt using both the fixed point search and Newton's method:

;;; fixed point
(define (sqrt x)                        ; [1]
  (fixed-point (average-damp (lambda (y) (/ x y)))
               1.0))
;;; Newton's method
(define (sqrt x)                        ; [2]
  (newtons-method (lambda (y) (- (square y) x))
                  1.0))

The latter [2] expands to:

(define (sqrt x)                        ; [3]
  (fixed-point (newton-transform (lambda (y) (- (square y) x)))
               1.0))

Both [1] and [3] have the same pattern—each method begins with a function and finds a fixed point of some transformation of the function (average-damp or newton-transform). We can express this general idea itself as a procedure:

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

Then the two methods become:

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

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

When looking for the smallest value, the predicate smaller or equal to (<=) must be used. If only < is used, in evaluating (f 2 2 3), the first two and condition will evaluate to false. The result would be (sum-of-squares 2 2), which is very wrong.

(define (sum-of-squares a b)
  (+ (* a a) (* b b)))

(define (f a b c)
  (cond [(and (<= a b) (<= a c)) (sum-of-squares b c)]
        [(and (<= b a) (<= b c)) (sum-of-squares a c)]
        [else                    (sum-of-squares a b)]))

(f 2 2 3)                               ; 13

In order to find the two larger ones out of three, a simpler solution:

(define (f a b c)
  (sum-of-squares (max a b)
                  (max (min a b) c)))

For the first two numbers (a, b), at least one of them is in the result. So the bigger one ((max a b)) must be in the result. As for the smaller one ((min a b)), it needs to be compared with c.

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

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

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

Using the substitution model, (p) infinitely expands to itself. Evaluating (p) will lead to an endless recursion.

In applicative-order evaluation, the interpreter first evaluates all its operands, including (p). So the whole expression will not evaluate to any result.

However, in normal-order evaluation, not all operands will necessarily be evaluated (not until they are actually needed). The expression is first expanded into (if (= 0 0) 0 (p)). Since the predicate is true, the (p) on the false branch is never needed. The whole expression evaluates to 0.

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that \((b^{n/2})^2 = (b^2)^{n/2}\), keep, along with the exponent \(n\) and the base \(b\), an additional state variable \(a\), and define the state transformation in such a way that the product \(a b^n\) is unchanged from state to state. At the beginning of the process a is taken to be \(1\), and the answer is given by the value of \(a\) at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

Original recursive code to compute \(b^n\):

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

Iterative code:

(define (fast-expt b n)
  (define (iter b n prod)
    (cond [(= n 0) prod]
          [(even? n) (iter (square b) (/ n 2) prod)]
          [else (iter b (- n 1) (* prod b))]))
  (iter b n 1))
;; the same thing:
(define (fast-expt b n)
  (define (iter a b n)                  ; a * b^n
    (cond [(= n 0) a]
          [(even? n) (iter a (square b) (/ n 2))]
          [else (iter (* a b) b (- n 1))]))
  (iter 1 b n))

The idea of smoothing a function is an important concept in signal processing. If \(f\) is a function and \(dx\) is some small number, then the smoothed version of \(f\) is the function whose value at a point \(x\) is the average of \(f(x-dx)\), \(f(x)\), and \(f(x+dx)\). Write a procedure smooth that takes as input a procedure that computes \(f\) and returns a procedure that computes the smoothed \(f\). It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtain the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from Exercise 1.43.

The definition of smooth is quite easy:

(define (smooth f)
  (define dx 0.01)
  (define (average a b c)
    (/ (+ a b c) 3))
  (lambda (x)
    (average (f (- x dx))
             (f x)
             (f (+ x dx)))))

((smooth square) 2)                     ; 4.000066666666666
((smooth (smooth square)) 2)            ; 4.000133333333333
((smooth (smooth (smooth square))) 2)   ; 4.0001999999999995

However, the repeated application of smooth should be written as:

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

((n-fold-smooth square 1) 2)            ; 4.000066666666666
((n-fold-smooth square 2) 2)            ; 4.000133333333333
((n-fold-smooth square 3) 2)            ; 4.0001999999999995

Not as:

(define (wrong f n)
  (repeated (smooth f) n))

((wrong square 1) 2)                    ; 4.000066666666666
((wrong square 2) 2)                    ; 16.00060000444444
((wrong square 3) 2)                    ; 256.01926716889415

The wrong implementation actually expands to:

((smooth square) ((smooth square) 2))   ; 16.00060000444444
((smooth square) ((smooth square)
                  ((smooth square) 2))) ; 256.01926716889415

Comput \(\sqrt[n]{x}\) by calculating the fixed point of the function \(x / y^{n-1}\) average damped \(\lfloor \log_2 n \rfloor\) times.

(define (nth-root x n)
  (define (log2 n) (/ (log n) (log 2)))
  (let ([c (inexact->exact (floor (log2 n)))])
    (fixed-point ((repeated average-damp c)
                  (lambda (y) (/ x (expt y (- n 1)))))
                 1.0)))

Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of Section 1.1.7 and the fixed-point procedure of Section 1.3.3 in terms of iterative-improve.

(define (iterative-improve  good-enouth? improve)
  (define (try guess)
    (if (good-enouth? guess)
        guess
        (try (improve guess))))
  try)

(define (fixed-point f first-guess)
  ((iterative-improve
    (lambda (guess)
      (< [abs (- guess (f guess))] 0.00001))
    f)
   first-guess))

(define (average-damp f)
  (lambda (x) (/ (+ x (f x)) 2)))

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

(sqrt 9)                                ; 3.000000001396984