A Return To Basics

My copy of The Elements of Computing Systems came in the mail and I've been having a great time digging into the absolute fundamentals of programming. While I'm passingly familiar with some of the material, working the examples in the text has me finally feeling like I deeply understand the concepts.

Gates

Making a NAND

The text covers the basics of digital logic at a brisk pace, conceding the NAND gate to be the most fundamental aspect of its coverage. For the sake of completeness, I sketched out both creating a NAND from an AND/NOT pair, as well as the composition of the more basic gates from the "universal" NAND gate. Any further in creating these is an interesting, but distracting exercise with transistors -- which as the book states, are more the realm of electrical engineers than computer scientists.

So, how do you make a NAND gate? It's pretty simple, with NAND being the inversion (NOT) of the AND operation ¬(A·B)

Annoyingly, the hardware simulator accompanying the book assumes Nand.hdl to be a built-in and doesn't allow you to shadow with your own, so it must be named something like not-and.hdl. More annoyingly still, a direct translation of the above, while sensible, doesn't work and instead requires two NOT gates to invert each pin of the AND chip. I haven't worked out why this is the case, but it seems to be strictly an issue with the tool itself. So instead the working not-and.hdl file looks like:

CHIP NotAnd {
     IN a, b;
     OUT out;

     PARTS:
         Not(in=a, out=a2);
         Not(in=b, out=b2);
         And(a=a2, b=b2, out=out);
}

Because the NAND gate exhibits functional completeness the first interesting exercise is to re-implement those gates using only NAND.

NOT

If you squint just a bit at the truth table for the NAND gate, you'll notice that a NOT operation is emergent for two equivalent inputs. Consequently, all you have to do is wire both inputs together and you're done:

CHIP Not {
     IN in;
     OUT out;

     PARTS:
         Nand(a=in, b=in, out=out);
}

AND

Without getting boring, you can imagine then how AND can be implemented by (re)inverting a NAND gate.

CHIP And {
     IN a, b;
     OUT out;

     PARTS:
         Nand(a=a, b=b, out=o);
         Not(in=o, out=out);
}

OR

Another obvious one, included for completeness sake - OR is the logical inversion of NAND, not much to it, really.

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
        Not(in=a, out=a2);
        Not(in=b, out=b2);
        Nand(a=a2, b=b2, out=out);
}

XOR

XOR is an interesting one because it too exhibits functional completeness. It only clicked for me during the exercise that XOR is the same as ¬Equivalent, which was a fun realization (from an implementation perspective).

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
        Not(in=a, out=nota);
        Not(in=b, out=notb);
        And(a=na, b=b, out=c);
        And(a=a, b=nb, out=d);
        Or(a=c, b=d, out=out);
}

Tremendously frustrating, the above implementation also doesn't work with the hardware simulator. It appears to be a known issue and possibly a result of a recent update. I'm hugely impressed at the amount of tooling that went into the book, but only a little disappointed to have found what look like so many bugs out of the gate. XOR is pretty simple to validate by hand: ( x · ¬y ) + ( ¬x · y )

Adders

I was most excited to dig into adders (and the yet-to-be-explored ALU), Forth has given me and appreciation for low-level programming, but some of the fundamentals still elude me. I can appreciate pointer-arithmetic, but I couldn't tell you exactly how a register works. In that vein, implementing a half-adder and full-adder (2-bit and 3-bit, respectively) using only basic logic gates is a sound footing on which to get started.

Half-Adder

This one was pleasantly surprising in how easy it is, two gates!

The output of the AND is the carry and the output of the XOR is the sum.

Full-Adder

If the half-adder was pleasantly surprising, the full-adder was a revelation. It wasn't until I had it implemented that I realized the potential to use the same idea for an adder of any arbitrary n-bits. I've simplified the diagram below by replacing the above half-adder with a white box. The output of the OR is a check on the potential for a carry value in either of the two half-adders, the other output is the sum.

The similarity with the kind of design-by-contract advocated in How To Design Programs is interesting, and allows for an entertaining level of modularity. Because the inputs and outputs are maintained, it is possible to replace the boxes with the half-adder implementation, but why stop there - we could similarly replace it all with the NAND gates they are (logically) composed of!

My minor complaints with the software accompanying the book aside, I am thoroughly enjoying The Elements of Computing Systems. Just working the examples has me thinking of all kinds of retro-computing projects I might attempt next (specifically, I'm eyeing my copy of Threaded Interpretive Languages which was written against Z80 assembly).