Some time ago, I got a copy of the first edition of SICP on eBay. It’s a fascinating book, for many reasons. I’ve been slowly working through it in fits and starts, but I’ve decided that this year I’m going to really focus on finishing this book and doing all of the exercises.

Therefore, for the sake of completeness, I’d like to backtrack a bit and record my work on SICP exercises 1.1 through 1.4. My goal is to be able to do every single exercise from SICP (1st ed.) and explain it here. (You can see all of the SICP-related posts here.)

For each of the exercises below, I’ll first provide the problem text from the book, and then my answer (or attempt at an answer).

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

Here are the expressions, followed by my answers.

Expression | Result |
---|---|

10 | 10 |

(+ 5 3 4) | 12 |

(- 9 1) | 8 |

(/ 6 2) | 3 |

(+ (* 2 4) (- 4 6)) | 6 |

(define a 3) | UNDEFINED |

(define b (+ a 1)) | 4 |

(+ a b (* a b)) | 19 |

(= a b) | #f |

(if (and (> b a) (< b (* a b))) b a) | 4 |

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

### Exercise 1.2

Define a procedure that takes three numbers as arguments and

returns the sum of the squares of the two larger numbers.

Here is the procedure definition, along with a couple of helpers.

(define (square x) (* x x)) (define (sos x y) (+ (square x) (square y))) (define (sos-largest-two a b c) (let* ((sorted (sort (list a b c) >)) (large (first sorted)) (medium (second sorted))) (sos medium large)))

### Exercise 1.3

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

An interpreter that uses applicative-order evaluation will enter an infinite recursion.

An interpreter that uses normal-order evaluation will return 0.

The reason for this is that an applicative-order interpreter follows the usual “evaluate arguments, then apply” recipe. I believe this is also known as “call-by-value”.

The normal-order interpreter never gets around to evaluating the second argument to `test`

because it doesn’t need to (and of course, once inside `test`

, the `if`

form behaves as in the problem description).

### Exercise 1.4

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)

0Delighted, 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.

Running this procedure exceeded MIT Scheme’s maximum recursion depth. I decided to trace the procedure to better see what was happening (note that I renamed the procedures to `alyssa-sqrt-iter`

and `alyssa/sqrt`

to differentiate them from the original versions).

(trace alyssa-sqrt-iter) ;Unspecified return value (alyssa/sqrt 100) ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 1. ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 50.5 ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 26.24009900990099 ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 15.025530119986813 ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 10.840434673026925 ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 10.032578510960604 ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 10.000052895642693 ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 10.000000000139897 ;; 100] ;; [Entering #[compound-procedure 12 alyssa-sqrt-iter] ;; Args: 10. ;; 100] ;; ... et cetera ... ;Quit!

The last line, where the arguments to `alyssa/sqrt-iter`

are 10 and 100, repeats hundreds of times. Even though the call to `good-enough?`

(shown again below) returns `#t`

, `new-if`

still ends up evaluating the `else-clause’ and causing the linear recursion instead of returning the current value of `guess`

(as it should).

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

This problem illustrates the reason we need `if`

to be a special form: we need it to exhibit “short-circuiting” behavior, i.e., we need it to avoid evaluating all of its arguments.