Last week I finished the Nand to Tetris online course taught by Noam Nisan and Shimon Schocken, after seven months of working on it (part time). This is a course where you design and computer from the ground up, starting with the smallest of logic gates. Then you program the computer, creating a simplified version of the Java programming language and writing an entire operating system in that language. I’ve been programming for decades, and still found it to be a fascinating exploration of what is going on behind the scenes.
The Hardware
You start with a nand gate, nand standing for “not and.” It is just about the simplest of electronic gates, with two wires going in and one wire coming out. If one incoming wire is on and the other is off, the outgoing wire turns on. Otherwise, the outgoing wire turns off. Using multiple nand gates, you then design computer chips for the standard logical operators: and, or, and not. Nisan and Schocken then prove that with those three chips you can design a chip for any function working on Boolean (on/off or true/false) values. And then you design a bunch of them. And a bunch more, and a bunch more, until you have a working computer called the Hack computer.
I’m saying “design” rather intentionally. You don’t actually make physical computer chips. You specify how each chip is made from smaller chips, and then run that specification through a hardware simulator to make sure it gives the correct values. So the computer you are designing is being simulated on another computer.
And you don’t design everything for the computer. You are given three things: a one bit memory chip, a keyboard interface, and a screen interface. The memory chip can persistently store one on-or-off value. It can be designed solely from nand gates, but it requires this weird double loop that they don’t expect students to figure out on their own. And the course is about the internals of computers, not the electronics of building keyboards and monitors.
One thing I found fascinating was the mux chip, mux being short for multiplexer. A mux chip has three wires coming in and one wire going out. If the third wire is on, the outgoing wire is equal to the second wire. If the third wire is off, the outgoing wire is equal to the first wire. It’s a conditional at the lowest level. This is a chip that is often used in communications. You turn the third wire on and off repeatedly, and that interlaces the input from a two (or more) wires into a single wire. Then you have a demultiplexer chip (which does the opposite of a mux chip) at the other end, which splits the single, interlaced signal into the two original signals.
Not only is this a really cool chip, it brought back a childhood memory. I’m a gadget freak, and I got that from my dad. My dad actually owned a PDP-11 mainframe computer when I was a kid. At the time, I was into Dungeons & Dragons (well, I still am) and I was creating random creatures from the lower planes and drawing pictures of them. My dad had me draw a picture of the “mux” creature for the new mux he had gotten for his PDP-11. Now I understand what the mux was doing.
The Software
The central processing unit (CPU) of the computer, which uses a complicated arithmetic logic unit (ALU), can take a command encoded in a binary number (a number made using only 1’s and 0’s) and output changes to make to the computer’s memory, and the memory address of the next command to execute. By repeatedly sending commands in and then letting the CPU tell you what command to send next, you run a computer program.
But again, all these commands are numbers. For example, the command to subtract the current memory address from the stored data register and store it back in the data register is 62,672 (1111010011010000 in binary). It’s not easy to program in just numbers, so you have to write an assembler. The assembler converts easier to understand commands like ‘D=D-M’ into numbers like 62,672.
But the assembly language commands are incredibly simple, making it incredibly tedious to write computer programs. So you write higher level languages, like Java or Python. These require a compiler that converts easier to use commands like ‘let length = Keyboard.readInt(“How many numbers? ”);’ into a series of very simple commands like ‘D=D-M’ that can be converted into numbers that the CPU understands. In this course, you write a simplified version of the Java language that the professors call Jack.
The class teaches you to do the compilation of the higher level language as a two step process. This is common in modern computer languages because it simplifies making higher level languages available on different computers that are using different CPUs that are expecting different numbers. In this class you first create a low level virtual machine. The virtual machine is a stack machine which it works on a stack of numbers. You can push a number onto the top of the stack, pop a number off of the top of the stack (and store it somewhere), and do simple operations on the top two numbers of the stack. The instructions for a stack machine can be converted into assembly code for a particular CPU. So you could make different virtual machines that run on different CPUs for Macs. Windows, and Linux. Then you would only need one compiler to convert your high level computer language into stack machine instructions. By switching out the virtual machine you are using, you can run the same Jack program on different machines (without having to write a full compiler for each machine). In addition, this conceptually simplifies the difficult process of converting high-end Jack programs into incredibly low-end assembly programs.
Once you have a Jack compiler, you use Jack to write an operating system for the computer. This is not an operating system like we might think of an operating system, but it provides the high level programmer with tools to access various parts of the computer like the keyboard, the screen, and the memory.
This was another big learn for me: memory allocation. I always knew that you had to manage how programming data and objects were stored somehow, but it was totally opaque to me. This course made me get down into the weeds of memory allocation, deallocation, defragmentation, and memory leaks.
Once you have a high level language, and an operating system it can make use of, you write Tetris. You don’t have to write Tetris, but the idea is to write some application on that level. I chose to write a version of Conway’s Game of Life, a favorite among computer programmers.
Limitations
The class has very significant limitations, for good reason. This is a class meant to be done in a couple of semesters at college. You are not going to learn to write Windows 11 in that time frame. The Hack computer you are designing is incredibly stripped . It only has 16K of memory. It’s screen is 256 x 512 black and white pixels. There is no file system whatsoever. Whatever program it runs must be hard coded into a ROM (read-only memory) chip. Only the fact that it was being run in a simulation made it possible to change out the computer program you were using. Back in the 80s I grew up with an Apple ][ computer that my mom got when she went back to school. That computer is blown away by any phone these days, and it is still way more powerful than the Hack computer this class teaches you to design.
Likewise there are definite limitations to the “high-level” language that you write the compiler for. You are very limited in the data types you have. Furthermore, under the hood they are all stored as integer values from -32768 to 32767. There’s no floating point arithmetic, and while there are strings, oh my God they are a pain in the butt to deal with. You do have classes you can create, but the language is missing inheritance, a cornerstone of object oriented programming.
Furthermore, there are no safety features. While you ostensibly declare the type of each variable you create, that means next to nothing. It is only used in determining what method of a class variable should be used. You can add a complicated object you have defined to a string and the Jack programming language will happily give you an integer value in response. And anything can be treated as an array. Take these two commands: ‘int x; x = 0;’. Even though I have declared x as a simple integer, I can treat it as an array with ‘x[n]’. Then Jack treats the 0 stored in x as the base address of the array, adds n to get the memory address to return, and you can now access any register in the entire memory of the computer. This sort of flexibility can allow you do all sorts of interesting hacks, but it can also allow you to completely mess up the stack machine, the memory management, and just about anything else.
However, I think they made smart choices when simplifying the hardware and the software. If you are going to teach a class like this in a reasonable amount of time, you have to simplify things. But this computer is still robust enough to allow for a wide variety of programming.
Problems
The first problem I ran into was that I was auditing the course, so I didn’t get any feedback. Hardware has never been my focus. I managed to design all of the computer chips, and all of my chips passed the specifications and tests. But I was often sitting there wondering if I had designed them well. They often seemed like clunky solutions, and I was curious if there was a more efficient way to do things. But you’re not getting feedback on the assignments when you’re taking the course for free.
Another problem is that I don’t like the Java Runtime Engine (JRE). It’s an annoying piece of software that constantly wants updates, and if I am not actively developing in Java or using several Java applications, it drives me nuts. So I didn’t download the software you need to take the course. Instead, I used the online software. The online software is fine, up to a point. That point is when you start programming the screen with the high-end Jack language, which requires the online virtual machine emulator. The screen in the online software is not responsive at all, so it doesn’t respond to the programs you are tasked with writing. I searched the problem online and found others with the same problem. Apparently, the online screen takes three minutes to respond to a key press.
Obviously I needed to download the JRE and the course software. But I’ve been working on being a cranky old man, so I decided to rewrite the entire virtual machine emulator in Python. I will admit this was a stupid choice, but I enjoyed doing it. But this caused another problem. You are really testing the compiler for Jack that you have written. Your program is using the operating system functions, but you haven’t written those yet. So the virtual machine emulator that comes with the course provides them for you. Therefore I had to write the operating system while testing my compiler. But since they depend on each other, this is rather difficult. I did manage to wade through it, however.
In writing the virtual machine, I could have taken various shortcuts. For example, the ALU chip that you design for the computer can’t do multiplication or division. This is handled by the operating system. I could have just used Python’s multiplication operator to return the product of the two numbers. However, I took the time to program the multiplication algorithm they teach you, because that was something I wanted to learn. In the end, after programming it all in Python, I decided not to program it all over again in Jack.
It should be clear that the problems I had with the course were problems with me, not problems with the course. I think it was a well done and fascinating class. I recommend it for any programmer who is even vaguely interested in what is going on behind the scenes.