This is the code:
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))
What I think(not sure) is that for applicative-order interpreter, (p) procedure is evaluated first which results in an infinite loop.
While for the normal-order interpreter, test procedure is evaluated, which results in test procedure returning 0. So p procedure will not be evaluated.
Your assumptions are right, evaluation occurs just as predicted. In an applicative-order evaluator the parameters to a function call are evaluated before binding them to the procedure's parameters - so the argument (p)
will result in an infinite loop, and we'll never enter test
's body.
On the other hand, a normal-order interpreter delays evaluation until the last moment, and the (p)
invocation will not be evaluated until needed - in other words, (test 0 (p))
will not result in an infinite loop because this execution path never uses the y
parameter (which was bound to (p)
), whereas (test 1 (p))
will loop forever because we manage to reach the point where y
is being used to produce a value.
Testing this is easy for the applicative-order interpreter - that's how standard Scheme works. For testing the normal-order evaluation, you can use an special interpreter with lazy evaluation, like the one implemented in chapter 4 of SICP.