From Nand to Tetris Note - 从与非门到俄罗斯方块课程总结

发表于   |   分类于

简介

课程官网：From Nand to Tetris
Course 视频课程：part1, part2

课程在 Coursera 上可免费观看，课后的作业可通过官网的工具进行正确性的验证（也可申请 Coursera 奖学金，通过网站的评分系统进行作业的提交）。

本课程的全称是“依据基本原理构建现代计算机：从与非门到俄罗斯方块”，是一门完整介绍计算机软硬件，并且带你一步步实现一个简单、却包含所有关键元素的计算机的课程。感受如何从与非门开始，到完整构建出一个计算机的过程，坚持完成下来一定会让你受益匪浅。

课程分为上下两部分，第一部分是计算机的硬件部分：使用一门叫 hdl 的硬件描述语言来模拟计算机硬件的实现。这部分将实现计算机硬件中最核心的部分：逻辑元件、ALU、CPU、RAM、汇编程序等等；第二部分是计算机的软件部分：这里会介绍一门高级语言 Jack，一门与 Java 有些许类似并简化了许多功能的语言，我们将学习它的基本用法，并使用它来完成自己构思的一个应用程序。接着是编写 Jack 的编译器，将其编译成虚拟机代码（VM code，类似Java的JVM）。再之后便是完成虚拟机代码到汇编代码的转换 VM translator，整个课程的探索路径就如下图所示：

为什么叫从与非门到俄罗斯方块？

看了这个标题后，未免让人有些疑惑，俄罗斯方块和与非门有什么关系？为什么这个课程叫做“从与非门到俄罗斯方块”？其实看完上面那张图你就知道个大概了，接下来我大致介绍下这门课程的内容，以每周所需要完成的任务为维度，来看看这门课程是如何引导我们循序渐进地实现一个计算机的。

第一周 Boolean Logic

与非门（Nand）是本课程里的一个最基本的逻辑门元件，是我们构建一切的基础，它能完成以下逻辑运算：

任务：使用Nand完成以下 15 个逻辑门元件（上面是逻辑门元件的名称，下面是它所能实现的功能描述，大致扫一眼）

  1. Not
1
2
3
Inputs: in
Outputs: out
Function: If in=0 then out=1 else out=0.
  1. And
1
2
3
Inputs: a, b
Outputs: out
Function: If a=b=1 then out=1 else out=0.
  1. Or
1
2
3
Inputs: a, b
Outputs: out
Function: If a=b=0 then out=0 else out=1.
  1. Xor
1
2
3
Inputs: a, b
Outputs: out
Function: If a=/b then out=1 else out=0.
  1. Mux
1
2
3
Inputs: a, b, sel
Outputs: out
Function: If sel=0 then out=a else out=b.
  1. DMux
1
2
3
Inputs: in, sel
Outputs: a, b
Function: If sel=0 then {a=in, b=0} else {a=0, b=in}.

  1. Not16
1
2
3
Inputs: in[16] // a 16-bit pin
Outputs: out[16]
Function: For i=0..15 out[i]=Not(in[i]).
  1. And16
1
2
3
Inputs: a[16], b[16]
Outputs: out[16]
Function: For i=0..15 out[i]=And(a[i],b[i]).
  1. Or16
1
2
3
Inputs: a[16], b[16]
Outputs: out[16]
Function: For i=0..15 out[i]=Or(a[i],b[i]).
  1. Mux16
1
2
3
4
Inputs: a[16], b[16], sel
Outputs: out[16]
Function: If sel=0 then for i=0..15 out[i]=a[i]
           else for i=0..15 out[i]=b[i].
  1. Or8Way
1
2
3
Inputs: in[8]
Outputs: out
Function: out=Or(in[0],in[1],...,in[7]).
  1. Mux4Way16
1
2
3
4
5
Inputs: a[16], b[16], c[16], d[16], sel[2]
Outputs: out[16]
Function: If sel=00 then out=a else if sel=01 then out=b
else if sel=10 then out=c else if sel=11 then out=d Comment: The assignment operations mentioned above are all
           16-bit. For example, "out=a" means "for i=0..15 out[i]=a[i]".
  1. Mux8Way16
1
2
3
Inputs: a[16],b[16],c[16],d[16],e[16],f[16],g[16],h[16], sel[3] Outputs: out[16]
Function: If sel=000 then out=a else if sel=001 then out=b else if sel=010 out=c ... else if sel=111 then out=h
Comment: The assignment operations mentioned above are all 16-bit. For example, "out=a" means "for i=0..15 out[i]=a[i]".
  1. DMux4Way
1
2
3
4
5
6
Inputs: in, sel[2]
Outputs: a, b, c, d
Function: If sel=00 then {a=in, b=c=d=0}
           else if sel=01 then {b=in, a=c=d=0}
           else if sel=10 then {c=in, a=b=d=0}
           else if sel=11 then {d=in, a=b=c=0}.
  1. DMux8Way
1
2
3
4
5
6
7
Inputs: in, sel[3]
Outputs: a, b, c, d, e, f, g, h
Function: If sel=000 then {a=in, b=c=d=e=f=g=h=0}
           else if sel=001 then {b=in, a=c=d=e=f=g=h=0}
           else if sel=010 ...
           ...
           else if sel=111 then {h=in, a=b=c=d=e=f=g=0}.

以最基本的与、或、非逻辑门举例，看如何用已有的与非门来实现

首先我们实现Not，由上面的 Nand 真值表可以看出来，当 x 和 y 都为 0 时，输出为 1，当 x 和 y 都为 1 时，输出为 0，于是我们可以根据这个特性，将同一个输入值分别赋值给 x、y，就得到了 Not：

即：Not(x) = (x Nand x)

同样的，And 元件的实现也很简单：(x And y) = Not(x Nand y)

