This is the first post in my long-promised series of follow-up posts to The Education of a Programmer. I must have started this post at least 5 times, and each time I read the first sections of Structure and Interpretation of Computer Programs (SICP). I can’t really come up with words to do it justice—Abelson and the Sussmans describe the core concepts of computer programs in the most concise yet understandable way I’ve ever seen. Since I can’t improve on the original, these posts will just be a sort of running diary as I work through the exercises in the book. And without further ado…

Exercise 1.1

In this exercise, we are asked to manually evaluate each expression as if we were the interpreter.

<table summary="A table comparing my answers to the actual result from the interpreter">
  <caption>Results from <abbr title="Structure and Interpretation of Computer Programs">SICP</abbr> Exercise 1.1</caption>
  <thead>
    <tr>
      <th id="my-answer">My Answer</th>
      <th id="interpreter-result">Interpreter's Answer</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td headers="my-answer"><kbd>10</kbd></td>
      <td headers="interpreter-result"><kbd>10</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>12</kbd></td>
      <td headers="interpreter-result"><kbd>12</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>8</kbd></td>
      <td headers="interpreter-result"><kbd>8</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>3</kbd></td>
      <td headers="interpreter-result"><kbd>3</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>6</kbd></td>
      <td headers="interpreter-result"><kbd>6</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer">(this was sort of a trick question - the interpreter doesn't print anything when it evaluates <code>define</code> expressions)</td>
      <td headers="interpreter-result"></td>
    </tr>
    <tr>
      <td headers="my-answer">see above</td>
      <td headers="interpreter-result"></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>19</kbd></td>
      <td headers="interpreter-result"><kbd>19</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>#f</kbd></td>
      <td headers="interpreter-result"><kbd>#f</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>4</kbd></td>
      <td headers="interpreter-result"><kbd>4</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>16</kbd></td>
      <td headers="interpreter-result"><kbd>16</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>6</kbd></td>
      <td headers="interpreter-result"><kbd>6</kbd></td>
    </tr>
    <tr>
      <td headers="my-answer"><kbd>16</kbd></td>
      <td headers="interpreter-result"><kbd>16</kbd></td>
    </tr>
  </tbody>
</table>

Exercise 1.2

In this exercise, we are asked to convert a mathematical expression into prefix notation.

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

Exercise 1.3

In this exercise, we are asked to define a procedure that takes three numbers as parameters and returns the sum of the square of the two largest parameters. If you were starting from scratch, the solution would look something like this:

  (define
    (sum-of-squares-for-two-largest a b c)
    (cond ((and (< a b) (< a c)) (+ (* b b) (* c c)))
          ((and (< b c) (< b c)) (+ (* a a) (* c c)))
          (else (+ (* a a) (* b b)))))

But that’s not very clean. There’s too much repeated logic, and it’s not very readable; we need some abstraction. The most obvious abstraction is to create a square procedure that looks something like this:

  (define
    (square a)
    (* a a))

Using this new procedure, we can rewrite our sum-of-squares-for-two-largest procedure like so:

  (define
    (sum-of-squares-for-two-largest a b c)
    (cond ((and (< a b) (< a c)) (+ (square b) (square c)))
          ((and (< b c) (< b c)) (+ (square a) (square c)))
          (else (+ (square a) (square b)))))

That’s better, but there’s still room for improvement: we can create a sum- of-squares procedure that looks like this:

  (define 
    (sum-of-squares a b) 
    (+ (square a) (square b)))

Look at that: we created the same procedures that the authors walked us through creating earlier this chapter. Using our new sum-of-squares procedure, sum-of-squares-for-two-largest looks like this:

  (define
      (sum-of-squares-for-two-largest a b c)
      (cond ((and (< a b) (< a c)) (sum-of-squares b c))
            ((and (< b c) (< b c)) (sum-of-squares a c))
            (else (sum-of-squares a b))))

Exercise 1.4

In this exercise, we are asked to describe what the following procedure is doing.

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

This procedure is summing a and the absolute value of b. The (if (> b 0) + -) tells us that the procedure being applied to the arguments will differ based on whether b is positive or non-positive. When it’s non-positive, b will be subtracted from a, which is functionally equivalent to always adding the absolute value of b to a.

Exercise 1.5

Applicative-order

This will result in an infinite loop, because the interpreter will attempt to evaluate `p`, which is recursive and has no exit conditions Normal-order

This will return 0 because the interpreter will evaluate the `if` before deciding whether to evaluate `p` or return 0, and the results of the `if` will indicate it should return 0

Back to flipping out…