Blog
My Journey from Nand to Pong
TL;DR - I built a virtual computer system from the ground up starting at the level of basic Nand logic gates. Then I played Pong on it.
I recently spent some time working through the celebrated computer science course From Nand to Tetris. The accompanying textbook is called The Elements of Computing Systems, by Noam Nisan and Shimon Schocken. I loved both the course and the book and I'd definitely recommend them to anyone with an interest in computer science. Here, I've jotted down a few notes about the journey.
The course involves gradually building a computer system from first principles starting at the level of simple logic gates (Nand = not-and gates) and working your way up. It was a lot of work, but it was a wonderful way to understand what's going on under the hood of a modern computer. There was a fair bit of figuring out, but the textbook is good at holding your hand through the hairier design details so you don't get permanently stuck on things.
You start at the level of basic logic gates, after which you move up to chip sets, the CPU and the RAM. Once the (virtual) hardware is setup and working you move on to the software. You write an assembler to produce machine code, a virtual machine to produce assembly, and finally a compiler to translate a high-level programming language into a lower-level VM language for the virtual machine. Each step in the process adds a layer of abstraction on top of what was built in previous steps. As a final step, you write a basic operating system to provide programs with convenient access to things like graphics, keyboard input, dynamic memory allocation etc.
In the end you can get a proper interactive application running (it was Pong for me, maybe Tetris for you?) on an operating system you built yourself, compiled down to machine code with a compiler you wrote yourself, run on a (virtual) CPU and RAM you built yourself. Feels like magic - except you made the magic!
Just to be clear - you're not actually building physical bits hardware in this course (although I suppose there would be nothing stopping you). What you are actually doing is writing out a specification for how the hardware should all be wired together using something called Hardware Description Language. One of the really neat bits of software that the course provides you with is a hardware simulator which allows you to test out your design implementations quickly and conveniently.
The course is split across the 12 chapters of the textbook. Each chapter teaches you something new and then provides instructions for a project that uses what you've learned in order to build up the system further.
Chapter 1 - Boolean Logic
The opening chapter has you building all the various logic gates that you'll need to build chips within the chapters to come. You start with the axiomatic Nand (not-and) gate and build every other gate using combinations of it. The work builds on itself, so for example once you have Or and And gates built it makes it easier to build an XOR gate, but ultimately everything is made out of Nand gates when you look closely enough. In the end you have working versions of: Nand, Not, And, Or, XOR, Multiplexor (2, 4 and 8 way), Demultiplexor (2, 4 and 8 way), as well as multi-bit versions of the simple gates.
Chapter 2 - Boolean Arithmetic
The next project involves building the Arithmetic Logic Unit (ALU). This is the central "brain" of a computer's CPU and is where all the logical operations happen. Building it is pretty tricky and you have to use a whole constellation of logic gates to do it. Luckily the text is pretty good at taking you through the process in slowly increasing levels of complexity which makes it more manageable. Eventually after some perseverance you have a bunch of logic gates wired together that can do math!
Chapter 3 - Sequential Logic
How do you build a machine that has a memory? The answer turns out to be with some flip-flops and a clock. Flip-flops are a basic computing element which can maintain state through time as well as produce some very simple time dependent behaviour. The computer's internal clock provides a continuous oscillating signal through time (or tick-tocks) which synchronize the time-dependant behaviour of all the flip-flops in your system. This chapter guides you through all the necessary steps for building CPU registers and blocks of RAM using just these flip-flops and a bunch of logic gates. I thought this step was was pretty satisfying and also found it interesting to realise how important a computer's internal clock is for making memory work properly.
Chapter 4 - Machine Language
This chapter is dedicated to getting your feet wet with the low-level assembly language that will be used in the coming chapters. As you go through the chapter you learn the assembly language syntax and then, as a project, write a couple of basic programs in the language to confirm that you've understood what's going on. It's strange, and to be honest a little painful writing programs in raw assembly but it does make you realise a few things. For example, I discovered how important CPU registers are, and why its nice to have as many of them as possible.
Chapter 5 - Computer Architecture
This chapter feels a bit like doing a jigsaw puzzle where the pieces are all the bits of hardware you've made in the previous chapters. When the jigsaw puzzle is complete you are left with a functioning von Neumann machine capable of running real computer programs :) First you build the RAM out of 16,000 addressable memory registers. Next you build the CPU out of the ALU, some memory registers and an assortment of logic gates. Then you build another memory device used to store runnable programs in memory (the ROM). And finally, you wire all that together into the overall computer. You design everything assuming that a screen and a keyboard are connected to your system and that you can interact with them through a memory mapping in your system's RAM. Once you have all this put together you load and run a small collection of supplied machine code programs in order to celebrate and make sure that everything is working as expected.
Intermission:
The computer is built! At least the hardware has been built. However, that is only half the journey and there are still many more interesting things to learn in what's to come. The rest of the course involves building up the software necessary to run a high-level programming language directly on the computer. The next step is to build a full compiler capable of translating a modern programming language into the 1s and 0s that a CPU understands. That turns out to be is a pretty serious undertaking so it's gradually carried out through chapters 6 - 11.
Chapter 6 - Assembler
The first step in building the full compiler involves building its lowest level component - the assembler. This is a program that translates assembly language into the binary machine code that can be fed directly into the CPU. Assembly language is a very low level language that is essentially a series of CPU instructions relating to loading data in and out of CPU registers and carrying out logical and arithmetic operations on them. An additional complication is that the data in these CPU registers can sometimes represent a binary number, sometimes represent a RAM memory address (to a binary number) and sometimes represent both! You also need to keep track of an arbitrary number of symbols, which are essentially the equivalent of variables in assembly, each of which needs to point to a unique memory address assigned to them when the assembler runs. I wrote my assembler in Python and, if curious, you can have a look at it here.
Chapter 7 - Virtual Machine I: Stack Arithmetic
This chapter is very interesting. A lot of new ideas are introduced that need to be carefully understood and then built. The strategy taken for this particular compiler is to build it with a virtual machine (VM) as an intermediate layer between the source code and the bare metal of the CPU. The simple language the VM accepts (and turns into assembly) is a sort of "intermediate-level" representation of the program's code. It mostly consists of simple instructions for manipulating data on the stack, performing low-level arithmetic and logic operations, and some branching commands for control flow. This VM language is introduced here along with the way the program execution should be organized on the stack. I've always known about "The Stack" but never had it explained so clearly to me before - hats off to the authors here. Most of the chapter's project involves coding up the logic for the stack and some operations that can access objects on the heap.
Chapter 8 - Virtual Machine II: Program Control
The half-created virtual machine is now extended to include branching control flow and subroutine calling. The way a subroutine is called and setup on the stack with all its arguments and local variables in its own personal little environment is devilishly tricky to implement but wonderfully elegant once you realise how it works. Getting the logic right with this was tough, but it was another moment of great satisfaction once I had it working. Even got it working with multiply recursive function calls. Incredible. I implemented the whole virtual machine in Python and you can have a look at it here if you like.
Chapter 9 - High-Level Language
With the virtual machine complete the next step is to build the high-level compiler. This is a program that will translate high-level code into the VM language expected by the virtual machine. This chapter is dedicated to introducing the specific high-level programming language that the compiler is to be written for - a language called Jack.
Jack is a programming language invented by the creators of the course specifically to make the process of building a compiler a bit less painful and a bit more instructive. Jack feels similar to Java. The syntax is similar, it is object orientated, and, like Java, it is compiled before being run on a VM. Jack is also, in certain ways, a fairly simple language which keeps the complexity of the necessary compiler under control. Specifically, Jack does not support class inheritance, it is weakly typed, and there are only a few native data types available. Also, memory management is manual in Jack so there is no need to worry about building a garbage collector from scratch. This chapter is essentially a tour of the Jack language specification and the chapter's project involves writing a simple program of your choice using Jack to get into the swing of things. I wrote a Jack version of Tic Tac Toe.
The next couple of chapters involve writing your own Jack-to-VM-language compiler. This turned out to be pretty hard. Rome wasn't built in a day and neither was this compiler (nowhere close actually) but I did get there in the end.
Chapter 10 - Compiler I: Syntax Analysis
The first two things that need to be built are the Jack tokenizer and the Jack parser. The tokenizer splits the code into individual chunks of text called tokens, and the parser generates a tree-like representation of the hierarchical structure of the program. I was able to test both of these by generating XML versions of their output and comparing them against supplied test files provided in the course resources.
Chapter 11 - Compiler II: Code Generation
This chapter was very tricky. The task is: Given the syntax tree provided by the parser built in the previous chapter, turn that into the intermediate-level language expected by the VM. This step, from parsed Jack to VM language, turns out to be a pretty significant step down the pyramid of abstraction. There is a lot of logic, organization and edge case weirdness to think about in order to get things working properly.
You have to work out how to setup and manipulate variables, arrays and objects on the stack and heap. The Jack conditional control flow methods (if/else and while statements) need to be implemented with the VM go-to commands. Functions need to be defined and called correctly with all their arguments and local variables arranged on the stack correctly. Arbitrarily complex and potentially nested arithmetic expressions need to be split up and evaluated correctly. Variable scope needs to be defined and respected in every part of the program. I developed a large amount of respect for modern compilers (as well as the people that create them) during all this. The final (working!) version of my compiler, written in Python, can be viewed here. I am, it must be said, rather proud of my little Jack compiler.
Chapter 12 - Operating System
The final stage in the course involves building a basic operating system for your fledgling computer with its shiny new compiler. The resulting library of Jack classes significantly extend the scope of what you can conveniently do with Jack programs and generally makes everything a bit more interesting. Specifically: The useful Array and String data types are implemented, several basic mathematical operations are implemented, algorithms for dynamically allocating and de-allocating memory on the heap are implemented, convenient ways of accepting user input from the keyboard are setup, and all the complicated logic for drawing graphics and text on the screen (using the RAM memory map) is implemented and hidden away in the OS. It was quite fun to learn, for example, how to implement multiplication, division and square roots using only the addition and subtraction operations offered by my modest CPU's instruction set. (By the way, the simple way of doing multiplication with repetitive addition you just thought of is wrong unfortunately - it'll work, but it's far too inefficient. Is there a better way? Have a think about it.)
As a final step, bringing me on to the sweet lofty summit of a fully operational system, I compiled the whole operating system (written by me in Jack) using the Jack compiler I wrote in the earlier chapters and ran a basic version of Pong on the virtual computer hardware. Thankfully no blood, but certainly some sweat and tears went into creating this. Never thought I'd be so happy to see a Pong ball bouncing around my screen. 🧙♂️
*
Pong *
* /\
/##\ *
/\/ ##\ __
/##\ ##\___ /##\
* /# #\ \/ #\
___/ - \ / \ /\
/ \ \/ \/ \
/ ------ \ / \
________________________________ / --- \ / \
__/
O Nand
/|\
/ \