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