when evaluating the procedure:
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
by evaluating:
(test 0 (p))
under both normal order and applicative order evaluation, you will see;
under applicative order evaluation, we would first fully evaluate any arguments to a procedure, then evaluate the procedure with those values.
to evaluate (test 0 (p)
we would first need to evaluate 0
and (p)
0
is a primitive value, and thus evaluates to the value 0
.
(p)
is a procedure in the global environment, defined as (p)
. we would recieve a value of (p)
, which according to our evaluation strategy would need to be fully evaluated before we can continue evaluating (test 0 (p))
. this would create an infinite loop as we would never reach a value of (p)
that doesnt require further evaluation, and our program will hang.
under normal order, we do not evaluate arguments until they are needed. thus, to evaluate (test 0 (p))
, the following steps are taken:
(test 0 (p))
(if (= 0 0) 0 (p))
(if #t 0 (p))
0
the first line is our initial procedure application
the second is our definition of test
, with the substitutions x
-> 0
and y
-> (p)
.
the special form if
will only evaluate the third argument, if the first (the predicate) is false.
the third line is the aftermath of evaluating (= 0 0)
in order to check the value of our predicate, which is true
.
the fourth line is the result of the if
procedure, returning 0
.
notably, as we are following normal order application, we never needed to evaluate (p)
(thus avoiding hanging our program). however had the predicate to the if
procedure returned false
, we would then need to evaluate (p)
to find a value for the wider if
application, and enter a loop.