Blog Single

SICP Chapter 1.1, notes and (some) solutions in Clojure

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

Known as an all-time classic, the “Structure and Interpretation of Computer Programs”1 (called SICP for short) has been on my todo list for a long time. As it has been for many2 others3.

My plan is to go through this book myself, doing (most of) the exercises in Clojure (which I’m still somewhat new to) and blog about it. So, yet another SICP blog? Yes. This is mostly blogging to learn. My intention is to go ahead rather fast (keeping notes to the minimum) and focus on those exercises that I found most valuable (which is subjective of course). What might be different to other is that I write mostly from a Java developers view so if that is your situation too you might find some hints here.

I also provide my solutions in Github4.

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 organize and express our ideas. We have basically three mechanism to do that:

  • primitive expressions
  • means of combination to form compound elements from simple ones
  • means of abstraction by which compound elements can be names 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”. But 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 parenthese has to be an operator. Sounds trivial but can be confusing in the beginning.

Abstraction is accomplished by naming computational objects:

(def size 2)

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

(defn square [x] (* x x))

We can now combine any kind of complex procedures:

(defn sum-of-squares [x y]
	(+ (square x)(square y)))

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”, that is 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 imperative describe “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:

(defn p [] (p))

(defn test [x y]
  (if (= x 0) 0 y))

What happens if we execute:

(test 0 (p))

The function p is an endless recursive function that will lead to an infinite loop if executed. 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 just use

(defn new-if [predicate then-clause else-clause]
  (cond (predicate) then-clause
		:else else-clause))

Applying this to the iterative calculation of square:

(defn good-enough? [guess x]
  (< (abs (- (square guess) x)) 0.001))

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

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 can not 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 pases. 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):

(defn abs [n] (max n (- n)))

(defn square [x] (* x x))

(defn average [x y]
  (/ (+ x y) 2))

(defn improve [guess x]
  (average guess (/ x guess)))

(defn good-enough? [guess previous-guess]
  (< (abs (- guess previous-guess)) 0.001))

(defn sqrt-iter [guess previous-guess x]
  (if (good-enough? guess previous-guess)
	guess
	(sqrt-iter (improve guess x) guess x)))

(defn sqrt [x]
  (sqrt-iter 1.0 0 x))

Share this

Would you like to know more about functional programming?

Get my best content and findings on software development, coding skills and taking advantage of artificial intelligence. Expect to hear from me monthly(ish). Oh, and I hate spam the same way as you do.