**Exercise 1.40**

*Cubic* creates and returns a procedure that takes an argument *x* and maps it to the value of *x ^{3} + ax^{2} + 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 *2 ^{3} = 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

*2*applications of the procedure

^{4}= 16*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 *⌊ log _{2}n⌋* 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))
```