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
2005
368 pp.
$50.00
http://www.idc.ac.il/tecs

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.)

8 Responses to “A 12-Step Program to Build Video Games from Logic Gates”


  1. michael Says:

    Sounds like a great book. This semester I’m designing and teaching a course at Georgia Tech, CS 2260: Media Device Architectures, that is supposed to do exactly this; demystify the operation of computers, provide an introduction to hardware and software systems, but all from an interactive media-centric perspective. To do this we’ll be doing Gameboy Advance programming. Unfortunately there are constraints on the course that would make Elements of Computer Systems not the perfect approach (not without redesigning other courses that would appear before and after 2260). As I start teaching the course next week, I’ll write a post about the design of the course and the curricular constraints I’m trying to satisfy. However, it may be that some chapters of the book will be useful for 2260.

  2. mark Says:

    I haven’t read this book, so can’t comment on it in particular, but I’ll comment on your comments about undergraduate curricula. I’d say it’s really a subjective decision what should be covered—ideally, everyone needs to know a little bit about everything, but only so much fits in 4 years. In particular, does a CS major in 2006 need to know how logic gates are put together to make a CPU, or is it sufficient to deal with things at a higher level of abstraction (perhaps only going down to the assembly level, or maybe not even below C)? How about further down in the abstraction hierarchy; should they understand how circuits are laid out on silicon; heat dissipation problems; maybe even the physics of how transistors work?

    It depends on what you want to do, really. It’s all useful on some level, but not necessarily more useful than other things—for example, students interested in AI may benefit more from a class on philosophy of mind or cognitive science (or both) than from a class on circuit design. I’d also argue that a basic class on formal logic should be a part of every CS curriculum, while currently that doesn’t seem to be the case.

  3. nick Says:

    Mark, sure, one can go lower, but that’s physics and engineering, and the question becomes whether one wants to try to expand the discipline of CS or continue into other disciplines.

    My point wasn’t that CS programs should cover more systems topics, but that a holistic look at systems is worthwhile for all CS students. Maybe it’s better for students to do a one- or two- semester course like this and have a unit on building on a CPU instead of spending a whole semester putting logic gates together? The real benefit is not that you sneak in more topics that you otherwise wouldn’t (virualization, for instance) but that a complete view of comptuer systems (everything that is part of the discipline of CS, anyway) can be attained, rather than just an in-depth understanding of a few pieces.

    Having taken that course in logic, which was required in my undergrad program, I agree about the importance of that course.

  4. mark Says:

    I suppose that’s the real sticking point—what *is* part of the discipline of CS? Perhaps more importantly, does it even make sense as a unified discipline, or is that a historical relic of the time when the field was relatively small, like the days when physics and chemistry used to be the same field?

    I agree that having a holistic view of computer systems is often useful, but I’m not sure it’s always necessary or the best thing to spend time on. In particular, I think modern computer systems are at the point where designing a physical computer system is a distinct discipline from designing something that uses a computer system—it might be nice to know how a TLB works, how NAND gates are assembled into higher-order logical circuits, and so on, but is this actually any more necessary for a CS student to know than what a 65-nm process is, how transistors work, and so on? Even leaving aside future field shifts, I’d say even today I’d consider designing CPUs out of logic gates to be more a part of engineering than CS, though admittedly closer to CS than chip fabrication or transistor physics are.

    Which isn’t to say it’s not useful, but I think how useful it is depends on what sort of CS student one is. If someone is more interested in, say, theory of computation, or machine learning, or another area of that sort, I think having a much more solid grounding in mathematics than is typically common in CS undergraduate programs would be a better use of time.

  5. Charles Says:

    I recently graduated with a CS degree, and in my particular case, I was required to take both a class similar to the one described in the book, as well as at least one class dealing exclusively with logic and computational models. One of the things I remember was that nearly every professor I had mentioned how upset they were that there wasn’t more time for “culture” lessons, i.e. stuff that isn’t directly applicable to programming, but rather is important to being a well educated Computer Scientist in general. I find it hard to accept that a person is a Computer Scientist without at least a passing familiarity with the machine level.

    When I finished the course and I realized that I understood how a computer worked from the logic gates all the way to the assembler, it really blew me away. This sort of course most importantly reveals that computers aren’t “magic”, the knowledge of the processes all the way down makes people better equipped (mentally if not practically) to deal with any number of computer-related situations. I can’t imagine a person with a legitimate curiousity about computers not benefitting from this sort of course, and definitely feel that my own computer science education would have been incomplete without it.

  6. Grand Text Auto » You Can and Must Understand Giant Brains Now! Says:

    [...] With its simple but thorough descriptions of how computer systems work, it is an ancestor of The Elements of Computer Systems, but the book is also notable as a predecessor of the populist and manifesto-like Computer Lib / [...]

  7. Tina Anderson Says:

    This is essential reading for anyone that wants to gain a basic understanding of how computers work. While this book can obviously benefit computer science students, I think it can really help new media program students and people in general who want to really understand the inner parts of computers and how they function. I would recommend it to anyone in this field of study.

  8. Post Position » Computing with Your Torch Says:

    [...] the way to creating a full CPU, is the one described in The Elements of Computing Systems, a book I wrote about on Grand Text Auto back in 2006. Comments [...]

Powered by WordPress