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

The procedure `p`

returns itself. So when you call it, the interpreter needs to evaluate `(p)`

in order to evaluate `(p)`

. It gets stuck in an infinite loop, trying over and over to evaluate `(p)`

.

Using applicative-order evaluation, the interpreter evaluates the operator and operands before it applies the operator to the operands. So when you input `(test 0 (p))`

, the interpreter first tries to evaluate `(p)`

before applying `test`

to `0`

and `(p)`

. It gets stuck in a loop while trying to evaluate `(p)`

and never gets to `test`

.

Using normal-order evaluation, the interpreter doesn’t evaluate the operator and operands until it needs to. So when you input `(test 0 (p))`

, it applies `test`

according to the instructions in the definition of `test`

. It gets to the second line and substitutes `0`

in for `x`

and evaluates `(if (= 0 0))`

to true. So it goes to the third line and returns `0`

. It doesn’t need to evaluate `(p)`

because it never gets to the fourth line. Since it never tries to evaluate `(p)`

, it doesn’t get stuck on it.