SICP exercise 1.5

There are a group of Hacker Schoolers working on the SICP book and today is the first forum. I was scheduled to present for SICP exercise 1.5 but because of my poor dental health (root canals, the horror!!!), I would not be able to attend the first meeting so I’m writing about the solution here instead.

The problem statement is as follows:

Exercise 1.5. Ben Bitdiddle has invented a test to determine whether the
interpreter he is faced with is using applicative-order evaluation or normal
order evaluation. He defines the following two procedures:

(define (p) (p))

(define (test x y)
(if (= x 0)
0
y))

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses
applicative-order evaluation? What behavior will he observe with an
interpreter that uses normal-order evaluation? Explain your answer.
(Assume that the evaluation rule for the special form if is the same whether
the interpreter is using normal or applicative order: The predicate
expression is evaluated first, and the result determines whether to evaluate
the consequent or the alternative expression.)

In applicative-order evaluation, the body of the procedure (operands) is evaluated before the procedure (the operator) and finally, the procedure is applied to the body. So in our exercise, 0 and p are evaluated before test in (test 0 (p)). But because p also evaluates to p in (define (p) (p)), it just goes on forever recursively and never terminates.

On the other hand, normal-order evaluation expands the expression all the way down, and does not evaluate the arguments (operators) to the procedure (operand) until it really has to, i.e. until the expression is composed of the most primitive elements. If we apply normal-order evaluation to the exercise above:

(test 0 (p)) would expand to

(if (= 0 0) 0 (p))

0

Because x is 0, the result returned will then be 0 and never reaches p because it already found what it needed in the first place.

If you find errors in the way I thought about it or could add more to my understanding, please let me know and I’ll ponder upon this exercise and about evaluation methods further!