What research have you done to answer that question? I just plugged it as it is in Google, and got as second answer (the first may be as good, I did not check) a reference to a section of a bible on your topic: Hal Abelson's, Jerry Sussman's and Julie Sussman's Structure and Interpretation of Computer Programs (MIT Press, 1984; ISBN 0-262-01077-1), aka the wizard book. The reference is to the section "Normal Order and Applicative Order".

It states:

Scheme is an applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed.

and adds that the latter is called lazy evaluation.

So you have your definitions wrong, and taking one for the other:

• applicative order evaluates subexpressions when, i.e. just before, the procedure is applied.

• normal order passes subexpressions as they are, without evaluation, and proceeds with the evaluation only when the corresponding formal parameter is actually to be itself evaluated. (there is a further twist to it regarding environment issues ... but we better forget that at this point).

Furthermore, you do not properly understand the call mechanism which involves two things:

• the parameter passing mechanism, which include proper processing of actual arguments to the call, depending on the evaluation rule;

• the "replacement" of the call to the function by the body of the function (without the header).

In the case of applicative order evaluation of ( test 0 (p) ), you are supposed to evaluate the argument subxpressions first. These are 0 and (p).

• evaluation of a literal value like 0 yield that value.

• the second argument however is a procedure call to a parameter-less procedure called p. It has no parameter, so that we have no worry about evaluation order. Then, in order to pursue evaluation, we have to replace the call by the body of the procedure which follows the list of arguments, and then evaluate that body. The body of procedure p, as defined by the declaration (define (p) (p) ), is (p), so that we are left with the evaluation of what we were just trying to evaluate. In order words, the evaluation process is caught in a loop, and will not terminate.

... and you never get to actually finish the call to the function test, since evaluation of its arguments does not terminate. Your program does not terminate.

This risk of non termination, even when the guilty argument will never be used in the call, is one of the reasons to use instead normal order evaluation, which may be a bit harder to implement, but may have better termination properties.

Under normal order evaluation, you do not touch the argument sub-expressions. What you do is replace the call ( test 0 (p) ) by the body of the function test, i.e. (if (= x 0) 0 y), where the names of the (formal) arguments x and y are replaced by the corresponding actual arguments 0 and (p) (up to environment, or renaming issues, that are important but would complicate the explanation here, and are the main difference between the original Lisp and the Scheme language).

Hence you replace the evaluation of ( test 0 (p) ) by the evaluation of (if (= 0 0) 0 (p)).

Now the function if is a primitive function that usually always evaluate its first argument, but evaluates its last 2 arguments in normal order, evaluating only the useful one, depending on whether the first evaluates to false or true (actually NIL or #f for false, or some other value for true, in the case of Scheme - if my memory does not fail me). Since (= 0 0) evaluates to true, evaluation of the conditional amount to evaluating the yet unevaluated second argument, which is 0, which unsurprisingly (except in old Fortran) evaluates to 0.

Deep breath.