Tech Book Face Off: How to Design Programs Vs. Structure and Interpretation of Computer Programs

After reading and reviewing dozens of books on programming, software development, and computer science, I've finally come to a couple of books that I should have read a long time ago. I'm not quite sure why I didn't read these two books earlier. Distractions abound, and I always had something else I wanted to read first. I still wanted to see what they had to offer, so here I am reading How to Design Programs by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi and Structure and Interpretation of Computer Programs by Harold Abelson, Gerald Jay Sussman, and Julie Sussman. As I understand it, these books are meant to introduce new students to programming so not reading them until now will probably make it difficult to accurately critique them from the perspective of the target audience. I'm still going to give it a try.

VS.

How to Design Programs

While I have read many programming books as ebooks on my Kindle, this is the first book I've read as an online book. It's available in print version, but the online version looked nicely formatted and was heavily cross-linked, which was quite helpful. Also, since the book was right alongside my code editor, I could easily try out the problems and copy-paste code into the editor to run it.

The programming language used in this book as the vehicle for learning was a variation on Scheme called BSL (Beginning Student Language) that had heavy restrictions on the language features available for use. For example, lists could not be constructed with (list <list of elements>) or '(<list of elements>), instead needing to be built up from (cons <element> <list>). These and other features were added with BSL+, ISL (Intermediate Student Language), and ISL+ as the reader progressed through the book.

I was not a big fan of this approach, since it was tedious to learn the wrong way first (or at least the way nobody actually writes code) and then learn the right way that also makes more sense. Starting with the reduced forms of the language didn't add anything to the explanations, and it mostly served as a point of frustration as the reader was forced through unnecessary tedium until the nicer language features were introduced. It was also not clear by the end that ISL+ was equivalent to the full Scheme programming language, so by the time the student reached the end of the book, they wouldn't even be sure that they had learned a real programming language.

The book was quite ambitious, since learning how to design programs starting from square one actually involves learning three almost distinct things at once: the syntax of a programming language, how to write code, and how to program. The first task is about learning what a programming language is, what keywords and punctuation are available, and what it all does when put together in the correct structure. This task alone can be overwhelming for the new student. Then, the second task, learning to write code, involves taking a small, well-defined problem statement, thinking up a solution to it, and translating that solution into code that can execute in the newly learned programming language. Normally, once some part of the language has been learned, the first two tasks can be done together, and they support each other as the student practices them both.

The third task, learning how to program, is a much deeper activity that takes a much longer time to become proficient. Learning how to program is not just about solving bigger problems that may not be self-contained or well-defined. It's about learning how to organize all of the required code to solve the problem in a way that makes that code easy to understand, is less likely to suffer from bugs, is testable (and tested), and hopefully is flexible and extensible. I'm not convinced that this book taught this much more advanced skill, or at least not thoroughly.

The book starts out with a little prologue chapter entitled "How to Program." It gives a short introduction and a few examples of how to write some simple programs in BSL, and here the authors try to get the reader excited about what they'll be learning in the rest of the book. I had some misgivings about it. They have a strange way of trying to connect with the reader by disparaging various subjects that the reader is likely taking in school, or at least has fresh memories about, like physics:

Physics?!? Well, perhaps you have already forgotten what you learned in that course. Or perhaps you have never taken a course on physics because you are way too young or gentle. No worries.

I don't understand this kind of writing. It's not cool and it's not helpful to pretend to joke along with students about how much physics or mathematics or any subject sucks. It drives me nuts. Why can't we encourage students to take more of an interest in these subjects by showing how the knowledge can be useful, interesting, and dare I say, fun?! Thankfully, these comments don't continue in the rest of the book, but it's still irritating that they subtly perpetuate this anti-learning bias. It ended up coloring my opinion of the book in a negative way.

