计算机系统要素

源码：https://github.com/felicityin/nand2tetris-rs

1 计算机

布尔逻辑

原始门电路：Nand (if a=b=1 then out=0 else out=1)。

基本门电路：Not、And、Or、Xor、Mux、DMux

算术逻辑单元 ALU

是组合芯片，即输出结果仅依赖输入变量的组合。

有符号数在计算机中存储为补码，因为补码可以利用加法器来计算减法。

ALU 通过 6 个控制位得到 f(x, y) 的输出值。f(x, y) 可表示 x、y 的所有运算。

寄存器 & RAM & PC

是时序芯片，不仅可以计算值，还可以存取数据。

时钟：提供连续的交变信号。

触发器：是最基本的时序单元。DFF 简单将前一个时间周期的输入值作为当前周期的输出 out(t) = in(t-1)。

寄存器：可以存储某个时刻的值，比如在时刻 t 重现时刻 t-1 的值，out(t) = out(t-1)。if load(t-1) then out(t) = in(t-1) else out(t) = out(t-1)，前者是写操作，后者是读操作。

RAM：可直接访问的记忆单元，由 n 个 w 位寄存器组成的阵列。典型的 RAM 接收三种输入：数据输入、地址输入和加载位。地址指定了当前时钟周期内哪个 RAM 寄存器被访问。

PC：可执行 out(t) = out(t-1) + 1。相对于寄存器，有两个额外的控制位控制位：reset 和 inc。

if reset(t-1) then out(t) = 0
else if load(t-1) then out(t) = in(t-1)
else if inc(t-1) then out(t) = out(t-1) + 1
else out(t) = out(t-1)

中央处理器 CPU

CPU 由 ALU、数据寄存器（D，data register）、地址寄存器（A，address register）、程序计数器（PC，program counter）组成。

每个时钟周期内整个计算机的操作：

• 指令解码：解析指令的目的地址和跳转指令。 指令格式：i xx a cccccc ddd jjj
  • i 位域：
    • 0 代表 A 指令，为寄存器 A 设置 15 位值
    • 1 代表 C 指令，决定了计算什么，计算结果存储到哪里，下一步做什么
  • a、c 位域：共同表示要执行什么计算
  • d 位域：计算结果存到哪里，ADM
  • j 位域：跳转指令，LEG
• 指令执行：指令的各个域会被同时发送到 CPU 的各个组件，各组件协同执行指令。
  • 寄存器 A：根据指令的内容，可以存储数值、RAM 地址或 ROM 地址。
    • 如果 MSB=0（i 位域 instruction[15] =0），寄存器 A 被置为指令中内含的 15 位常数。
    • 如果 MSB=1（instruction[15] =1）且 load=1（d 位域 instruction[5]=1），寄存器 A 被置为 outputM。
    • 如果 load=0（instruction[15] =1 且 instruction[5]=0），寄存器 A 中的值不变。
  • 寄存器 D： 根据 d 位域 instruction[4] 加载 ALU 的计算结果。
• ALU：进行算术或逻辑操作。第 1 个操作数从寄存器 D 获取，第 2 个操作数需要根据 a 位域 instruction[12] 决定从 A 寄存器还是 inM 中获取一个操作数。输出包括 outputM 。
• 读取下一条指令
  • PC：根据当前指令的 jump 位域和 ALU 的输出决定是否要跳转，如果是跳转，PC 被置为寄存器 A 的值；否则，PC 值加 1。PC 的输出连接到 ROM 芯片的地址输入端。这样 ROM 芯片总是输出 ROM[PC]，即 PC 所指向的指令内存单元。

总结：

• 根据指令填充寄存器 A，可能是数值，也可能是地址。
• D 加载 ALU 的输出。
• D、A / M 是 ALU 的输入。
• 指令的 jump 位和 ALU 的输出决定了 PC 是否跳转，如果跳转，A 中当初加载的是地址；否则，PC 加 1。

指令内存

ROM，可以直接访问的只读内存设备。

数据内存

Hack 平台的 Memory 芯片主要由三个底层芯片构成：RAM16K、Screen、Keyboard。这 3 个底层芯片应该实现一个统一的逻辑地址空间。

输入和输出

计算机与 I/O 设备交互的最简单的实现技巧之一就是 I/O 映像。创建 I/O 设备的二进制仿真，使其对于 CPU 而言，看上去就像是普通的内存。每个 I/O 设备在内存都分配了独立的区域，作为它的”内存映像“。

