Exercise

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:

1
2
3
4
5
6

(define (p) (p))

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

Then he evaluates the expression

1

(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.)

Student Response

Applicative order evaluation is “evaluate the arguments and then apply”. So the interpreter will first evaluate (p) and then apply the result to test. Since (p) will never terminate, the interpreter will never terminate.

Normal order evaluation is “fully expand and then reduce”. So the interpreter will first expand (test 0 (p)) to (if (= 0 0) 0 (p)) and then reduce it to 0.

Teacher Evaluation

Evaluation

Critique my description of the behavior. Provide notes on what I am overlooking.

Your explanation is generally correct, but I can help add some important nuance to make it more precise:

  1. Applicative Order (your explanation is correct)

    • You’re right that the interpreter will hang because (p) needs to be evaluated first
    • (p) is an infinite recursion that calls itself forever
    • This matches how most modern languages and Scheme implementations work

  2. Normal Order (needs more detail)

    • Your explanation is correct but could be more detailed
    • Here’s the step-by-step expansion:
      1. (test 0 (p)) is expanded by substituting the body of test
      2. Becomes (if (= 0 0) 0 (p))
      3. The predicate (= 0 0) is evaluated first (as noted in the exercise’s parenthetical note)
      4. Since it’s true, the consequent 0 is returned
      5. Crucially, (p) is never evaluated because it’s in the alternative branch
    • The key insight is that normal-order evaluation only evaluates expressions when their values are actually needed

The main thing you’re not emphasizing enough is that this is actually a very clever test because it specifically takes advantage of how if works as a special form. The fact that if only evaluates the branch that’s taken is what makes this test definitively distinguish between the two evaluation orders.

Would you like me to suggest an edit to your markdown file to incorporate these details?

No.

Understood! Let me know if you have any other questions.