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

From Drewiki
Jump to: navigation, search

Problem

Given an alternative implementation of if:

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

and a square-root procedure which uses it (good-enough? and improve taken from section 1.1.7):

(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 the new sqrt-iter?

Solution

Consider the definition of sqrt-iter given in the text; let's call it sqrt-iter-orig here. It uses the special form if:

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

The if expression in sqrt-iter-orig only evaluates its else-clause expression if the predicate expression is false, so sqrt-iter-orig only performs an additional iteration (using an improved guess) if the current guess isn't good enough.

new-if isn't a special form, it's a compound procedure. The interpreter will attempt to evaluate all three of its arguments -- predicate, then-clause and else-clause -- regardless of the value of its predicate. Since evaluating the else-clause of new-if in the body of sqrt-iter requires evaluating sqrt-iter again, the interpreter will never return a value for applications of sqrt-iter. The guess will continue to improve, but there is no expression in the sqrt-iter procedure that will "short-circuit" the evaluation of subsequent guesses once the guess is good enough.

Personal tools