What I learned from Nand2Tetris

I completed the The Elements of Computing Systems course, a.k.a. Nand2Tetris just now, and I wanted to share what I learned from it while my memories are still warm.

I started it roughly a month ago, out of curiosity. It looked like an expansive course touching so many topics I wanted to research, but found tiresome to do. The description said it didn’t go into the gory details, which was a great relief for me. It was also mostly self-contained, and that was appealing too, because I’m mostly a novice programmer.

I gotta admit, I was into programming since I was a middle-schooler, but I never got the chance to really dive into it. It was nothing but laziness, since I always found programming intriguing. Although I haven’t been programming at all, I’m an avid Hacker News reader.

Let’s talk about the course, not me. It starts with the logic gates and walks you through building a complete computing system, hardware and software. While you need to build all the components, it’s recommended to follow the design given in the course materials. Designing the system by yourself would be out of the scope of the course, and in many cases, reinventing the wheel.

First you’re introduced to the logic gates, and you’re supposed to build all basic gates out of NAND gates, and other gates you have built on the way. It’s basically the essence of the course; you got to build bigger things using what you built in the previous chapters. You build arithmetic units and ALU on top of the logic gates you built. Then you’re introduced to sequential logic and you build registers, RAM and program counter. With the help of those, you’ll build a CPU, memory and eventually the computer. The last thing you do in the first half of the course is writing an assembler that converts assembly code — its specification is provided — to the hardware description language you’ve been using to combine the logic gates.

My first choice of programming language for building the assembler was Ruby, but after I wrote the skeleton of the API, I scrapped it and switched to Python. I feel like it would be more natural to write in Ruby than Python, but it was a pragmatic choice. While Ruby is pretty mature now, Python is used more widely and it’s easier to find a job with Python experience here in where I live.

The second half of the course is about making a modern computing platform. This requires you to build two parts of a compiler; the first half translates intermediate virtual machine code to assembly language of the hardware platform (called ‘Hack’), while the second part compiles the high level Java-like code (called ‘Jack’) to the VM bytecode. Since writing a compiler is pretty hard, it’s split into two chapters. When building the VM translator, first you learn stack arithmetic and use it to perform arithmetic operations. You also implement access to different memory blocks, and this concludes the first part of the VM.

Second part of the VM implementation handles the function calling and branching part of the virtual machine. It seems easy at first, but function calling requires you to push arguments, local variables and so on; and you have to deallocate these when returning from the function. You also need to return a variable, but if that function has void type, the return value (which is ‘0’ for null functions) is discarded (popped to an unused memory segment). It takes a lot of time and patience, but it’s pretty enlightening.

With the virtual machine completed, you learn the specification of the high-level language, Jack. You come back to it for the next two chapters, where you build the second part of the compiler. The first chapter dedicated to the compiler is about syntax analysis and building a tokenizer. I knew the term tokenizer and abstract syntax tree before, back when I was learning Lisp, but I didn’t appreciate Lisp before building one myself. I could use Python’s Pygments library for this part, but I wanted to get my hands dirty instead. It wasn’t particularly pretty. I had to generate an XML tree and it was one of the most horrible things I had to deal with in my whole life. Unfortunately, the reference files I had to compare with were XML, so I didn’t have much choice.

After countless curses to XML I completed it and went on with the second part; code generation. I had to add a symbol table to keep track of the variables and replace the tokenizer output module to output VM bytecode instead of XML. It seemed fairly easy, but turned out really hard and time consuming. There were six tests, and my code broke in every single one of them. I’d pass one test and the next one would throw errors I wouldn’t even imagine. I guess it was because I forgot the VM code and design while I was building the tokenizer part and dealing with ugly, ugly XML.

Sometimes I would get really hopeless and cheat a little by compiling the test code with the provided compiler and decrypting the VM code in my head. (Well, I wouldn’t really call it cheating, the compiler was there and compiled code was kind of a reference.) In the end I fixed all the bugs which didn’t let it pass the test and it still wouldn’t compile the test code for the next chapter correctly. (The provided compiler would also show useful error messages for errors in my Jack code, which I didn’t implement in my half-baked compiler. I didn’t really care because I had to move on and passing the tests were good enough for me.)

That was an important part of the course. I mean, I would read a book about compilers, but all the details and optimization and whatnot would just confuse me and I’d get discouraged and drop it. This course is — in its own words — simple enough, but not simpler. You’re developing everything on your own. You’re just provided with the design and implementation tips but nothing more. There’s the VM Emulator, which runs your VM code instead of you translating it into hardware code and running it on the Hardware Simulator, but it’s there just for the sake of efficiency. Once you build the VM, you can run it on the Hardware Simulator if you have a really fast computer. (It doesn’t get any lower-level than the Hardware Simulator though; actually building the hardware is out of the scope of the course.)

It was a really great experience to take this course. I did it at my own pace and it took a little more than a month. (Including vacations and breaks I took out of desperation.) It touched so many different topics, teaching me of their essence; if I wanted to pursue any single one, I would know what to expect. The chapters were well split and completing them were just hard enough to keep my interest while giving me the feeling of accomplishment for doing it. It’s truly a job well done.

The last chapter was about building the operating system and standard library functions in Jack language, previously provided for testing purposes. It briefly touched the topics of algorithms, complexity and data structures. As my next move, I’ll dive into these, which seems pretty important. Oh, and lastly when I was learning about the specs of the Jack language I was supposed to build a game in it, I chose to build a single player Pong clone; which looks more Breakout than Pong, minus the bricks. One of the things I really wanted to get into was game development, and I made my first mini-game in this course, with a language I have implemented!

All in all, I’m really happy I took this course. This is my favorite course so far, maybe head to head with Programming Languages course by Dan Grossman I took a year ago on Coursera. It taught me many topics I was curious about, while keeping fun, and in a month. What else could I expect?

If you’re into programming but you’re too young for college, or studying another major, or graduated and looking for a fun project; I completely recommend this course. Even if you’re a starter. (According to the course introduction, it’s CS101 in at least one college.)

One more thing. It’s never too late. I graduated from mechanical engineering and I’m planning on pursuing a career of programming. I’ll be taking more courses, learning and developing. So if you’re interested in hiring me, contact me on my Twitter.

Update 10/2016: I have a full time job at a great company and working on my M.S. on Computer Science. Guess I was on the right track.