组成计算机

Hack 计算机是最小的系统。

2 汇编编译器

机器语言一般分为两类：符号型和二进制型。

比如，二进制码 110000101000000110000000000000111，最左边的 8 位代表操作码 LOAD，接着的 8 位代表寄存器 R3，剩下的 16 位表示地址 7。该条指令等价的汇编是 LOAD R3, 7 ，将 Memory[7] 的内容加载到寄存器 R3 中。

汇编编译器：将汇编翻译成二进制码的程序。

汇编程序中的符号：

• 变量符号，每遇到新的变量时，就在数据内存 RAM 中分配内存地址
• 标签符号，指代下一条命令在指令内存 ROM 中的地址

符号解析：将变量或标签映射到内存地址。解决方式是读两遍代码：

• 第一遍读取，在符号表中建立每条命令及其在 ROM 中的地址，只构建符号表而不生成代码。遇到 A 指令或 C 指令时，指令的 ROM 地址加 1；遇到标签或注释时，不变。
• 第二遍读取，对每一行进行语法分析。如果遇到 A 指令，且其中的符号没有在符号表中查到，说明是变量，为其在 RAM 中分配地址并插入到符号表中。

汇编编译器实现：语法分析器、编码（提供所有汇编命令对应的二进制码）、符号表。

2.1 A 指令

例如 @1 翻译成二进制：

0000000000000001

例如预定义标签 @R1 翻译成二进制：

0000000000000001 // R1 在 RAM 中的地址

例如标签 @label1 翻译成二进制：

0000000000001010 // label1 所指代的命令的 ROM 地址

例如变量 @var1 翻译成二进制：

0000000000010000 // var1 在 RAM 中的地址

2.2 C 指令

dest=comp;jump，其中，dest 或 jump 可以省略。

例如 D=A 翻译成二进制：

// 111 表示是计算指令
// 0110000 表示寄存器 A
// 010 表示将结果存到寄存器 D
// 000 表示不跳转
1110110000010000

例如 D=M 翻译成二进制：

// 111 表示是计算指令
// 1110000 表示 M
// 010 表示将结果存到寄存器 D
// 000 表示不跳转
1111110000010000

例如 D=D-M 翻译成二进制：

// 111 表示是计算指令
// 101001 表示 D-M
// 010 表示将结果存到寄存器 D
// 000 表示不跳转
1111010011010000

例如 D;JGT // if D>0 (first is greater) goto output_first 翻译成二进制：

// 111 表示是计算指令
// 0001100 表示寄存器 D
// 000 表示不存储结果
// 001 表示大于 0 时跳转
1110001100000001

3 虚拟机

虚拟机指令是高级命令分解而成的中间处理步骤。

在 VM 操作中的操作数和结果应该驻留到哪里，“最干净利落”的解决方式是放在堆栈里。

VM 语言包括 4 种类型的命令：

• 算术和逻辑命令，在堆栈上执行算术和逻辑操作
• 内存访问命令，在堆栈和虚拟单元之间转移数据
• 程序流控制命令，使条件分支操作和无条件分支操作变得容易
• 子程序调用，调用函数并返回调用处（即函数调用指令的下一条指令地址）

3.1 算术和逻辑命令

VM 语言有 9 个面向堆栈的算术命令和逻辑命令。7 个面向二元的：add, sub, and, or, eq, gt, lt；2 个面向一元的：not，neg。

例如 add 翻译成汇编：

@SP
AM=M-1 // SP -= 1，指向 y
D=M    // 加载 y
A=A-1  // SP -= 1，指向 x
M=M+D  // x = x + y

例如 eq 翻译成汇编：

@SP
AM=M-1 // SP -= 1，指向 y
D=M    // 加载 y
A=A-1  // SP -= 1，指向 x
D=M-D  // x - y
M=0    // 记录：发生了跳转
@eq_0
D;JNE  // 如果 x - y == 0，则跳转到 eq_0
@SP
A=M-1  // 否则，没有跳转，继续出栈，SP-=1
M=-1   // 记录：没有发生跳转
(eq_0)

例如 neg 翻译成汇编：

@SP
A=M-1 // SP -= 1，指向 y
M=-M  // y = -y

3.2 内存访问命令

