SICP 1.1: “The Elements of Programming”

(Structure and Interpretation of Computer Programs) 1.1

My 1.1 exercise solutions are also on Github here: https://github.com/bolducp/SICP/tree/master/exercises/chapter_01/1.1_exercises

I love the title of this first subsection — “The Elements of Programming”. I’m not sure whether the authors intended the reference to Strunk and White’s classic The Elements of Style text, but I believe that their analysis of the primitive elements, methods of combination, and means of abstraction in programming provide an apt parallel for the ways that Strunk and White describe the art of composition.

Points of Note

Section 1.1 is primarily about how computer languages provide a means for conceptualizing and structuring computer program to enable processes. The authors break this down language agnostically in simple terms as follows.

“the means that the language provides for combining simple ideas to form more complex ideas”:

primitive expressions, which represent the simplest entities the language is concerned with,

means of combination, by which compound elements are built from simpler ones, and

means of abstraction, by which compound elements can be named and manipulated as units.

Models for procedure application

• substitution model for procedure application
• applicative order versus normal order

Scheme Syntax

• naming & environment — function & variable definition
• conditional expressions and predicates
• nice succinct definition: “the word predicate is used for procedures that return true or false, as well as for expressions that evaluate to true or false”

1.1 Exercises

My solutions are provided in gray text blocks below each exercise question.

Exercise 1.1

Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.

(My answers inserted as comments to the right of each expression)

10 ;10(+ 5 3 4) ;12(- 9 1) ;8(/ 6 2) ;3(+ (* 2 4) (- 4 6)) ;6(define a 3) ;a(define b (+ a 1)) ;b(+ a b (* a b)) ;19(= a b) ;#f

(if (and (> b a) (< b (* a b)))ba) ;4

(cond ((= a 4) 6)((= b 4) (+ 6 7 a))(else 25)) ;16

(+ 2 (if (> b a) b a)) ;6(* (cond ((> a b) a)((< a b) b)(else -1))(+ a 1)) ;16

Exercise 1.2

Translate the following expression into prefix form.

(/ (+ 54(- 2 (- 3 (+ 6 (/ 4 5)))))(* 3(- 6 2)(- 2 7)))

Exercise 1.3

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

(define (square x) (* x x))(define (sum-of-squares x y) (+ (square x) (square y)))(define (sum-two-largest-squares x y z)(if (> x y)(if (> y z) (sum-of-squares x y) (sum-of-squares x z))(if (> x z) (sum-of-squares x y) (sum-of-squares y z))))

;; test(= 34 (sum-two-largest-squares 3 2 5))

Exercise 1.4

Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

(define (a-plus-abs-b a b) ((if (> b 0) + -) a b))

The if-statement returns either the primitive procedure - or the primitive procedure +, depending on whether b is greater than 0. This procedure is then applied to the operands a and b.

Exercise 1.5

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

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

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

With applicative-order, the expression will try to evaluate all of the operands so that the procedure is fully expanded before it is reduced. Thus, it will try to evaluate p, which just calls itself in a recursive loop, and test will never end up getting invoked.

With normal order, p will never be evaluated (and thus will never have the chance to enter into its infinite loop), because the first condition of the if-statement in test (x = 0) evaluates to true and the procedure returns 0 without calling p.

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:

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

I had some trouble with this question at first, because I was missing what the question was really trying to ask. I thought that the comparison under discussion was using "cond" as opposed to "if", and this does, in fact, work:

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

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

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

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

(define (good-enough? guess x)(< (abs (- (square guess) x)) 0.001))

This code above, which replaces the "if" statement with the "cond" statement in `sqrt-iter` works.

However, the question is actually asking about what happens when you replace the if-statement with a custom designed function, which fails because since Scheme is an applicative-order language, it evaluates all of the arguments as soon as a function is called. Since `new-if` is a procedure, all of its subexpressions get evaluated as soon as it is applied, before it acts upon the operands provided. This includes a call to `sqrt-izer`, which then recursively calls `new-if`, and creates an infinite loop.

Exercise 1.7.

The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers.

An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?

Here's an example of the `sqrt` function not working as well for very small numbers: (sqrt .00004) returns .03167509508023218, instead of the accurate 0.02 value. This happens because, currently, `good-enough?` returns true when the our original number and the square of our next guess have a difference of less than 0.001.

For understanding why calling our `sqrt` function on very large numbers never returns a value, I had to look for help online. It seems that this is a result of losing precision for storing very large floating point numbers.

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

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

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

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

(define (good-enough? guess old-guess)(< (abs (- guess old-guess)) 0.001))

(sqrt 9999999999998)(sqrt 0.001)

; Yes, this does seem to improve for both very large and very small numbers.

Exercise 1.8.

Newton’s method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value

(x/y^2 +2y) / 3

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In Section 1.3.4 we will see how to implement Newton’s method in general as an abstraction of these square root and cube-root procedures.)

(define (cube-root x)(cube-root-iter 1.0 0 x))

(define (cube-root-iter guess old-guess x)(if (good-enough? guess old-guess)guess(cube-root-iter (improve guess x)guessx)))

(define (improve guess x)(/ (+ (/ x (square guess))(* 2 guess))3))

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

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

(define (good-enough? guess old-guess)(< (abs (- guess old-guess)) 0.001))

(cube-root 25)