SICP Exercise 1.41

Question

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)

Answer

(define (double f)
  (λ (x) (f (f x))))

(((double (double double)) inc) 5)

Result:

21

Why 21? Well, because the doubling of the doubling is itself doubled again. We basically have \(2^{2^2}\), which of course is 16.

To better understand this, compare to the following variation:

((double (double (double inc))) 5)

Result:

13