# Difference between normal-order and applicative-order evaluation

The language I'm learning is Scheme and I'm working on an exercise that gives this:

(define (p) (p) )

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


Then the question asks to evaluate the expression: (test 0 (p) ) and to comment on the behavior that would be observed under normal - order and applicative order evaluation.

These are my thoughts:

Under normal order, the program would evaluate the subexpressions before proceeding:

Thus ( test 0 (p) ) becomes:

(test 0 p)
( if (= x 0) 0 p))


Returning output 0

The only difference in applicative order would be that the program would run as:

( test 0 (p) ) becomes:

(test 0 (p))
( if (= x 0) 0 (p)))


Returning output 0

Thus (p) would never be evaluated as it won't be needed.

Is this correct? Please let me know as I have almost no experience programming.

• I felt the question to be general enough, beyond the Scheme language itself, to justify treatment here. – babou Mar 26 '15 at 14:26

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.

• I think OP is confused with definition in chapter 1 as per this – SMA Mar 4 '16 at 16:12
• I just started SICP, and I was confused by the wording as well. If I have it right, applicative-order evaluates all of the arguments fully before it applies the procedure. In the case of test above, you get a loop because it's trying to evaluate (p) fully and therefore never terminates - and in fact never even reaches the "if". In normal-order evaluation, the arguments are passed as-is to the procedure, so test immediately applies if, where only the consequent is evaluated. – Tony Jul 21 at 18:25
• There's a great summary here. – Tony Jul 21 at 23:31