This is a series of posts related to SICP exercises, in continuation of a previous post.

The chapters that lead to the exercises are:

1. Building Abstractions with Procedures

   1. The elments of programming.

      7. Example: Square Roots by Newton's method (1 - 6 covered in previous post)

The chapter starts with a case for calculating square roots.

The most common way is to use Newton’s method of successive approximations, which says that whenever we have a guess y for the value of the square root of a number x , we can perform a simple manipulation to get a better guess (one closer to the actual square root) by averaging y with x/y.

Example:

Using the above, we get to the following strategy:

;; Missing procedures will be created later.
(define (sqrt-iter guess x) 
  (if (good-enough? guess x) 
    guess 
    (sqrt-iter (improve guess x) x)))

Now we need another procedure to improve our guess:

;; Reference to the example table.
(define (average-of-two x y) 
  (/ (+ x y) 2))
  
(define (improve guess x) 
  (average-of-two guess (/ guess x)))

The good-enough? procedure is a measure of how close the guess is to the square of original number. We can express this as:

;; precision is a metric of closeness required for the guess 
;; to be the square root of x.
(define (good-enough? guess x) 
  (< (abs (- (square guess) x)) <precision>))

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

Finally we can have:

;; A default guess of 1.0 is chosen.
(define (sqrt x) 
  (sqrt-iter 1.0 x))

There is some emphasis on being able to express the above without the need of loops, compared to other standard languages.

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:

;; Implementing `if` to work using `cond`
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
  (else else-clause)))

Eva demonstrates the program for Alyssa:

;; Some tests
(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:

;; The final implementation of sqrt-iter
;; assuming other procedures are same as above.
(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.

Answer: new-if is a procedure and if is a special form. That means, the sqrt-iter would be evaluated differently.

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

We have a problem here, if behaves lazily, so it will first evaluate the predicate (good-enough? guess x) first and the evaluation of consequent or alternative will be deferred until then.

Instead of that, we have new-if which is a procedure and not a special-form causing all the arguments to be evaluated after the operator. This would cause the (sqrt-iter (improve guess x) x) to be evaluated irrespective of the output of (good-enough) as per the applicative order of procedures, leading to a non-terminating condition.

if follows normal order of evaluation and hence, the arguments will be evaluated depending after, and, on the output of the predicate. The stopping condition being predicate returning true.