2 Call-by-value (applicative order) and Call-by-name (normal order) (SICP Exerci

Question

2 Call-by-value (applicative order) and Call-by-name (normal order)
(SICP Exercise 1.5) Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with
is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
Then he evaluates the expression
(test 0 (p))
What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior
will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the
evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order:
The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or
the alternative expression.)

Explanation / Answer

If the interpreter uses applicative-order, then (test 0 (p)) will not return (it will run in an infinite loop) because when the interpreter evaluates (test 0 (p)) it will evaluate the argument (p). When the interpreter evaluates (p), it will evaluate (p) again since the definition of p is p. So it will continue evaluating p forever. If the interpreter uses normal-order evaluation, then (test 0 (p)) will return 0. The interpreter will evaluate the expression (if (= 0 0) 0 (p))) (substituting in 0 and (p) in the definition of test), then it will evaluate the if statement, which will result in a return value of 0. (p) will not be evaluated since (= 0 0) is true.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.