## **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

## Problem

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

## Solution

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