Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.41

From Drewiki
Jump to: navigation, search

Problem

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)

Solution

Here's the requested procedure double:

(define (double f)
  (lambda (x) (f (f x))))

We can show that it works by substitution using inc:

(define (inc x) (+ x 1))
 
((double inc) 3)

This expression expands by substitution as follows:

((double inc) 3)
 
((lambda (x) (inc (inc x))) 3)
 
(inc (inc 3))
 
(inc (4))
 
5

To answer the question posed by the exercise, let's again use substitution to figure it out. The exercise asks us to evaluate the combination

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

We need to evaluate the operator in this expression. Again by substitution:

((double (double double)) inc)
 
((double (lambda (x) (double (double x)))) inc)

We stop expanding the lambda expression (lambda (x) (double (double x))) at this point, because we can't expand it any further until it's applied to an argument x. Now we expand the outer-most (double f) expression, where f is (lambda (x) (double (double x))). In fact, let's just name that expression f here to keep things simple:

((double f) inc)
 
((lambda (x) (f (f x))) inc)

Now apply this lambda expression to inc, substituting inc for x:

(f (f inc))

Now let's re-expand f in the inner-most expression,

(f ((lambda (x) (double (double x))) inc))

By applying the lambda expression to inc in the inner expression ((lambda (x) (double (double x))) inc) we get

(f (double (double inc)))
 
(f (double (lambda (x) (inc (inc x)))))

Abbreviate the lambda expression (lambda (x) (inc (inc x))) as g:

(f (double g))
 
(f (lambda (x) (g (g x))))

And abbreviate this lambda expression (lambda (x) (g (g x))) as h:

(f h)

Recall that f itself is an abbreviation for a lambda expression, so now we can apply it to h. Re-expand f to get:

((lambda (x) (double (double x))) h)
 
(double (double h))
 
(double (lambda (x) (h (h x))))

Abbreviate this lambda expression (lambda (x) (h (h x))) as i:

(double i)
 
(lambda (x) (i (i x)))

Now we've got a lambda expression for the operator in the original expression; i.e., (lambda (x) (i (i x))) is the expansion of ((double (double double)) inc). Let's apply it to 5:

((lambda (x) (i (i x))) 5)
 
(i (i 5))

and now we re-expand the abbreviations we used for our intermediate results. Start with the combination (i 5):

(i ((lambda (x) (h (h x))) 5))
 
(i (h (h 5)))

Now (h 5):

(i (h ((lambda (x) (g (g x))) 5)))
 
(i (h (g (g 5))))

Now (g 5):

(i (h (g ((lambda (x) (inc (inc x))) 5))))
 
(i (h (g (inc (inc 5)))))
 
(i (h (g (inc 6))))
 
(i (h (g 7)))
 
(i (h ((lambda (x) (inc (inc x))) 7)))
 
(i (h (inc (inc 7))))
 
(i (h (inc 8)))
 
(i (h 9))
 
(i ((lambda (x) (g (g x))) 9))
 
(i (g (g 9)))
 
(i (g ((lambda (x) (inc (inc x))) 9)))
 
(i (g (inc (inc 9))))
 
(i (g (inc 10)))
 
(i (g 11))
 
(i ((lambda (x) (inc (inc x))) 11))
 
(i (inc (inc 11)))
 
(i (inc 12))
 
(i 13)

We can shortcut here: we started with (i (i 5)) and that became (i 13). So it appears that (i x) adds 8 to x, meaning that:

(i 13)
 
21

Indeed, this is the same answer we get by evaluating this expression in the Scheme interpreter:

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

Output:

21


So ((double (double double)) inc) adds 16 to its argument. Sixteen is <math>2^{2^2}</math>, so it looks like each additional application of double adds a power of two. We can guess that ((double (double (double double))) inc) would add <math>2^{2^{2^2}}</math>, or 256, to its argument. Let's try it by evaluating the expression in the interpreter:

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

Output:

261


which is in fact 5 + 256.

Personal tools