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.)
Normal-order returns 0 while applicative-order loops forever:
The former is "lazy" (evaluating body before arguments), while the latter is "eager" (evaluating arguments before body).
Ben Bitdiddle is attempting to solve the "halting problem" for which there is no general solution (i.e. halt detector that itself halts).1
Footnotes
-
cf. Ex 4.15, p. 387. ↩