SICP Exercise 1.5: Applicative-Order and Normal-Order Evaluation

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 the case of applicative-order evaluation, the interpreter attempts to evaluate the operands before evaluating the operator. When it tries to evaluate the second operand of the expression (test 0 (p)) (i.e. (p)) prior to applying the operator test it enters an infinite evaluation loop and so either does not terminate or runs out of resources (depending upon how the interpreter is implemented). The infinite evaluation loop occurs when evaluating p because the value of p is defined to be the value of evaluating p, so in order to evaluate p the interpreter must first evaluate p!

In the case of normal-order evaluation, the interpreter does not try to evaluate any operands until they are required in order to evaluate the value of the operator. So under normal-order evaluation, neither of the operands to test are evaluated prior to evaluating test. Instead, the interpreter starts by evaluating the body of test, which leads it to evaluate an if conditional expression. In order to do this it must first evaluate the predicate, which causes the interpreter to evaluate the first operand to test. This evaluates to 0 and so the predicate evaluates to #t (as 0 = 0). As the predicate is true, the consequent expression is then evaluated and so the overall expression yields 0. No attempt is made to evaluate the alternative expression, (p), and so no infinite evaluation loop results.