SICP Exercise 1.5

Exercise1-5.md

(define (p) (p))

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

(test 0 (p))

When we evaluate the above expression, one of the following occurs based on the evaluation order

Applicative-order evaluation

(test 0 (p))

(test 0 (p))

(test 0 (p))
...

In applicative-order evaluation, the expression fails to terminate. This is because each formal parameter is replaced by its corresponding argument first(operator and operands are both expanded). Thus, the interpreter tries to evaluate (p) first which itself evaluates to (p) and so on. Thus, the evaulation does not terminate.

This is the behavour exhibited by MIT-Scheme.

Normal-order evaluation

(test 0 (p))

(if (= 0 0 ) 0 (p))

(if #t 0 (p))

0

In normal-order evaluation, the operand is not evaluated until it is required to do so. Thus, the interpreted evaluates the operator test first. Since the condition evaluates to #t for the resulting if operation, only the first arguement is evaluated which is 0.