14 Nand2Tetris opcodes “they” don’t want you to know about!

Nand2Tetris is absolutely awesome, and I can’t recommend it enough. It’s a computer course that takes you from a single NAND gate all the way up the stack to a simple operating system. If you want a basic grounding in how computers really work, you should dive in.

I was introduced to Nand2Tetris last year when one of my sons took the course in college. I started following along, doing the assignments, and rapidly became addicted — I ended up writing a version of Conway’s Life in the HACK assembly language:

One of the assignments in the course is to write a simple assembler for the HACK machine language (lecture notes here). The machine language has two types of instructions: A=Address and C=Command, and 6 bits in C instructions directly control the CPU’s Arithmetic-Logic Unit (ALU).

The Hack ALU is a masterpiece of minimalist design; it has two 16-bit inputs (x and y) and 6 control bits (applied in order):

• zx : zero x
• nx : negate x
• zy : zero y
• ny : negate y
• o : if set, add x and y; if clear, and x and y
• no : negate o

So the python code for the ALU would look like this:

def alu(x: int, y: int, zx: bool, nx: bool, zy: bool, ny: bool, f: bool, no: bool) -> int:

   x = 0 if zx else x
   x = ~x if nx else x

   y = 0 if zy else y
   y = ~y if ny else y

   o = (x + y) if f else x & y
   o = ~o if no else o

   return o & 0xffff

Believe it or not, from this you can derive a huge number of useful instructions. The Hack Assembly language lets you compute 0, 1, -1, X, -X, -Y, Y, NOT(X), NOT(Y), X AND Y, X OR Y , X+1, Y+1, X-1, Y-1, X+Y, X-Y, and Y-X

For example, ALU instruction 111111 returns a constant 1 (zero x, negate x [x=-1], zero y, negate y [y=-1], add [o=-2=fffe], negate [o=1])

Now, there are 64 possible ALU opcodes, but the Hack assembler uses only the 18 listed above. So I started wondering whether any of the other opcodes were useful, and wrote a quick python script to explore what they did.

Many of the instructions simply provide the same result as other instructions; for example, X, Y, NOT(X) and NOT(Y) each have 4 variants, and the constants 0 and -1 each have 11 variants.

But that leaves 14 opcodes unaccounted for. What do they do?

The Obviously Useful

There are some opcodes that are obviously useful. In the list below, the ALU instruction bits are zx-nx-zy-ny-o-no.

111110 : 65534 (-2)
000001 : X NAND Y  : 00,01,10,11 TruthTable=1110
010100 : X NOR Y   : 00,01,10,11 TruthTable=1000

On a personal note, I think it’s a pity that the assembler for the Nand2Tetris CPU doesn’t implement NAND :)

The Logical but Weird

There are 4 instructions that implement logical operations with unusual truth tables.

010000 : NOT(X) AND Y      : 00,01,10,11 TruthTable=0100
010001 : NOT(NOT(X) AND Y) : 00,01,10,11 TruthTable=1011
000101 : NOT(X AND NOT(Y)) : 00,01,10,11 TruthTable=1101
000100 : X AND NOT(Y)      : 00,01,10,11 TruthTable=0010

Interestingly, the HACK ALU does not have an XOR instruction! In fact, because HACK only has two registers, you cannot do an XOR or XNOR on the machine without using a temporary memory variable; it’s quite costly. All the other 2-input boolean operations can be done in a single instruction:

+---- x=0, y=0
|+--- x=0, y=1
||+-- x=1, y=0
|||+- x=1, y=1
||||
vvvv
0000 X=0
0001 X AND Y
0010 X AND NOT(Y)
0011 X
0100 NOT(X) AND Y
0101 Y
0110 (unavailable) XOR
0111 X OR Y
1000 X NOR Y
1001 (unavailable) XNOR
1010 NOT(Y)
1011 NOT(NOT(X) AND Y)
1100 NOT(X)
1101 NOT(X AND NOT(Y))
1110 X NAND Y
1111 X=-1

The Truly Bizarro

There are 7 arithmetic instructions that just plain weird, though I can imagine that in unusual circumstances, they might prove useful.

010111 : X + Y + 1
000110 : X — Y — 1
011110 : -(X + 2)
110110 : -(Y + 2)
010110 : -(X + Y + 2)
000011 : -(X + Y + 1)
010010 : -(X — Y + 1)

One Last Thing…

It turns out that the official HACK machine emulation software does not actually emulate the ALU; instead it only implements the documented instructions. I’ve mentioned this to the creators, but likely they implemented it this way so that it would catch “bad” output from student-written assemblers.

Oh well… I’m sure that I would have spent many hours trying to find ways to justify using them in programs, so perhaps it’s for the best!