## Sunday, November 8, 2009

### SICP Exercises 1.9 and 1.10

Exercises from section 1.2.1 Linear Recursion and Iteration

Exercise 1.9 asks us to use the substitution model to illustrate the processes generated by the following two procedures:
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))

(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
You may recognize these procedures as the two Peano Arithmetic examples from Lecture 1B. As we saw in the lecture video, the first procedure produces a linear recursive process, while the second produces an iterative process (the two procedures are given here in the reverse order from the lecture).

Remember also from that lecture that the steps for evaluating an application are:
• Evaluate the operator to get procedure
• Evaluate the operands to get arguments
• Apply the procedure to the arguments
• Copy the body of the procedure substituting the arguments supplied for the formal parameters of the procedure.
• Evaluate the resulting new body.

If we are to evaluate (+ 4 5) using the first procedure we'll see that the increment operations are deferred.
(+ 4 5)
Evaluate the operator to get the procedure
(if (= a 0)
b
(inc (+ (dec a) b)))

Evaluate the operands to get arguments
(if (= 4 0)
5
(inc (+ (dec 4) 5)))

Since 4 is in fact not equal to 0, this expression evaluates to
(inc (+ (dec 4) 5))

This is where things begin to get interesting. We can evaluate (dec 4), but then we need to evaluate the recursive call to + before we're able to evaluate the inc operation. That means the inc operation is deferred until we return from the recursive call.

Greatly simplified, the expansion of this expression proceeds as follows:
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))

At this point, the innermost expression, (+ 0 5), can be evaluated because the first operand is 0, which is a the base case of the recursive definition. The process will now contract until we have our answer.
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

Evaluating (+ 4 5) with the iterative procedure is much more straight forward, as we should expect. No operations are deferred, so we don't see the expand-and-contract process shape that is the signature of a recursive process.
(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9

Exercise 1.10 gives the following definition for Ackermann's function (note that this is a different definition than the one given in the Wikipedia entry for the Ackermann function. The analysis that follows is for the procedure given in the text.):
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))

The next part of the exercise asks us to evaluate a few expressions that use the function. Our Scheme interpreter is the best tool for this job.
> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536

Next, we're asked to give concise mathematical definitions for the following functions defined in terms of A:
(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

I'll take them one at a time. If we plug a few values in for (f n) we can see how the function grows.
> (f 0)
0
> (f 1)
2
> (f 2)
4
> (f 3)
6
> (f 4)
8

It's pretty clear from these results that

f(n) = 2n

which is what we should expect from examining the given procedures.
(define (f n) (A 0 n))
(f n) just calls A with the x argument set to 0. The procedure for A has a condition defined just for this input.
((= x 0) (* 2 y))

Next, plugging in a few values for (g n) we get:
> (g 0)
0
> (g 1)
2
> (g 2)
4
> (g 3)
8
> (g 4)
16

This sequence is growing exponentially.

g(n) = 2n, when n > 0
g(n) = 0, when n = 0

Finally, plugging in values for (h n) we get:
> (h 0)
0
> (h 1)
2
> (h 2)
4
> (h 3)
16
> (h 4)
65536

This one had me scratching my head for a few minutes. If you evaluate (h 5) you'll see that it's a number so large that I won't even try to describe it. I didn't see a pattern in these results until I wrote them out in a slightly different way.

h(0) = 0
h(1) = 2 = 21
h(2) = 4 = 22
h(3) = 16 = 24
h(4) = 65536 = 216

From these results I noticed that

h(n) = 2h(n-1), when n > 1
h(1) = 2
h(0) = 0

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

Anonymous said...

I did 1.10 all by hand... and got it wrong :-)

Ruth Wang said...

According to your formula h(n) = 2^h(n-1), when n > 0, h(1) should be 2^h(0)=1.

Bill the Lizard said...

Ruth Wang,

Yes, you're right. I added another base case to fix that error. Thank you for pointing it out.

Josiah said...

Wouldn't it be prettier to express h in terms of g, namely h(n) = g^(n-1) (2)? The only special case then required is h(0) = 0.

Alexander Grebenyuk said...

We can prove this pattern using mathematical induction. We need a base case and inductive case.

Inductive case:

Speaking in terms of Scheme we can represent h(k+1) in terms of h(k) where k is integer and k > 0.

