RSS Feed

Exercise 1.10

Posted on Tuesday, September 11th, 2007

(A 1 10)(A (0 (A 1 9)))

(A 0 (A 0 (A 1 8)))

(A 0 (A 0 (A 0 (A 1 7))))

(A 0 (A 0 (A 0 (A 0 (A 1 6)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))

(A 0 (A 0 (A 0 (A 0 (A 0 32)))))

(A 0 (A 0 (A 0 (A 0 64))))

(A 0 (A 0 (A 0 128)))

(A 0 (A 0 256))

(A 0 512)

1024(A 2 4)(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

(A 1 (A 0 (A 0 (A 1 2)

Um, I think this is going to go for a long time so since the instructions don’t say to do it by hand the answer is 65,536.

And (A 3 3) is the same 65,536.

(define (f n) (A 0 n)) = 2n

(define (g n) (A 1 n)) = 2n

(define (h n) (A 2 n)) = I dunno

Categorized as SICP Chapter 1, SICP Exercises

One Response to
“Exercise 1.10”

  • Matt says: September 17th, 2007 at 5:55 pm

    (h n) is easier to figure out once you see that (A 2 n) resolves to (A 1 (A 2 (- n 1)). And we already have a function for handling (A 1 X), don’t we? Yes, it’s (g n). So we can think of (h n) calling (g n) until (= n 1), at which point it will return 2, and we already know that (g 2) returns 2^n.

    So (h n) returns a series of nested calls to (g n) like this: (g (g (g (g ... (g n))))), which, because (g 1) returns 2 and (g 2) returns 2^n, will produce the “tetration” of n (found the term tetration via a comment at Ken Dyck’s blog).

    For example:

    (h 2)
(g (A 2 (- 2 1)))
(g (g (A 2 (- 1 1))))
(g (g (g 2)))
(g (g 2^n))
(g (2^(2^n)))
2^(2^(2^n)))

    (h 3)
(g (A 2 (- 3 1)))
(g (g (A 2 (- 2 1))))
(g (g (g (A 2 (- 1 1)))))
(g (g (g (g 2))))
(g (g (g 2^n)))
(g (g (2^(2^n))))
(g 2^(2^(2^n))))
2^(2^(2^(2^n))))

    Thus, this exercise provides a good lesson on code re-use as well–when faced with a difficult problem, look to see if you’ve already solved some part of the problem. This kind of ‘change the problem into a different problem’ thinking keeps coming up in this book. Great stuff! Wish I could catch on quicker, though. :-)