Nand2Tetris Korean lecture materials

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Nand2Tetris is the process of creating a computer, compiler, and operating system starting from a single NAND gate. If you look at each chapter individually, it looks like a collection of HDL code or Python code, but in fact, the results of the previous chapter become the material for the next chapter.

good night. In this article, let’s connect the existing code from Chapters 1 to 12 into one flow.

full flow

NAND
  ↓
logic gate
  ↓
Adder and ALU
  ↓
registers and memory
  ↓
Hack CPU and Computer
  ↓
assembler
  ↓
VM Translator
  ↓
Jack Compiler
  ↓
Jack operating system

Chapters 1-5 create hardware, Chapters 6-8 create a low-level translator. Chapters 9-12 cover high-level languages, compilers, and operating systems.

Chapter 1. Boolean logic and basic gates

target

• Create another logic gate using only NAND.
• Look at the truth table and think about HDL connections.
• Understand how Mux and DMux select and distribute data.

NAND outputs 0 only when both inputs are 1. It may seem simple, but connecting the inputs to the same line creates NOT, and combining NOT again can create AND and OR.

Not(a) = Nand(a, a)
And(a, b) = Not(Nand(a, b))
Or(a, b) = Nand(Not(a), Not(b))

Mux isselSelect a or b depending on. DMux, on the other hand, sends one input to either a or b.

Chapter 1 View Code

verification problem

1. Why does NOT occur when I put the same value on both inputs of NAND?
2. Let's explain the difference between Mux and DMux in terms of data direction.
3. Mux16What is the same as a 1-bit Mux?

Chapter 2. Boolean Arithmetic and ALU

target

• Understand the difference between half adder and full adder.
• Let's look at the process of carrying in the addition of multiple bits.
• Understand ALU, which performs several operations with control bits.

A half adder adds two bits to create sum and carry. The full adder receives the carry from the previous position as input.

HalfAdder: a + b
FullAdder: a + b + carry-in
Add16: 16-bit adder connected to FullAdder

The key to ALU is not to create a separate circuit for each operation. zx, nx, zy, ny, f, noOne circuit is used in several ways by changing the input and output with signals.

Chapter 2 View Code

verification problem

1. Why is XOR used as the sum of addition?
2. What happens if you discard the last carry in a 16-bit addition?
3. ALU'szr, ngWhat function will the output be used for in the next chapter?

Chapter 3. Sequential logic and memory

target

• Understand the difference between combinational logic and sequential logic.
• I understand that DFF is the smallest unit that stores time.
• See how Bit, Register, RAM, and PC expand.

In the circuits in Chapters 1 and 2, the output is determined only by the current input. However, the memory must remember the value of the previous clock.

The output of DFF is not the current input, but the input at a previous point in time. By attaching a Mux here, you can create a Bit that stores a new value only when load is 1.

DFF → Bit → Register → RAM8 → RAM64 → RAM512 → RAM4K → RAM16K

PC isreset, load, incpriorities are important. Usually reset is the strongest, then load, and last is inc.

Chapter 3 View Code

verification problem

1. Let's explain with Mux the process by which a bit maintains its existing value when the load is 0.
2. Why do we need DMux and Mux in RAM8?
3. What kind of bugs will occur if the PC's control signal priorities are reversed?

Chapter 4. Hack machine language

target

• Distinguish between A commands and C commands.
• Understand the roles of A, D, and M registers.
• See how branches and loops are expressed in assembly.

The A instruction puts a value into the A register.

@10

C instructions express calculation, storage location, and jump conditions in one line.

D=M+1;JGT

Mis not a separate register.RAM[A]means. If you miss this point, it is easy to get confused as to whether the A register is used as a value or an address.

Chapter 4 View Code

practice

1. RAM[2] = RAM[0] + RAM[1]Write .
2. Write a loop that adds from 1 to 10.
3. Check why the SCREEN address is 16384 in the Fill code.

Chapter 5. Hack computer architecture

target

• Connect CPU, Memory, and ROM32K into one computer.
• Understand how the bits of instructions control the ALU and registers.
• We see a structure where fetch and execute are repeated.

The CPU interprets the current instruction and decides where to store the ALU result: A, D, or M. If the jump condition is true, the A register value is inserted into the PC, otherwise it moves to the next instruction.

For Memory, select RAM16K, Screen, and Keyboard depending on the address range. In other words, you can operate the screen and keyboard simply by reading and writing memory addresses.

Chapter 5 Code View

verification problem

1. instruction[15]Why are A/C commands divided by ?
2. writeMWhen this is 1, at which address is the value actually stored?
3. Why doesn't the keyboard need a load signal?

Chapter 6. Hack Assembler

target

• .asm16 bit file.hackConvert to file.
• Process labels and variable symbols.
• Understand why reading twice is necessary.

Labels are not actual instructions and should not increment the ROM address. So in the first pass(LOOP)Addresses of the same label are collected, and the actual instructions are translated in a second pass.

