Exercise from SICP:
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?
With applicative order the first step is to evaluate
(test 0 (p)), expanding
(p) by its definition.
But that evaluates to itself so the program gets stuck in an infinite loop and does not terminate.
We get the evaluation chain:
(test 0 (p)) (if (= 0 0) 0 (p)) (if #t 0 (p)) 0
So it results in 0.
Because we expand the definitions in normal order, and the
if statement avoids it, we never hit the recursive loop in normal order.