summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFrederick Yin <fkfd@fkfd.me>2022-08-18 20:44:33 +0800
committerFrederick Yin <fkfd@fkfd.me>2022-08-18 20:44:33 +0800
commit9b4dc7b918935c31659e72cf36c1af0ea4fa8981 (patch)
tree5f6ec12923ebd7770e077618936e8d6e38553228
parent18cb29e1a166eddcc783838f3171c9f000d45577 (diff)
New post: projects/nand2tetris_1
-rw-r--r--docs/projects/img/nand2tetris/6502.jpgbin0 -> 235588 bytes
-rw-r--r--docs/projects/img/nand2tetris/alu.krabin0 -> 507037 bytes
-rw-r--r--docs/projects/img/nand2tetris/alu.pngbin0 -> 122130 bytes
-rw-r--r--docs/projects/img/nand2tetris/alu_highlighted.pngbin0 -> 93144 bytes
-rw-r--r--docs/projects/img/nand2tetris/and_gate.pngbin0 -> 11081 bytes
-rw-r--r--docs/projects/img/nand2tetris/and_gate_nand.pngbin0 -> 17995 bytes
-rw-r--r--docs/projects/img/nand2tetris/and_gate_nand_not.pngbin0 -> 16708 bytes
-rw-r--r--docs/projects/img/nand2tetris/computer.krabin0 -> 460149 bytes
-rw-r--r--docs/projects/img/nand2tetris/computer_registers.pngbin0 -> 143235 bytes
-rw-r--r--docs/projects/img/nand2tetris/cpu.krabin0 -> 841631 bytes
-rw-r--r--docs/projects/img/nand2tetris/cpu.pngbin0 -> 222785 bytes
-rw-r--r--docs/projects/img/nand2tetris/cpu_book.pngbin0 -> 170476 bytes
-rw-r--r--docs/projects/img/nand2tetris/cpu_controls.pngbin0 -> 196576 bytes
-rw-r--r--docs/projects/img/nand2tetris/cpu_emulator_pong.pngbin0 -> 49719 bytes
-rw-r--r--docs/projects/img/nand2tetris/cpu_hunch.pngbin0 -> 177527 bytes
-rw-r--r--docs/projects/img/nand2tetris/cpu_mysterious_jump_logic.pngbin0 -> 227952 bytes
-rw-r--r--docs/projects/img/nand2tetris/mux.pngbin0 -> 27133 bytes
-rw-r--r--docs/projects/img/nand2tetris/pc.pngbin0 -> 84490 bytes
-rw-r--r--docs/projects/img/nand2tetris/pc_incorrect.pngbin0 -> 83727 bytes
-rw-r--r--docs/projects/img/nand2tetris/register.pngbin0 -> 15090 bytes
-rw-r--r--docs/projects/img/nand2tetris/register_internal.pngbin0 -> 26004 bytes
-rw-r--r--docs/projects/img/nand2tetris/zx_nx.pngbin0 -> 26921 bytes
-rw-r--r--docs/projects/index.md8
-rw-r--r--docs/projects/nand2tetris_1.md947
24 files changed, 955 insertions, 0 deletions
diff --git a/docs/projects/img/nand2tetris/6502.jpg b/docs/projects/img/nand2tetris/6502.jpg
new file mode 100644
index 0000000..06c6e7f
--- /dev/null
+++ b/docs/projects/img/nand2tetris/6502.jpg
Binary files differ
diff --git a/docs/projects/img/nand2tetris/alu.kra b/docs/projects/img/nand2tetris/alu.kra
new file mode 100644
index 0000000..a86fafa
--- /dev/null
+++ b/docs/projects/img/nand2tetris/alu.kra
Binary files differ
diff --git a/docs/projects/img/nand2tetris/alu.png b/docs/projects/img/nand2tetris/alu.png
new file mode 100644
index 0000000..64bed05
--- /dev/null
+++ b/docs/projects/img/nand2tetris/alu.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/alu_highlighted.png b/docs/projects/img/nand2tetris/alu_highlighted.png
new file mode 100644
index 0000000..3290f07
--- /dev/null
+++ b/docs/projects/img/nand2tetris/alu_highlighted.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/and_gate.png b/docs/projects/img/nand2tetris/and_gate.png
new file mode 100644
index 0000000..95a8ec6
--- /dev/null
+++ b/docs/projects/img/nand2tetris/and_gate.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/and_gate_nand.png b/docs/projects/img/nand2tetris/and_gate_nand.png
new file mode 100644
index 0000000..9af285a
--- /dev/null
+++ b/docs/projects/img/nand2tetris/and_gate_nand.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/and_gate_nand_not.png b/docs/projects/img/nand2tetris/and_gate_nand_not.png
new file mode 100644
index 0000000..e230230
--- /dev/null
+++ b/docs/projects/img/nand2tetris/and_gate_nand_not.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/computer.kra b/docs/projects/img/nand2tetris/computer.kra
new file mode 100644
index 0000000..72cab90
--- /dev/null
+++ b/docs/projects/img/nand2tetris/computer.kra
Binary files differ
diff --git a/docs/projects/img/nand2tetris/computer_registers.png b/docs/projects/img/nand2tetris/computer_registers.png
new file mode 100644
index 0000000..4999988
--- /dev/null
+++ b/docs/projects/img/nand2tetris/computer_registers.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/cpu.kra b/docs/projects/img/nand2tetris/cpu.kra
new file mode 100644
index 0000000..2022f55
--- /dev/null
+++ b/docs/projects/img/nand2tetris/cpu.kra
Binary files differ
diff --git a/docs/projects/img/nand2tetris/cpu.png b/docs/projects/img/nand2tetris/cpu.png
new file mode 100644
index 0000000..c29068f
--- /dev/null
+++ b/docs/projects/img/nand2tetris/cpu.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/cpu_book.png b/docs/projects/img/nand2tetris/cpu_book.png
new file mode 100644
index 0000000..2611a06
--- /dev/null
+++ b/docs/projects/img/nand2tetris/cpu_book.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/cpu_controls.png b/docs/projects/img/nand2tetris/cpu_controls.png
new file mode 100644
index 0000000..77c034a
--- /dev/null
+++ b/docs/projects/img/nand2tetris/cpu_controls.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/cpu_emulator_pong.png b/docs/projects/img/nand2tetris/cpu_emulator_pong.png
new file mode 100644
index 0000000..5dd9a75
--- /dev/null
+++ b/docs/projects/img/nand2tetris/cpu_emulator_pong.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/cpu_hunch.png b/docs/projects/img/nand2tetris/cpu_hunch.png
new file mode 100644
index 0000000..5c12596
--- /dev/null
+++ b/docs/projects/img/nand2tetris/cpu_hunch.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/cpu_mysterious_jump_logic.png b/docs/projects/img/nand2tetris/cpu_mysterious_jump_logic.png
new file mode 100644
index 0000000..a460fcd
--- /dev/null
+++ b/docs/projects/img/nand2tetris/cpu_mysterious_jump_logic.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/mux.png b/docs/projects/img/nand2tetris/mux.png
new file mode 100644
index 0000000..da7f3d2
--- /dev/null
+++ b/docs/projects/img/nand2tetris/mux.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/pc.png b/docs/projects/img/nand2tetris/pc.png
new file mode 100644
index 0000000..0cbbd20
--- /dev/null
+++ b/docs/projects/img/nand2tetris/pc.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/pc_incorrect.png b/docs/projects/img/nand2tetris/pc_incorrect.png
new file mode 100644
index 0000000..2ac3ae8
--- /dev/null
+++ b/docs/projects/img/nand2tetris/pc_incorrect.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/register.png b/docs/projects/img/nand2tetris/register.png
new file mode 100644
index 0000000..ff32d3c
--- /dev/null
+++ b/docs/projects/img/nand2tetris/register.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/register_internal.png b/docs/projects/img/nand2tetris/register_internal.png
new file mode 100644
index 0000000..f9ef91e
--- /dev/null
+++ b/docs/projects/img/nand2tetris/register_internal.png
Binary files differ
diff --git a/docs/projects/img/nand2tetris/zx_nx.png b/docs/projects/img/nand2tetris/zx_nx.png
new file mode 100644
index 0000000..14330a2
--- /dev/null
+++ b/docs/projects/img/nand2tetris/zx_nx.png
Binary files differ
diff --git a/docs/projects/index.md b/docs/projects/index.md
index f151c77..91d2bc6 100644
--- a/docs/projects/index.md
+++ b/docs/projects/index.md
@@ -8,6 +8,14 @@ MkDocs). But the few that do, are here.
Projects below are sorted reverse chronologically (most recent first).
+## [nand2tetris, Part 1](nand2tetris_1)
+
+![Diagram of a simple computer](img/nand2tetris/computer_registers.png)
+
+In July 2022 I enrolled in a course called nand2tetris. In part one of
+this course I built a computer from NAND gates and ran assembly on it. It
+was great fun.
+
## [SIRTET](sirtet)
![Screenshot of SIRTET mid-game](img/sirtet/sirtet.png)
diff --git a/docs/projects/nand2tetris_1.md b/docs/projects/nand2tetris_1.md
new file mode 100644
index 0000000..12a8704
--- /dev/null
+++ b/docs/projects/nand2tetris_1.md
@@ -0,0 +1,947 @@
+# nand2tetris, Part 1
+
+2022-08-18
+
+> _"It takes building one yourself to realize you don't deserve a computer."_
+
+On 2022-07-22, I finally clicked into the bookmark that had been sitting
+in my "University readlist" folder, untouched, since last August. Somehow
+I justed wanted to build a computer all of a sudden.
+
+First a bit of background. [Nand to Tetris](https://www.nand2tetris.org/)
+is a course available online by Noam Nisan and Shimon Shocken that teaches
+you how to build a modern (albeit extremely simple) computer all the way
+up from NAND gates. The course is divided in two parts, to which I have
+given the following nicknames:
+
+- Part 1, NAND to Computer
+- Part 2, Computer to Tetris
+
+The first part of the course consists of 6 projects. On 2022-08-16
+I completed all of them. In this blogpost I will recap what I learned from
+the course, and from my mistakes. __WARNING: There will be spoilers. If
+all you need is reasons why you should enroll, go to [Course
+review](#course-review)__.
+
+I've uploaded my current projects to [this git repo](https://git.fkfd.me/nand2tetris.git/).
+
+## Project 01: Elementary gates
+
+In this project I built a few basic logic gates, such as AND, XOR, and the
+(De)Mux, using a custom HDL language invented for the course. Here is the
+code for the AND gate:
+
+```
+CHIP And {
+ IN a, b;
+ OUT out;
+
+ PARTS:
+ Nand(a=a, b=b, out=nout);
+ Not(in=nout, out=out);
+}
+```
+
+Graphically, the HDL describes the following schematic:
+
+![A NAND connected to a NOT](img/nand2tetris/and_gate_nand_not.png)
+
+Here `a`, `b` and `out` are hardcoded, but `nout` is an arbitrary name
+I gave to the internal pin. If we further substitute the implementation of
+`Not` in `Nand`, this is what _actually_ lives on the silicon:
+
+![Two NANDs](img/nand2tetris/and_gate_nand.png)
+
+Once we have written this HDL code, we can encapsulate the AND gate in the
+following symbol, which is in essence two NAND gates in a trenchcoat:
+
+![One AND](img/nand2tetris/and_gate.png)
+
+And this is one of the few chips that have so few pins exposed (hence
+"elementary") that you can craft a truth table for it, and thus can test
+them manually.
+
+<details>
+<summary>
+ <b>How I built and optimized the XOR gate by toying with boolean
+ expressions (click to expand)</b>
+</summary>
+
+Here is the truth table of XOR, and you have to implement it with chips
+you already made, which are AND, OR, NOT, and NAND.
+
+```
+ a | b | out
+---|---|----
+ 0 | 0 | 0
+ 0 | 1 | 1
+ 1 | 0 | 1
+ 1 | 1 | 0
+```
+
+The solution is not immediately obvious (you can skip this part if you
+find it so). It is proven that, given any truth table of finite columns,
+you can construct a boolean expression satisfying it using what's called
+a "disjunctive normal form". Here's how it works. First you extract every
+row that outputs 1:
+
+```
+ a | b | out
+---|---|----
+ 0 | 1 | 1
+ 1 | 0 | 1
+```
+
+Then we tie a NOT to each 0 input (excuse the pun), thus synthesizing two
+sufficient conditions so that <code>out=1</code>:
+
+```
+(NOT a) AND b => out=1
+a AND (NOT b) => out=1
+```
+
+Finally, we OR them both, resulting in a single boolean expression:
+
+```
+((NOT a) AND b) OR (a AND (NOT b))
+```
+
+From a pragmatic perspective, our job is done. But the whole premise of
+nand2tetris is that, we're building every chip out of NAND gates, and I'm
+challenging myself to use as few as possible. So let's count how many NAND
+gates we need to make a XOR.
+
+```
+Gate | # of NAND gates
+-----|----------------
+NAND | 1
+NOT | 1
+AND | 2
+OR | 3
+XOR | ?
+```
+
+```
+((NOT a) AND b) OR (a AND (NOT b))
+ ^ ^ ^ ^ ^
+ 1 2 3 2 1
+```
+
+That's 9 in total. Can we optimize it? Let's try eliminating the OR first,
+based on the fact that <code>a OR b = NOT((NOT a) AND (NOT b))</code>:
+
+```
+ ((NOT a) AND b) OR (a AND (NOT b))
+= NOT((NOT((NOT a) AND b)) AND (NOT(a AND (NOTb))))
+```
+
+At first glance this might seem more complicated, but remember,
+<code>NOT(a AND b) = a NAND b</code>… which is exactly our atomic building
+block! We continue our equation:
+
+```
+= ((NOT a) NAND b) NAND (a NAND (NOT b))
+```
+
+Since NOT and NAND are both made of one single gate, our optimized number
+of gates is 5. (However, this optimization did not matter for a reason
+I will explain later.)
+</details>
+
+There were many other chips I was already familiar with, so I implemented
+them with little trouble apart from the HDL syntax.
+
+## Project 02: ALU
+
+The goal of building a computer in this theoretical approach is to conjure
+up a way to make a pool of NAND gates capable of thinking. This project
+does exactly that. Yes, you are right: I built an ALU.
+
+The fundamental idea of an ALU is that, you give it two inputs `x` and `y`
+and pick a function `h`, and for some reason it outputs `h(x, y)` where
+`h` is one of the following:
+
+```
+0, 1, -1, // constant value
+x+y, x-y, y-x // arithmetics
+x, y, -x, -y, !x, !y, // single variable function
+x+1, y+1, x-1, y-1, // one variable + constant
+x&y, x|y // boolean operation
+```
+
+You supply 6 bits known as "control bits" that let the ALU decide what
+function you want. They are:
+
+- `zx`, `zy`: coerce x or y to zero when set
+- `nx`, `ny`: negate x or y when set (binary NOT)
+- `f`: performs binary arithmetics when set, boolean operation otherwise
+- `no`: negate output-to-be
+
+But how do you know when you need to negate or zero the operands? Doesn't
+this call for an `if` statement? Well, in project 01 I made a chip named
+`Mux16` and it is _tremendously_ helpful. It's the hardware embodiment of
+`if () ... else ...`.
+
+![Schematic of a mux](img/nand2tetris/mux.png)
+
+(In reality we are using the 16-bit version, but in principle they're the
+same.)
+
+This means I just need to hook `nx` and `zx` to `sel` pins, and route
+`a`'s and `b`'s somewhere.
+
+The HDL that does this job for `x` is:
+
+```
+Mux16(a=x, b=false, sel=zx, out=zdx); // false = all 0's
+Not16(in=zdx, out=ndx);
+Mux16(a=zdx, b=ndx, sel=nx, out=px);
+```
+
+Graphically:
+
+![Two muxes in series outputting "px"](img/nand2tetris/zx_nx.png)
+
+(The order of the muxes matters, because when `zx = nx = 1`, this logic
+configuration yields `~0 = -1` while the other way gives you 0.)
+
+The same goes for `y`. Now that we have the processed version of `x` and
+`y`, denoted `px` and `py`, it's time to force this pile of imaginary NAND
+gates to do math for us. The boolean AND operation is trivial, so we will
+only be talking about the Adder, which is a chip that takes two binary
+numbers `x` and `y` and outputs `(x+y) % 65536`, that is, carries every
+bit except the MSB.
+
+But wait! Didn't we just see "x-y" and "y-x"? How can an Adder possibly do
+that? Note that there is no "Subtractor"; to do `x-y` you simply calculate
+`~(~x + y)` where `~` denotes bitwise negation, thanks to 2's complement.
+
+<details>
+<summary><b>Proof that <code>x-y = ~(~x + y)</code></b></summary>
+
+We know in 2's complement,
+
+```
+~x + x = 0xffff = -1 <==> ~x = -1 - x
+```
+
+Add y to both sides, we get
+
+```
+~x + y = -1 - x + y
+```
+
+Therefore, by means of negation,
+
+```
+~(~x + y) = -1 - (~x + y)
+ = -1 - (-1 - x + y)
+ = -1 + 1 + x - y
+ = x - y ⌷
+```
+</details>
+
+(Nisan and Shocken have supplied this course with a table where you can
+look up the ALU output given six control bits, or vice versa, but it won't
+be a necessity until project 06.)
+
+In addition to a 16-bit output bus (we call a group of indexable pins
+a "bus"), the ALU outputs two flags: `ng` and `zr`. If the final output is
+negative, `ng` is set; if it is zero, `zr` is set. The clever thing is,
+`ng` is just the highest bit of the output, i.e. `out[15]`, and `zr` is
+set iff every bit in `out` is zero.
+
+That's it, we have completed the ALU! I know y'all are anticipating the
+schematics; how can I let you down?
+
+![Schematic of ALU](img/nand2tetris/alu.png)
+
+For some reason nand2tetris only provided me with `Or8Way`, which OR's
+together 8 bits, so I had to use two of them to do all 16. I tried writing
+an `Or16Way` "helper chip" in the project 01 folder, but when I tried to
+include it in the ALU, it did not work. Why?
+
+When you tell the hardware simulator to load a chip, it first looks for
+`<chip_name>.hdl` under the working directory; if there's no such file, it
+proceeds to look for builtin chips implemented in Java. No other directory
+is in its path, even project 01. This explains why the optimization I made
+in project 01 does not matter.
+
+<details>
+<summary><b>If it did matter, how many NANDs are there in this ALU?</b></summary>
+
+It's Python scripting time! I just need to recursively find out how many
+NANDs in each subchip, then add them up. The syntax of HDL is pretty
+simple, and the script goes as follows (simplified):
+
+```
+HDL_PROJECTS = ["01", "02", "03/a", "03/b", "05"]
+
+CHIPS = {
+ "Nand": 1,
+ "DFF": 6, # https://commons.wikimedia.org/wiki/File:Edge_triggered_D_flip_flop.svg
+}
+
+
+def count_nands(project_path, chip):
+ # figure out where the HDL is
+ f = None
+ for dir in HDL_PROJECTS:
+ try:
+ f = open(project_path + dir + f"/{chip}.hdl")
+ break
+ except FileNotFoundError:
+ continue
+
+ if f is None:
+ print(f"Chip not found: {chip}", file=stderr)
+ return 0
+
+ while f.readline().strip() != "PARTS:":
+ continue
+
+ nands = 0
+ line = f.readline() # e.g. " Not (in=in, out=out); // comment"
+ while line:
+ code = line.split("//")[0].strip() # e.g. "Not (in=in, out=out);"
+ if "(" not in code:
+ line = f.readline()
+ continue
+ subchip = code.split("(")[0].strip() # e.g. "Not"
+ if subchip not in CHIPS:
+ CHIPS[subchip] = count_nands(project_path, subchip)
+ print(f"{subchip}\t{CHIPS[subchip]}")
+
+ nands += CHIPS[subchip]
+ line = f.readline()
+
+ f.close()
+ return nands
+
+chip = "ALU"
+nands = count_nands("/path/to/nand2tetris/projects/", chip)
+print(f"There are {nands} NAND gates in {chip}")
+```
+
+The output is (vertically aligned):
+
+```
+Not 1
+And 2
+Or 3
+Mux 8
+Mux16 128
+Not16 16
+And16 32
+Xor 5
+HalfAdder 7
+FullAdder 17
+Add16 262
+Or8Way 21
+There are 1156 NAND gates in ALU
+```
+
+Pretty sure my algorithm's right. Honestly it's fewer gates than
+I imagined because the ALU seemed to do so many things.
+</details>
+
+Most of the chips I made in project 02 are too complex to test by hand,
+but fortunately nand2tetris provides test scripts and compare files you
+can run in a hardware simulator that simulates the logic described by the
+HDL.
+
+While I was drawing the schematics, a question came to mind: If I set `f`
+to zero, will the Adder be working the same way as if `f=1`?
+
+<details>
+<summary><b>Answer</b></summary>
+
+Yes, it will. Simply put, chips "downstream" do not directly affect those
+"upstream" as far as this course is concerned. The implication is that,
+when you give an x and a y to the ALU, it does both computations at once:
+boolean AND and binary addition. It is the Mux's job to select which
+branch to pass downstream, and which one to discard. This is, in
+a stretch, called
+<a href="https://en.wikipedia.org/wiki/Speculative_execution"> speculative execution</a>.
+
+<img alt="Schematic of ALU. The AND, Adder, and &quot;f&quot; mux are
+highlighted" src="../img/nand2tetris/alu_highlighted.png" />
+
+As you see in the highlighted area, <i>both</i> of these gates are
+switching internally, and both of them consume power, even when one of
+them does not generate useful output. Recall the <code>if</code> statement
+in programming:
+
+```
+if (boolean) {
+ do_a();
+} else {
+ do_b();
+}
+```
+
+Either but not both of <code>do_a</code> or <code>do_b</code> will be run.
+This is one of the major mindblowers I came into, and I think it's worth
+writing about it.
+</details>
+
+## Project 03: Memory
+
+In project 02 we made an ALU think, but only once. This is because it
+doesn't remember anything. So if we want to build a computer, we need to
+make something that keep a record of what has been done, and what is left
+to do.
+
+The D flip-flop (DFF) is a chip that remembers one bit of information for
+one clock cycle. It's the fundamental building block for sequential logic
+in nand2tetris. Limitations in the simulator forbid building it from NAND
+gates yourself, because to do that you would need to wire an output into
+the input, which forms an infinite loop which the simulator is incapable
+of resolving. Instead, it provides a builtin chip, `DFF`, using which you
+can build registers from 1 bit to 16K words.
+
+Here's how a register works from the user's point of view:
+
+![Schematic of chip with in, load, and out pins](img/nand2tetris/register.png)
+
+If you give it some data via `in` and pull `load` to logic one, the data
+will show up in `out` at the next clock cycle. However as long as `load`
+remains zero, `out` does not change, as if "remembering" the data.
+
+But doesn't the D flip-flop only keep its data for one clock cycle? Yes,
+but we can find our way around it. We simply use a Mux as a "valve": it
+only lets `in` pass through when `load` is high. Otherwise, we feed `out`
+into the DFF again, creating an eternal feedback loop, but this time the
+simulator handles it with no problem, because the loop is delayed by one
+clock cycle each step.
+
+![Schematic of Mux and DFF in register](img/nand2tetris/register_internal.png)
+
+The RAM I proceeded to build is just an array of arrays of arrays of … of
+arrays of registers. Just copy and paste; no thinking required.
+
+The Program Counter (PC for short) however, ground my brains like jelly in
+a blender. Its job is to remember a number, increment it by one each clock
+cycle, and set it to some other value when required. The user controls it
+using three control pins: `load`, `inc`, and `reset`. The increment
+happens when `inc=1`, unless `load=1`, in which case the PC swallows the
+data on the `in` bus and spits it out at the next clock cycle, then
+increment that value from now on. `reset`, of course, forces the output to
+zero.
+
+It's not hard to think of using the Register for storage and Inc16 (16-bit
+incrementer) to do the math. The rest is Muxes, just like this:
+
+![PC with "out" wired to output of the final "reset" mux](img/nand2tetris/pc_incorrect.png)
+
+There is a problem with this solution. Do you see it? Let's read the chip
+specs again carefully:
+
+```
+if (reset[t] == 1) out[t+1] = 0
+else if (load[t] == 1) out[t+1] = in[t]
+else if (inc[t] == 1) out[t+1] = out[t] + 1 (integer addition)
+else out[t+1] = out[t]
+```
+
+Note that the first line tells us that `out` should be zero if `reset` at
+the _previous_ clock cycle is one, whereas in the schematic above, `out`
+becomes zero as soon as `reset` rises to one, because the Mux is
+a combinatorial chip — it does not wait for the clock. So what can we do?
+We just need a way to delay `out` by one clock cycle. The only sequential
+chip here is the Register, so let's try hooking `out` onto its output
+instead:
+
+![PC with "out" wired to output of Register](img/nand2tetris/pc.png)
+
+Simulation tells me that this works perfectly, but deep inside I feel I'm
+still extremely sloppy at clocked logic.
+
+## Project 04: Assembly
+
+There's no HDL in project 04. Instead, I learned to write assembly. Nisan
+and Shocken, once again, invented an assembly language for this very
+architecture called HACK. The language understands two sorts of
+instructions. But first, we need to imagine we have a computer.
+
+![Incomplete schematic of computer. Inside blue rectangle: ROM, CPU, RAM.
+Inside the CPU is a blob labeled "ALU and stuff", A Register, and D Register.
+Outside: Reset button, screen, keyboard.](img/nand2tetris/computer_registers.png)
+
+Here you see three devices inside the blue rectangle: ROM, CPU, and RAM.
+
+- ROM: Read-Only Memory. Our computer fetches and executes instructions
+ from it. We did not write HDL for it because it's just a read-only
+ version of the RAM, and it's builtin.
+- CPU: An encapsulation of the ALU that works by black magic until project
+ 05.
+- RAM: Random Access Memory. Our computer can read and write data in it.
+
+HACK assembly provides an extremely rudimentary way to control the CPU.
+The key to understanding HACK assembly is the three registers: D, A, and
+M. D stands for "Data" (probably). It holds a 16-bit value; so do the
+other two. You can do two things to it in our assembly language:
+
+- Read it as an ALU input
+- Write ALU result into it
+
+A stands for "Address". It works pretty much the same way D does, with
+one more added function:
+
+- Set it to an assemble-time constant
+
+which can be realized using this line of assembly (or instruction):
+
+```
+@42
+```
+
+<details>
+<summary><b>Expand to learn more about the difference between A and D</b></summary>
+
+In HACK assembly, the A register is the only one you can directly assign
+an value to, like we just did. In contrast, if you want to write 42 into
+D, you will need to go through two steps:
+
+```
+@42 // this sets A to 42
+D=A // this copies the value of A, 42, into D
+```
+
+However, if you need to set A to some non-constant, you have to use
+another trick:
+
+```
+A=D // this sets A to current value of D
+```
+</details>
+
+M stands for "Memory". Note that it is not a register in the literal
+sense; it is actually an alias for RAM[A]. For example,
+
+```
+@42
+M=-1
+```
+
+sets the 42nd word (if you count from zero) in RAM to -1, i.e. set all
+bits to one.
+
+We call an instruction an "A-instruction" if it begins with "@" and
+"C-instruction" otherwise. By executing a C-instruction the ALU always
+computes something — even zero. You can prefix it with a __destination__
+to decide where the result should be saved. You can either pick or not
+pick any of the three registers, A, D, and M, resulting in
+8 possibilities, like this:
+
+```
+D+M; // compute D+M, but do not save it anywhere
+AD=1; // set A and D to 1 simultaneously
+AMD=1 // set A, M and D to 1 simultaneously
+```
+
+C-instructions can also do something really cool, which is <b>jumping</b>.
+The syntax is different from what you might find in an industrial assembly
+language.
+
+```
+@42
+D;JEQ // this jumps to ROM[42] if D=0
+```
+
+The <code>JEQ</code> here is a <b>jump instruction</b>. A jump instruction
+compares ALU output to zero, and jumps if it is greater/equal/not
+equal/etc.
+
+<details>
+<summary><b>What if I want to jump to 42 if RAM[69] is zero?</b></summary>
+
+Can I just:
+
+```
+@69
+@42
+M;JEQ // does this work?
+```
+
+No. <code>@42</code> completely overwrote <code>@69</code>, so the M on
+line 3 is actually RAM[42]. To perform this maneuver, we need to make use
+of D.
+
+```
+@69 // set A to 69
+D=M // D is now RAM[69]
+@42 // set A to 42
+D;JEQ // if D=0, jump to ROM[42]
+```
+</details>
+
+For convenience, we can attach a label to an instruction in assembly and
+reuse it later:
+
+```
+(END)
+@END
+0;JMP
+```
+
+In this code `(END)` points to `@END`, and `JMP` is an unconditional jump,
+so this creates an infinite loop. It is good practice to terminate
+a program with this, lest the ROM address overflows and the computer runs
+the program again from instruction 0.
+
+You can also use custom symbols after an "@" to assign or reuse
+a static address starting from 16. It is like declaring a variable whose
+value is stored in RAM[n] where n ≥ 16. Why not 0-15, you ask? Well, they
+are reserved for symbols R0-R15.
+
+This `@symbol` notation goes further by mapping a monochrome screen to
+a memory area `@SCREEN`, namely 16384-24575, and a keyboard to `@KBD`,
+which is 24576. If you write the highest bit to one in RAM[16384], you
+paint the top left pixel black. If you press space, it sets RAM[24576] to
+32 (0x20). You can interact with them in the CPU emulator.
+
+!["Pong" running in the CPU emulator](img/nand2tetris/cpu_emulator_pong.png)
+
+▲ CPU Emulator running Pong
+
+Here's a snippet of HACK assembly I wrote that increments RAM[16] from
+0 until it is equal to whatever you put in RAM[0] before running the
+program:
+
+```
+@x
+M=0 // x = RAM[16] = 0
+
+(LOOP)
+@R0
+D=M // D = RAM[0]
+@x
+D=D-M // D -= x
+@END
+D;JEQ // if D == 0 goto END
+@x
+M=M+1 // otherwise x += 1
+@LOOP
+0;JMP // goto LOOP
+
+(END)
+@END
+0;JMP
+```
+
+## Project 05: Computer
+
+After a project that seemed to come out of nowhere, it sounds reassuring
+that we're back to building the computer hardware. First we need to decide
+the architecture. It is common to build a computer on the Von Neumann
+architecture. But canon Von Neumann stores both instructions and data in
+a single memory unit, commonly RAM, so the CPU can modify both. But even
+so, a tiny ROM is needed to instruct the CPU in its booting process. In
+our application however, we will just straightforward use two units simiar
+in size. This means given a single ROM, our computer can only run one
+specific program. This is called the Harvard architecture, technically
+a subset of Von Neumann. AVR microcontrollers also use this architecture.
+
+So this means there will be three things inside the computer: CPU, ROM,
+and RAM. Since we made RAM in project 03 and ROM is builtin, all that's
+left is the CPU.
+
+The CPU needs to:
+
+- Read instruction from ROM
+- Read data from RAM
+- Compute something
+- Write data to A, D, and RAM
+- Run instruction one by one
+- Jump to another instruction if programmer asks it to
+
+The instant I read the requirements, I knew there will be a ton of
+internal wires. Fortunately, the authors provided a block diagram similar
+to this one:
+
+![Incomplete diagram of CPU. Many labels are question marks](img/nand2tetris/cpu_book.png)
+
+Yikes! What's with the question marks? Apparently it's the authors' own
+version of spoiler alerts. I had to figure out what they are by myself,
+and that's a good thing. I like challenges.
+
+Let's first make sure we know what each pin/chip is doing.
+
+- Instruction in ROM comes from pin `instruction`
+- Data from RAM come from pin `inM`
+- Both RAM and ROM addresses are selected using `addressM`
+- The ALU takes two registers and churns out an output
+- The A and D Register accept inputs from ALU
+- ALU output also goes to RAM via `outM`
+- `writeM` tells RAM to load data
+- The PC increments, resets or jumps to instruction
+
+What's an instruction anyway? It's a 16-bit value that describes what we
+want the CPU to do in this clock cycle. An assembler, which we will write
+in project 06, translates assembly to binary code, but in this project
+let's assume it came from nowhere.
+
+What the 16 bits represent depends on the type of instruction you're
+writing. It is specified by the highest bit, called the __opcode__. In an
+A-instruction, the opcode is 0, which is followed by 15 bits of address.
+Considering the size of our larger memory unit, ROM, is 32768 words, 15
+makes sense. In this case the CPU will store the value in the A register.
+
+The C-instruction with opcode 1 is more complicated, but boils down to
+four groups of control bits:
+
+```
+ fixed ALU control jump instruction
+\ / \ / \ /
++-----+---+--------+--------+--------+
+| 111 | a | c1..c6 | d1..d3 | j1..j3 |
++-----+---+--------+--------+--------+
+ / \ / \
+ A/M destination
+```
+
+- `a` decides whether the ALU takes in D and A, or D and M.
+- `c1..c6` correspond to control bits on the ALU.
+- `d1..d3` tell CPU to save ALU output to A, D, and M respectively.
+- `j1..j3` tell CPU to jump to ROM[A] when ALU output <0, =0, and >0,
+ respectively.
+
+In a hunch, it seems we have the answer to most of the question marks.
+
+![CPU but some question marks are replaced with bit names](img/nand2tetris/cpu_hunch.png)
+
+This is simple but wrong. Let's take a close look at the `load` pin
+labeled `d1` on the A register. If we try to load address 1 into it, using
+an A-instruction `@1`, what will happen? Let's assemble it:
+
+```
+0000 0000 0000 0001
+^\________________/
+| ^
+| |
+opcode integer value 1
+```
+
+The mux on the left will let the instruction through because `opcode` is
+0, but remember, HDL doesn't recognize `d1`, it only recognizes
+`instruction[5]`. What's gonna happen is, the A register will refuse to
+load, because `instruction[5]` is zero. Something similar will also happen
+to `d2` and `d3`, so we add a little logic:
+
+![CPU with correct logic controls at d1, d2, and d3](img/nand2tetris/cpu_controls.png)
+
+This ensures that A, D and M load data if and only if we explicitly tell
+them to. Now we shift our attention to the only two question marks left:
+`zr` and `ng` coming from the ALU, and `load` going into the PC.
+
+Notice something? `j1..j3` are missing, so it's definitely them. Recall
+that we can set the PC to its input if we pull `load` to high, and this
+way we can jump to ROM[A]. But how?
+
+![CPU with a blob labeled "mysterious logic that decides whether we jump
+or not"](img/nand2tetris/cpu_mysterious_jump_logic.png)
+
+It's actually very straightforward! Apparently the authors thought it
+through when specifying the ALU.
+
+![Complete diagram of CPU](img/nand2tetris/cpu.png)
+
+(Actual gates may differ)
+
+And that's it, we made a CPU! We are super close to the computer; all we
+need to do is connect all the wires. I'm feeling too tired to sketch up
+another diagram so here's the HDL:
+
+```
+CHIP Computer {
+ IN reset;
+
+ PARTS:
+ ROM32K(address=pc, out=instruction);
+ CPU(
+ inM=inM, instruction=instruction, reset=reset,
+ writeM=writeM, outM=outM, addressM=addressM, pc=pc
+ );
+ Memory(in=outM, address=addressM, load=writeM, out=inM);
+}
+```
+
+## Project 06: Assembler
+
+Having gone through project 04 and 05, if you think something's missing,
+then you're right. We haven't talked about how we translate assembly to
+binary instructions. In nand2tetris, you are asked to write an assembler
+in any high-level language (or not write one at all and assemble by hand).
+As the grammar is pretty simple and well-defined, it wouldn't take too
+much effort, yes?
+
+For some reason my self-obsessive ass, after two successful projects in
+C (one of them being [SIRTET](../sirtet)), decided to write the assembler
+in this very cursed language.
+
+Roast me all you want, but most of the time I'm thinking about stuff like
+"what if the programmer slid in illegal characters in the variable name"
+and "hmm so I malloc a piece of memory and strcpy the second to
+second-to-last characters from this string. We'll need a null terminator
+so the size has to be one byte smaller than the source string blah blah
+blah" and I'll take another minute to decide how long this piece of memory
+will live until I free it.
+
+I shall skip the part where I wrote the program because that will bore you
+and me to death. Instead, let's watch the results if we assemble the
+assembly I showed you in [project 04](#project-04-assembly). The
+executable is called `hack-as`, just like `avr-as`.
+
+```
+$ ./hack-as -v test/inc.asm
+====== SYMBOLS =====
+label addr
+LOOP 2
+END 12
+x 16
+
+====== RESULTS =====
+addr binary inst
+0 0000000000010000 @16
+1 1110101010001000 M=0
+2 0000000000000000 @0
+3 1111110000010000 D=M
+4 0000000000010000 @16
+5 1111010011010000 D=D-M
+6 0000000000001100 @12
+7 1110001100000010 D;JEQ
+8 0000000000010000 @16
+9 1111110111001000 M=M+1
+10 0000000000000010 @2
+11 1110101010000111 0;JMP
+12 0000000000001100 @12
+13 1110101010000111 0;JMP
+
+Binary written to test/inc.hack
+
+$ cat test/inc.hack
+0000000000010000
+1110101010001000
+0000000000000000
+1111110000010000
+0000000000010000
+1111010011010000
+0000000000001100
+1110001100000010
+0000000000010000
+1111110111001000
+0000000000000010
+1110101010000111
+0000000000001100
+1110101010000111
+```
+
+nand2tetris provided me with a few other assembly files I can test my
+assembler against. The longest one was over 28k instructions. All of them
+passed.
+
+As always, I did some memory profiling with valgrind:
+
+```
+$ valgrind --leak-check=full --show-leak-kinds=all ./hack-as test/inc.asm
+==31030== Memcheck, a memory error detector
+...
+Binary written to test/inc.hack
+==31030==
+==31030== HEAP SUMMARY:
+==31030== in use at exit: 0 bytes in 0 blocks
+==31030== total heap usage: 49 allocs, 49 frees, 77,587 bytes allocated
+==31030==
+==31030== All heap blocks were freed -- no leaks are possible
+==31030==
+==31030== For lists of detected and suppressed errors, rerun with: -s
+==31030== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
+```
+
+(It is indeed weird that it needs 77kB of heap memory, but since we've
+been overdoing it all along we might as well just ignore it.)
+
+The whole process took one night, one day, and one morning. And the
+afternoon following that morning, I decided to implement it again using
+Python to see how much easier it is.
+
+The advantage of Python over C is human-oriented string methods like
+`str.split` and `str.partition`. Also, no manual memory management.
+I finished it in less than an hour, not because Python is easy, but
+because I already have C code to refer to. This, in hindsight, is a big
+mistake. I should have prototyped it in Python first, _then_ proceed to
+write it in C. However the speed benefit C provides is an overkill for
+this kind of simple task, so in that case I might just not write C at all.
+
+And thus we have bridged the gap between assembly language and machine
+code. Our computer can run _anything_. (As long as it fits in the ROM)
+
+## Course review
+
+### Conceptual
+
+nand2tetris part 1 takes you on a journey from NAND gates as promised. You
+climb a ladder from the humble logic gate to more and more complex chips,
+representing increasingly advanced logic, but they're NANDs all the way
+down. The authors say that the goal of nand2tetris is to "demystify
+computers": Every time you witness the very chip you made do something
+exciting, like adding up two numbers or remembering 16 bits of data, one
+layer of mystery dissolves, because you _know_ X happens when chip Y does
+Z, not because TSMC soaked your wafer in .25 mol/L holy water.
+Philosophical takeaway: One complicated thing is just many simple things
+arranged in a clever way.
+
+### Technical
+
+The project-oriented approach really gets your hands dirty, but not
+completely covered in copper particles thanks to its simulators. They are
+offered in a software suite, which verifies your work against test scripts
+bundled along. This is the best thing of this course. If you grab some
+university textbook, the first chapter might be like "OK now go download
+NI® Multisim™ for 628 dollars" or "we'll give you an answer to every
+question and you just need to convince yourself it works", whereas the
+nand2tetris software suite is GPL'd. I only have two points of criticism:
+
+- It is buggy at times (the safe kind, you just need to restart it)
+- It is written in Java (I have a prejudice against everything Java)
+
+As I mentioned in [Project 02](#project-02-alu), every time you advance into
+a new project, all the chips you've made thus far become builtin Java code
+instead of HDL. For example, when you simulate the ALU, the
+Mux/And16/whatever you're seeing is no longer what you wrote in project
+01, but part of the simulator itself.
+
+Pro: Complex chips run more efficiently and reliably.
+
+Con: You can't verify your prior chips _actually_ works beyond the test
+scripts.
+
+Of course, the pro beats the con by an order of magnitude. Don't you have
+this deep-rooted fear that one loose jumper wire on the breadboard can
+knock your Ben Eater-style computer completely off the rail?
+
+![DIP chips and LCD connected with numerous jumper wires on three
+breadboards; the LCD reads "6502 Computer kit"](img/nand2tetris/6502.jpg)
+
+▲ Image credit: [Ben Eater, "Build a 6502 computer"](https://eater.net/6502)
+
+### Course outcome
+
+The purpose of this course is, in my opinion, to prove to you that
+computers are not magic, and that it is _possible_ to build your own
+computer. It's like one of those workshops that lets you make a little
+bottle opener, but you don't wind up being a blacksmith. That said, the
+course does not bother you with the intricacies and technicalities of
+real-life engineering. Every step is like playing with Legos, except
+there's no microplastic.
+
+Moreover, there is a very valuable "Perspective" unit at the end of each
+project where the instructors, Nisan and Shocken, sit together and explain
+something that's technically outside the scope of this course, but good to
+know nonetheless. For example, how NAND gates are made in CMOS logic and
+how D flip-flops are made from NANDs. This opens up a whole new door if
+you happen to be interested.
+
+To make my own computer almost from scratch is a greatly pleasant
+experience. I would definitely recommend this course.