1st pass: label → ROM address
2nd pass: A/C instruction → 16-bit code
Variable symbols: allocated in order starting from RAM[16]

Chapter 6 View Code

practice

1. Write a preprocessing function to remove spaces and comments.
2. Even if the same variable appears multiple times, check that the address is assigned only once.
3. dest, comp, jumpAn error is output when an input that is not in the table is encountered.

Chapter 7. VM Translator I

target

• Understand stack-based virtual machines.
• Convert arithmetic instructions and memory segments to Hack assembly.
• Understand why comparison operations require unique labels.

Most VM instructions take values ​​from the stack, calculate them, and then put the results back in.

push constant 7
push constant 8
add

local, argument, this, thatfollows the base address, temp, pointer, staticEach uses its own set address rules.

Chapter 7 View Code

verification problem

1. Why do push and pop change the SP in a different order?
2. eq, gt, ltWhat happens if you don't create a unique label for each?
3. Why should static variable names include the file name?

Chapter 8. VM Translator II

target

• Label, goto, and if-goto are processed within the scope of the function.
• Understand stack frames of function, call, and return.
• Understand what bootstrap code does.

When calling a function, the return address and current frame state must be saved.

return-address
LCL
ARG
THIS
THAT

return isFRAME = LCL, RET = *(FRAME - 5)First save the caller's segment and then restore it. Since the LCL changes during recovery, RET must be saved first.

Chapter 8 View Code

practice

1. Check that return labels do not overlap in recursive function calls.
2. several.vmCheck that the static segment of the file does not conflict.
3. In bootstrap, set SP to 256 andSys.initCall .

Chapter 9. Jack high-level language

target

• Distinguish between Jack's class, constructor, method, and function.
• Understand how objects and arrays are stored in memory.
• Process input and output using the OS API.

Jack looks similar to Java, but its functionality is much simpler. The fields of the object are stored in the heap, and the address of the current object is stored in the method.thisIt becomes.

The constructor allocates memory of the required size and thenthisreturns . Arrays are also closer to contiguous blocks of memory rather than special data structures.

Chapter 9 View Code

practice

1. Create two Counter objects and make sure the values ​​are kept separate.
2. Prevents duplicate processing while key input is continuously pressed.
3. Explains why dispose is necessary for objects that have been used.

Chapter 10. Jack parser

target

• Understand the process by which a tokenizer divides source code into tokens.
• Jack grammar is implemented as a recursive descent parser.
• Output the parse tree as XML.

Symbols inside strings and outside comments must be handled differently. Therefore, simply splitting by space will not create a correct tokenizer.

The parser looks at the current token and decides which grammar function to call.

class
 ├─ classVarDec
 ├─ subroutineDec
 └─ statements

Chapter 10 Code View

verification problem

1. in the string//Why can't I delete it with a comment?
2. What is convenient about separating expression and term?
3. What is the benefit of checking the expected type before consuming the token?

Chapter 11. Jack Compiler

target

• Convert the parse tree to VM instructions.
• Distinguish between class scope and subroutine scope symbols.
• Understand the hidden behavior of method calls and constructor calls.

The symbol table doesn't just store names. The type, type, and index are stored together to determine which VM segment to use.

static   → static
field    → this
argument → argument
var      → local

The method receives the current object as the first argument.pointer 0Connect to The constructor is as many as the number of fields.Memory.allocAfter calling , the return address ispointer 0Put it in.

Chapter 11 Code View

practice

1. Check which symbol is selected when a local variable of the same name obscures a field.
2. In array assignment, we organize the order in which addresses and values ​​should be stored on the stack.
3. doreturn value of inquirytemp 0Explain the reason for discarding it.

Chapter 12. Jack operating system

target

• Directly implements the basic library used by the Jack program.
• Separate the responsibilities of Math, String, Array, and Memory.
• It fills in the final blank space between hardware and high-level language.

An operating system does not start with a huge kernel. The key is to implement the functions expected by the Jack program in the Jack language.

• Math: multiplication, division, absolute value
• String: character storage, length, output conversion
• Array: contiguous memory allocation
• Memory: Heap allocation and deallocation
• Screen: Pixel and shape output
• Keyboard: key input
• Output: Output letters and numbers
• Sys: Initialize, Standby, Shutdown

Chapter 12 Code View

verification problem

1. Why can multiplication and division be implemented without CPU instructions?
2. Why does a String object have separate length and capacity?
3. What problems will occur in the Jack program if memory is not freed?

Recommended learning order

It is best to proceed through each chapter in the following order.

1. Before looking at the completed code, write down the input/output and truth table first.
2. Test small parts first.
3. If the test passes, it is used as a next-stage component.
4. If it fails, don't just look at the output, but find out in which layer the value changed.
5. At the end, compare the existing blog code with your own code.

If you enter the correct code as is, the project will be completed quickly. But what's important in Nand2Tetris is understanding how the layer one level below the answer itself supports the current layer.

Once we see the flow of NAND leading to an operating system, computers no longer seem magical.