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 behaviour will Ben observe with an interpreter that uses applicative-order evaluation? What behaviour 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.)

Applicative-order is essentially eager evaluation. The interpreter must evaluate an operand expression before evaluating the procedure it is being passed to. Likewise, normal-order is lazy evaluation. An expression is only evaluated once its value is absolutely necessary.

The procedure p just calls itself. This means any time p is called, it calls itself forever, which may result in a time-out or a stack overflow.