What's the explanation for Exercise 1.6 in SICP?

Question

I'm just beginning to work through SICP (on my own; this isn't for a class), and I've been struggling with Exercise 1.6 for a couple of days and I just can't seem to figure it out. This is the one where Alyssa re-defines if in terms of cond, like so:

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

She tests it successfully on some simple cases, and then uses it to re-write the square root program (which worked just fine with if):

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

The question then asks: "What happens when Alyssa attempts to use this to compute square roots? Explain." [If necessary, I'm happy to reproduce the other procedures (good-enough?, improve, etc.), just let me know.]

Now, I know what happens: it never returns a value, which means that the program recurses infinitely. I just can't explain why this happens. Whatever subtle difference exists between if and new-if is eluding me. Any and all help much appreciated.

Answer 1

new-if is a function. When a function is called, what's the first thing that Scheme does with the argument list? It evaluates all the arguments.

Answer 2

new-if is a procedure, and Scheme uses applicative-order evaluation (1.1.5), so even before new-if is actually performed, it has to evaluate all the arguments first, which are guess and (sqrt-iter (improve guess x) x). You can see that the latter argument is a recursion, which calls a new new-if procedure, this is how the infinite loop occurs.

The ordinary if need not evaluate its arguments first, just go along the way, this is the difference between if and new-if. :)

Answer 3

First of all you have to understand the difference between applicative order evaluation and normal order. Lisp uses applicative order, but conditional expressions are evaluated not like normal functions (sicp chapter 1.1.6):

(if <predicate> <consequent> <alternative>)

To evaluate an if expression, the interpreter starts by evaluating the <predicate> part of the expression. If the <predicate> evaluates to a true value, the interpreter then evaluates the <consequent> and returns its value. Otherwise it evaluates the <alternative> and returns its value.

Answer 4

There are three ways a form may be evaluated in Scheme:

1. Applicative Order
   • evaluate the arguments and then apply
   • given f(x)=x+x: 3*f(1)*f(1) ⇒ 3*2*2
2. Normal Order
   • fully expand and then reduce
   • given f(x)=x+x: 3*f(1)*f(1) ⇒ 3*(1+1)*(1+1) (also used in "lazy evaluation")
3. Special Forms For example:
   • Booleans and and or. For example: (and <e1> ... <en>) evaluates Left → Right. If any evaluates to false, the value of the and expression is false, and the rest of the <e>'s are not evaluated.
   • Conditionals like if and cond
     • (if <predicate> <consequent> <alternative>): If the <predicate> evaluates to a true value, the interpreter then evaluates the <consequent> and returns its value. Otherwise it evaluates the <alternative> and returns its value
     • (cond (<p1> <e1>) ... (<pn> <en>)): The predicate <p1> is evaluated first. If its value is false, then <pn> is evaluated. If <pn>'s value is also false, then <pn+1> is evaluated. When true predicate, the interpreter returns the value of the corresponding consequent expression <e>.

In the case of Exercise 1.6:

• new-if is a normal procedure. In Scheme (and many other languages), arguments are fully evaluated before the procedure is called. This is known as applicative order. ∴ sqrt-iter is called every time new-if is called, resulting in an infinite loop.
• For the reader's edification, normal ifs are a special form. The recursive statement wouldn't be evaluated unless the <alternative> is called.

Answer 5

Previous answers are great. I'll add another one that explains in a more thorough way.

Another way to think of this difference is like this: How is the recursion using if stopping at some point and the one using new-if looping forever?

First lets see how these two ifs work in general and then how they work for this case.

if

This is explained by @alex-vasi:

To evaluate an if expression, the interpreter starts by evaluating the <predicate> part of the expression. If the <predicate> evaluates to a true value, the interpreter then evaluates the <consequent> and returns its value. Otherwise it evaluates the <alternative> and returns its value.

new-if

This is explained by @Schmudde:

All arguments are fully evaluated before the procedure is called.

How is the recursion using if stopping at some point?

It's stopping because at the point where the guess is good enough (ie (good-enough? guess x) is true), we will have:

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

And since the predicate is now true, the interpreter will evaluate the consequent (which is guess), return its value and will no longer evaluate the alternative (which is (sqrt-iter (improve guess x) x)).

So if actually evaluates (sqrt-iter (improve guess x) x) recursively up until the guess is good enough. Then it stops the recursion.

How is the recursion using new-if looping forever?

As with if, with new-if (sqrt-iter (improve guess x) x) will be evaluated recursively up until the guess is good enough.

But then it will keep evaluating (sqrt-iter (improve guess x) x) again and again. Why? Because when evaluating:

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

since new-if is a procedure, it will not check if (good-enough? guess x) is true or not in order to decide to evaluate either guess or (sqrt-iter (improve guess x)). What it will do is that it will evaluate (good-enough? guess x), guess and (sqrt-iter (improve guess x)) because those are the arguments of the procedure. So even when guess is good enough it will keep calling (sqrt-iter (improve guess x)) recursively :/.