January 8, 2006

A 12-Step Program to Build Video Games from Logic Gates

by Nick Montfort · , 2:53 pm

TECS book coverA Review of The Elements of Computing Systems: Building a Modern Computer from First Principles
Noam Nisan and Shimon Schocken
MIT Press
368 pp.

The Elements of Computing Systems has a remarkable assemblage of virtues: it’s a book that covers systems at basically every level, it’s appropriately minimal and lines out just enough to study in each one, it’s clearly written and well-illustrated, there is a nice supply of accompanying cross-platform software available for free online, and the exercises are fun to do. Besides being a nice book about computer systems, it also brings a nice perspective on how we can learn about different abstracted levels in computer science and then put these pieces of understanding together. Really, I’m embarrassed that I like an undergraduate computer science textbook this much.

I heard a very interesting talk by Shimon Schocken last February – it was here at Penn, and entitled “from NAND to Tetris in 12 Steps.” Schocken discussed classes that used early versions of this book, leaving me very curious to get my hands on The Elements of Computing Systems. In courses Schocken and his co-author developed, students go all the way through to building graphical applications written in a high-level language, starting off with just NAND gates, false, and flip-flops and building up everything they need.

When I did get the book, I found it quite compelling, and, although I probably had better things to do, I ended up not just reading it but doing most of the exercises, and learning a good bit from them. It’s true that I’ve sometimes been accused of being a – “toolman” is the epithet, I believe – but whatever my geeklike inclinations, I don’t usually choose to snack on systems textbooks. The hands-on but thoughtfully directed and structured approach of this book, and the integrated view it gives of systems all through the hardware levels and software hierarchy, made it quite compelling though, and I think it will be of similar interest to others studying independently, as well as to those in the appropriate undergrad courses.

The “market” for this book is, of course, the textbook market. It’s ready for use by undergraduates in, for instance, a “capstone” course designed to give a full overview of the important technologies and techniques that go into computer systems, to show how everything fits together. But I believe the potential readership for The Elements of Computing Systems also includes:

Something that is relevant to all three types of readers is that the book is modular, so people can choose to read from 1 to 12 of the main chapters, and do the corresponding exercises, in just about any order. This is possible because of an important concept in computer science, abstraction – the isolation of the essential. Abstraction in its use here allows an understanding of a selected, separate level, such as an assembler, without requiring the simultaneous understanding of everything else, such as the details of how the CPU is actually built out of logic gates or the details of how a virtual machine or high-level language is to produce assembly code. Nisan and Schocken use abstraction (this form of “selective ignorance” that allows us to concentrate on what’s important at the moment) very well, to enable an understanding of different levels of systems and then, if we want to go through everything in the book, to let us bring these together into a reasonably complete understanding of how a modern computer works.

The book first covers how to construct any combinatorial logic gate from NAND and false; how to build an ALU out of these; and how to add sequential logic (flips-flops are provided as primitives) and construct a CPU. All the hardware construction is done in simulation by writing HDL (Hardware Description Language) statements; many other tools, written in Java, are provided for the software hierarchy. After the hardware is done there’s machine language, writing an assembler, writing a virtual machine, defining a high-level language and a compiler for it, and even building a sort of minimal operating system – although everything here is pretty minimal. That’s appropriate, though, since the systems are nevertheless interesting and the scheme provides a way to cover every section of the book in an advanced undergraduate class. As a final project, students can write a game for the computer system they’ve built. (A version of Pong is included to allow students to test their system.) A capstone course could swoop through all the strata of computer systems, getting an integrated view that will help both those inclined to work with systems research later on and those who will have such a course as their send-off from systems. But programming is the only prerequisite, so the book can also be used, in whole or part, immediately after an introduction to programming course.

While digital media graduate students might not find the time in their studies to pursue The Elements of Computing Systems at length, it can serve several useful purposes in the study of new media and video gaming. For those diving deep into the machine, a broad study of systems that only requires programming seems like just the thing. Others might find that going through the readings and exercises in just a chapter or two is a big boon to their intuitive grasp of low-level computing technologies, and that even if this doesn’t provide system-development skills, it helps to demystify the machine. Anyway, since about half the book is available online (click “Book”,) there’s no cost to checking out a chapter. Finally, while reading the book without doing the exercises is not so useful – some of the major insights come from figuring out how to implement things and are not spelled out in the book – it’s better than nothing, and can be one source for understanding the computer’s workings. The real benefit definitely comes from reading and programming, though, and although the book isn’t beyond critique – I found the amount of help provided too much in some chapters and too little in others, and the time to complete all of chapter’s exercises to vary a bit much – the problems are thoughtful and the material is definitely well-presented.

One worry I have is that the typical CS curriculum is not ready for a book like this. There are usually a few in-depth undergraduate courses on a few of these levels (with only the most serious systems students taking all of them) and no integrated course on all of them. That sort of thing left people like me wondering how a semester-long lab on logic gates improved either my reasoning ability or a my understanding of the workings of computer systems. Of course, change has to start somewhere. The Elements of Computing Systems is a good place for it to start.

(Note: MIT Press is my publisher, and I did not pay for the copy of this book that I reviewed.)