This is a record of my working through Structure and Interpretation of Computer Programs, a classic text on programming. Each section covers the exercises included in the text. Actually, I have decided to allow one exercise per chapter to be skipped. The sort of questions I skip are usually the very open-ended ones, or those that seem to add little to what I’ve learned. As mentioned, there are only a very small number of these.
My posts are meant to help anyone studying the book on their own, as I did. I try to provide a testing-based approach, to give some context in what the exercises should try to do. I always encourage anyone solving them to add to what I’ve done. Hopefully what I’ve provided is a good starting point for you.
Generally each set of exercises is introduced without indication of how to solve them, but may include a discussion of how to test possible solutions. Just a link to the exercise set on Github is provided, with some context of what’s being covered. A second post on the section (the ‘solution’) will discuss the exercises in more detail.
The whole repository can be found at http://github.com/parzival/SICP.
July 2, 2012
A few years back I decided to learn a bit more about computer programming. While I’ve taken several programming courses, they were mostly designed to teach a language with a few additional concepts thrown in incidentally. But I never had formal instruction in the underlying principles of ...July 5, 2012
The first section of the book to include exercises is 1.1.6. The very first ones, although I have included them, are probably better to enter in on your own separately, in order to see what your Scheme interpreter gives as a response. The later ones get into actually writing a few short procedu...July 12, 2012
Ex. 1.1 Nothing really to do here but enter the lines and see what happens. I’ll mention here that I’m using Dr Racket as my interpreter. Racket is a language based on Scheme, although not a strict superset. At this point the differences will not be noticed, but it will come into pla...July 13, 2012
This section deals with results that are floating point numbers. Floating point math on computers is actually a fairly complex subject. The testing section gets into this a little bit by comparing the results for different computational methods. The procedure name is fixed in order to allow for...July 18, 2012
Ex. 1.6 The problem with Alyssa’s definition is that the clauses are now arguments of her procedure. With applicative order, they will both be evaluated regardless of what the predicate’s truth-value is. That’s not what’s expected in most conditional programs. In the par...July 20, 2012
This is the start of a new subsection, looking more at how procedures do the work they do. Most of the problems still have a math focus, so the answers are easy to check. However, much of the work involves looking at how things are processed and describing it. That is the case with the two sho...July 28, 2012
Ex. 1.9 These two procedures are pretty simple to understand. They perform addition when only the increment or decrement operation is available. This particular approach is of mild historical interest, since that was sometimes how it was done with some primitive circuits, and possibly even some...August 7, 2012
More math problems, which can be solved fairly simply. This section looks at the effect of different approaches on how much computation is needed. I’ve put in a few test numbers that may take a really long time to compute. It’s entirely possible your computer is much faster or slowe...August 16, 2012
Ex. 1.11 Here are the two solutions, to help draw the comparison. First, the recursive version: (define (fun n) (cond ((< n 3) n) (else (+ (fun (- n 1)) (fun (- n 2)) (fun (- n 3)) )) ) )This is concise and quite clearly shows how the recurrence relation works. It’s practic...August 24, 2012
This section, on orders of growth, is merely a page in the book. But it’s the barest of introductions to a complex and much-studied subject in computer science. These two exercises are among the trickiest in the whole book, although they involve essentially no programming. The solutions a...August 30, 2012
Ex 1.14 The first part, namely the graph, is fairly easy to produce, if a bit tedious. Simply go through each part of the procedure and add to the tree whenever there is a new call to cc. Naturally I did this by hand on paper first, but I’ve provided a more readable version below. ItR...September 22, 2012
This section continues to look at orders of growth, this time by comparing a few algorithms. Much faster ways to solve a problem can often exist, although quite often the code involved is more complicated and harder to understand. Since there are several ways of doing the same thing going on, an...September 28, 2012
Ex 1.16 The mathematical solution to this one is relatively easy, as it can be based on the existing fast-expt procedure. The iterative one just stores the cumulative result in the a argument instead of backing it out by recursion. To test the results, we compare the answers we get using the ori...October 8, 2012
After some lengthy exercises in the past few sections, this one’s a bit of a break. Just one example to look at. It’s comparing normal and applicative order, and if you didn’t work it out before, it’s worth figuring out just what order your interpreter is using. Exercise...October 19, 2012
Ex. 1.20 Working this problem shows how lengthy a simple algorithm can become when recursion is involved. Euclid’s Method is easy to apply in steps, but the processing involved in computing it shows that more steps are required than is often apparent. Even in my solution, I’ve skippe...November 9, 2012
This section’s questions get into the details of the time taken by a computation. As one might expect, it’s going to be something that’s very processor-dependent. It also will end up being slightly different for different flavors of Scheme, because they may have different ways ...November 16, 2012
This whole section is one of the book’s several in-depth examples. As such, it tends to use concepts and require testing techniques that might go a bit beyond what has been done in other sections. But it is good to delve into a practical application now and then. Don’t be worried if...January 2, 2013
This section introduces the idea of procedures that work with other procedures as arguments. Scheme makes it easy to do this, since the arguments to a procedure can be anything, as long as it is used correctly within the procedure. The exercises work with several math functions which are called ...April 16, 2013
Ex 1.29 Writing the Simpson’s Rule solver isn’t all that difficult. Given the topic of discussion, it’s clear that using sum is the desired approach. Computing a single term of the series is perhaps a bit more complicated, but with that written, it’s still only one line ...November 3, 2013
This is a very brief section with only one exercise, and it’s actually just something to test the interpreter with. Therefore there is only an exercise file for this section, and I’ll discuss the results right here. So if you’d rather figure it out yourself, go and play with i...November 19, 2013
There is more math to be done in this section, but there isn’t that much mathematical knowledge required to work the exercises. Still, if you are unfamiliar with continued fractions, it might be worthwhile to brush up on them. Solutions to a problem by finding a fixed point is also brough...November 25, 2013
Ex 1.35 Demonstrating that the transformation is equal to φ is easily done. The book definition already described φ as satisfying the equation φ 2 = φ + 1. Dividing this equation by φ yields an expression with φ itself on the left side, which is equivalent to the transfo...December 13, 2013
This section continues to deal with numerical solvers, with some slightly more complex methods. They’re also allowing a bit more abstraction, which can prove quite useful. Functions are now being passed around not just as arguments but as the result of procedures. The result of the proce...December 18, 2013
Ex 1.40 This is straightforward, and merely requires an understanding of what the Newton’s method solver requires. It needs the calculation of the function, or rather a procedure that calculates the value of a function. This means that the cubic procedure must return a procedure that take...December 23, 2013
Chapter 2 begins with just one exercise. The procedures are already written for you, and the exercise is in making a modification that produces more sensible results. Included in the file are various test values, but as with any set of tests, feel free to try your own set of numbers. The require...December 30, 2013
Ex 2.1 In order to cleanly handle negative values in rational numbers, all possible cases in which negative values may appear must be considered. Those cases are: Both numerator and denominator are positive. The numerator is negative, the denominator is positive. The denominator is negative, ...January 7, 2014
The exercises continue to be fairly short, with only two this time. These can build on each other, although given that we’re dealing with abstractions, they don’t necessarily have to. The use of the abstractions and the suggested names for the procedures to implement allows for easy...January 30, 2014
Ex 2.2 Certainly there are any number of ways to represent a line segment that is defined by two points, but the problem statement itself practically gives the suggestion of using a pair. Which is probably the simplest, and works well for our requirements. Points, as well, can be stored in the s...February 10, 2014
This section gets to some of the more philosophical ideas about data. Exactly what a piece of data is, and what it means to process it can lead to rather interesting notions of representation. Church numerals arose as a tool in the lambda calculus, which is a means of performing operations that...February 17, 2014
Ex 2.4 To verify this for ‘any’ x and y, we need to understand how this process works. Although punching in a few possible values and examining the results is by no means a complete verification process, it can be a useful starting point. So, for a first pass, a handful of objects o...March 27, 2014
This section is marked as an ‘Extended Exercise’, which means an in-depth exploration of a particular system. These will include the ideas presented in the previous section, but with a focus on more practical applications. In this case, we want a system for dealing with interval ari...April 7, 2014
Ex 2.7 There’s nothing particularly difficult here. The interval is a pair, and getting the bounds is using either car or cdr to get the proper bound. Technically the constructor isn’t properly specified, as we don’t know what a or b is meant to signify. The intuitive solutio...May 7, 2014
After tackling pairs, we move on to a data structure that is even more useful, the list. Certainly if you are working in the LISt Processing language (or in a dialect such as Scheme), you expect that comprehending how lists actually work is important, and you wouldn’t be wrong. That said,...May 11, 2014
Ex 2.17 This one isn’t too hard, but there is an important detail that needs to be observed. The title of the procedure is last-pair. Yet it only returns a single element from the list. The function is required to return a list, not just the last member of it. The pair in question, the...June 25, 2014
Having established the useful building block of the list, we move on to more complex structures. This section shows how to build and use a tree and similar structures. We start by looking at how they’re actually built (using lists), and then get on to using them. For the later exercises ...July 2, 2014
Ex 2.24 The interpreter expression is easy to generate. As a box-and-pointer diagram, here’s what it is: One quick check that can be done using a box-and-pointer diagrams is to count the number of lists. We know from the expression that, with three parenthesized statements, three lists mu...July 7, 2014
From abstract data structures that can be manipulated at a higher level than just the lists or pairs, we move on to common interfaces more generally. As detailed in the text, finding the connection between similar problems that allows them to be treated with a common interface requires a certain ...July 31, 2014
Ex 2.33 These aren’t overly complex statements, and they give a good idea of how these list manipulations can all be reduced to the simple operation of building up a new list after processing one element at a time. It’s worth realizing that because accumulate works recursively, the ...September 18, 2014
This section presents an “example”, which is a more practical application of the methods studied in the text so far. Often the examples require a bit of extra effort to fully implement, and this one is definitely no exception. Most obviously, we need a simple way to display graphics...September 29, 2014
If you don’t understand how the SICP picture library package is being used here, be sure to read the Exercises segment for this section first. Ex 2.44 The exercise itself tells you exactly what to do: pattern this one on right-split, but with below and beside swapped. This works by recursi...January 31, 2015
In this section we get into an extremely useful new form of expression, the quoted form. Having some form of this allows a wide variety of expressions to use. Rather than having only lists of numbers or already-defined variables, we can use quoted lists. But the more valuable effect is that we ...February 8, 2015
Ex 2.53 There’s little to figure out here, and the answers are found by observation. One concept apparently emphasized here is that quotation ends up applying to everything within its expression. It makes nested lists easy to write (as in the cadr and memq examples) without having to repe...February 15, 2015
After the introduction of symbolic data, we jump right into one of several examples of how to use it. In this section, we create a symbolic differentiation processor. It seems like quite When I first encountered this section, I have to admit I was quite impressed with how easy it is to create a ...February 23, 2015
Ex 2.56 The selectors for exponentiation don’t present much of a problem. Using the suggested notation, you’d want the expression to look like (** base exponent), and the selectors use car and cdr to get the proper part of that. The constructor should have the built-in rules that ha...March 1, 2015
In this section we consider another Example, this time with sets. It considers several approaches to abstract data representation. We’re not focusing on symbols now, just considering them as something that we can use. This is an integration of several of the ideas we’ve seen so far...March 8, 2015
Ex 2.59 Taking the union of two sets isn’t too difficult. We simply pick one set, and add every member of the other set to it. As long as we use adjoin-set to add the elements of the other set, we won’t need to worry about duplicate items. Ex 2.60 Allowing for duplicate elements let...April 7, 2015
This last example for the section covers the topic of encoding and decoding messages. It introduces the subject of how to pack information, or data, efficiently. Symbolic data allows the use of words, letters, or really anything to be the target of the code. The testing in this section isn̵...April 7, 2015
Ex 2.67 This involves simply demonstrating the result of an already-written operation. There’s nothing to do other than make sure to use the correct arguments for the procedure. Its primary purpose is to be used as a test for the next exercise. Ex 2.68 There are several ways to tackle the...April 26, 2015
There are no exercises for this section, but that’s no reason not to examine the code. Even with it already written and functioning, it’s an opportune moment to talk more about testing. This section happens to be a great example to use. It has the same interface with different under...May 3, 2015
The subject of this section is the creation of a looser abstract system for complex numbers that can accomodate both implementations previously used. While the addition of tags requires a bit more computation time, it allows for greater flexibility. We’ll be getting a lot of use out of ty...May 16, 2015
Now that we’ve developed the abstract system through several sections, we come to more formalized methods of abstracting an interface. The approaches used here are data-directed and message-passing. While these terms themselves don’t see broad usage, the concepts are both used in ma...May 24, 2015
Ex 2.73 The data-directed derivative operation simplifies the deriv procedure, and allows for a more modular system. Instead of having a conditional statement that must be modified every time a new operation is added, all expressions involving operators are handled by the dispatch table. This m...June 28, 2015
In this section we’re building up the components of the previous section into a system with a generic interface. This system will be gradually altered over the course of 2.5, but its core functionality will remain the same. As we’ll see, the interface will largely be unchanged as wel...June 28, 2015
This is an extra post in which I’ll discuss some more advanced testing procedures, which will be used in the next section. It requires one special type of function not handled in the book, but otherwise only uses concepts we’ve already covered. While this testing system is not as full...August 9, 2015
Ex. 2.77 The procedure magnitude is defined to call apply-generic with the argument given, which happens no matter what the number is. The error occurs because it cannot find an entry for magnitude with the type complex. The newly-added definitions are rather simple. All they do is call magnit...August 30, 2015
In this section the generic arithmetic package continues to expand. It will now allow operations that mix the types of numbers allowed. While the system works nearly identically to the one in 2.5.1, there are some new types that the exercises rely on. To avoid crowding the definitions into the ...May 29, 2016
Ex. 2.81 Adding the ‘self-coercion’ routines causes a problem. If a matching procedure is not found in the table, apply-generic will attempt to coerce the arguments. If a coercion exists, even if it coerces the type to its current type, then a new search for a procedure will commenc...August 7, 2016
In this section the generic arithmetic system gets stretched even further, by adding the ability to work with polynomials. It’s not that hard to treat polynomials as ‘numbers’ in this manner, as long as we keep to the restrictions in the book. The generic nature of the system a...August 14, 2016
Ex. 2.87 Adding a test for zero is straightforward for polynomials. We simply check all the terms. If every term’s coefficient is =zero?, then the polynomial itself is considered to equal zero. My procedure checks the first element in the term list, along with the term list consisting of ...September 15, 2016
This extended exercise will require changes to several parts of the arithmetic system. The polynomials will see the most extensive change, but the rational numbers will change and other parts (such as the integers) may also require modification. There are several approaches to take, and the nec...September 16, 2016
Ex. 2.93 The main part of the exercise is simply changing all operations within the rational package to use the generic procedures instead of built-in Scheme procedures. Each + gets replaced with add, * with mul, etc. This change only needs to take place in the internal procedures like add-rat, d...March 12, 2017
In Chapter 3, a completely new concept is introduced — storing values to create a local state. This changes our programs so that they have memory and can change over time. As we’ll see, that has benefits and drawbacks. For these exercises, the tests are back to a simpler form. They won...April 2, 2017
Ex. 3.1 Our procedure needs to produce something that is itself a procedure, since the accumulator adds the value upon execution. To keep track of the value, I used a variable sum that is adjusted using set! on each call to the procedure that is returned. Because sum is the argument originally ...May 28, 2017
While this section is mainly about the benefits of assignment, once we start to test our procedures, one drawback is almost immediately apparent. An effect of variable assignment is that we can easily have functions where the output can vary for the same input, at times even randomly. The probl...June 11, 2017
Exercise 3.5 This exercise has essentially two parts: the integration procedure itself, and then the means of applying it (which will also test that it functions correctly). I’ll discuss them separately. Since we are using the Monte Carlo approach for integration, we first have to set up th...