Search code examples
schemeinterpretersicp

What behaviour would I see for an interpreter that uses applicaitve-order evaluation vs a normal-order based interpreter?


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.


Solution

  • 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.