**Exercise 1.41:** Define a procedure `double`

that takes a procedure of one argument as argument and returns a
procedure that applies the original procedure twice. For example, if `inc`

is a procedure that adds 1 to its
argument, then `(double inc)`

should be a procedure that adds 2. What value is returned
by `(((double (double double)) inc) 5)`

```
(define (double f)
(lambda (x) (f (f x))))
(define (inc x)
(+ x 1))
```

```
> (((double (double double)) inc) 5)
21
```

At first glance it’s possible to assume the answer should be 8+5=13 instead of 21 (16+5).

13 is achieved through:

```
> ((double (double (double inc))) 5)
13
```

In order to understand what is happening here it is better to start simple and work up to the complex example:
Again, which ever function `D`

receives it will apply it twice.

$$ f(x) = x+1 $$

$$ D(f) = (f \circ f)(x) = f(f(x) $$

$$ D(D(f)) = (f \circ f) \circ (f \circ f)(x) $$

$$ D(D(D(f))) = \left( \left( (f \circ f) \circ (f \circ f) \right) \circ \left( (f \circ f) \circ (f \circ f) \right) \right)(x) = f(f(f(f(x)))) \circ f(f(f(f(x)))) = f(f(f(f(f(f(f(f(x)))))))) $$

$$ f(f(f(f(f(f(f(f(5)))))))) = 13 $$

Clearly it’s pain to trace through all those function compositions but if need be it can be done to verify that
indeed f is applied 8 times to 5 in order to give the result of 13. It’s time now to go to
`(((double (double double)) inc) 5).`

The main difference from the previous statement is the `(double double)`

part.

$$ f(x) = x+1 $$

$$ D(f) = (f \circ f)(x) = f(f(x)) $$

$$ (D(D(f)) = D^2(f) = D(D(f)) = (f \circ f) \circ (f \circ f)(x) $$

$$ D(D(D(f))) = D^2(f) \circ D^2(f) = D(D(f)) \circ D(D(f)) = D(D(D(D(f))))(x) $$

So `(double double)`

in fact returns a composition of `(double (double f))`

which in turn get’s composed with itself
to form `(double (double (double (double f))))`

.