The rest of the book is split into six major sections with "intermezzos" between each section. I'm not quite sure why the intermezzos are there because they just seem to continue on with more topics that would fit in as additional chapters within the six sections, but that doesn't matter much. The first section introduces BSL features in more detail than the prologue, and it also lays out the recommended steps of a design process in chapter 3. These steps are touted as the steps for how to design a program, but they're really steps for how to design a function. The process is fine as far as it goes, but it doesn't really scale to large programs. This process is used and refined throughout the book.

The first section only introduced language features that allow for fixed-size data, so the next section introduces lists and recursion. It's a whole five chapters on lists, including basically a whole chapter of problems for the reader to solve. I don't remember lists being quite so hard to understand that it would require five chapters to adequately get the point across, especially with lists being a fundamental data structure of Scheme. Sorry, BSL+. Part of the problem is that the authors seem to explain things in as many words as possible. The text ends up plodding along with slow, tedious explanations, some of which don't even make much sense.

Another part of the problem of understanding in this book is the poor choice of variable names. When the authors are not using single-letter names (shudder), they're using names like alos. What is alos? Is it like, "Alos, poor Yorick! I new him, Horatio?" No, that's not right. That would be 'alas.' Instead, alos means "a list of strings." But why not just use list-of-strings, or even strings if you're into the whole brevity thing. The point is, these super abbreviated and truncated variable names make things more confusing than they need to be, because you have to keep the translation to the full name in your head along with the meaning of the variable and the rest of the code. Using full words for variable names makes the code so much more readable and understandable. It's not like we're working under any space constraints with the text of the code, except for the constraints of our own working memory.

The third section goes into detail on functions and how they enable abstractions that will make the programmer's life easier. Abstractions allow the programmer to solve low-level problems once and then think about harder problems from a higher level. It's a critical programming skill to learn. This section follows a similar format to the last one, with four chapters on functions done in excruciating detail, one of which is full of problems for the reader. We also advance to ISL for this section, and near the end we achieve the final level up to ISL+. Yipee! I remember hating when textbooks would introduce one way of doing things and then later contradict themselves and reveal the real way of doing it. This failing is worse with simplified languages, so I'm pretty tired of "student languages" by now.

The next section covers intertwined data, which is a convoluted title for a section that doesn't have a strong theme. The chapters in this section range from introducing trees to building a simple interpreter to processing multiple lists in parallel. The fifth section focuses on recursion for five chapters, and here they make the distinction between structural recursion, which is based on scanning lists, and generative recursion, which is more general and doesn't use lists as the looping mechanism. The final section discusses accumulators that are used with recursion to enable calculating properties of data that requires keeping track of additional state during the recursion. It's basically passing extra state variables in the recursive call in order to calculate aggregate or cumulative values on the data. All of these sections continued to have chapters near the end that were filled with extra problems for the reader.

This book was super long at nearly 750 pages—one of the longest programming books I've read in a while—and it did not seem like it covered enough ground to warrant that length. There were also 528 problems in total, so a huge amount of practice if the reader worked through all of the problems. Most of the problems were pretty decent, and they stayed relevant and reasonable for the material covered beforehand. But the book as a whole didn't hold up to its goal of teaching the beginner how to design programs. Learning how to program is a huge undertaking, and I don't believe it's possible to adequately cover that whole process in one book. On top of that, the level of discussion in much of the book was too complex for the beginner, and it would just as likely serve to confuse them as to teach them. Conversely, it doesn't seem to work well as a second programming book, either because it is so slow and tedious and long. By the end all we've learned is the basics of Scheme, lists, functions, and recursion. The Little Schemer taught much more in a more entertaining way in less than 200 pages. I can't recommend slogging through this book instead.

Structure and Interpretation of Computer Programs (SICP)

