Exercise 1.5

Pre-exercise theory

Applicative-order evaluation

In this evaluation, the interpreter evaluates the elements of the operation and then applies the procedure. For example:

(* (+ 2 (* 4 6)) (+ 3 5 7))

; The interpreter first evaluates (* 4 6)
; reducing the operation to:
(* (+ 2 (24)) (+ 3 5 7))

; The interpreter then reduces (+ 2 (24))
(* (26) (+ 3 5 7))

; The interpreter then reduces (+ 3 5 7)
(* (26) (15))

; And then yields the result
390

Normal-order evaluation

All the operators are expanded until only "primitives" are left, then, only at the end, the reduction is performed:

(sum-of-squares (+ 5 1) (* 5 2))

; becomes
(+ (square (+ 5 1)) (square (* 5 2)))

; becomes
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))

; becomes
(+ (* 6 6) (* 10 10))

; becomes
(+ (36) (100))

; becomes
136

Further

Lisp uses the applicative-order evaluation because it can avoid multiple evaluation of expressions as in the example above with (+ 5 1) and (* 5 2) and because normal-order is very complicated when procedures can't be modelled by substitution.

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

Answer

Using applicative-order evaluation, we have the following reductions:

; p is evaluated and returns itself.
(test 0 (p))

; try to evaluate (p) again, because
; the expression hasn't been reduced.
(test 0 (p))

; stays in an infinite loop because
; (p) can never be evaluated.

Running the above in guile never returns.

In normal-order evaluation, everything must be expanded first.

(test 0 (p))

; becomes
(if (= 0 0) 0 (p))

; becomes
(if (#t) 0 (p))

; resolves to:
0