Why normal-order and applicative-order evaluation are not giving the same value?

Question

I am reading this book Structure and Interpretation of Computer Programs, 2nd edition and on page 21 under the subsection "Applicative order versus normal order" it is written that -

It can be shown that, for procedure applications that can be modeled using substitution (including all the procedures in the first two chapters of this book) and that yield legitimate values, normal-order and applicative-order evaluation produce the same value. (See Exercise 1.5 for an instance of an “illegitimate” value where normal-order and applicative-order evaluation do not give the same result.)

Now in the above mentioned exercise, the code is as follows:

(define (p) (p))

(define (test x y)
  (if (= x 0) 0 y))

(test 0 (p))

If I use substitution model,

1. Retrieve the body of test procedure:

(if (= x 0) 0 y)

2. Replace the formal parameter x by the argument 0 and y by the argument (p):

(if (= 0 0) 0 (p))

(if #t 0 (p))

0

I think 0 is a legitimate value in scheme.

Now according to the text, both normal order and applicative order evaluation should give the same result.

Normal order evaluation:

1. Expansion (first substitute operand expressions for parameters):

(if (= 0 0) 0 (p))

(if #t 0 (p))

2. Reduction:

0

Applicative order evaluation:

test will evaluate to the procedure defined.

0 will evaluate to the number O.

(p) will evaluate to (p), which will evaluate to (p)

On the evaluation of the argument (p), the interpreter will continue to evaluate it forever (in an infinite recursion). So, we will not get the value of the expression.

You can see that normal order gives a value whereas applicative order does not. So, if substitution model gives a legitimate value, then why they are not the same?

Edit:

My bad. I did not evaluate the operator and the operands first in the substitution model before applying the value of operator to the operands. That is what missing in the above detail.

The substitution model will not give a legitimate value (or any value at all) as evaluation of the argument (p) will never terminate. Hence, normal order will give a value of the expression whereas applicative order will not.

Answer 1

Given the definition

(define (p) (p))

Does the substitution model give a legitimate value for (p)? Does it give any value at all?

No: it doesn't: the computation fails to terminate. So applicative and normal order are not equivalent in this case. In particular normal order will give a value to the expression (test 0 (p)) and applicative order will not.

In fact given the above definition of p then (p) simply does not have a value as it never terminates: this doesn't depend on using the substitution model, it just depends on the fact that the definition of p is circular: there's no base case to the definition.

But given

(define (test x y)
  (if (= x 0) 0 y))

Then, under normal order evaluation, (test 0 (p)) will never attempt to evaluate (p) at all and thus will terminate. Applicative order evaluation, on the other hand, will attempt to evaluate all of the arguments to test, and will therefore attempt to evaluate (p), and fail to terminate.

Answer 2

Perhaps the book isn't very precise with its wording, but I guess it is meant that all procedures involved must always be that way.

(p) clearly isn't. But (test x y) as well does not always return a legitimate value.

Pronouns are a source of unclarity; I guess "that" in that sentence refers to "procedures", not to "applications". So while the application (test 0 (p)) does return a legitimate value, i.e. 0, the procedure test does not always return a legitimate value.

So the following wording might be clearer:

It can be shown that, for procedure applications that can be modeled using substitution, and for such procedures that always yield legitimate values, normal-order and applicative-order evaluation produce the same value.

This is of course not very stylish English prose. Indeed the famous advice by Boltzmann cited by Einstein proposes that "matters of elegance ought to be left to the tailor and to the cobbler", and clarity should always be preferred.

Substitution vs environment model of evaluation refers to such situations as evaluating (+ y y) where y is some function's parameter bound to some expression, e..g (p).

Then under the environment model y's value will only be found once, and reused for its second appearance in the expression (+ y y).

But under the substitution model for evaluation, evaluating (+ y y) leads to evaluating (+ (p) (p)), i.e. it can cause re-evaluation of the same expression more than once.

Normal order vs. applicative order is orthogonal to that. Under applicative order, when evaluating an application, the function's arguments' values are found before entering the function's body.

But under the normal order the function body is entered right away, and its parameter's value is found only when it is needed, thus causing the evaluation of the corresponding argument only at that time. Now, under environment model that value would be remembered from that point on, and reused if needed; and under substitution model it won't be remembered -- because the argument's expression is already substituted for the parameter inside the function's body, so there's no more parameter there to refer to.