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.)
Applicative Order Evaluation
(test 0 (p))
Will become and infinite loop. Since AOE evaluates all the arguments as much as possible before passing
them to a function test, clearly p is has no terminating case. Since p is a case of infinite recursion
the program goes into an infinite loop.
Normal Order Evaluation:
(test 0 (p))
This time p won’t be evaluated and test will enter the conditional in which the function terminates by returning 0.
The pesky else case is never ran and hence the infinite loop condition never comes up. However if the first argument
to test was anything but 0, an infinite loop would still occur.