**Summary**: *Yet another SICP blog, but in Clojure and with a little bit of a Java developers’ perspective.*

The *“Structure and Interpretation of Computer Programs”*^{1} (called SICP for short) is considered by many^{2}^{3} as one of the most influential books in computer science.

The book uses LISP as the programming language and explores concepts from a functional programming viewpoint. In a series of blog post, I going to give a short review of what I consider the most important concepts (which is subjective of course) and will provide my solutions for a selected number of exercises in **Clojure**.

I also intend to write for developers with a *Java background*. If that’s your situation, you might find some hints here.

I also provide my solutions in Github^{4}.

Note: do yourself (and your software engineering career) a big favour and **go through the book yourself first**. If you only read one (programming) book in your life, choose SICP. Once you have read the corresponding chapter of each post *and* tried the exercises yourself, come back here to compare your results. I’m happy to discuss in the comments below anything you found out.

Today I start with chapter 1.1.

## 1.1 Elements of programming

Programming is not only a means to instruct a computer to perform a task but also a way for us to organise and express our ideas. We have three mechanisms to do that:

- primitive expressions
- means of combination to form compound elements from simple ones
- means of abstraction by which compound elements can be named and manipulated as units

The fundamental activity of programming is to *form complex elements from simple ones*. We have **data** (“*the “stuff” we want to manipulate*”) and **procedures** which are the descriptions of rules about how to manipulate data. The result is a (computational) **process** that gets executed.

The most basic element of a programming language is an expression.

```
42
```

Together with a primitive procedure we can form a compound expression, and we get to the infamous *prefix notation* of LISP:

```
(+ 41 1)
```

which can lead to any complex expression we like to:

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

**Java note**: *so yes, Clojure (Lisp) is this language with those many parentheses. As a Java developer new to Lisp, you might think (as I did in the beginning): “when in doubt, throw in some more parentheses, just to be sure”. However, this, of course, is wrong: (42) is not a correct expression (as it would be in Java), because in prefix notation the first element after the opening parentheses has to be an operator. Sounds trivial but can be confusing in the beginning.*

Abstraction is accomplished by naming computational objects:

Applied to procedure we get to **compound procedures** (functions):

We can now combine any kind of complex procedures:

To execute a procedure, the interpreter of a programming language has to reverse what we have combined from simple expressions by applying a *substitution model* to the procedure.

There are two ways to evaluate an expression:

**Applicative-order evaluation**: evaluate an expression*“from inside out”*, meaning, evaluate first the arguments and then apply**Normal-order evaluation**:*“from outside in”*or “fully expand and then reduce”

**“Procedure”** versus **“Function”**: SICP does not use the word “function” (as it is common in functional programming) but always “procedure” to distinguish the fact that a function is *declarative* knowledge in contrast to *imperative* knowledge. Declarative descriptions are concerned with “what is” whereas the imperative way describes “how to do” things. An example is the calculation of a square root function. In mathematical terms, the square root of x is y so that with y >= 0 the square of y is x. That does not serve us if we want to compute the result. Newton’s method helps here by calculating the result in successive approximations until we have a “good enough” result.

## Exercises

Partial solutions to the exercises of Chapter 1.1. For the full solutions, please see my Github repo.

### 1.5 Applicative-order test

Given following functions:

What happens if we execute:

The function `p`

is an endless recursive function that leads to an infinite loop. If a programming language evaluates in applicative-order (from “inside out”) the expression `(test 0 (p))`

evaluates `p`

first and won’t finish. Normal-order evaluation, however, would finish as evaluating from “outside in” would expand test and terminate (given that `if`

is a special form that does not use applicative-order evaluation, see next exercise).

### 1.6 Why `if`

is a special form

What if we don’t define `if`

in a special form and use instead following:

Applying this to the iterative calculation of square:

What will happen?

As in exercise 1.5 shown, Clojure (Lisp) uses applicative-order evaluation. `(new-if pre then else)`

gets evaluated by substituting all arguments first, including the `else`

argument. The predicate cannot prevent that. For `sqrt-iter`

that means that the recursion is going to end up in an indefinite loop.

### 1.7 Improving `sqrt-iter`

by providing a better `good-enough`

calculation

The `sqrt-iter`

procedure terminates when the `good-enough`

test passes. So far the condition was to measure the average error between the squared result and x. If this error is smaller than a threshold, we terminate. That fixed threshold, however, does not work for extreme cases. A better way is to measure the relative change between each iteration. If the change becomes minimal, we can stop calculating.

The solution is quite simple: we can re-use `good-enough`

, but instead of calculating the error of the square of the current result and x, we calculate the difference between the current guess and the previous one. We only need to add another argument that stores the previous guess (and set it to 0 in the beginning):