Nand2Tetris: Build a computer system from the ground up, from nand to tetris (nand is the fundamental logic gate to build others gates), from hardware to software.
This github repository is place I store my taken notes and exercises when reading the book The Elements of Computing Systems: Building a Modern Computer from First Principles and learning the related courses on Coursera.org.
Thanks professor Noam Nisan and professor Shimon Shocken for writing a super cool book and creating excellent tools and teaching great courses.
What I hear, I forget; What I see, I remember; What I do, I understand
—Confucius, 551–479 BC
- Truth table representation
- Canonical representation
- Logic gates
- Nand(a, b)
- Not(in)
- And(a, b)
- Or(a, b)
- Xor(a, b)
- Mux(a, b, sel) multiplexor choose one from many
- DMux(in, sel)
-
Signed Binary Number: Most computer systems today use the method called 2's complement, aka radix complement. In 2's complement of n bits, x + (minus) x = 2 to the n. With radix complement we don't need to care about substraction operation. We can substract with add operation. That's super cool. So we only need Adders chip.
-
HalfAdder
-
Full Adder
-
ALU
-
Combinational vs Sequential Logic
- Combinational Logic: An implementation of boolean function. The output depends on only the input. Meaning with a certain input there is a certain output.
- Sequential Logic
- Use clock
- Maintain state
- Output depends on input and the current state
- Good explaination of differences between Combinational and Sequential
-
Data Flip-Flop (DFF) contains a clock input, a gate's input and a gate's output. DFF behavior is out(t) = in(t-1) where t is the current clock cycle.
-
1-bit Register (Bit) is a storage device. It can store(remember) a value over time. Its behavior is out(t) = out(t-1)
-
Memory
- A Instruction
- C Instruction
-
Central Processing Unit (CPU) of Hack Computer
- CPU Abstraction
- CPU Implementation
- CPU Abstraction
-
Hack Architecture
-
Symbols
- Label symbols (In the program above LOOP and END are label symbols) are used to mark the memory location of the next instruction in the program. Label symbols are used for control flow in the program.
- Variable symbols (In the program above i and sum are variable symbols) are treated as variable. Variables are mapped to consecutive memory locations.
-
Symbols table: Since Hack instructions can contain symbols, the symbols must be resolved into actual addresses.
Symbol Memory location i 16 sum 17 LOOP 4 END 18 The table above is the symbol table for the program above. Since in Hack system we allocate memory for variable from memory 16 so the memory location for variable i will be 16 and sum will be 17. To specify label LOOP and END we count the number of instructions in the program so that LOOP will be4 and END will be 18.
The compilation of high-level programming language into a low-level one focuses on 2 main issues: data translation and command translation
-
Variables For variables we need to care about some of its properties
- type: integer, char, boolean, array, object
- kind: field, static, local, argument
- scope: class level, subroutine level
-
Symbol table: A data structure to keep track all identifiers. Whenever a new identifier is encountered for the first time the compiler adds its description to symbol table. Whennever an identifies is encountered elsewhere in the source code the compiler looks it up in symbol table and get all information needed from symbol table.
-
Handling variable
-
Handling object
-
Handling array
-
Handling expression
-
Handling flow of control
- Memory management
- Heap management
- Heap management
