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,
test procedure:(if (= x 0) 0 y)
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:
(if (= 0 0) 0 (p))
(if #t 0 (p))
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.
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.