• push segment index：将 segment[index] 的值压入堆栈
• pop segment index：将栈顶的元素弹出，然后存入 segment[index]

push argument 2 和 pop local 1 会把函数的第三个参数的值存储在函数的第二个局部变量中。

操作数组：

操作对象：

3.2.1 push

例如 push constant 1 翻译成汇编：

@1
D=A // D = 1
​
// 将 D 中的值存到 *SP，SP++
@SP
A=M   // A = SP
M=D   // M[A] = D
@SP
M=M+1 // SP = SP + 1

例如 push argument 1 翻译成汇编：

// 将 ARG[1] 的值存到 D
@1
D=A   // D = 1
@ARG
A=M+D // A = ARG + 1
D=M   // D = M[A]
​
// 将 D 中的值存到 *SP，SP++
@SP
A=M   // A = SP
M=D   // M[A] = D
@SP
M=M+1 // SP = SP + 1

例如 push pointer 1 翻译成汇编：

@1
D=A   // D = 1
@3
A=A+D // A = 3 + 1
D=M   // D = M[4]
​
// 将 D 中的值存到 *SP，SP++
@SP
A=M   // A = SP
M=D   // M[A] = D
@SP
M=M+1 // SP = SP + 1

例如 push static 1 翻译成汇编：

@filename.1
D=M
​
// 将 D 中的值存到 *SP，SP++
@SP
A=M   // A = SP
M=D   // M[A] = D
@SP
M=M+1 // SP = SP + 1

3.2.2 pop

例如 pop local 1 翻译成汇编：

@1
D=A   // D = 1
@LCL
D=M+D // D = LCL + 1
@R15 
M=D   // R15 = D，记录第 1 个变量的地址
​
//  SP--，将 SP 指向的值存到 M[address]
@SP
AM=M-1 // A = SP = SP - 1
D=M    // D = M[A]，SP 指向的值
@R15
A=M    // A = R15
M=D    // M[A] = D，将 SP 指向的值存到 M[A]，即第 1 个变量中

例如 pop pointer 1 翻译成汇编：

@1
D=A   // D = 1 
@3
D=A+D // D = 3 + 1
@R15  
M=D   // R15 = D，记录了地址 4
​
//  SP--，将 SP 指向的值存到 M[address]
@SP
AM=M-1 // A = SP = SP - 1
D=M    // D = M[A]，SP 指向的值
@R15
A=M    // A = R15
M=D    // M[A] = D，将 SP 指向的值存到 M[A]，即地址 4 指向的内存中

例如 pop static 1 翻译成汇编：

@filename.1
D=M
@R15
M=D // R15 = D
​
//  SP--，将 SP 指向的值存到 M[address]
@SP
AM=M-1 // A = SP = SP - 1
D=M    // D = M[A]，SP 指向的值
@R15
A=M    // A = R15
M=D    // M[A] = D，将 SP 指向的值存到 M[A]

3.3 程序控制流命令

VM 语言有三种形式的程序控制流命令：

• label label，标记程序中某条指令的位置
• goto label，无条件跳转
• if-goto label，条件跳转。先将布尔表达式的运算结果从栈顶弹出，如果非 0，则跳到 label；否则，执行下一条命令。跳转到目标地址必须位于同一个函数内。

例如 label label1 翻译成汇编：

(cur_funcname$label1)

例如 goto label 翻译成汇编：

@cur_funcname$label1
0;JMP

例如 if-goto label1 翻译成汇编：

@SP
AM=M-1 // A = SP = SP - 1
D=M    // D = M[A]，SP 指向的值
@cur_funcname$label1
D;JNE  // D 非 0 则跳转到 (cur_funcname$label1)

3.4 函数调用命令

对于运行期的每个子程序调用，底层必须处理如下细节：

• 将参数从调用者传递给被调用者
• 跳转前，保存调用者状态
• 为被调用者的局部变量分配空间
• 跳转并执行被调用者
• 被调用者的运行结果返回给调用者
• 从被调用者返回前，回收被调用者的内存空间
• 恢复调用者状态
• 返回到调用语句之后的下一条语句继续执行

VM 语言有三种函数相关的命令：

• function f n，一段函数名为 f 的代码，有 n 个参数
• call f m，调用函数 f，m 个参数已被调用者压栈
• return，返回调用者

例如 function f 2 翻译成汇编：

