The question can be found here.
In the book, I found one description of normal order evaluation was:
"An alternative evaluation model would not evaluate the operands until their values were needed. Instead it would first substitute operand expressions for parameters until it obtained an expression involving only primitive operators, and would then perform the evaluation."
I also found another description in short: "fully expand and then reduce".
In the exercise, I thought the definition of p was something like (lambda () (p)),
which would never expand to a primitive operator, thus never terminate.
However, on the other hand, after googling some answers to this question, it seems normal order evaluation should terminate because it only evaluates things as needed, and actually (p) won't be evaluated.
So I think there must be some difference between "expand" and "evaluate" and what the interpreter does here is to evaluate things.
What exactly is the difference, or are there some points that I have missed?
Another question: Should I say "(p) is evaluated to (p)" or "(p) is expanded to (p)"?
You're right that an applicative-order evaluator would not terminate if asked to evaluate (p). However, the question at hand mentions that if has a particular evaluation semantics which is shared by the applicative and normal-order evaluators. Specifically:
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 code from the exercise is
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
and the test under consideration is
(test 0 (p))
Normal-order evaluation is the "fully expand and then reduce" option. Under normal-order evaluation, (test 0 (p)) is fully expanded as
(test 0 (p)) ==
(if (= 0 0)
0
(p))
Since if has the semantics described above, and the test condition in the expansion is (= 0 0), which is true, the normal-order evaluator determines to evaluate the consequent, which is 0, so the value of the expression is 0.
Using the applicative-order evaluation however, the first step in evaluating (test 0 (p)) is to evaluate the expressions test, 0, and (p), and then call ("apply", hence "applicative") the value of test with the values produced by evaluating 0 and (p). Since the evaluation of (p) will not complete, neither will the evaluation of (test 0 (p)).