adrianwong programmer · retired coal miner

SICP section 1.1 - the elements of programming

This is the first of what I hope to be a total of 22 posts on SICP - each post corresponding to a section of the book. In these posts, my aim is to discuss points and exercises that I find to be particularly insightful and/or interesting.

In other words, I’m plagiarising Eli Bendersky’s idea, but I won’t go to the depth he has with his posts.

So! Without further ado, here is SICP section 1.1!

Selected exercises

Exercise 1.05

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

; Normal-order evaluation:
(test 0 (p))
(if (= 0 0) 0 (p))
(if (#t) 0 (p))
0

; Applicative-order evaluation:
(test 0 (p)) ; Never terminates

Note #1: the definition of (p) is infinitely recursive.

Note #2: if is a special form. It first evaluates the predicate, then evaluates the then-clause if the predicate evaluates to #t, or it evaluates the else-clause if the predicate evaluates to #f.

Normal-order evaluation does not evaluate the operands until the values are needed, but will instead expand the expression until it only consists of primitive operators. With normal-order evaluation, (p) is never evaluated - once the expression is fully expanded, if evaluates to true and the expression returns a value of 0.

Applicative-order evaluation first evaluates the operator and operands, then applies the resulting procedure to the resulting arguments. This means that all sub-expressions are evaluated prior to procedure application. This includes (p), which proceeds to infinitely recurse.

Exercise 1.06

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

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

This exercise is similar to 1.05. if is a special form, new-if is not. new-if is a procedure, and thus follows applicative-order evaluation.

All sub-expressions of new-if are evaluated prior to procedure application - this includes sqrt-iter, which in turn evaluates its sub-expression new-if, which in turn evaluates its sub-expression sqrt-iter, which in turn evaluates its sub-expression new-if. This continues indefinitely.

Exercise 1.07

The tolerance value in the good-enough? procedure is set to a fixed value of 0.001, which is significantly large when computing the square root of a small value. Using some arbitrarily small radicand 0.0001, the squared value of the sixth iteration guess 0.03231 is within 0.001 of the radicand, resulting in the procedure returning this incorrect value instead of the expected 0.01.

For very large numbers, the question provides a hint: “arithmetic operations are almost always performed with limited precision”, i.e. the system has insufficient precision to represent comparatively small differences between large numbers. Using some arbitrarily large radicand 10000000000000, it can be observed after 25 iterations or so that calling improve continually returns the same value 3162277.6601683795. The squared value of this guess is not within 0.001 of the radicand, resulting in infinite recursion.

Implementing the alternative strategy for good-enough?:

; Replace fixed value tolerance with small % of guess
(define (good-enough? old-guess new-guess)
  (< (abs (- old-guess new-guess)) (* new-guess 0.001)))

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