This book was the textbook for the entry-level computer science course at MIT for a number of years. I, unfortunately, was unaware of it until after I had finished college (not at MIT) and had come across it mentioned in a blog post by Steve Yegge, I think. Ah, yes, here it is. Apparently, that's also where I got the idea to read How to Design Programs, but fortunately, SICP was a better recommendation. I also didn't have the same issues with the book's humor that Steve did. I didn't mind the silly names of the students in the exercises, (you always know that Louis Reasoner got it wrong; you just have to figure out how) and some of the other jokes were actually kind of funny:

In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.

I mean, come on. That's not half bad for a computer science joke. The majority of the book was not about fun and games, though. It's a serious book on introducing the computer science student to how programming languages—particularly Scheme—work.

SICP is split into five fairly balanced chapters. Each chapter starts off easy with an introduction to the material covered in the chapter and more detailed explanations of the mechanics of Scheme or the interpreter or whatever is the topic for the chapter. As things develop, the difficulty ramps up until near the end you can feel your brain going numb and draining out of your ears. Then you get a breather at the beginning of the next chapter with another gentle introduction.

The first chapter starts off with the requisite intro-to-the-language stuff that every book for a new programming language needs. After covering Scheme's operators and primitives, we move on to functions and immediately jump into recursion. By the end of the chapter we're learning about how to pass functions around as arguments and return values, and I wonder how an entry-level student could really grok all of this in a semester course. This is just chapter 1!

Chapter 2 teaches us all about how to structure and process data in Scheme. Since the fundamental data structure in Scheme is the list, this means we're going to get very comfortable with list processing (which is how Lisp gets its  name, see?). Between these first two chapters, we gain a thorough understanding of the foundations of Scheme and how to put together Scheme programs to do interesting things with data. Even after reading so many books on programming and practicing it in the field for a couple of decades, I was quite enjoying this "beginner" programming book.

Helpful exercises are interspersed with the text throughout the book, generally at the end of each subsection, and they are quite well thought-out exercises. With 356 exercises in all, they provide a ton of practice to ensure that the reader is understanding the material. At first they seem to be somewhat random but standard fare, asking the reader to solve programming problems with rational and complex numbers and other such mundane mathematical problems. Then, near the end of chapter 2, we learn how to implement generic arithmetic operations that can automatically promote and demote arguments from one class of number to another. It's pretty slick, if somewhat impractical. I can't think of a system where this behavior would be necessary, but it's cool to get it working nonetheless.

The next chapter kind of let the wind out of my sails a bit. The previous chapters had really exemplified the elegance of Scheme with beautiful functional programming, but now we had to learn about the mucky reality of objects and mutable state. This chapter introduces the set! operations that allow variables to be changed in place instead of creating and returning new variables that are set with the define primitive. The allowance for changing variable values enables the creation and maintenance of objects with state, and this complicates the analysis of program execution because now we have to deal with side effects. The authors did a nice job of explaining when objects are useful, because we don't want to use them for everything:

The object model approximates the world by dividing it into separate pieces. The functional model does not modularize along object boundaries. The object model is useful when the unshared state of the “objects” is much larger than the state that they share. An example of a place where the object viewpoint fails is quantum mechanics, where thinking of things as individual particles leads to paradoxes and confusions. Unifying the object view with the functional view may have little to do with programming, but rather with fundamental epistemological issues.

The second half of the chapter continues on from objects with concurrency, which does not play nice with mutable state at all, and introduces streams in order to deal with that problem. Streams are a mechanism that enables lazy execution of functions on lists. Instead of performing all of the computations on a list at the time the processing function is called, the function will return another function that will do the computation on its corresponding list element at the time that element is needed to be read. It's wild and confusing at first, but working through the exercises helps clarify how it all works.

Chapter 4 tackles the task that all Lisp books seem to reach eventually, and that is to write an interpreter. How to Design Programs did it. The Little Schemer did it. SICP does it to, but it doesn't simply stop with one interpreter. No, after the basic interpreter, we go on to write a lazy interpreter that does delayed evaluation. Then, we write another interpreter that does ambiguous evaluation, meaning the programmer can specify a problem and an input range for that problem, and the interpreter will perform a search to find a solution (or every solution) that satisfies the constraints of the problem. Think that's enough? Not now that we're on a role! The final interpreter extends Scheme to be a logic language similar to Prolog. You would think the previous ambiguous interpreter would be a good basis for this extension, but the text uses the lazy interpreter as the base instead. Extending the ambiguous interpreter is left as an exercise.

