Hack CPU emulator: from NAND gates to a running program

Pick a program or write your own in Hack assembly; the listing on the left shows each instruction's address and 16-bit machine word as you type. Set the inputs in RAM[0] and RAM[1], then Step one instruction at a time or Run. The CPU panel shows the A and D registers, the memory word A points at, and the program counter; the RAM table highlights the last word written. Programs that write to addresses from 16384 draw on the screen. Copy machine code gives the assembled program in the .hack text format, one binary word per line.

A NAND gate outputs 0 only when both inputs are 1. It is functionally complete: any Boolean function can be built from NANDs alone, so in principle a whole processor can be too. That is the premise of The Elements of Computing Systems by Noam Nisan and Shimon Schocken, whose nand2tetris course builds a computer called Hack from a NAND gate upward. The constructions used on this page, counted by evaluating them, take:

The Hack ALU computes a function of two 16-bit inputs, x and y, chosen by six control bits applied in order: zx sets x to 0, nx inverts x bitwise, zy and ny do the same to y, f selects x + y or x & y, and no inverts the result. Two flags report whether the output is zero (zr) or negative (ng). These six bits produce 18 useful functions, including 0, 1, −1, x, −x, x + 1, x − y and x | y; x − y, for example, is !(!x + y), since in two's complement !x = −x − 1. The explorer above evaluates the ALU gate by gate through 654 NANDs, and its results are checked against ordinary arithmetic for every function.

Hack has two instructions. The A-instruction @value loads a 15-bit constant into A; its word starts with 0. The C-instruction dest=comp;jump starts with 111, followed by one bit choosing whether the ALU's y input is A or M = RAM[A], the six ALU control bits, three dest bits (A, D, M) and three jump bits (less than, equal to, greater than zero). So @17, D=D+M, M=D and 0;JMP assemble to:

0000000000010001
1111000010010000
1110001100001000
1110101010000111

Because A both holds addresses and selects M, most work is a pair: @x to point at a variable, then a C-instruction to read or write it. A jump goes to the address in A, so @LOOP comes before 0;JMP.

The assembler makes two passes. The first walks the program counting instructions and records each label (LOOP) as the address of the instruction after it. The second translates each line: C-instructions by table lookup, and A-instructions by number, predefined symbol (R0 to R15, SP, LCL, ARG, THIS, THAT, SCREEN = 16384, KBD = 24576), label, or, if none of those, a new variable placed at the next free address from 16. In the multiplication program, n is such a variable and lands at RAM[16].

Every clock cycle the CPU fetches the instruction at the program counter and executes it: an A-instruction loads A; a C-instruction feeds D and A or M through the ALU, writes the result to the chosen destinations, and sets the PC either to A (if the jump condition holds) or to PC + 1. Writes to M and the jump use A's value from the start of the instruction. Counting instructions shows what a loop costs: adding two numbers takes 6 instructions, multiplying 6 by 7 by repeated addition 94, and summing 1 to 100 takes 1,410 to reach 5,050. The cost of the last two grows with their input, which is why real CPUs have hardware multipliers.

Hack has no I/O instructions. The screen and keyboard are memory-mapped: RAM from 16384 to 24575 is the screen, 256 rows of 32 words, one bit per pixel, with the least significant bit of each word the leftmost pixel; RAM[24576] holds the code of the key being pressed. Drawing is writing memory, so the "Draw on the screen" program writes −1 (sixteen 1 bits) to one word per row, adding 32 to the address to move down a row.