Book Review: The Elements of Computing Systems

I do not fear computers. I fear the lack of them.
– Isaac Asimov

Introduction

Computer programming is a passionate hobby for me from my school days. But I ended up taking a degree in electrical engineering. Almost everything I know about computing is self learnt. This is true for a lot of programmers out there. Most of us are proficient in one or more computer languages and are familiar with the technology stack we use in our day to day work. Yet most of us also have a nagging feeling that we don’t know fully how computers work!

Interestingly this is a problem faced even by computer science graduates! This is due to the high level of specialization and separation of computer science topics. Hence even CS graduates miss the elegant big picture of the computing field. The Elements of Computing Systems is a book designed to address this gap. This book attempts to provide a complete high level summary of the computing basics in just about 250 pages! Man, it does a really good job at that!

As you go through each chapter in the book, you are required to build each building block of a computer. You start with the basic Boolean logic gates and then move onto building complex Boolean circuits, Arithmetic & Logic Unit (ALU), CPU, memory modules, machine language, assembler, virtual machine, high level language, compiler and finally even an operating system!

Book Review: The Elements of Computing Systems

The Elements of Computing Systems (also known as Nand2Tetris) is written by two computer science professors, Noam Nisan and Shimon Schocken. It is a self study guide for building a modern computer from first principles. The book’s basic premise is that the best way to understand how computers work is to build one from scratch! The book consists of 13 chapters each containing a project that the reader is supposed to solve. The only pre-requisite for the book is the knowledge of a programming language.

If you study the book and then solve all the programming problems in it, you will get a deep understanding of the following topics,

  • Boolean logic and logic design
  • Data representation in computers
  • Designing memory, ALU and CPU
  • Practical use of data structures & algorithms such as stack, list, recursion etc.
  • Method call stack, object allocation and heap
  • Variable types, scope, object and array representation
  • Memory addressing and memory mapped I/O
  • How to write an assembler, virtual machine, compiler and operating system!

Obviously building a full fledged computer from basic logic gates is a very complex undertaking. However the authors have simplified this challenge substantially by adopting a number of clever strategies. These strategies ensure that the programming problems doesn’t become too complex for a beginner,

  • We use a hardware simulator for building computer hardware. This avoids the need for working with physical components. Yet at the same time this teaches you everything you need to know about hardware!
  • This course ignore error handling and optimization problems. For example, when you write a compiler you can assume that the program being compiled is error free. Optimization is an important yet hard problem. Ignoring it makes things simpler.
  • The ALU (Arithmetic and Logic Unit) and CPU built as part of this course has a very simple instruction set. For example, the CPU we build won’t have any native multiplication capability. Also it only works with 16-bit integers.
  • The assembly language and high level language (Jack) are all a bit verbose. But this substantially reduces the complexity in building assembler, VM code generator and compiler.
  • Each chapter contains almost the entire design of what you are building. The design and the hints provided are the keys to the simplicity and the power of this course.

The Elements of Computing Systems consists of 13 chapters contained in about 250 pages. Each chapter starts with a background section, describing relevant concepts. The next section is specification, which provides a clear statement of the system’s abstraction – namely, the various services that is expected to deliver. The chapter then proceeds to discuss how the abstraction can be implemented leading to a proposed implementation section. The next section, perspective, highlights the important issues left out from the chapter. Each chapter ends with a project section, which provides a detailed guide on building and testing the system described in the chapter.

