Nand 2 Tetris

#cs🏛️

Nand 2 Tetris is the brainchild of two CS professors at the Hebrew University of Jerusalem, Noam Nisan and Shimon Schocken. They have a corresponding textbook, The Elements of Computing Systems.

From Professor Schocken's personal website

In Nand 2 Tetris you build a computer from scratch using first principles. Starting with the most elementary logic gates (Nand is short for 'not and') you assemble each week's homework into a computer called 'Hack' that eventually becomes powerful enough to run a game of Tetris.

Nand 2 Tetris was one of the courses recommended over at teachyourselfcs.com, along with other very exciting courses on networking, databases, distributed systems, Lisp programming, and more. I want to study them all, but I'm starting with N2T. Below is a liveblog of units as I complete them. The challenges at the end of each week are sometimes pretty hard. I spend a lot of time in the blogs below simply celebrating.

Unit 1 - Logic Gates

Logic gates! Biggest challenge was realizing they expected (?) you to hard-code the 16 bits of the bigger chips. I looked up the solution there because I couldn't figure out how to do it programmatically, then it felt like cheating once I saw how it was done. It took me about a month to write all these logic gates. I only chip away at my coursework for an hour each day after work, so if I get stumped it can take a while. I was flying to a get-together of some internet people in March and was crammed into a coach seat with two other poor souls, my big elbows jostling them as I busted out my HackerMan ThinkPad laptop, fired up Neovim, and set my mind toward writing these Muxes and Demuxes.

Unit 2 - Binary Addition

I coded the ALU today, on April 6th. Feels like a million bucks. Turns out it all boiled down the multiplexors.

Mux16(a=first_bus,
b=second_bus, sel=function_controller,out=pass_it_down_the_line)`

Like a glorious little game of relay. Shocking how long it can take to crack these. For a long time I was wondering how to make the 16 bit busses talk to the single bit ones. Literally a Multiplexor's purpose!

Unit 3 - Sequential logic

Woe is me, I am Program Counter, destroyer of worlds.

This unit I breezed through early on, coming ferociously out of the gate to make a whole humongous RAM chip without breaking a sweat, then hitting a gnarly wall when I tried implementing the program counter chip.

Picture this like a wildebeest's head mounted on my wall. Finally, I got it today. I'm full of joy. It took a whole lot of pain to get here. The secret to my solution was to "invent" a value that was always 1, then pass it to a register such that that Register always spit out what was in it one second ago no matter what. Oh, it feels so good. jk

Unit 4 - Machine Language

Challenge 1: Mult.asm

May 25, 2022: Mult.asm hath been slain.

This was the moment the foe was felled. I was so used to seeing "Comparison error on line 2" that "End of script" made no sense to me for about ten seconds. I stared with my mouth open for a minute after that. This one was by far the most frustrating assignment, since I couldn't get the GUI Emulator to work and had to run everything from the terminal.

The problem all along was the I assigned my variable too late in my first iteration, even though logically it produces the same result--the test script specified the product of the operation get set to -1 at the outset, to make sure we initialized it as zero at the start of the program (which I didn't do). After that, all of the code worked.

Challenge 2: Fill.asm

And just shy of one month later... I've passed the other challenge of this unit, Fill.asm. This was an assembly program that turned the whole screen dark if a key was pressed, and otherwise left the screen white. What a ride. This was so hard. In my defense most of the month was getting Java to run well on my machine, but this was tough all the same.

Here lies June 21st, 2022 as the day I finally finished Unit 4.

In brief, my code:

  • stores the memory map location of the screen in RAM to a variable, address
  • sets the length of the screen's memory map to another variable, n
  • begins a loop initializing i to zero and checking the value of the keyboard memory map
  • if i (the incrementor of the loop) is greater than the length of the screen's memory map, go back to start and check the keyboard value again
  • checks keyboard memory again and loops through the length of the screen setting each byte/row of screen pixels to 0 (16 white pixels) if the key is 0 (unpressed) and -1 (16 black values) if the key is anything else (key is pressed)
  • goes back to the start of the loop

Gah, so glad this is over. One does not simply write machine code...

Unit 5 - Creating the Computer

CPU

July 26th, 2022: Today I completed my implementation of the CPU.

I made this. I was jamming out to Tame Impala while I passed the final test, so if you want to vicariously enjoy my elevated vibestate, let it happen. It wasn't as hard as I prepared for, to be honest. No doubt, it was quite challenging, but Unit 4 would've destroyed someone less committed. My reward for the persistence, I guess, is to knock this one out without many months of anguish. It was beautiful how the CPU distributes the instruction across its chip, slicing up each bit and placing its value in the appropriate gate. It is like watching a symphony, truly. Part of the genius of this course is the way it hits you with these grand reveals when you cross big milestones. We had no idea how the ALU worked to compute the necessary instructions in the computer; only now do we find out the x and y combined therein were the A, D, and M registers of machine code all along, waiting for the right instructions to activate. Glorious, truly. But I still need to do the ROM and peripherals, so let's not gush too much.

Memory

On this beautiful day, August 1st, I passed the Memory test, after only a short time in the simulator. Next up we'll wire them together to create the computer. So magical.

worker laying bricks

Workin' on it!

This post is still in the shop.