Endless recursion when `if` is redefined, why?

Question

I'm new in programming and started learning the language Scheme. (I study on the book Structure and Interpretation of Computer Programs) and there came across one task which is described below. I wrote two codes replacing if with cond, but for some reason when running the first code there is endless recursion, but when running the second code there is no endless recursion and it normally calculates sqrt...although the code is the same, why is that?

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.

First Code:

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

(define (square x)
  (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (better-good-enough? prev-guess guess)
  (< (abs (- guess prev-guess))
     0.00001))

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

(define (better-sqrt x)
  (better-sqrt-iter 0 1.0 x))

Second Code:

(define (square x)
  (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (better-good-enough? prev-guess guess)
  (< (abs (- guess prev-guess))
     0.00001))

(define (better-sqrt-iter prev-guess guess x)
  (cond ((better-good-enough? prev-guess guess)
      guess)
        (else (better-sqrt-iter guess
                        (improve guess x)
                        x))))

(define (better-sqrt x)
  (better-sqrt-iter 0 1.0 x))

Answer 1

This smells like a homework question, but, assuming you are using Scheme, consider what happens when a general form (so, not any kind of special form) like

(f a b c)

is evaluated:

1. f, a, b & c are evaluated in some undefined order (possibly all at once even);
2. The value of f (the result of evaluating it in other words), which should be a function, is applied to the results of evaluating a, b & c;
3. The function returns a value (or values) and this is the value of the form.

What happens when you use this evaluation strategy to try to evaluate the first version of better-sqrt-iter? You can just do some of the evaluation by hand with paper & pencil to see what happens.

Why is that evaluation rule a problem here?

Answer 2

We can use the substitution model.

(better-sqrt 1) 
(better-sqrt-iter 0 1.0 1)
(cond
  ((better-good-enough? 0 1.0) 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1)
                     1))))
(cond
  (#f 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1)
                     1))))

(better-sqrt-iter 1.0
                  (improve 1.0 1)
                  1)
(better-sqrt-iter 1.0
                  1.0
                  1)
(cond
  ((better-good-enough? 1.0 1.0) 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1.0)
                     1))))
(cond
  (#t 1.0)
  (else
   (better-sqrt-iter 1.0
                     (improve 1.0 1.0)
                     1))))
1.0

Now let's try the same with new-if:

(better-sqrt 1) 
(better-sqrt-iter 0 1.0 1)

Scheme says you can evaluate procedures in any order. I Choose right to left!

(new-if (better-good-enough? 0 1.0) 
        1.0
        (better-sqrt-iter 1.0
                          (improve 1.0 1)
                          1))
(new-if (better-good-enough? 0 1.0) 
        1.0
        (new-if (better-good-enough? 1.0 1.0) 
                1.0
                (better-sqrt-iter 1.0
                                  (improve 1.0 1)
                                  1)))
(new-if (better-good-enough? 0 1.0) 
        1.0
        (new-if (better-good-enough? 1.0 1.0) 
                1.0
                (new-if (better-good-enough? 1.0 1.0) 
                        1.0
                        (better-sqrt-iter 1.0
                                          (improve 1.0 1)
                                          1))))
(new-if (better-good-enough? 0 1.0) 
        1.0
        (new-if (better-good-enough? 1.0 1.0) 
                1.0
                (new-if (better-good-enough? 1.0 1.0) 
                        1.0
                        (new-if (better-good-enough? 1.0 1.0) 
                                1.0
                                (better-sqrt-iter 1.0
                                                  (improve 1.0 1)
                                                  1)))))
;; goes on like this forever!

Notice that I never ever get to do any of the good-enough calls since all 3 expression need to be finished before the body of the new-if can be evaluated, whereas the built-in if evaluates the test expression first and then evaluates only one of the consequent expression or the alternative expression, based on the result of evaluating the test expression, and thus the recursion stops.