Feeds:
Posts

SICP Exercises Section 1.3.4

Exercise 1.40

Cubic creates and returns a procedure that takes an argument x and maps it to the value of x3 + ax2 + bx + c.

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

Even though this is a very simple example the smooth transition between algebraic notation and code is impressive.

Exercise 1.41

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

(define (inc x)
(+ x 1))

(((double (double double)) inc) 5)
=> 21

The evaluation of the expression above results in 21 = 5 + 16. This might seem strange at first because doubling something successively 3 times is equivalent to multiplying it by 23 = 8. So we could expect to get 13 = 5 + 8. But this is incorrect. The outermost double procedure creates 2 copies of the 2 inner double’s resulting in a “cascade” of 4 consecutive double’s, for a total of 24 = 16 applications of the procedure f. This can be clearly seen by applying the substitution model of evaluation.

Exercise 1.42

The capability of a procedure to take another procedure(s) as argument and to return a procedure as a value makes the implementation of compose simple and elegant:

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

Exercise 1.43

The returned procedure can in turn be passed as an argument to a procedure which returns a procedure. This “closure property” (in the mathematical sense) adds additional power to the language as can be seen in this and the next exercise.

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

Exercise 1.44

(define (average-3 x y z)
(/ (+ x y z) 3.0))

(define dx 0.001)

(define (smooth f)
(lambda (x)
(average-3 (f (- x dx))
(f x)
(f (+ x dx)))))

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

Exercise 1.45

As an experimental tool we can define a procedure n-th-root-test:

;; Tries to compute the n'th root of x using t average-damps.
(define (n-th-root-test n x t)
(fixed-point ((repeated average-damp t)
(lambda (y) (/ x (expt y (- n 1)))))
1.0))

It takes three arguments – n, x, and t. N determines the order of the root we want to compute, x is the number whose root we are computing, and t is the number of damping operations to be applied.

Running tests for n’s from 2 to 16 on x = 42 and taking t to be as small as possible we get:

;; Tests
(n-th-root-test 2 42 1)
(n-th-root-test 3 42 1)
(n-th-root-test 4 42 2) ; does not terminate with t = 1

(n-th-root-test 5 42 2)
(n-th-root-test 6 42 2)
(n-th-root-test 7 42 2)
(n-th-root-test 8 42 3) ; does not terminate with t = 2

(n-th-root-test 9 42 3)
(n-th-root-test 10 42 3)
(n-th-root-test 11 42 3)
(n-th-root-test 12 42 3)
(n-th-root-test 13 42 3)
(n-th-root-test 14 42 3)
(n-th-root-test 15 42 3)
(n-th-root-test 16 42 4) ; does not terminate with t = 3

A clear pattern emerges. Each time n reaches the next power of 2 one more average damping operation is needed to achieve convergence. In other words to compute the n-th root of x we need to apply ⌊ log2n⌋ damping operations. Embedding this knowledge into a new n-th-root procedure we get:

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

Exercise 1.46

Iterative-improve is slightly different from the procedures we saw so far. It can not return a lambda expression in the most straight forward manner. The reason is that the procedure returned is syntactically recursive (even though it generates an iterative process). So it must have a name:

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

(define (my-sqrt x)
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess)
(< (abs (- (* guess guess) x)) 0.00001))
(define (improve guess)
(average guess (/ x guess)))
((iterative-improve good-enough? improve) x))

(define (fixed-point f first-guess)
(define (good-enough? guess)
(< (abs (- guess (f guess))) 0.00001))
(define (improve guess)
(f guess))
((iterative-improve good-enough? improve) first-guess))