SICP Exercise 1.5

Question

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).

Answer

Let us first recall the difference between applicative-order and normal-order evaluation.

In applicative-order evaluation (which is what Lisp uses), arguments are first evaluated and the operation is then applied. In normal-order evaluation, the statement is first fully expanded and only then evaluated.

So how do these two paradigms differ in evaluating the above code?

Let us walk through evaluation of the program using applicative-order evaluation.

(test 0 (p))
; evaluate (p)
; since (p) just returns (p) again, the function call remains the same
(test 0 (p))

This creates an infinite loop. If the interpreter uses applicative-order evaluation, the program will never terminate.

So, how would normal-order work in comparison? Let us again walk through the evaluation of the program.

(test 0 (p))
; expand the statement
(if (= 0 0) 0 (p))
; (= 0 0) returns #t
(if #t 0 (p))
0

The program returns 0.