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
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...June 29, 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...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. That’s what the additions to the package will add. The new definitio...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, and then term list consisting of the re...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. With the ability to have a local state in our programs, our approach to...April 2, 2017
Ex. 3.1 Since the accumulator gives a value upon execution, our procedure needs to produce something that is itself a procedure. To keep track of the value, I used a variable sum that is adjusted using set! on each call to the accumulator. Because sum is the argument originally passed to make-a...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...July 16, 2017
There are only two exercises here. The first one is an extension to code from previous exercises (Section 3.1.1 specifically). If you have not completed all the exercises for that section, you’ll need to do so, or download the solution file. The tests also rely on check-eqv? defined as it...August 6, 2017
Exercise 3.7 This one doesn’t require modifying the account creation that already exists; what we’ll do instead is delegate any actions to the original account. Since that account is already considered to exist when we create a joint one, there is no need to do anything in make-joint...October 15, 2017
The exercises in Section 3.2, and some in Section 3.3, do not involve, or at least do not require, any code that needs to be verified by testing. (Section 3.2.1 does not even have any exercises.) The procedures are largely meant to be computed manually. Therefore there aren’t going to be a...October 22, 2017
In the following diagrams, the procedure objects are only shown once, and then omitted in later diagrams. Those procedures are still there. It’s just not really necessary to show them each time, as that part of the diagram does not change. In our model, a procedure (the two-circle symbol wi...October 28, 2017
Much like 3.2.2, this is another section with a single exercise involving environment diagrams. There will be a solution file with included code, merely to demonstrate the equivalence of the procedures. There isn’t much to say in advance of the exercises, so I’ll go over in more deta...November 5, 2017
Ex. 3.10 To complete a definition, we must determine the value to assign to our variable, which in this case is named W1. To get that value, a call to make-withdraw is made. This creates a new frame for that procedure call. In the course of make-withdraw, the let statement creates a lambda and ...November 19, 2017
Section 3.2 finishes off with one more single exercise. It’s another one that relies on working by hand and thinking through the environment structure. There are no files to test, but there will be a bunch of diagrams to look at. Exercise 3.11. We’re going to go through this one line ...February 21, 2019
The majority of the exercises in this section are meant to be done manually, which is to say the results are to be worked out without using the interpreter. In most cases, then, checking the code with the interpreter is only useful verification of a correct result. The file will include the expre...March 10, 2019
Ex. 3.12 First, let’s consider what happens with the constructor version append. It doesn’t change its argument, so x will thus remain unchanged from when it was created. Since x is a list of the symbols a and b, the remainder of the list after the car is just the list (b). Here’...April 28, 2019
Now that we have some understanding of the pointer structure of lists, and how to change them, the next few sections present concrete applications. This section (and the next) will cover data structures that can be created by allowing lists to be mutated. Something hinted at near the end of this ...May 12, 2019
Ex. 3.21 Ben’s primary confusion seems to be in thinking that multiple references to something are multiple instances of that thing. Although, as Eva points out, he additionally may not realize that what’s being printed to the screen is not a list representing the queue. After all, th...August 11, 2019
We’ve finally reached the point referred to by the text way back in Section 2.4.3, when data tables were first used. We can now find out how to make them. Something to note here is that the table used back then (for the generic arithmetic system) had ‘operation’ and ‘type&...October 9, 2019
Ex. 3.24 Since we are just replacing the equal? call in assoc with our own test, the natural solution is to write a new version of assoc that does that. (define (assoc-with-test key records equality-test) (cond ((null? records) #f) ((equality-test key (caar records)) (car records)) ...November 8, 2019
This section presents us with another system of moderate complexity. It’s one that is difficult to test without having most of the system in place. Luckily for us, we don’t actually have to implement or test the agenda system itself; we’re only creating and working with the comp...December 1, 2019
Ex. 3.28 By using the logical-or procedure and assuming a defined constant or-gate-delay, this one is nothing more than copying the and-gate procedure and replacing ‘and’ with ‘or’. It doesn’t need to be any more complicated than that. Ex. 3.29 The solution to this e...January 19, 2020
Even though this constraint system is only used for this section, it is still a complex system, and testing our components requires us to make a fairly large sets of checks. Moreover, there will be frequent points during the tests that we’ll need to reset or somehow clear the system, so tha...January 31, 2020
Ex. 3.33 To determine the average of two values, we add them together and divide by two (since there are two values we are averaging). So one side of the formula is the sum of the two values a and b, which is also equal to the average multiplied by two. We can use an adder block to produce the s...February 16, 2020
There is only one exercise in this first section on concurrency, and no coding is required to solve it. It’s a mental exercise, and the second part is particularly open-ended. This post will be the only one for this section. As there’s no real need to introduce the exercise, the remai...May 3, 2020
This section is fairly lengthy, yet it still kind of rushes through one of the more important topics in computer science. One of the ways SICP really shows its age is that it does not cover concurrency in as much depth as the topic deserves, especially in consideration of how modern processors wo...June 21, 2020
Ex 3.39 First off, we can see that this is similar to the fully serialized approach, and does not affect the situation where one process executes in its entirety before the second one. That gives the result of either 101 or 121 to begin with. We then have to consider how the processes can interle...August 9, 2020
While this section is a brief one, and merely an introduction to the ideas of streams and delayed procedures, there is something important missing. It’s not possible to fully test our answers without an element of the Scheme language that the book never really reveals. While we can get thro...September 6, 2020
Ex. 3.50 To fill in the blanks, let’s take a look at the original (single-stream) implementation of stream-map from the text. (define (stream-map proc s) (if (stream-null? s) the-empty-stream (cons-stream (proc (stream-car s)) (stream-map proc (stream-cdr s)) ...October 4, 2020
This section continues the trend of exploring how streams work, but gets a bit more into their application, especially with the inclusion of exercises involving power series. If you haven’t ever studied this part of mathematics, it’s going to make some of these problems much harder to...November 1, 2020
Exercise 3.53 Here is our mystery stream: (define s (cons-stream 1 (add-streams s s)))The first element is of course going to be 1. Then each element after that is the sum of the stream with itself, starting from 1 again. That means the second element is the first element added to itself, and th...December 13, 2020
This section continues to delve into the power (as well as the perils) of processing data using streams. It is also one that is quite difficult to test directly, since it’s about comparing different approaches and fixing subtle mistakes. Some of the exercises involve modifications made for ...December 27, 2020
Exercise 3.63 In the original version of sqrt-stream, a single stream is defined. It then maps onto the exact same stream, which is named guesses. In Louis’s version the stream is mapped to a call to the procedure sqrt-stream which constructs a stream and returns it. That means that an enti...May 2, 2021
We are still looking at infinite streams. The last section covered a lot of ground in the use of infinite streams, whereas this one focuses in on one particular aspect. Namely, the delayed evaluation that is critical in allowing streams to be effectively infinite, without causing programs to end ...June 5, 2021
Exercise 3.77 A straightforward way to solve this one is to just wrap the old version of the integrator with a let statement that forces the delayed integrand. There may be alternate approaches, but since we already have a version that works with a non-delayed argument, it may as well be re-used....July 11, 2021
This is a brief section that continues the theme of practical uses for streams. This time there isn’t anything particularly intricate related to internal workings of the stream. Instead, it’s leading toward a particular idea, of a stream that can create the same effect as assignment t...July 25, 2021
Exercise 3.81 The basic form of the solution is to take the rand procedure that accepts an argument, and use stream-map to apply it to the input stream. Minor adjustments need to be made so that the requests are accepted in the format used by the stream. To make a version that does not produce o...