From Nand to Tetris - My Way

A while back a free online course caught my eye called From Nand to Tetris. The idea behind Nand to Tetris is that at the beginning of the course it's assumed that god gave us the nand gate and from there we can build up to a computer that can run tetris.

I've watched a few of the videos in the past and have always really been interested in it. Since then I have done quite a bit of reading and learning about how computers work at the lowest level. I've worked through Ben Eaters 6502 and 8-bit CPU series and it's really sparked a new passion in me for understanding computers at the lowest level possible.

I, being me, can't just leave anything well enough alone. For that reason I'm going to follow the course closely, but I'm actually going to write everything in C.

Why not just follow the course, why write everything in C?

Well, I want to get better at writing C. That's kinda the whole reason. I'm not even close to being a good C programmer, or programmer for that matter. When you're self taught you have to find unique ways to learn and one of the most challenging parts is finding a project to work on this is both rewarding and realistic. Nand to Tetris gives the unique opportunity to fufill both the rewarding (building an entire computer from a nand gate, sweet) and realistic (the entire project is laid out clearly and sequentially, I just have to come up with the code).

Additionally, I think it's right at the edge of my comfort zone. I've worked quite a bit in C in embedded projects but I've never really been given an actual reason to do a complete cohesive project from the bottom up. I have some experience making some toy emulators and playing around with making some programming languages but this course is unique in that I get to write everything and it all has to work for this custom platform that is the hack computer.

Really, everything in C?

This is the last I'm gonna talk about this deviation from the course. No, not everything. I'm going to do the 'hardware' section using the supplied HDL language, and once I've done the implementations in HDL I will take a break from the course to write the emulator. It should make pretty good sense to me given I will have just created the architecture so it should go pretty quick.

The initial gates.

The first thing the course has you do is learn about how logic gates work, and then implement some of the basic ones. This was mostly pretty easy and when it wasn't it turned out that I was really just trying really hard to overengineer things. It's also already organized for you in the order that you should build the gates both in difficulty and in the order that makes sure you always have the dependant gates available to you.

The first gate we implement is the Not gate. The not gate simply takes one input, and outputs the opposite. Input is a 1, output is a 0, input is a 0, output is a 1.

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Not.hdl
/**
 * Not gate:
 * if (in) out = 0, else out = 1
 */
CHIP Not {
    IN in;
    OUT out;
 
    PARTS:
     Nand(a=in, b=in, out=out);
}

As you can see, the implementation is pretty straightforward. Simply send the input to both sides of a nand gate, and bingo.

Then it's the And gate. Again, a fairly simple implementation.

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/And.hdl
/**
 * And gate:
 * if (a and b) out = 1, else out = 0
 */
CHIP And {
    IN a, b;
    OUT out;
 
    PARTS:
      Nand(a=a, b=b, c=notout);
      Not(in=notout, out=out);
}

We want And, we have Nand, so we just take the nand and invert (Not) the output. This is what I mean about the course making sure you have the dependant gates available to you. Now, I'm not going to go through all the gates here but I will call out a couple that caught me off guard.

The Mux chip.

Mux (or multiplexer) is a gate that takes two inputs and a selector. The selector determines which input is passed through to the output. The implementation is pretty straightforward but it had me grinding my gears for a bit. This is an example of a gate that I spent a lot of time trying to overengineer when what I really needed to do was just step back and realize that these are all really rudimentary gates.

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/And.hdl
/**
 * And gate:
 * if (a and b) out = 1, else out = 0
 */
CHIP And {
    IN a, b;
    OUT out;
 
    PARTS:
      Nand(a=a, b=b, c=notout);
      Not(in=notout, out=out);
}

I wish I had some code examples of what I was writing when I first tried this. I'd guess there were around 10-15 lines of code under 'PARTS', but, in hindsight I was just being a fucking idiot.

The Mux8Way16 chip.

This one is a really fucky chip. It takes 16 inputs, has 3 select lines, and outputs the value of the selected input. This one really ate at me, and ended up taking me a couple hours to actually get. It's was challenging in part because a.) I was still trying to overengineer things and b.) there is a bit of syntax that I missed during the HDL introdction video. There's a sort of 'spread' operator that you can use that I wasn't aware of and didn't find until I was on my last leg and reading the HDL reference on the nand2tetris website.

 
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Mux8Way16.hdl
/**
 * 8-way 16-bit multiplexor:
 * out = a if sel = 000
 *       b if sel = 001
 *       c if sel = 010
 *       d if sel = 011
 *       e if sel = 100
 *       f if sel = 101
 *       g if sel = 110
 *       h if sel = 111
 */
CHIP Mux8Way16 {
    IN a[16], b[16], c[16], d[16],
       e[16], f[16], g[16], h[16],
       sel[3];
    OUT out[16];
 
    PARTS:
    Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=muxabcd);
    Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=muxefgh);
 
    Mux16(a=muxabcd, b=muxefgh, sel=sel[2], out=out);
}
 

As you can see it works out to be only 3 fucking lines of code. Mux4Way16 for each of the 8 ways, but the part that hung me up was the sel[0..1] syntax. I was trying to find a way to build a selector from the 3 select lines, but it turns out that you can just use the spread operator to pass the entire selector array to the Mux4Way16 gates.

I worked through all of the basic gates and will be on to the next section that will be the half-adder, adder, and up to the ALU. I think this is the part that's gonna get really exciting for me. Shortly after that we'll likely be making RAM and, of course, the CPU. Once that piece is done, I'll move on to building the emulator.