（以上两个逻辑门的证明可将 x、y 分别带入 0 和 1 填写真值表，再将两张真值表的结果做对比）

Xor 可根据如下结构完成：

其他的逻辑元件也是类似，使用上述已经完成的元件进行拼装，便能实现各自的逻辑运算。

至此，就完成了从 Nand 与非门到实现 15 个基本的逻辑门。

第二周 Boolean Arithmetic

任务：基于第一周完成的逻辑元件，完成以下 5 个复杂逻辑门元件（大致扫一眼）

  1. HalfAdder (实现 2 bit 的加法运算)

  2. FullAdder (实现 3 bit 的加法运算)

  3. Add16 (16-bit adder)

  4. Inc16

1
2
3
4
Inputs: in[16]
Outputs: out[16]
Function: out=in+1
Comment: Integer 2’s complement addition.
  1. ALU (算数逻辑单元)

一旦完成了 ALU，我们便有能力在硬件层面上对输入进行诸如 +、- 等算数运算以及一系列诸如 x&y、x|y 等逻辑运算。

第三周 Sequential Logic

到了第三周就需要手动实现大名鼎鼎的 RAM(random access memory)

依然是通过实现一个个基本的元件来完成：

  1. DFF: Data Flip-Flop (primitive)
  2. Bit: 1-bit register
  3. Register: 16-bit register
  4. RAM8: 16-bit / 8-register memory
  5. RAM64: 16-bit / 64-register memory
  6. RAM512: 16-bit / 512-register memory
  7. RAM4K: 16-bit / 4096-register memory
  8. RAM16K: 16-bit / 16384-register memory
  9. PC: 16-bit program counter

第四周 Machine Language

第四周是教你使用机器语言，尽管我们大多数时候并不会真的去写机器语言，但是学习机器语言将有助于我们理解计算机底层的运算，以及课程后续编译器的编写。

其实机器语言虽然并不直观，但是它却比高级语言容易掌握得多，原因在于它只有简单的几个固定的指令，所以很快就能掌握。

第五周 Computer Architecture

这一周介绍了计算机组成原理，冯诺依曼模型，获取-执行周期等，完整揭示了计算机是如何执行指令，并且获取下一条指令等一系列的周期。本周的任务是完成计算机硬件的集大成部分：

  1. Memory.hdl
  2. CPU.hdl
  3. Computer.hdl

第六周 Assembler

第六周是实现一个汇编器，将第四周所学习的机器语言转换成二进制指令，从而运行在第五周建立的计算机之上。

实现这个汇编程序可以基于四个模块：Parser 模块用于解析输入，Code 模块用于生成二进制代码，SymbolTable 模块来记录一些变量，还有一个主模块用于驱动整个编译过程。

Parser Module

Code Module

完成了汇编程序后，我们也就完成了计算机的硬件部分，也是课程第一部分的终点。

第二部分

从第七周开始就是课程的第二部分，在这一部分会关注计算机的软件部分。我们将在这部分中学习一门高级语言：Jack，并且在第九周中使用这么高级语言来根据自己的想法实现一个复杂应用，最关键的是，我们将实现从 Jack 语言到机器语言的编译，这样我们才算是完成了整个计算机软件到硬件的完整链路。

在第 10、11 周，我们将编写 Jack 语言到虚拟机语言的编译器，第 7、8 周实现的是虚拟机语言到机器语言的编译。

那么为什么不直接编写一个从 Jack 语言到机器语言的编译器呢？这里我们就要介绍一个 『two-tier translation model』 的概念了。

由于硬件的实现存在一定的差异，不同的计算机底层提供了不同的指令集、手机与电脑之间也存在差异。所以需要一个中间层来抹平这一差异，这一中间层也就是虚拟机。当程序员在编写代码时无需关心底层细节，而只要专注于功能即可。

第七周 VM I: Stack Arithmetic & 第八周 VM II: Program Control

这两周将学习如何将虚拟机语言编译成机器语言。

首先是学习如何使用虚拟机语言，涉及到运用栈去进行函数调用及数据存取，程序的流程控制等等。

第九周 High-Level Language

这周将深入了解 Jack 语言的一些基本特性。与大多数高级语言相比，Jack 的功能简单许多，所以上手起来也比较快，并且由于学习Jack的目的是为了更好给编写Jack语言的编译器做准备，所以并不需要你多么精通它的各个属性。

在学习完这么语言之后，本周的任务是使用这门语言实现一个自己构思的应用，并且运行在课程提供的工具平台上。为了与本课程题目相吻合，我在这实现了俄罗斯方块这个应用。

第十周 Compiler I: Syntax Analysis

这周是实现 Jack 编译器的第一部分：语法分析。

想要完成语言的转换，第一步必然是理解需要被翻译的语言，那么如何让计算机理解它所要翻译的语言呢？

好在我们在编写高级语言时，是按照严格的语法规范来的，某种特定的符号、关键字都代表了特定的含义，所以第一步是将所编写的高级语言转化成一个个独立的词：

接着，我们再根据各个关键字所代表的特性含义，去进行相应语法的编译。下图是 Jack 语法的总结：

第十一周 Compiler II: Code Generation

基于上周的语法分析器，我们将在这周实现相应的代码生成逻辑。

第十二周 Operating System

在这一周所实现的内容是在前面几周内容的基础上，实现几个计算机系统内置的类和方法，比如常用的数学运算、String类、输入输出等。

第十三周 Postscript: More Fun to Go

在经历了这么一趟完整的计算机软硬件之旅后，相信你已经对计算的的内部实现有了自己的理解，但是我们目前所构建的计算机与我们日常所使用的计算机相比，仍然缺少了许多功能，如：网络连接、图形化界面等等，后续更多的有趣探索等待你去发现！