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