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.)
Recall that in applicative-order-evaluation, every single subexpression is first evaluated in the evaluation tree, the evaluation then traverses up the tree. In an applicative-order-evaluation, the operand 0, and (p) are evaluated first. (p) will be stuck in an infinite recursion, and eventually throws a stack overflow error.
In normal-order-evaluation, a mental model is that the operand will first be substituted by the body of the procedure, until we hit a primitive procedure, we will then evaluate the primitive procedures. (An expand and evaluate approach). In this case, test 0 (p) will substitute to:
(if (= 0 0) 0 (p))
We entered the if condition, the predicate (= 0 0) returns true, so the if statement returns 0 and the interpreter does not evaluate (p)