What behavior will I see for an interpreter that uses Applied Order Evaluation versus an interpreter based on normal order?

This is the code:

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


What I think (not sure) is that for the applicative order interpreter, it evaluates (p) first which results in an infinite loop.

Whereas, for the normal order interpreter, a test procedure is evaluated, the results of which in a test procedure returning 0. Thus, procedure p will not be evaluated.


source to share

1 answer

Your assumptions are correct, the assessment is proceeding exactly as predicted. In the applicative order evaluator, the function call parameters are evaluated before binding them to the procedure parameters, so the argument (p)

will result in an infinite loop and we will never enter the body test


On the other hand, the normal order interpreter delays evaluation until the last moment, and the call (p)

will not evaluate until needed - in other words, (test 0 (p))

it will not result in an infinite loop, because this path execution never uses the parameter y

(which is bound to (p)

). whereas it (test 1 (p))

will cycle forever, because we manage to reach the point at which it is y

used to create value.

Testing is easy for the application order interpreter - how the standard schema works. To test the normal order evaluation, you can use a special lazy-evaluating interpreter, such as the one implemented in SICP Chapter 4 .



All Articles