# SICP - Solution: Exercise 1.5

##### September 27, 2018

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

## Solution #

The key is to notice that `(define (p) (p))`

defines a function that evaluates to itself.

An interpreter that uses **applicative-order evaluation** will “evaluate the arguments and then apply”. When this kind of interpreter evaluates the expression `(test 0 (p))`

, it will start by evaluating `0`

, then it will try to evaluate `(p)`

and finally apply `test`

to the values of the evaluation of the two parameters.

`test`

will evaluate to the procedure defined.

`0`

will evaluate to the number O.

`(p)`

will evaluate to `(p)`

, which will evaluate to `(p)`

To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

When the interpreter try to evaluate the expression `(p)`

, it will:

- replace each formal parameter by the corresponding argument in the body of the procedure: since there is no formal parameter in this case, the body of the procedure will just be
`(p)`

. - evaluated the body of the procedure, which will be
`(p)`

in our case, which in turn starts the evaluation all over again, thus making an infinite loop.

With an interpreter that uses **normal-order evaluation**, the interpreter will “fully expand and then reduce”. In this model, the interpreter will not evaluate the operands until their values are actually needed. In that case `(test 0 (p))`

will evaluate as follows:

```
(test 0 (p))
```

will be expanded to:

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

Since the predicate `(= 0 0)`

evaluates to `#t`

in the `if`

, then `(p)`

will not be evaluated and the result will be:

```
0
```