Exercise 1.6 of SICP

2009-05-17

sicp

Exercise 1.6: Alyssa P. Hacker doesn’t see why if needs to be provided as a special form. “Why can’t I just define it as an ordinary procedure in terms of cond?” she asks. Alyssa’s friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
		(else else-clause)))

Eva demonstrates the program for Alyssa:

> (new-if (= 2 3) 0 5) 
5 
> (new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite the square-root program:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
		  guess
		  (sqrt-iter (improve guess x)
					 x)))

What happens when Alyssa attempts to use this to compute square roots? Explain.

sqrt-iter implemented with new-if will create an infinite loop, this is because scheme uses Applicative Order Evaluation rule by default. In a regular if statement all expressions get evaluated in order of need not at the same time. This difference in the order of evaluation is what makes an passing arguments to an if statement different than passing arguments to functions such as new-if in Applicative Order systems. The way sqrt-iter is implemented using new-if implies the following evaluation rules: good-enough? returns true or false (doesn’t matter which), “guess” is already a number and hence in the simplest form it doesn’t get evaluated any further. The infinite recursion occurs at sqrt-iter call because it will get evaluated no matter what good-enough? does since new-if is just a regular function and under AOE all arguments must be evaluated fully before passed to a function.

Another example of the difference between argument evaluation:

> (if (> 1 0) 1 (/ 1 0)))
1 
(new-if (> 1 0) 1 (/ 1 0)))
*** ERROR -- Divide by zero (/ 1 0)

Clearly a standard if doesn’t evaluate the last argument until it must. It will only evaluate it in the case where the predicate (> 1 0) will evaluate to false, which will never happen. On the other hand new-if evaluates everything right away, the interpreter tries to expand and pass the following (new-if #t 1 *ERROR!*)

It’s interesting that to make new-if behave correctly only requires to change the evaluation strategy to Normal Order Evaluation and the sqrt-iter code will work. I wouldn’t want to trace the NOE version of sqrt-iter because improve functions don’t get evaluated and just get passed along with every recursive call which makes them, a nightmare to untangle on paper.

Contents