Here is a summary of the chapters,

  1. Boolean Logic – The book starts with quick introduction to Boolean logic and logic gate circuits. Using the basic Nand gate, a hardware description language (HDL), and a hardware simulator, you will build other logic gates such as And, Or, Xor and Multiplexer. An HDL tutorial is provided in the appendix.
  2. Boolean ArithmeticHack Machine CodeChapter 2 introduces Boolean arithmetic and signed integer representation in computers. You will build logic circuits for adding binary numbers using the chips built in the previous chapter. Finally you will build an arithmetic and logic unit (ALU) capable of doing arithmetic and logical operations.
  3. Sequential Logic –  Introduces sequential logic and explains why a clock is necessary to maintain state in logic circuits. This chapter assumes flip-flop as the basic building block and then proceeds to show how memory registers can be built. You will build a program counter and memory units as large as 8K.
  4. Machine Language – Introduces a simple machine language capable of doing computation and memory access. The compute instruction is defined such that it can be implemented using the ALU built in the previous chapter. The machine language is simple and easy to learn and implement.
  5. Computer ArchitectureHack Assembly Instructions This chapter combines the hardware components and the machine language to build a full fledged computer. You will combine memory, ALU and control chips to build the Hack computer. A keyboard and display is also added using memory mapped I/O. In Hack architecture, instruction memory and data memory are kept separate.
  6. Assembler –  This chapter take us to the software land. You need to know a high level language to solve the programming problems from this chapter onwards. A simple mnemonic set is defined for the Hack machine language. You will then build an assembler for converting these mnemonics to actual machine language. 
  7. Virtual Machine – I: Stack Arithmetic – Many modern languages (Java, C# etc.) are compiled to an intermediate virtual machine code for portability. This chapter introduces a stack based virtual machine language/architecture. You will need to write a program to convert the VM instructions to the assembly language defined in the previous chapter. This is a complex activity and hence is split into two chapters.
  8. Virtual Machine – II: Program ControlHack VM Code This is a continuation of the previous chapter and you will build the program control part of the virtual machine. Once you have completed the VM to assembly converter, you can write programs with less effort compared to the assembly language.
  9. High-Level Language – Introduces a high level language called Jack. It is similar to Java but is more verbose so as to help the compiler writer. Write a number of programs in Jack language to get a feel for it.
  10. Compiler – I: Syntax Analysis – The next logical step is to write a compiler that can translate the high level Jack code to the virtual machine code. It is a complex project and hence is attempted in two chapters. This chapter introduces the syntax analysis and parsing techniques of compilers. You will write a parser for the Jack program to convert it into a sequence of tokens.
  11. Compiler – II: Code GenerationJack code for Tic Tac Toe Introduces the common compiler techniques for code generation. Using the parser from the previous chapter, you will write a full fledged Jack compiler. However you will need to use a number of library Jack classes for your program to work. In the next chapter, you will build these library classes.
  12. Operating System – Introduces the concept of an operating system. You will build a number of library classes in Jack language providing the basic OS services for the Hack platform. These include modules such as Keyboard, Screen, Output, Math, Array, String and Sys.
  13. Postscript: More Fun to Go – The final chapter provides a number of pointers to extend the Hack platform. Optimization and error handling are two obvious things to do. Another challenging thing would be to relax the rules of Jack language to increase the complexity of the Jack compiler.

All the required software (including source code) for the book is available on the nand2tetris home page.

The book is elegant, concise and very well structured. Clearly the course material has undergone extensive testing over the years. Each chapter provides hints so you get a high level idea of the solution. But it rarely tells you how to solve something. That is what makes this book so good. You have to really think and find solutions to tough programming problems. Also later chapters are tougher than initial ones.

I think there isn’t even a single redundant/unnecessary sentence in the book!

It took me around 20 days of dedicated work to complete the entire book including all the projects. It took me a while to solve the compiler code generator and the operating system chapter. I got stuck many times while working on the projects. I had an irresistible urge to look for solutions on the Web. But luckily I was able to overcome that urge and solve them on my own. This is something I suggest you do too. Don’t look up solutions on the web or forums. Try to solve problems on your own for the reward of intellectual satisfaction.

One limitation of the computer system we build as part of this course is that it can only work with 16-bit integers. This means that instruction memory size is limited to 32K. Since the code generators we build are not optimized, even simple Jack programs can lead to large machine code that won’t fit in instruction memory. This means that you won’t be able to compile your Tetris program all the way to machine code and then run it on the virtual hardware you built using HDL. Instead you will have to use the VM emulator to run your programs.

Finally this course reminds us the importance of abstractions in human progress. Most of the time we never need to look at what happens under the hood. Our abstractions protect us from all the underlying complexity. But never hesitate to look beyond the abstractions when needed.

Many colleges run computer science courses based on this book. The first half of the book is also available as a course in Coursera.

For a quick introduction to the book, please check out this short video by one of the authors (Shimon Schocken),

Summary

Computers have become an integral part of human existence. Almost everyone now carries a full fledged computer in their pocket! If you are looking for just one book that will help in you in understanding how computers really work, this is the book.

If you are a software developer or is planning to become one in future, you should read the book and complete all the programming projects. It will give you a deep insight into computer architecture and you will find it valuable throughout your career.

I enjoyed the book very much including all the projects in it. In fact this book gave me the best self-study experience in my life. The whole learning journey is one of intellectual thrill and intellectual satisfaction. Some may even find it a life changing experience. Highly recommended!

My Rating: 10/10

Further Reading/Additional Resources


October 2, 2016 | Posted in Programming No Comments » | By Jayson

Leave a Comment