(A 2 k)
(A 1 (A 2 (- k 1)),
which transcribes to h(k+1) -> g(h(k)) in mathematical terms. Knowing some base h(k) we can compute h(k+1) and any h(n) where n is larger than k.

Base case:

let n = 1
h(1) -> 2
h(n+1) -> g(h(n)) -> 2^2 = 4

And there is a special case for (A 2 n) where n = 0. h(0) -> 0.

So we proved the formula for all non-negative integers.

Alexander Grebenyuk said...
This comment has been removed by the author.
Anonymous said...

A simpler way to think of the h function is:

h(1) : 2

h(2) : 2 ^ 2

h(3) : 2 ^ (2 ^ 2)

h(4) : 2 ^ (2 ^ (2 ^ 2))

The function parameter is the number of times you exponentiate.

Just as exponentiation is repeated multiplication, h is a function that is the result of repeated exponentiation.

test said...

Hey Bill!

Thanks for putting this online: I began to read the book and I was having a hard time understanding the substitution process.

There is still one thing that I can’t understand yet, though. When describing the substitution process for the first implementation, you say:

> This is where things begin to get interesting. We can evaluate (dec 4), but then we need to evaluate the recursive call to + before we're able to evaluate the inc operation. That means the inc operation is deferred until we return from the recursive call.

I think I understand this. What I can’t understand is why isn’t this valid for the second implementation? I mean after the first substitution, it looks like this:

(+ (dec 4) (inc 5))

and then

(+ 3 6)

As I understand it is: we can evaluate (dec 4) and replace it with (3), but how can we evaluate (inc 5) if it depends on (+)? Doesn’t this still hold true in this context: “we need to evaluate the recursive call to + before we're able to evaluate the inc operation”?

Bill the Lizard said...

test,

We don't know anything about the inc function except that it increments its argument by 1. We don't have its implementation, so we don't know that it depends on +. In fact, we assume that inc is a primitive function that does not depend on + or anything else.

The reason the call to inc is deferred in the first example is because + makes a recursive call to itself that must be evaluated, not because inc depends on +.

I hope that clears up your question.

Yes it does. Thank you!

Matthew Mulholland said...

Maybe I'm misunderstanding something, but I believe the point of the evaluation exercise was to write things out by hand, not just use whatever interpreter you have. It gives you some very nice visuals. Here's my correct results:

1. (A 1 10) ==> 1024

(A x y)
(A 1 10)
((A (- 1 1) (A 1 (- 10 1))))
((A 0 (A 1 9)))
((A 0 (A (- 1 1) (A 1 (- 9 1)))))
((A 0 (A 0 (A 1 8))))
((A 0 (A 0 (A (- 1 1) (A 1 (- 8 1))))))
((A 0 (A 0 (A 0 (A 1 7)))))
((A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1)))))))
((A 0 (A 0 (A 0 (A 0 (A 1 6))))))
((A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 6 1))))))))
((A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5)))))))
((A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 5 1)))))))))
((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 (- 1 1) (A 1 (- 4 1))))))))))
((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 (- 1 1) (A 1 (- 3 1)))))))))))
((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 (- 1 1) (A 1 (- 2 1))))))))))))
((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 (* 2 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 (* 2 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 (* 2 8))))))))
((A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))))
((A 0 (A 0 (A 0 (A 0 (A 0 (* 2 16)))))))
((A 0 (A 0 (A 0 (A 0 (A 0 32))))))
((A 0 (A 0 (A 0 (A 0 (* 2 32))))))
((A 0 (A 0 (A 0 (A 0 64)))))
((A 0 (A 0 (A 0 (* 2 64)))))
((A 0 (A 0 (A 0 128))))
((A 0 (A 0 (* 2 128))))
((A 0 (A 0 256)))
((A 0 (* 2 256)))
((A 0 512))
((* 2 512))
1024

Matthew Mulholland said...

Here's part 2:

2. (A 2 4) ==> 65536

(A x y)
(A 2 4)
(A (- 2 1) (A 2 (- 4 1)))
(A 1 (A 2 3))
(A 1 (A (- 2 1) (A 2 (- 3 1))))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A (- 2 1) (A 2 (- 2 1)))))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A (- 1 1) (A 1 (- 2 1)))))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 (* 2 2)))
(A 1 (A 1 4))
(A 1 (A (- 1 1) (A 1 (- 4 1))))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A (- 1 1) (A 1 (- 3 1)))))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1))))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 (* 2 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 (* 2 4)))
(A 1 (A 0 8))
(A 1 (* 2 8))
(A 1 16)
(A (- 1 1) (A 1 (- 16 1)))
(A 0 (A 1 15))
(A 0 (A (- 1 1) (A 1 (- 15 1))))
(A 0 (A 0 (A 1 14)))
(A 0 (A 0 (A (- 1 1) (A 1 (- 14 1)))))
(A 0 (A 0 (A 0 (A 1 13))))
(A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 13 1))))))
(A 0 (A 0 (A 0 (A 0 (A 1 12)))))
(A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 12 1)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 11 1))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 10 1)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 9 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 8 1)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 6 1)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 5 1))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 4 1)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 3 1))))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1)))))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 4))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 8)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 16))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 32)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 64))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 128)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 256))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 512)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (* 2 1024))))))
(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
(A 0 (A 0 (A 0 (A 0 (* 2 2048)))))
(A 0 (A 0 (A 0 (A 0 4096))))
(A 0 (A 0 (A 0 (* 2 4096))))
(A 0 (A 0 (* 2 8192)))
(A 0 (A 0 16384))
(A 0 (* 2 16384))
(A 0 32768)
(* 2 32768)
65536

Matthew Mulholland said...

And here's the last part:

3. (A 3 3) ==> 65536

(A x y)
(A 3 3)
(A (- 3 1) (A 3 (- 3 1)))
(A 2 (A 3 2))
(A 2 (A (- 3 1) (A 3 (- 2 1))))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A (- 2 1) (A 2 (- 2 1))))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A (- 1 1) (A 1 (- 2 1))))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 (* 2 2))
(A 2 4)
...
65536

I stop here because this expression evaluates to the same result for #2 above. Neat.

Anonymous said...

Hi

I did try the question and I got the same answers as you. However, I would like to point out that we need not calculate the answer when n=0 as the question stated "...Give concise mathematical definitions for the functions .... for positive integer values of n"

Nice work though and I must say that I am finding it of good help when I need to verify my answers or am stuck on some problem.

Thanks