(f) // 为函数入口声明一个标签
​
// push 0，压栈第 1 个参数，并将其初始化为 0
@SP
A=M
M=0
@SP
M=M+1
​
// push 0，压栈第 2 个参数，并将其初始化为 0
@SP
A=M
M=0
@SP
M=M+1

例如 call f 2 翻译成汇编：

// push return-address
@End$f$0
D=A
@SP
A=M
M-D
@SP
M=M+1
​
// push LCL
@LCL
D=M
@SP
A=M
M-D
@SP
M=M+1
​
// push ARG
// push THIS
// push THAT
...
​
// ARG = SP - n - 5，重置 ARG（n = 参数数量）
@7
D=A
@SP
D=M-D
@ARG
M=D
​
// LCL = SP，重置 LCL
@SP
D=M
@LCL
M=D
​
// goto f
@f
0;JMP
​
// 为返回地址声明一个标签
(f)

例如 return 翻译成汇编：

// FRAME = LCL，FRAME 是临时变量
@LCL
D=M
@R15
M=D
​
// RET = *(FRAME - 5)，将返回地址放入临时变量中
@5
D=A
@R15
A=M-D
D=M
@R14
M=D
​
// *ARG = pop()，重置为调用者的返回值
@SP
AM=M-1
D=M
@ARG
A=M
M=D
​
// SP = ARG + 1，恢复调用者的 SP
@ARG
D=M+1
@SP
M=D
​
// THAT = *(FRAME - 1)，恢复调用者的 THAT 段指针
@R15
A=M-1
D=M
@THAT
M=D
​
// THIS = *(FRAME - 2)，恢复调用者的 THIS 段指针
@2
D=A
@R15
A=M-D
D=M
@THIS
M=D
​
// ARG = *(FRAME - 3)，恢复调用者的 ARG 段指针
// LCL = *(FRAME - 4)，恢复调用者的 LCL 段指针
...
​
// goto RET，跳转到返回地址（在调用者代码中）
@R14
A=M
0;JMP

4 编译器

编译器：将高级语言翻译成目标语言。

编译器一般组成：

• 语法分析，理解高级源程序的结构。第一步是词法分析。
• 代码生成

4.1 语法分析

递归下降分析，是应用由语法规则描述的嵌套结构来尝试递归地分析 token stream，可用来构建语法分析树。如果非终结符仅由终结符构成，直接处理；否则，对于规则的右边的每个非终结符块递归调用“分析该非终结符”的程序。整个处理过程递归进行，直到所有终结符全部被处理完毕。

每当一个非终结符有多种可选的导出规则时，其第一个 token 足以确定该非终结符所属的表达式类型，而不会出现不确定的情况。具有这种属性的语法称为 LL(0)。递归下降算法可简洁明了地处理这类语法。

4.2 代码生成

将高级语言编译成低级语言主要涉及两个主要的问题：数据的翻译和命令的翻译。

4.2.1 数据翻译

数据翻译涉及变量类型、变量的生命周期和作用域。

符号表：记录每个标识符的类型（int、bool 等）、种类（局部变量、静态变量等），记录标识符的作用域。

变量处理：将各种变量类型映射到目标平台内存。不同变量类型有不同大小的内存块，不同的生命周期。不过，VM 层已通过通过使用全局堆栈和虚拟内存段，处理了变量的分配和释放细节。编译器唯一需要做的事情就是将源程序中的变量映射到虚拟内存段上，然后用 VM 命令来表达操控这些变量的高级命令。

数组处理和对象处理：见本文的 3.2 节。但对于类中的方法，在目标代码层只存在唯一副本。因此，编译 b.mult(5) 就好像被写成 mult(b, 5)。

4.2.2 命令翻译

命令翻译设设计表达式求值和程序流程控制。对于表达式求值，可遍历语法分析树，生成对应的 VM 代码。对于程序流程控制，只使用 goto 和 if-goto 来表达 if、while 语句，另外，控制结构也可能是嵌套的。

表达式求值：

程序流程控制：

5 操作系统

操作系统通常由高级语言编写，并被编译成二进制形式。不过，操作系统代码必须了解它所运行的硬件平台。

Hack 操作系统比较初级，其服务包括数学函数、字符串操作、内存管理、文本和图形输出到屏幕的处理，会涉及一系列优秀的算法。