Things are getting pretty mind-bending by now, so why don't we finish things off with something truly warped. The last chapter goes through implementing a register machine model in Scheme. What's a register machine? It's basically a model of a computer that uses fixed registers, a load-store memory model, and low-level operations to execute an assembly language. Then we need something to run on this register machine, so we modify the interpreter to run on top of this assembly language. Now let's step back and think about what we've done. We now have an interpreter that takes in Scheme code, spits out assembly code, and runs it on a model of a computer (the register machine); and this is all done inside another Scheme interpreter running on a real computer. Wat? Let's think again about what we've done:

From this perspective, our evaluator is seen to be a universal machine. It mimics other machines when these are described as Lisp programs. This is striking. Try to imagine an analogous evaluator for electrical circuits. This would be a circuit that takes as input a signal encoding the plans for some other circuit, such as a filter. Given this input, the circuit evaluator would then behave like a filter with the same description. Such a universal electrical circuit is almost unimaginably complex. It is remarkable that the program evaluator is a rather simple program.

It's mind-blowing, really, but we're not done. The last part of the last chapter walks through building a compiler so that we can compile Scheme functions down to the assembly language of the register machine, and modify the register machine so that it can run the assembly code directly instead of it being fed from the interpreter. If that's not enough, the last two exercises are simply about writing a scheme interpreter in C and a compiler in C instead of what we just did in Scheme. Easy-peasy, right?

While these last two chapters were fun and fascinating, they were quite a stretch for one book. The first three chapters plus the basic Scheme interpreter would have been enough for the learning experience. I'm not sure how much practical knowledge readers would get out of the rest of the interpreters, the register machine, and the compiler. The explanations became very mechanical and it felt like a major effort just to fit in the code listings and brief descriptions while still keeping the book around 600 pages. Beyond the issue of cramming a bunch of complex stuff in the last chapter and a half of the book, there are much better books out there on compilers and interpreters, like the dragon book or Writing Compilers and Interpreters, that go into more detail and explain those details more thoroughly. Likewise for machine languages and computer architecture, if you really want to understand the underlying machine language and hardware, Computer Architecture: A Quantitative Approach is excellent. Although, for a lighter introduction, Computer Organization and Design might be a better place to start.

That criticism notwithstanding, SICP is an excellent book on both how to write programs in Scheme and how to write a Scheme interpreter. It's a solid textbook for a second course in programming, but not a first course. I can't imagine most entry-level students would grok everything this book tries to present, so it would be good to have some other programming language under your belt before tackling this beast. Given its age, it's still surprisingly relevant as a programming textbook, and quite enlightening.


SICP is far and away the better book in this face off. True, How to Design Programs is meant for a less technical audience, but I'm not convinced that it would be an appropriate book for non-programmers, either. Scheme is just not the right introductory language, and something like Python or Ruby would be a much better learning language. Taking that consideration out of the equation, SICP packs a ton more content into 150 less pages, and it goes in much more depth on both basic programming concepts like lists and functions, and advanced concepts like streams and interpreters. Did I mention it also uses way better variable names? The code is much easier to understand as a result, and it's only the complexity of the concepts later in the book that make that code difficult.

Definitely pass on How to Design Programs, but if you're in the mood to level-up your fundamental programming knowledge, give SICP a look. If you're so inclined to read it online, check out this version at Sara Bander's GitHub site. It's rendered in a beautiful Linux Libertine font that's an absolute joy to read on a screen, and the footnotes come up in text boxes when clicked. It's the best experience I've had reading an ebook.