2011-08-30

SICP Exercise 1.6: A New If

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.

In order to evaluate sqrt-iter the interpreter must evaluate new-if. Now as Scheme uses applicative-order evaluation (for non-special forms), prior to evaluating new-if the interpreter will attempt to evaluate all three of the predicate, then-clause and else-clause operands. Note that this means that an attempt will be made to evaluate both the then-clause and else-clause operands, regardless of what the predicate evaluates to.

When the interpreter tries to evaluate the else-clause an infinite recursion occurs. This happens as evaluating the else-clause operand requires evaluation of a further sqrt-iterator expression which, of course, requires a further evaluation the else-clause operand, and so on.

No comments:

Post a Comment