Exercise 1.41 of SICP

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)

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)

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