Note: this wiki is now retired and will no longer be updated!
The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.
SICP exercise 1.05
Ben Bitdiddle has invented a test to determine whether the interpreter he is faced is 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))
and a test expression:
(test 0 (p))
What behavior will Ben observe with an applicative-order interpreter? With a normal-order interpreter?
(Assume that the evaluation rule for the special form if is the same regardless of the interpreter's evaluation order: the predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)
When evaluating a combination, an applicative-order interpreter evaluates the combination's operands and operators before applying the resulting procedure (operator) to the resulting arguments (operands). A normal-order interpreter, on the other hand, only evaluates an operand when the procedure requires its value.
In the test expression (test 0 (p)), note that the 2nd operand, (p), is a combination. To evaluate this operand, the interpreter must invoke the procedure named by p. But the result of evaluating (p) is another combination (p), and so on, ad infinitum. In other words, if the interpreter attempts to evaluate the 2nd operand of the test expression, it will never produce a value.
An applicative-order interpreter will attempt to evaluate the 2nd operand of the combination (test 0 (p)) when that expression is evaluated, so this interpreter will enter an infinite loop and never produce a value for the test expression.
A normal-order interpreter does not immediately evaluate the 2nd operand of the combination (test 0 (p)) when that expression is evaluated, because its value is not required to expand the expression. The test expression will first evaluate to:
(if (= x 0) 0 y)
This expression is an if expression. if is a special form, one which evaluates its predicate before choosing to evaluate either its consequent or its alternative. In this case, the if's predicate is (= x 0), so the interpreter must now evaluate x in order to determine the value of the predicate. Note, however, that it does not yet need to evaluate y (the if expression's alternative) because that value is not yet needed.
x in this context is the first formal parameter of the procedure test, which is currently bound to the value 0; so the if expression now evaluates to
(if (= 0 0) 0 y)
Since the predicate's value is true, the if expression now needs the value of its consequent, which is 0, and this is the value returned by procedure test. So a normal-order interpreter will produce the value 0 when asked to evaluate the expression (test 0 (p)), because the interpreter never needs the value of the 2nd argument, (p).