HUJ nans2tetrics 笔记（四）
算法分析
该算法的运行时间完全由 y 的值主导。循环将执行 y 次。在计算机科学中，我们通常从最保守的角度评估算法，即考虑最坏情况。
假设 n 是我们可能需要相乘的 y 的最大值。那么，在最坏情况下，该算法将进行 n 次迭代。每次迭代大约需要执行10次机器级操作（具体数字可能因编译等因素而变化）。因此，总操作数约为 10 * n。无论常数是10、20还是40，起主导作用的都是 n，所以该算法的运行时间与 n 成正比，即 O(n)。
如果 n 是一个非常大的数，这个算法的运行速度会非常慢。
算法二：基于二进制位运算的乘法
现在，让我们考虑第二种解决方案，它基于我们在小学学过的竖式乘法原理，但采用了更适合计算机实现的二进制形式。
例如，计算 27（二进制 11011）乘以 9（二进制 1001）：
-
将乘数
x（11011）写下。 -
根据乘数
y（1001）的每一个二进制位（从最低位到最高位），将x左移相应的位数后写下。若该位为1，则此行的值有效；若为0，则此行值为0。 -
将所有有效行的结果相加，得到最终乘积。
一个更系统化的算法描述如下：
def multiply_fast(x, y):
sum = 0
shifted_x = x
W = 16 # 假设字长为16位（在Jack中）
for i in range(0, W):
if (y & 1) == 1: # 检查y的最低位是否为1
sum = sum + shifted_x
shifted_x = shifted_x + shifted_x # 左移一位（相当于乘以2）
y = y >> 1 # 将y右移一位，检查下一个比特位
return sum
算法分析
这个算法有一个非常优良的特性：它的运行时间不依赖于输入数字 n 的大小，而是依赖于数字的二进制表示位数 W。
-
在Jack中，
W=16。 -
在现代计算机中，
W可能是 64 或 128。 -
表示一个数字
n所需的位数大约是 log₂(n)。
因此，该算法的运行时间与 W 成正比，即 O(W) 或等价于 O(log n)。W 是一个固定的常数（如16、64），所以无论 n 是百万、十亿还是万亿，算法都只进行固定次数的循环（如16次、64次）。
此外，该算法只涉及加法和移位这两种非常基础且高效的操作。移位操作在二进制中非常简单（例如，左移一位等价于该数自己加自己）。
对数级运行时间的威力 💪
为了理解 O(log n) 的效率有多高，让我们看一些具体例子。
下表对比了线性时间 O(n)（假设系数为10）和对数时间 O(log n) 在不同输入规模 n 下的运行时间（迭代次数）：
| 输入大小 (n) | O(n) ~ 10n | O(log n) ~ 10 * log₂(n) |
| :— | :— | :— |
| 1,024 | 10,240 | 100 |
| 1,048,576 | 10,485,760 | 200 |
| 1,073,741,824 | 10,737,418,240 | 300 |
从图表上看，随着 n 的增长，线性函数（红色）急速上升，而对数函数（蓝色）则缓慢增长，渐近有界。
对数运行时间的一个关键特性是：当输入规模 n 翻倍时，算法所需的迭代次数仅增加 1 个单位。这是一个非常卓越的特性，具有深远的实际意义。
现实世界的例子：网络搜索
你们都在使用搜索引擎在互联网上查找信息。所有搜索引擎的核心都使用了各种版本的二分查找算法，该算法的运行时间就是 O(log n)。
这意味着什么？
假设互联网上有 10亿 个可搜索项，找到一个特定项需要大约 300 次迭代（假设常数因子为10）。
-
如果明天互联网规模翻倍到20亿项，找到一项需要 310 次迭代。
-
如果规模再次翻倍到40亿项，则只需要 320 次迭代。
可以看到，即使互联网的规模爆炸式增长，搜索时间也仅以对数速度缓慢增加，永远不会变得过大。这生动地展示了对数级运行时间算法的强大威力。因此，在计算机科学中，无论是理论还是应用领域，设计出对数级运行时间的算法总是令人欣喜的。
总结 🎯
在本单元中，我们围绕效率这一主题展开讨论，并以乘法运算为例，比较了线性时间 O(n) 算法与对数时间 O(log n) 算法的巨大差异。我们了解到，对于操作系统这类底层、基础的服务，采用高效的算法（如基于位运算的乘法）至关重要，因为它会被上层大量调用，其效率直接影响整个系统的性能。对数级算法因其“输入翻倍，耗时仅增一”的卓越特性，在处理大规模数据时具有无可比拟的优势。
在下一单元，我们将以此为基础，继续探讨其他数学运算（如除法、平方根）的高效实现。
069：数学运算 🧮
在本节课中，我们将继续讨论数学运算，重点介绍除法与平方根的高效算法实现。我们将对比朴素算法与高效算法，并探讨在Jack操作系统中的具体实现细节。
上一节我们讨论了线性运行时间与对数运行时间的巨大差异，并以此为基础介绍了两种乘法算法。本节中，我们来看看除法与平方根运算。
除法运算 ➗
在Jack程序中，除法可以通过两种语法形式实现：
-
x = something / something -
直接调用
Math类的divide函数
第一种形式因其可读性更佳而被推荐，但编译器最终会将两者都转换为函数调用。
朴素除法算法
以下是实现除法的朴素方法：计算在余数严格小于除数y之前，能从被除数x中减去多少次y。
例如，计算20除以6：
-
20 - 6 = 14 （减1次）
-
14 - 6 = 8 （减2次）
-
8 - 6 = 2 （减3次）
-
2 < 6，停止。
结果为商3，余数2。
该算法的运行时间取决于x的大小。如果n是可表示或被要求相除的最大数字，则运行时间与n成正比。这不仅意味着运行时间可能很长，而且不可预测，在某些输入下算法可能需要运行数百万甚至数十亿次。
高效长除法算法
幸运的是，我们有一个基于长除法的更优算法。以175除以3为例：
该算法的核心思想是加速减法过程。我们不是一次减去一个3，而是寻找能一次性减去多个3的最大倍数。
-
首先确定：在100, 90, 80, …, 10中，最大的
x使得3*x ≤ 175？答案是50（因为50*3=150）。 -
将50记录在结果中，并计算余数：175 - 150 = 25。
-
接着处理余数25：在9, 8, 7, …, 1中，最大的
x使得3*x ≤ 25？答案是8（因为8*3=24）。 -
将8加到结果中（累计商为58），并计算新余数：25 - 24 = 1。
-
由于1 < 3，除法完成。最终结果为商58，余数1。
此算法的美妙之处在于，其运行时间与输入数字的位数成正比，即O(log n)。对于二进制数是log₂ n，对于十进制数是log₁₀ n。这是一个巨大的改进。
为了总结这两种算法，让我们快速回顾一下：
-
重复减法算法：运行时间取决于输入大小，可能非常巨大。
-
长除法算法：运行时间取决于输入位数，永远不会太大。
例如，对于一个天文数字，朴素算法的运行时间将是该数字本身的数量级，而长除法算法的运行时间仅为27（即该数字的位数）。这展示了长除法的极高效率。
递归除法算法
在我们的操作系统中，将使用另一种递归除法算法。该算法基于以下洞见：若想计算x / y，可以先计算(x/2) / y的结果，再根据奇偶性进行调整。
算法思路（伪代码表示）：
function divide(x, y):
if (y > x) return 0
q = divide(x, 2*y)
if (x - 2*q*y < y)
return 2*q
else
return 2*q + 1
该算法的运行时间同样是O(log n)，达到了此类算法的理论最优。其优点在于仅涉及加法和减法操作，因此无论在软件还是硬件中都能高效实现。这就是我们要求在Jack操作系统的Math类中实现的divide函数所使用的算法。
平方根运算 √
平方根函数具有两个吸引人的特性：
-
其逆运算（平方）很容易计算：
sqrt(x)的逆运算是x * x，而我们已经掌握了高效的乘法算法。 -
平方根函数是单调递增的。
基于这两个特性，我们可以使用二分查找算法来计算平方根。二分查找算法的运行时间也是对数级的，即O(log n)。
因此，我们将使用二分查找算法在操作系统中实现平方根运算。这同样是一个高效的算法。
内容回顾与实现说明 📝
我们讨论了乘法、除法和平方根的高效算法。其余函数（如绝对值、最小值、最大值）较为简单，相信你能轻松处理。
接下来，讨论一些重要的实现注意事项，因为数学运算总存在一些必须处理的潜在问题。
乘法实现要点
以下是C语言风格的乘法算法伪代码，我们需要处理三个问题：
-
如何处理有符号数：如果输入使用二进制补码表示，该算法无需特殊处理即可正常工作。
-
如何处理溢出：算法中可能发生溢出的地方（如
sum = sum + shiftedX）。该算法返回的结果是模2^16的正确值。这意味着它可能无法给出完整结果，但给出的位是正确的。通常我们不会遇到溢出，因此这个结果是可以接受的。 -
如何提取特定位：算法需要提取16位值
y的第i位。我们建议将此操作封装在一个名为bit的布尔函数中。
由于Jack语言不支持位运算，我们需要一个变通方案。我们建议创建一个静态数组，在计算机启动时一次性构建。该数组保存16个值：2^0, 2^1, …, 2^15。
// 在Math类中声明静态数组
class Math {
static Array twoToTheI;
...
}
可以使用Math.init()来构建并填充这个数组。一旦有了这个数组，就可以轻松地实现bit函数。重申一下，这个数组仅在操作系统启动时构建一次，这是操作系统的典型做法——在初始化阶段构建各种将在整个执行过程中使用的数据结构。
除法实现要点
对于除法算法，需注意：
-
有符号数处理：建议先计算输入绝对值的除法，然后根据需要设置结果的正负号。共有四种情况（正/正，正/负，负/正，负/负），可以轻松处理。
-
溢出处理：在递归计算中，
y可能溢出（因为我们会将其乘以2）。我们建议监控y的值。对于一个增长的二进制补码正数，当其变为负数时，就发生了溢出。因此，我们可以在算法条件中添加判断：如果y > x或y < 0，则返回0。这足以处理溢出。
平方根实现要点
对于平方根算法，同样存在潜在溢出点（例如在计算中点值的平方时）。我们建议在算法的条件判断中添加额外的子句，以妥善处理溢出。
这些就是这三个函数的实现要点。至此，我们完成了Math类的实现，因为其余函数确实很简单。
总结 🎯
本节课中我们一起学习了：
-
除法运算：对比了运行时间为**O(n)的朴素重复减法算法与运行时间为O(log n)**的高效长除法算法。并介绍了将在Jack操作系统中使用的递归除法算法。
-
平方根运算：利用其单调性和易求逆的特性，采用运行时间为**O(log n)**的二分查找算法实现。
-
关键实现细节：包括有符号数处理、溢出检测，以及在缺乏位运算支持的Jack语言中，通过预计算2的幂次数组来高效提取特定位的技巧。
我们已经完成了第一个操作系统类——Math类的实现。在下一单元，我们将讨论内存管理。
070：内存访问 🧠
在本节课中，我们将学习操作系统如何管理内存，特别是如何通过两个基础操作——peek和poke——来实现对内存的直接访问。我们将从理解需求开始，探讨解决方案，并最终了解如何在Jack语言中实现这些功能。
内存管理的需求与解决方案
上一节我们介绍了操作系统在程序与硬件之间扮演的桥梁角色。本节中，我们来看看内存访问的具体需求。
程序运行在宿主计算机的RAM上。然而，高级语言（如Jack）编写的程序并不直接操作RAM，而是通过变量、对象和数组等抽象概念来间接访问。同样，应用程序需要从键盘读取输入或向屏幕输出内容，而无需关心这些操作在硬件层面的具体实现。
操作系统的作用，就是提供一座桥梁，连接高级程序与底层硬件。屏幕和键盘等设备正是通过内存映射技术实现的，这些映射区域也位于RAM中。因此，所有操作最终都归结为对RAM中特定比特位的读写。
核心内存操作：Peek与Poke
为了实现对RAM的直接访问，操作系统提供了底层的peek和poke服务。基于这些基础原语，操作系统可以构建出更高级的功能（如读取和打印），从而为高级程序员提供他们期望使用的抽象接口。
以下是这两个核心操作的定义：
-
peek：此函数旨在返回RAM中指定地址的值。- 公式/代码描述：
value = Memory.peek(address)
- 公式/代码描述：
-
poke：此函数接收一个地址和一个值，并将该值设置到RAM的对应地址中。- 公式/代码描述：
Memory.poke(address, value)
- 公式/代码描述：
例如，假设地址19003中存储着数字7。
-
执行代码
let x = Memory.peek(19003);后，变量x的值将变为7。 -
执行代码
Memory.poke(19003, -1);后，该地址的内容将变为二进制补码表示的-1（即16个1）。
在Jack中实现内存访问
现在我们已经理解了peek和poke的功能，本节中我们来看看如何在Jack语言中实现它们。关键在于如何让Jack程序能够访问整个RAM空间。
首先，让我们考虑一个直观但行不通的方案。
一个行不通的方案
一个天真的想法是：在内存类中创建一个名为Ram的数组，其大小与整个RAM（32768个单元）相同。
// 这是一个行不通的方案
class Memory {
static Array Ram;
...
}
这个方法会失败，原因有二：
-
Jack编译器会尝试在堆中分配这个巨大的数组，但堆空间不足以容纳它。
-
即使能分配，通过这种方式创建的数组也无法访问屏幕、键盘等硬件内存映射区域。
可行的实现方案
虽然上述方案失败了，但它引导我们找到了正确的解决方案。以下是可行的实现方法。
我们在Memory类中创建一个静态数组Ram，但关键在于其初始化方式。某些操作系统类拥有不向用户公开的init函数，用于内部初始化和簿记工作。我们可以在Memory.init函数中执行以下特殊赋值：
class Memory {
static Array Ram;
function void init() {
let Ram = 0; // 关键步骤：将数组变量指向地址0
}
...
}
这个语句 let Ram = 0; 看起来很奇怪，因为它将数组当作一个普通变量来赋值。然而，这恰恰是我们需要的技巧。由于Jack是一种弱类型语言，编译器允许这样的操作。
这个技巧之所以有效，是因为它将数组Ram的基地址设置为0。此后，在程序中任何地方，当我们执行 Ram[address] = value 时，实际上访问的是RAM中地址为 0 + address 的位置。这样，我们就通过高级语言获得了一个通往整个RAM的“后门”。
当然，这种强大的能力也意味着责任。系统程序员（如操作系统开发者）必须清楚自己在做什么，因为错误的操作可能会破坏栈、堆等关键内存区域。
实现Peek与Poke
有了Ram数组这个强大的工具，实现peek和poke函数就变得非常简单。它们本质上只是一两条语句的封装，你可以尝试自己思考如何实现。
总结与展望
本节课中，我们一起学习了操作系统内存管理的基础。我们了解了程序为何需要操作系统作为与RAM硬件交互的桥梁，并重点探讨了实现直接内存访问的两个核心底层操作：peek（读取内存）和poke（写入内存）。更重要的是，我们学习了一个在Jack语言中访问整个RAM空间的巧妙技巧——通过初始化将数组指向地址0。
现在，我们已经为Memory类打下了基础。掌握了peek和poke之后，我们就可以在下一单元继续讨论更高级的内存管理功能：alloc（内存分配）和deAlloc（内存释放）。
071：堆管理 🧠
在本节课中，我们将要学习操作系统如何管理计算机的主内存资源，特别是“堆”这一部分。我们将探讨两个核心操作：alloc（分配内存）和deAlloc（回收内存），并了解如何通过一个称为“空闲链表”的数据结构来高效地管理堆内存。
堆管理的需求
上一节我们介绍了操作系统如何通过peek和poke操作来访问内存。本节中我们来看看操作系统如何管理程序动态请求的内存区域——堆。
在程序运行时，高级语言（如Jack）编写的程序会创建许多对象和数组。每个对象和数组在内存中都有一个对应的数据块，而指向这些数据块的指针通常存储在栈中。存放所有这些对象和数组数据的内存区域，在计算机科学中被称为堆。
挑战在于如何高效地管理堆内存资源。具体来说，我们需要知道：
-
如何在被请求时分配内存。
-
如何回收不再需要的对象和数组所占用的内存。
我们将通过操作系统的一个名为Memory的类来实现这些功能。它主要包含两个函数：
-
alloc(size)：接收需要分配的内存块大小作为参数，在RAM中找到一块合适大小的内存，并返回该内存块的起始地址给调用者。 -
deAlloc(object)：接收一个对象或数组的地址，回收该对象或数组在RAM中占用的空间。
高级程序员的视角
在深入操作系统实现之前，让我们先从一个高级程序员（如Jack程序员）的角度看看发生了什么。
当程序员声明一个对象变量（例如 Point p）时，系统会在栈上分配一个变量p并将其初始化为null（即0）。当程序员通过构造函数（例如 let p = Point.new()）实际创建对象时，会发生以下事情：
-
构造函数内部会隐含地调用
alloc(2)向操作系统请求分配2个字（word）的内存（假设Point对象有两个字段x和y）。 -
操作系统找到一块可用的内存（例如地址8012），将其分配给这个新对象。
-
构造函数将这块内存的基地址（8012）存入变量
p中，从而建立链接。
当对象不再需要时，程序员应显式调用 p.dispose()。dispose方法内部会调用 deAlloc(p)，通知操作系统回收该对象占用的内存。
注意：像Java/C#这类语言拥有垃圾回收器，能自动跟踪对象引用并在引用数为零时自动回收内存。但Jack语言不包含此功能，因此需要程序员手动管理内存的回收。
堆管理的基本实现思路
现在，让我们向下迈进一步，探讨在操作系统层面如何实现堆管理。我们将介绍两种方法：一种简单但低效，另一种更复杂但高效。
简单方法：顺序分配
一个最简单的堆管理方法是维护一个指针（例如 free），它始终指向堆中下一块可用内存的起始地址。
-
初始化：
free = HeapBase（堆的起始地址，在Hack计算机中是2048）。 -
分配 (
alloc(size))：-
block = free（记录要返回的块地址） -
free = free + size（将空闲指针向后移动size个字） -
return block（返回分配的内存块地址）
-
-
回收 (
deAlloc(block))：什么都不做。
代码描述:
// 伪代码示意
function alloc(size) {
block = free;
free = free + size;
return block;
}
function deAlloc(block) {
// 什么也不做
}
这种方法的问题显而易见：它只分配，不回收，最终会导致内存耗尽。它只适用于程序运行时间很短或创建对象极少的情况。
高效方法：使用空闲链表
一个更现实的解决方案是使用一个空闲链表来跟踪所有当前可用的内存段。
链表中的每个“段”具有以下结构：
-
两个开销字（Overhead Words）：
-
size：本段中数据区的大小（以字为单位）。 -
next：指向链表中下一个空闲段的指针。
-
-
数据区：紧随其后的、实际可用来存储对象或数组数据的连续内存空间。
公式描述一个内存段：
[段地址] -> [size | next | data...]
初始时，整个堆是一个大的空闲段，链表只有一个节点。
以下是核心操作流程：
内存分配 (alloc(size))
当请求分配大小为 size 的内存时，操作系统需要搜索空闲链表，找到一个足够大的段。
寻找策略：
-
首次适应：从链表头开始，找到第一个大小 >=
size + 2的段（+2是用于存放size和next的开销）。这是一种贪心算法，速度较快。 -
最佳适应：搜索整个链表，找到大小 >=
size + 2且最小的段。这有助于减少内存碎片。
找到合适段后，从中“切出”一块大小为 size + 2 的内存（包含开销）。剩余部分（如果有）形成一个新的、更小的空闲段，需要更新链表。最后，返回被切出块的数据区起始地址（即块地址 + 2）给调用者。
内存回收 (deAlloc(block))
当回收一个对象时，我们获得的是其数据区的起始地址。我们需要将其对应的整个内存块（包括开销）重新链接到空闲链表中。一个简单的实现是将其追加到链表的末尾。
内存碎片整理
随着频繁的分配和回收，空闲链表会变得“碎片化”，即包含许多小的、不连续的空闲段。这可能导致无法分配较大的对象，即使总空闲空间足够。
碎片整理算法会周期性地遍历空闲链表，将物理地址相邻的空闲段合并成更大的段。这是一个高级功能，在本课程的操作系统实现中是可选的扩展项目。
实现技巧与内存布局
在Hack操作系统的Memory类中实现上述想法，需要一些具体的技巧。
我们可以在Memory类中声明一个静态数组heap，但它并不是通过Array.new创建的真正数组。我们只是借用“数组”这个概念，将其起始地址设置为堆的基地址（2048），然后将其当作一块大的、可自由读写的内存区域来管理我们的空闲链表。
初始化 (init)：
-
设置
heap的基地址为2048。 -
初始化空闲链表：让链表头指向
2048。 -
在第一个“段”（地址2048）处，设置
size = 16384 - 2048（整个堆的大小），next = 0（链表结束标志）。
访问段信息：
-
对于一个位于地址
addr的段：-
其
size存储在heap[addr]。 -
其
next指针存储在heap[addr+1]。 -
其数据区从
heap[addr+2]开始。
-
通过操作这个“伪数组”heap，我们可以实现alloc、deAlloc以及可选的defrag函数。
总结
本节课中我们一起学习了操作系统堆管理的核心概念。我们了解到：
-
堆是用于动态分配对象和数组内存的区域。
-
堆管理通过
Memory类的alloc和deAlloc函数实现。 -
一种高效的实现方式是使用空闲链表来跟踪可用内存段。
-
分配时可采用“首次适应”或“最佳适应”策略在链表中寻找合适内存块。
-
回收时将内存块简单地链接回空闲链表。
-
内存碎片是长期运行程序的挑战，可以通过碎片整理算法来缓解。
现在，你已经理解了现代操作系统中内存管理的基础原理。在接下来的单元中，我们将探索另一个核心主题：图形系统。
072：图形处理 🖥️
在本单元中，我们将学习图形处理的基本概念，并重点介绍如何实现Jack操作系统中用于处理图形操作的Screen类。我们将探讨一个图形库，该库提供了在屏幕上绘制图形和像素的几种基本操作。
概述
首先，我们将介绍图形的基本概念，特别是两种主要的图形表示技术：位图和矢量图形。接着，我们将深入探讨如何在我们的操作系统中实现最基础的图形操作——绘制单个像素。
图形表示技术
上一节我们介绍了本单元的学习目标，本节中我们来看看两种核心的图形表示技术：位图和矢量图形。
请看这两幅看起来相同的图片，它们都是唐老鸭试图理解计算机工作原理的图案。如果我们移除计算机并开始放大图像，一个显著的差异就会显现出来：右侧的图像放大后效果不佳，而左侧的图像则可以完美缩放。
这种差异源于两种不同的图形存储技术。左侧的图像使用矢量图形管理，而右侧的图像是位图的一个例子。接下来，我们将讨论每种技术的优点，并特别关注矢量图形。
位图 (Bitmap)
位图是一种直接的图形存储方式。它将屏幕上的每个像素映射为一个二进制值。
以下是绘制一个杯子的屏幕部分示例。在Jack语言（或Hack计算机）中，我们只有黑白两色（尽管可以轻松添加颜色）。杯子通过打开和关闭像素来绘制。
对应的位图文件会存储这个图像。对于每个白色像素，存储0；对于每个黑色像素，存储1。这样就得到了一系列数字，它们共同建立了图形与二进制数字之间的一一对应关系。
核心概念：位图存储的是每个像素的颜色值。
像素颜色值 = 0 (白) 或 1 (黑)
图像数据 = [像素1值, 像素2值, 像素3值, ...]
矢量图形 (Vector Graphics)
矢量图形存储的不是像素数据，而是一系列描述如何绘制图形的指令。
同样是那个杯子，矢量图形文件可能包含以下指令：首先，从坐标(30)到(110)画一条线，形成杯子的顶部。然后，利用一个大矩形，从(31)到(95)画一个矩形，这样一条指令就描述了大约35个像素。接着，继续画几条线来完成杯子的绘制。
核心概念：矢量图形存储的是绘制命令。
绘制命令列表 = [
drawLine(30, 110),
drawRectangle(31, 95),
...
]
技术对比
以下是两种技术的主要优缺点：
-
文件大小：矢量图形文件通常更小，因为它存储的是指令而非每个像素的数据。
-
缩放性：矢量图形可以完美缩放。只需按比例调整指令中的坐标参数，即可在任何分辨率下获得清晰的图像。位图缩放则会出现锯齿，需要复杂的插值算法，效果往往不理想。
-
适用性：在拥有多种屏幕尺寸（手机、相机、笔记本电脑、平板电脑）的世界里，矢量图形的可缩放性极其重要。此外，矢量图形可以随时转换为位图。
总而言之，矢量图形是一项非常重要的发明，我们的操作系统也将使用它。
基础绘图操作
在了解了图形表示的基础后，本节我们将聚焦于实现图形操作所需的三个基本原语。
我们将要探索的三个基本绘图操作是：
-
绘制单个像素
-
绘制一条线
-
绘制一个圆
我们将从绘制像素开始。需要说明的是，绘制像素是位图和矢量图形都需要的操作，它是最基础、最原始的操作。在此基础上，我们可以创建位图或矢量图形。
绘制像素的实现原理
现在，让我们深入了解绘制单个像素是如何在硬件和软件层面实现的。
首先需要回顾，在构建Hack计算机时，我们分配了一段特定的内存区域来表示屏幕。我们取用了8K（8192个）寄存器，称之为屏幕内存映射。
约定如下：如果我们要在屏幕上绘制像素，只需在内存映射中打开或关闭某些特定位，图像就会“自动”显示在屏幕上。其工作原理是，硬件实现了一个称为屏幕刷新的机制。每秒多次，计算机会自动例行刷新，读取内存映射中的所有位，并将其提交到物理屏幕上对应的像素点。
例如，假设我们想在屏幕上绘制坐标为(450, 200)的像素。在Jack中，我们可能会使用这样的命令：Screen.drawPixel(450, 200)。这个操作将由操作系统，特别是Screen类来实现。
当drawPixel例程被调用以绘制这个特定像素时，它会进行以下计算：
-
确定需要操作的内存字（word）的地址。
-
确定在该16位字中，需要操作的是哪一位（bit）。
屏幕是二维空间（宽512像素，高256像素），而RAM是一维的16位字数组。两者之间的映射关系是直接的。
通过数学计算，我们可以找到操作字地址的公式：
wordAddress = baseAddress + (y * 32) + (x / 16)
其中，baseAddress是屏幕内存映射的基地址，x和y是像素坐标。
然后，我们执行以下步骤：
-
从RAM中该地址读取当前的16位值。
-
将该值的第
(x % 16)位设置为当前颜色（1或0）。 -
将修改后的16位值写回RAM的同一地址。
你可能会问，为什么需要先读取再写入，而不是直接操作特定位？原因有二：
-
计算机必须以固定大小的数据块（如16位或64位）进行操作，无法直接操作单个位。因此，必须读写整个字来修改其中的一个位。
-
该字中可能已经绘制了其他相邻像素。通过先读取整个字，然后只修改目标位而不影响其他位，我们可以安全地更新像素，避免破坏周围的图像。
通常，我们会使用位操作（如OR运算）来设置特定位，然后将结果写回内存。
核心操作流程：
// 1. 计算目标字地址
address = Screen.baseAddress + (y * 32) + (x / 16)
// 2. 读取当前字的值
currentWord = Memory.peek(address)
// 3. 计算掩码并设置特定位
mask = 1 << (x % 16)
newWord = currentWord | mask // 假设是“画黑点”（置1），清空则用AND操作
// 4. 将新值写回内存
Memory.poke(address, newWord)
值得注意的是，Screen类中的drawPixel子程序会调用Memory类中的peek和poke子程序。这种操作系统模块间的相互依赖关系是非常典型的。
总结
本节课中我们一起学习了图形处理的基础。我们比较了位图和矢量图形两种技术，了解了矢量图形在文件大小和可缩放性方面的优势。我们深入探讨了在Hack计算机平台上绘制单个像素的实现原理，包括屏幕内存映射的概念、像素坐标到内存地址的换算，以及通过读取-修改-写入流程来安全更新像素值的方法。在下一单元，我们将在此基础上学习如何绘制一条线。
073：线段绘制 🖌️
在本节课中，我们将学习如何绘制线段。上一节我们介绍了矢量图形和位图图形，并讨论了矢量图形的优点。我们决定实现三个图形基元：绘制单个像素、绘制线段以及绘制圆形。本节我们将从绘制像素出发，学习如何使用绘制像素功能来绘制线段，以及如何利用绘制线段功能来绘制圆形。
线段绘制的动机
矢量图形的一个优点是，所有图形都由简单的代数语句控制。例如，我们可以将一组多边形分解为若干子图像，每个子图像都使用矢量图形绘制。以绘制鸟喙为例，我们可以通过连续绘制多条线段来构成这个多边形。
图像绘制是一系列线段绘制操作的集合。因此，线段绘制的速度至关重要。如果绘制速度慢，整个图形渲染过程就会变得迟缓，无法实现流畅的动画或视频播放。所以，我们需要尽可能快地绘制这些线段。
线段绘制算法详解
让我们通过一个示例网格来深入探讨线段绘制的细节。首先，我们做一个简化假设：只关注向东北方向延伸的线段。
假设我们要绘制从点 (x1, y1) 到点 (x2, y2) 的线段。由于我们只能控制像素的开关，因此只能通过近似的方式来绘制这条线段。在每次迭代中，我们只能选择向右或向上移动一个像素，以避免在线上产生空洞。
以下是绘制线段的基本算法：
-
我们使用变量
A和B来分别记录当前已向右和向上移动的像素数。初始时，A = 0，B = 0。 -
在每次迭代中，我们绘制像素
(x + A, y + B)。 -
然后，我们决定是向右移动（
A增加 1）还是向上移动（B增加 1）。 -
循环条件为：只要
A < dx且B < dy，就继续绘制。
决定向右还是向上的关键在于比较当前路径的斜率与目标线段的斜率。具体来说，我们比较 B/A 与 dy/dx 的大小。如果 B/A > dy/dx，说明当前路径过于陡峭，应向右移动以降低斜率；否则，应向上移动以提高斜率。
然而，这个比较涉及除法运算，计算成本较高。为了优化，我们可以进行如下转换：
比较 B/A > dy/dx 等价于比较 A * dy < B * dx。我们引入变量 diff = A * dy - B * dx。初始时 diff = 0。判断条件 B/A > dy/dx 就变成了判断 diff < 0。
当 A 增加 1 时，diff 增加 dy；当 B 增加 1 时，diff 减少 dx。这样，整个算法就简化为只包含加法和减法的操作，极大地提高了效率。
优化后的算法伪代码如下：
初始化 A = 0, B = 0, diff = 0
当 A < dx 且 B < dy 时，循环：
绘制像素 (x + A, y + B)
如果 diff < 0：
A = A + 1
diff = diff + dy
否则：
B = B + 1
diff = diff - dx
这个算法的运行时间仅取决于需要绘制的像素数量，是目前最高效的线段绘制算法之一。
使用线段绘制圆形
现在我们已经知道如何使用绘制像素来绘制线段，接下来看看如何利用线段绘制功能来绘制圆形。
要绘制一个圆形，我们需要至少三个输入参数：圆心坐标 (x, y) 和半径 r。在像素化的计算机屏幕上，我们无法绘制完美的圆形，只能通过近似来实现。
一种方法是绘制一个实心圆。我们可以通过绘制一系列水平线段来填充圆形区域。具体来说，对于从 -r 到 r 的每一个垂直偏移量 dy，我们计算对应的水平线段的起点和终点 x 坐标，然后绘制这条线段。
对于每个 dy，线段的 y 坐标都是 y + dy。起点和终点的 x 坐标可以通过勾股定理计算得出：
x1 = x - sqrt(r^2 - dy^2)
x2 = x + sqrt(r^2 - dy^2)
然后，我们调用绘制线段函数，绘制从 (x1, y+dy) 到 (x2, y+dy) 的线段。对所有 dy 执行此操作后，就得到了一个实心圆。
如果只需要绘制圆形的轮廓，我们可以修改算法：对于每个 dy，不绘制整条线段，而是只绘制两端的像素，即分别绘制像素 (x1, y+dy) 和 (x2, y+dy)。
实现注意事项
到目前为止，我们讨论的都是理想化的算法。在实际实现时，需要考虑一些细节。
对于 drawPixel 函数，它需要使用 peek 和 poke 操作来读写内存。此外，需要操作 16 位值中的特定位，这可以通过位运算来实现。
对于 drawLine 函数，需要进行几处修改：
-
我们的算法基于原点在左下角的坐标系，但计算机图形学中屏幕原点通常在左上角。因此需要调整算法以适应左上角原点。
-
算法只处理了向东北方向的线段。实际上，线段可能有八个方向（东、南、西、北、东北、东南、西北、西南）。需要扩展算法以处理所有情况。
-
水平和垂直线段可以作为特例处理，因为它们的绘制可以更高效，而这类线段在绘制矩形等图形时非常常见。
对于 drawCircle 函数，需要注意计算中的溢出问题。如果限制半径 r 不大于 181，通常可以避免溢出。这使得图形库在一定程度上依赖于硬件屏幕的大小。
屏幕类的其他函数相对简单，相信你可以运用自己的判断力来实现它们。
总结
本节课我们一起学习了计算机图形学中的核心绘制功能。我们首先探讨了高效的线段绘制算法，该算法通过巧妙的数学转换，将耗时的除法运算优化为快速的加减法运算。接着，我们学习了如何利用线段绘制功能来构建实心圆和圆形轮廓。最后，我们讨论了在实际编码实现这些功能时需要注意的细节，如坐标系转换、方向处理以及性能优化。掌握这些基础图形的绘制方法，是构建更复杂图形应用的关键第一步。
074：处理文本输出 📝
在本单元中，我们将学习计算机如何处理文本输出。计算机屏幕通常有两种工作模式：图形模式和文本模式。我们将重点介绍文本模式，以及如何通过操作系统中的 Output 类在屏幕上绘制字符。
屏幕的两种模式
上一节我们介绍了计算机屏幕的基本概念。本节中我们来看看它的两种工作模式。
计算机屏幕至少有两种处理模式。首先，程序可以以图形模式看待屏幕。在这种模式下，程序将屏幕视为一个由 256 行、每行 512 个像素组成的黑白网格。通过 Screen 类提供的各种抽象，我们可以绘制各种图形，实现面向图形的输出。
然而，在许多情况下，我们也需要开发文本应用程序。这些应用程序需要绘制字母、数字等。为此，我们提供了另一种操作模式，称为文本模式。在这种模式下，我们可以将屏幕视为一个由 23 行、每行 64 个字符组成的黑白网格。为了以这种方式使用屏幕，我们不使用 Screen 类，而是使用一个完全不同的类，称为 Output。因此，Screen 和 Output 这两个类提供了两种不同的方式来思考和操作屏幕。
请注意，就像 Screen 类实现了绘制圆形和矩形等抽象一样，Output 类也以非常类似的方式实现了绘制字母 K、Q、1、7 等抽象。字母 K 的图像本身就是一个抽象，需要有人努力才能在屏幕上实际绘制出这个图像。这正是本单元要讨论的内容。
字符集与字体
既然我们要处理文本输出，首先需要确定要绘制哪些字符。
我们的 Hack Jack 平台支持并识别许多不同规格的字符，其中之一就是这个字符集。计算机支持并识别所有这些字符，其中一些是可打印的，另一些是不可打印的。所有可打印字符都必须有相应的位图图像来在屏幕上显示它们。不可打印字符传达一些非常重要的信息，但它们没有视觉效果。当然，换行符和退格符除外，它们有视觉效果，但不会在屏幕上显示任何特定字符。
在这些表格中我们看到的是 ASCII 码或 Unicode（两者是相同的），以及这个字符的子集。在左侧，我们看到字符的名称或我们将在屏幕上看到该字符的方式。
以下是一个典型的文本输出示例。我们看到屏幕由一个网格来表征，X 轴从 0 到 63，Y 轴从 0 到 22。然而，我们必须记住，实际的物理屏幕仍然是 256 x 512 像素，这在我们的计算机内存中使用一个 8K 16 位字的块来表示。
因此，我们面临着一个底层挑战：如何使用一个 256 x 512 像素的网格来实现一个为文本应用程序设计的 23 x 64 字符网格。因为最终我们必须理解，我们将要绘制图片，例如构成单词 “AN” 的字母 A 和 N。这些是三个不同的位图图形，我们必须使用像素来绘制。我们应该怎么做呢？
让我们仔细看看这部分输出。让我们再靠近一点看。现在让我们真正靠近。我们看到这里的东西被称为字体。
Hack 字体在设计上，使用一个固定的 11 像素高、8 像素宽的区域来表示字符集中的每个字符。我们称这个区域为“帧”。如果你看这些帧，你会发现帧的右侧包含两个空列用于字符间距，底部包含一行用于行间距。现在你可能看起来底部有两行空行，但实际上，请记住我们有像 G 和大写 Q 这样有向下延伸部分的字母，所以我们必须多使用一行来处理这些字符。这里显示的四个字符恰好没有这些延伸部分，所以你在这里看不到，但我们稍后会看到。
这就是 Hack 字体。我们花了相当多的精力来设计它，因为我们必须绘制这些位图，为每个字符决定使用哪个图像。这个字体不是非常漂亮，但绝对可用。事实上，你定义的字体越多，你就越接近像花哨的文字处理器那样的东西。
所以，每种字体实际上是一整套图像，决定了如何在计算机屏幕上绘制每个字符。
字体的实现
现在，我们应该如何实现这个字体呢？坏消息是，这需要大量工作。好消息是，我们已经为你完成了，我们不期望你自己去做，因为这是重复性工作，我们不希望你做重复性工作。
我们使用接下来要探讨的 Output 类来实现这个字体。
以下是这个 Output 类。如你所见，我们首先定义一个名为 characterMaps 的静态数组。这个数组将保存我们字符集中每个成员的所有位图，总共 127 个字符。请注意，它必须是静态的，因为我们希望这个类中的每个方法都能出于各种目的使用这个字体。所以我们把它放在类级别，这样每个人都可以使用它。
我们编写了一个私有方法（私有函数）。在 Jack 语言中，我们没有私有和公有的指定，所以对我来说，私有函数是我不向外界公开的函数。外界甚至不知道这个函数存在，但我需要它，并且我需要它来一次性创建这些位图。
我首先定义数组 characterMaps。然后我使用一个方法，另一个名为 create 的私有函数，它实际上决定了为这些字符中的每一个需要写入的数字。
看一下代码块中的第一条语句，字母 ‘a’。你会注意到 create 函数的第一个参数是 97，这恰好是小写字母 ‘a’ 的 ASCII 码。然后我们有 11 个数字，这些数字决定了在位图的每一行需要绘制哪些数字。如果你看字母 ‘a’ 的图像，你会看到顶部三行是空的，确实它以三个零开始。下一行，字母 ‘a’ 的顶部，看起来像 0,1,1,1，然后是一些零。我们必须将其反转。所以实际上我们这里有的是 1,1,1,0，而 1,1,1,0 我认为是 14，确实我们下一个参数就是 14，依此类推。
这就是我们定义 ‘A’ 位图的方式，然后我们定义 ‘B’、‘C’ 的位图，以及字母表中的所有其他字母，然后我们处理数字，然后处理所有特殊字符。就是这样。如果你下载了 Nand2Tetris 软件套件并查看代码，你会看到我们实际上努力创建了这个字体。
剩下需要描述的是我们在这里使用的 create 函数。这就是 create 函数。它接受 12 个参数。第一个参数是数组的索引，顺便说一下，这个索引也恰好是 ASCII 码。然后是 11 个数字。
这个函数定义了另一个名为 map 的数组，这是实际字母的数组。之前的数组是保存所有位图的数组。这是一个特定的位图，所以我们定义一个名为 map 的数组，创建时有 11 个条目，对应字符帧中的每个数字。然后我们设置 charMaps[index] 为 map。本质上，我们正在实现一个二维数组。charMaps 是保存所有位图的静态数组。然后我们用实际的数字 A、B、C、D 等填充我们的小 map 数组，然后返回。
我们对字符集中的每个字符执行此操作 127 次。好消息是，我们只做一次。我们不必每次绘制字符时都这样做。当我们打开计算机，当我们重置时，我们也将重置操作系统，当操作系统重置时，它也会重置这个 Output 类，而 Output 类将运行一个 init 方法来创建这个字体。一旦这个字体被创建，我们就可以开始使用它，通过一些我还没有向你展示的方法，这些方法在你的课程材料中有详细记录。
光标管理
在处理文本时，我们必须担心的另一件事是所谓的“光标”。如果你看这里的例子，光标就是这个红色矩形显示的地方。我的意思是，当你在屏幕上看到这个输出时，实际上看不到红色矩形，我只是在幻灯片中使用它来向你展示我在说什么。所以光标是这个帧，11 像素深，8 像素宽，显示下一个字符将被写入的位置，如果以及当被要求写入下一个字符时。
光标这个概念既有逻辑上的表现，也有物理上的表现。首先，逻辑概念是我真的必须知道光标在哪里。我作为开发 Output 类的人，因为如果要求我写入一个字符，我必须知道把它放在屏幕上的什么位置，所以我必须做一些内部记录来记住光标的位置。显然，每次我绘制一个新字符时，光标的位置都会受到影响。
此外，我可能想友好地向用户显示光标在屏幕上的位置，以便她或他知道当她触摸键盘时会发生什么。当她触摸键盘时，她想知道在屏幕上的哪个位置会看到她将要触摸的下一个字母或按键。
所以，我可能想创建一些闪烁效果，或者可能只想放一个下划线或一个小箭头，这是一个设计决策，完全独立于光标逻辑状态的概念。我认为在我们的 Hack Jack 平台中，我们决定根本不显示光标。所以用户需要自己弄清楚光标在哪里。但我可能记错了，我不记得确切的细节了。这并不太重要。
那么，我们应该如何管理光标呢？我现在谈论的是逻辑光标。如果要求显示换行符，那么我们必须将光标移动到输出的下一行。如果要求显示退格符，我们必须将光标向左移动一列。如果要求显示任何其他字符，那么我们必须显示该字符并将光标向右移动一列。这些就是游戏规则。
Output 类 API
考虑到所有这些，我们现在可以仔细看看 Output 类。我们只会在 API 层面进行。
首先，我们有 init 方法。init 方法是将会调用我之前看到的创建字体的函数的方法。这只会做一次。
然后我们有几个函数，在我们想要使用文本的某些情况下（虽然不是每次）会为我们服务。我们有一个 moveCursor 函数，可以将光标放在屏幕上的任何位置。当我说 I J 时，我指的是光标将要到达的位置。
然后我们有一个 printChar 方法，它知道如何显示单个字符并相应地移动光标。我们有一个 printString，可以打印任何合理长度的字符串。我们有一个 printInt，它与 printString 非常相似，但它知道如何清晰地打印整数数字。
我们还有一个 printLine，基本上将光标移动到下一行。我们有一个我之前描述过的 backSpace。这些就是 Output 类的函数。鉴于我给你的所有信息，并且鉴于我们已经为你实现了 Hack 字体，所以你不必为此烦恼，因此实现这些函数肯定是你自己可以搞定的。
总结
本节课中我们一起学习了计算机如何处理文本输出。我们介绍了屏幕的图形和文本两种模式，重点探讨了在文本模式下，如何使用 Output 类在屏幕上绘制字符。我们了解了字符集、Hack 字体的结构及其实现方式，包括如何通过位图定义每个字符。我们还讨论了光标在逻辑和物理上的概念及其管理规则。最后，我们预览了 Output 类的主要 API 方法，为接下来的键盘输入处理学习做好了准备。
075：输入处理 🖥️⌨️
在本单元中，我们将探讨操作系统的输入能力，特别是介绍一个名为 Keyboard 的类，它负责管理计算机与物理键盘之间的所有交互。
键盘内存映射
上一节我们介绍了操作系统的基本架构，本节中我们来看看输入设备是如何在HEC平台上处理的。这曾在Nand2Tetris项目的第一部分以及本课程的模块0中提及。
按照惯例，我们在RAM中分配特定区域来代表屏幕。同样，我们在RAM中分配一个16位的寄存器来代表键盘。这个16位的表示足以代表Unicode字符集中的任何可能字符，因此足以处理键盘输入。这被称为键盘内存映射，它本质上是一个单独的RAM寄存器。
下图展示了这个概念：
右侧是一个键盘，与你当前使用的键盘大致相同。左侧是我们之前讨论的那个单独的RAM寄存器，按照惯例我们也称之为“键盘”。
以下是硬件实现的约定：当你在物理键盘上按下某个键时，键盘寄存器会立即、瞬时地显示该按键的扫描码（或Unicode/ASCII码）的二进制值。在HEC计算机可识别的字符子集内，这些编码是相同的。当你松开手指，没有按键被按下时，键盘寄存器被重置为0。因此，键盘寄存器通常为0，因为大多数时间无人触碰键盘。在我们触碰键盘的少数情况下，该寄存器会反映出一个非零值。
这个约定由硬件实现，我们无需担心。然而，我们将在操作系统的 Keyboard 类中构建的所有功能，都将建立在这个简单的基础之上。
工作原理示例
让我举例说明其工作原理。假设我按下 K 键。只要我的手指按住 K 键，我将在键盘寄存器中看到代表 K 的扫描码值，在ASCII中恰好是 75。一旦我抬起手指，键盘未被触碰，我将看到默认值 0。
再次按下代表数字 4 的键。数字 4 的ASCII码是 52，这将是键盘寄存器中的值。抬起手指，看到 0。按下空格键，只要按住，看到 32（代表空格的ASCII值）。抬起手指，看到 0。按下上箭头键，其ASCII码是 131，将在键盘寄存器中看到这个数字。抬起后，再次看到 0。你应该明白了。
HEC字符集
了解了字符的概念后，我们继续讨论 Keyboard 类。以下是HEC计算机识别的完整字符集。这个表格被分成几列以便阅读。左列是字符的约定名称，右列是代表该字符的整数值代码。所有这些字符共同构成了HEC Jack字符集。
Keyboard类API
我们选择基于四个子程序来构建这个类。以下是它们的简要介绍，我们随后将深入探讨并仔细实现每一个。
-
keyPressed: 设计用于捕获键盘按键按下的事件。 -
readChar: 设计用于从键盘读取一个字符的事件。 -
readLine: 读取一个字符串，直到遇到回车符。 -
readInt: 功能类似，但将读取的内容解释为整数。
这些共同构成了我们键盘适配器或 Keyboard 类的应用程序接口（API）。现在，让我们开始实现这个类。
实现 keyPressed
keyPressed 的实现相当简单。如果键盘有键被按下，则返回该键的扫描码，否则返回 0。你或许能猜到如何实现它，我们稍后在讨论实现说明时会详细说明。这是操作系统中最基本的输入函数。
请注意，这是一种实时监听函数。换句话说，当你调用它时，你得到的是调用该方法那一瞬间键盘上当前被按下的键。因此，它操作在“一瞬间”。你调用这个方法，它返回一个值，仅此而已。这是你能想到的最实时的函数。
实现 readChar
readChar 则完全不同。readChar 函数具有持久性；它返回用户最后按下的键。这与 keyPressed 有很大区别，我来解释原因。
keyPressed 是实时操作。然而，假设我写了一个程序，在屏幕上显示“请按任意键”的字符串，我告诉用户按一个键。现在，我必须等待并查看用户会做什么。这就是 readChar 的功能。
首先，用户可能不会立即配合。他们看到提示后可能决定去喝杯咖啡。十分钟后他们回来，还没有按键，然后突然按下一个键。我有些夸张，但即使是真实的按键，一次按键也可能需要几毫秒，不同用户的反应时间不同。所以，在某个时刻，用户会按下键。其次，我们也不知道用户愿意将手指放在键盘上多久，可能几秒钟，也可能立即抬起。
因此，我们看到 readChar 必须克服或处理两种不确定性：用户响应并按下键需要多长时间，以及用户愿意抬起手指需要多长时间。我们如何应对？我们必须消除这些不确定性。
首先，我们显示光标（如果希望用户体验良好），向用户展示他们按键的反馈将出现在屏幕的哪个位置。然后，我们必须等待直到有键被按下。最自然的方法是使用这个看起来有些奇怪的 while 循环：
while (keyPressed() == 0) {
// 什么也不做
}
这个循环的所有动作实际上都在条件判断中。这里的条件非常活跃，因为它为了其效果而调用了 keyPressed 函数，并且在一个可能是无限的循环中调用（如果用户不按任何键）。因此，这个循环本质上相当于对键盘进行采样。我们持续采样键盘，直到有事情发生。当有事情发生时，keyPressed 将不再为 0，于是我们跳出这个 while 循环。
然后，我们终于可以捕获用户按下的键，将其存入一个变量（我称之为 c）。现在记住，手指是按下的，我们不知道会按多久。因此，我们将等待直到键被释放，使用一个非常相似的循环：
while (keyPressed() != 0) {
// 什么也不做
}
只要手指按下，我们就什么也不做。一旦手指抬起，keyPressed 将再次变为 0。然后，我们最终可以给用户一些关于他/她按了什么的反馈，并将 c 返回给调用者。
我希望你能够理解 readChar 和 keyPressed 之间的区别，并明白我们需要 readChar 来克服这些我们无法控制的（程序层面的）不确定性。
实现 readLine
接下来要讨论的方法是读取字符串。回想一下，通常当我们要求用户输入某些内容，如“请输入您的姓名”或“请输入您的年龄”时，我们期望用户输入多个键，而不是一个，比如名字“Peter”或数字“53”等。通常，我们期望用户通过按回车键（有时称为返回键）来表示输入完成。
我们必须编写一些逻辑来处理这种用户行为，这就是操作系统键盘API中 readLine 的功能。
我们开始构建一个字符串（即用户正在输入的字符串），初始化为空。然后，我们将进入一个循环，根据用户提交的击键来增长这个字符串。
首先，我们读取一个字符。注意这个抽象的巧妙之处：我们说 readChar，但我们知道我们已经完全处理了手指按下和抬起的所有过程，这一切都被 readChar 封装了，我们已经处理好了。
然后，我们查看这个字符并检查它是什么。如果字符是换行符（即回车键的ASCII码），那么我们想要显示换行并返回字符串。显示换行不是我们的事，这是由输出类完成的，因此我们必须调用显示换行符的输出方法（你可以查看输出API了解如何操作），这将使光标移动到下一行。到那时，我们知道字符串 str 已经输入完毕，因此我们直接返回它。这就是过程的结束。
另一种可能是退格键。如果用户输入了退格键，那么我们知道最后输入的字符应该被擦除，因此我们从 str 中移除最后一个字符。然后，我们也想确认用户按了退格键，通过调用 output.backSpace() 函数来实现。这个函数（我们在上一单元讨论过）知道如何将光标向后移动一个位置，但这不是我们的事，输出类会为我们处理。
这些是输入字符的两种极端可能性。因此，如果既不是回车也不是退格，那么大概我们有一个真正的字符需要处理，我们取这个字符并将其附加到 str 的末尾。
这就是这里的逻辑。我们持续这样做，注意跳出这个循环的唯一方式是遇到换行符，这正是我们想要的。当这种情况发生时，我们返回 str。这就是从键盘读取行的函数。
实现说明
描述了这些函数的逻辑后，我想给你一些关于如何在HEC平台上实现它们的提示。
从 keyPressed 开始，它可以很容易地使用 Memory.peek 函数实现。如果你记得，我们有一个名为 peek 的函数，允许你获取RAM中任何寄存器的值并返回它。这些寄存器中恰好有一个保存着键盘的当前内容，你可以从这里入手，我相信你知道（或将会知道）如何实现它。
readChar 呢？readChar 只需实现我在上一张幻灯片中展示的伪代码。同样，readLine 你也可以实现其伪代码。
最后是 readInt。readInt 是一个与 readLine 非常相似的函数，只是我们期望用户只输入数字。当我们读取这些数字时，我们从中构建一个整数。同样，这是你应该能够根据我们之前给出的指导方针自己编写的逻辑。
这些是编写 Keyboard 类所需的所有必要实现说明。
总结
在本节课中，我们一起学习了操作系统的输入处理机制。我们首先了解了键盘在内存中的映射原理，即通过一个特定的RAM寄存器来实时反映按键状态。接着，我们探讨了 Keyboard 类的四个核心API函数：用于瞬时检测按键的 keyPressed，用于等待并读取单个字符的 readChar，用于读取整行字符串的 readLine，以及用于读取整数的 readInt。我们详细分析了 readChar 和 readLine 的实现逻辑，它们通过循环等待和状态判断来克服用户输入时间的不确定性。最后，我们给出了在HEC平台上实现这些函数的关键提示。至此，我们已经完成了操作系统中所有核心类的介绍，为后续的字符串处理等主题做好了准备。
076：字符串处理 🧵
在本单元中，我们将学习如何在Jack操作系统中处理字符串。字符串是编程中用于表示文本数据的基本结构。我们将通过一个名为String的类来了解其创建、操作和转换。
概述
Jack操作系统使用一个名为String的类来处理字符串。这个类提供了一系列方法，允许我们创建字符串、获取其长度、访问和修改特定位置的字符，以及在字符串和整数之间进行转换。理解这些操作对于构建更复杂的程序至关重要。
String类API
以下是String类的主要方法，它们构成了我们与字符串交互的接口：
-
new: 构造函数，用于创建一个具有给定最大长度的新空字符串。 -
dispose: 析构函数，用于销毁字符串对象并回收其内存资源。 -
length: 访问器，返回当前字符串的实际长度。 -
charAt: 返回当前字符串中给定索引位置的字符。 -
setCharAt: 将当前字符串中给定索引位置的字符设置为指定的字符。 -
appendChar: 将指定字符追加到当前字符串的末尾。 -
eraseLastChar: 删除当前字符串的最后一个字符。 -
intValue: 假设当前字符串的字符都是数字，则返回其对应的整数值。 -
setInt: 将给定的整数值转换为字符串表示形式。 -
newLine: 返回换行符的ASCII码值。 -
backSpace: 返回退格符的ASCII码值。 -
doubleQuote: 返回双引号的ASCII码值。
这个API的设计借鉴了其他面向对象语言中字符串类的常见功能，旨在提供直观且强大的字符串操作能力。
客户端视角
为了理解这些方法如何被使用，让我们从客户端程序的角度来看几个例子。
以下是创建和操作字符串的客户端代码示例：
var String s;
var int x;
let s = String.new(6); // 创建一个最大长度为6的空字符串
do s.appendChar(97); // 追加字符‘a’ (ASCII 97)
do s.appendChar(98); // 追加字符‘b’ (ASCII 98)
do s.appendChar(99); // 追加字符‘c’ (ASCII 99)
do s.appendChar(100); // 追加字符‘d’ (ASCII 100)
let x = s.length(); // 此时 x = 4
另一个例子展示了整数与字符串之间的转换：
var String numStr;
let numStr = String.new(5);
do numStr.setInt(314); // 将整数314转换为字符串“314”
let x = numStr.intValue(); // 此时 x = 314
let x = x * 2; // 此时 x = 628，展示了数值计算与字符串的不同
关键点在于区分整数值（如二进制表示的314）和字符串（如由字符‘3’、‘1’、‘4’的ASCII码组成的序列）。
核心算法：整数与字符串互转
setInt和intValue方法是实现中最具挑战性的部分。下面我们来看看它们背后的算法。
整数转字符串算法
这个算法的目标是将一个整数（如123）转换为其字符表示形式（“123”）。
算法步骤（递归实现）：
-
获取输入整数的最后一位数字：
lastDigit = value % 10。 -
将该数字转换为对应的ASCII字符。
-
如果
value < 10，则递归结束，返回该字符。 -
否则，将输入整数缩短：
remainingValue = value / 10。 -
递归调用算法处理
remainingValue，并将当前步骤得到的字符追加到递归结果的末尾。
通过递归，我们从最低位到最高位依次处理每一位数字，并在递归返回时拼接成完整的字符串。
字符串转整数算法
这个算法的目标是将一个数字字符串（如“123”）转换回整数值（123）。
算法步骤（迭代实现）：
-
初始化结果
result = 0。 -
从左到右遍历字符串中的每个字符。
-
对于每个字符：
-
将其ASCII码转换为对应的整数值
digit（例如，字符‘1’的ASCII码49转换为数字1）。 -
更新结果：
result = result * 10 + digit。
-
-
遍历结束后，
result即为最终的整数值。
这个过程模拟了我们将数字字符串“读”成一个整数的过程。
实现要点
了解了算法之后，我们来看看如何在Jack中实现String类。
内部表示：
一个String对象可以包含两个字段：
-
一个数组：用于存储字符串中每个字符的ASCII码值。
-
一个整数：表示字符串当前的实际长度（而非创建时指定的最大长度）。
方法实现思路：
-
构造函数 (
new)：根据指定最大长度分配数组，并将长度字段初始化为0。 -
基本操作 (
length,charAt,setCharAt,appendChar,eraseLastChar)：通过对内部数组和长度字段进行操作即可实现。 -
intValue和setInt：分别实现上述的“字符串转整数”和“整数转字符串”算法。 -
newLine,backSpace,doubleQuote：这些是简单的函数，直接返回对应字符的固定ASCII码值（例如128、129、34）。
总结
在本单元中，我们一起学习了Jack操作系统中的字符串处理。我们首先介绍了String类的API，了解了如何创建、修改和查询字符串。接着，我们从客户端代码的角度观察了字符串的实际使用。然后，我们深入探讨了setInt和intValue这两个方法背后的核心算法，即整数与字符串之间的相互转换。最后，我们概述了String类的实现要点，包括其内部数据表示和各个方法的实现思路。掌握字符串处理是进行更复杂编程的基础。下一单元，我们将探讨数组处理的实现。
077：数组处理 🧮
在本节课中，我们将学习操作系统中的数组处理。更准确地说，我们将探讨数组在内存中的表示方式，以及操作系统如何创建和销毁数组。我们将重点关注数组类的实现，其API非常简单，仅包含两个子程序。
数组类概述
上一节我们介绍了操作系统的基本结构，本节中我们来看看数组类。数组类的API设计得非常简洁，它只包含两个核心子程序。
以下是数组类的两个主要功能：
-
new：创建一个指定大小的新数组。 -
dispose：销毁调用该方法的数组。
从客户端视角看数组操作
为了更好地理解这些功能，我们先从一个客户端的角度来观察。客户端代码会创建数组并进行操作。
以下是一个典型的客户端代码示例：
// 创建两个数组引用
Array a, b;
// 构造一个大小为3的数组，并让a指向它
let a = Array.new(3);
let a[2] = 77;
// 构造另一个数组，并让b指向它
let b = Array.new(1);
let b[1] = a[2] - 100;
// 在某个时刻，销毁数组a
a.dispose();
这段代码展示了数组的创建、赋值和销毁过程。值得注意的是，像 b[1] = a[2] - 100 这样的数组元素操作，其处理权在于编译器，而非操作系统。我们之前已经用整个单元讨论了编译器如何生成此类操作的代码。
因此，操作系统（至少在Jack语言中）只需要关心两件事：创建数组和销毁数组。这主要涉及数组在内存中的表示。
实现细节：为何使用函数而非构造器
现在，让我们深入探讨如何实现这些功能。首先，请注意 new 子程序被设计为一个函数，而不是一个构造器。这是有原因的。
如果 new 是一个构造器，那么编译器在编译这个类时，会去查询该类的符号表，以确定需要为 Array 类型的对象分配多少内存空间（即计算其字段的总大小）。然而，数组对象本身并没有字段。因此，使用构造器会导致不必要的符号表访问和处理，甚至可能引发问题。
为了避免这种情况，我们选择使用一个普通的函数。当编译器编译一个函数时，它不会去查询符号表或做任何特殊处理。但我们必须记住，由于这不是构造器，系统不会自动为我们调用内存分配器。因此，我们需要在函数中显式地调用 Memory.alloc。
new 函数的实现非常简单，甚至有些微不足道。它的核心就是调用 Memory.alloc 来申请一块指定大小的连续内存空间，然后将这块新内存区域的首地址返回给调用者。之后，调用者（通常是编译器生成的代码）就可以开始向这个数组中填充值了。
实现细节：销毁数组
至于销毁数组的 dispose 函数，其实现同样直接。它也是一个非常简单的函数，主要任务就是调用内存管理模块中的 Memory.deAlloc 方法。Memory.deAlloc 会施展它的“魔法”，回收被该数组占用的内存区域，以便后续重新利用。
总结与过渡
本节课中，我们一起学习了操作系统中的数组处理。我们了解到，数组类的核心功能是管理数组在内存中的生命周期——通过 new 函数创建内存空间，并通过 dispose 函数回收内存空间。具体的数组元素访问和运算则由编译器负责。
至此，关于数组类的讨论就结束了。我们的操作系统构建之旅也接近尾声，只剩下最后一个类需要完成。
在下一单元，我们将讨论 Sys类，完成整个J操作系统的设计。
078：Sys类 🖥️
在本节课中，我们将学习如何实现操作系统的最后一个类——Sys类。Sys类包含几个关键方法，它们负责系统的初始化、控制以及错误处理，是连接硬件、虚拟机、操作系统和用户应用程序的桥梁。
系统初始化与引导程序 🔄
上一节我们介绍了操作系统模块的整体结构，本节中我们来看看Sys类的核心功能。首先，我们需要理解“引导程序”的概念。引导程序是指在计算机通电或重置后，将基本软件（尤其是操作系统）加载到内存中的过程。随后，操作系统负责按需加载其他软件。
在Jack平台上，实现引导需要满足四个不同层面的约定：
-
硬件约定：计算机重置时，执行总是从ROM地址0处的指令开始。
-
虚拟机约定：VM翻译器在翻译程序时，必须在ROM顶部（地址0）放置两条机器语言指令：
SP=256和call Sys.init。 -
Jack语言约定：每个Jack应用程序必须包含一个名为
Main的类，且该类中必须有一个名为main的方法，这是应用程序的入口点。 -
操作系统约定：操作系统必须提供一个
Sys.init函数。
当所有这些约定都被满足时，引导过程得以完成：硬件从ROM 0启动，执行VM设置指令并调用Sys.init。Sys.init函数随后初始化操作系统，并调用Main.main来启动用户应用程序。
Sys.init 函数详解 ⚙️
Sys.init是Sys类中最关键的函数，尽管它对用户是隐藏的。它的主要职责是初始化操作系统，然后启动用户程序。
以下是Sys.init函数需要完成的两个主要步骤：
-
初始化操作系统组件：遍历所有包含
init函数的OS类（例如Math、Memory），并逐一调用它们的init方法。这确保了操作系统各服务在应用程序使用前已准备就绪。 -
启动用户程序：调用
Main.main()方法。从此，控制权便交给了用户编写的高级应用程序。
其他实用方法 🛠️
除了init，Sys类还提供了一些必要的实用方法。
halt 方法
halt方法用于停止计算机的当前运行。一种简单的实现方式是让程序进入一个无限循环，从而制造出计算机已停止的假象。
代码示例：
function void halt() {
while (true) { }
}
wait 方法
wait方法用于实现延时，这在开发交互式程序时非常有用。它接收一个以毫秒为单位的时长参数，并让程序等待相应的时间。
实现wait的关键是使用一个循环，并通过调整循环内的“延迟因子”来控制总耗时。这个因子是平台相关的：在较快的计算机上需要更大的值来减慢循环，在较慢的计算机上则需要较小的值。
实现思路：
-
使用一个循环。
-
在循环体内进行空操作或简单计算以消耗时间。
-
通过实验（例如用秒表或手机计时）校准循环次数，使其符合指定的毫秒数要求。
error 方法
error方法是一个简单的内务处理工具，它接收一个错误代码，并将其清晰地打印到屏幕上。其实现非常直接，此处不再赘述。
总结 📝
本节课中我们一起学习了操作系统的最后一个类——Sys类。我们深入探讨了系统引导的完整链条，它需要硬件、虚拟机、编程语言和操作系统共同遵守约定才能实现。我们详细分析了Sys.init函数如何初始化OS并启动用户程序。此外，我们还了解了halt、wait和error这些实用方法的作用与实现思路。
正如T.S. Eliot的诗句所言：“我们不应停止探索，而所有探索的终点，都将回到起点，并第一次真正认识此地。” 通过这门课程，你们深入探索了计算机与操作系统的内部奥秘。当完成这些探索后，你们将对内存分配、图形绘制、数据转换等概念有全新的、透彻的理解，因为它们不再是神秘的黑箱，而是你们亲手构建过的系统的一部分。在接下来的单元中，我们将亲手实现这一切。
079：构建操作系统 🖥️
在本项目中，我们将从零开始构建一个完整的操作系统。这是课程的最后一个项目，我们将实现一个由八个不同类组成的操作系统，每个类负责特定的功能，如内存管理、屏幕管理和键盘管理等。
概述
操作系统本质上是一组应用程序接口，它定义了操作系统能为应用程序开发者提供的服务。在本项目中，我们不仅会学习这些API，还将亲手实现它们。
操作系统的结构
操作系统由八个不同的类组成，每个类都设计用于提供特定的功能。例如，Screen 类负责屏幕管理，Memory 类负责内存管理等。
以下是操作系统的主要组成部分：
-
Memory：内存管理 -
Array：数组操作 -
Math：数学运算 -
String：字符串处理 -
Output：输出控制 -
Screen：屏幕绘制 -
Keyboard：键盘输入 -
Sys：系统调用
实现策略：逆向工程
上一节我们介绍了操作系统的结构，本节中我们来看看如何实现它。我们将采用一种称为“逆向工程”的开发策略。
逆向工程是一种重要的软件开发技术。假设我们要实现一个现有的操作系统，它由多个可执行模块组成，但我们没有源代码。我们可以采取以下步骤：
-
专注于实现其中一个模块。
-
在开发过程中，调用其他模块的功能时，使用系统提供的可执行版本来支持。
-
逐个模块地重复此过程，最终完成整个系统的开发。
这正是像GNU和Linux这样的操作系统最初的开发方式。开发者从一个已知的可执行系统（Unix）开始，逐步替换并实现自己的版本。
以Screen类为例
让我们以 Screen 类为例，具体说明开发流程。Screen 类是操作系统的八个类之一。
开发步骤
我们将获得一个名为 Screen.jack 的存根文件。这个文件包含了 Screen 类中所有子程序（包括对应用程序开发者不可见的内部子程序）的签名。我们的任务就是使用Jack语言实现这些子程序的具体功能。
// Screen.jack 存根文件示例
class Screen {
function void init() { ... }
function void clearScreen() { ... }
function void drawPixel(int x, int y) { ... }
function void drawLine(int x1, int y1, int x2, int y2) { ... }
// ... 其他方法
}
测试方法
为了测试我们实现的 Screen 类，我们将使用一个名为 Main.jack 的测试文件。这个文件会调用 Screen 类中的各种方法。
测试流程如下：
-
将我们编写的
Screen.jack和提供的Main.jack放在同一个目录。 -
使用Jack编译器编译该目录，生成对应的VM文件（
Screen.vm和Main.vm）。 -
在VM模拟器中运行这个目录。
VM模拟器内置了操作系统的Java实现。但是，如果它发现了用户实现的VM函数（例如我们编写的 drawRectangle 或 drawLine），它会优先使用我们的实现。这样，我们就为逆向工程创造了理想的环境：我们的代码会运行，而它调用的其他OS服务则由内置版本提供。
运行测试后，如果我们的实现正确，屏幕上会显示一幅简单的图画，证明 Screen 类工作正常。
完成所有类
对于操作系统中的八个类，其中五个类（如 Screen）将完全采用上述技术进行开发和测试：提供存根文件和测试文件。
其余三个类的测试方式略有不同，会使用Jack测试脚本和比较文件。所有具体细节都可在课程网站的Project 12页面找到。
这些类可以按任意顺序开发，因为在VM模拟器中，你总是可以使用其他七个类的内置实现来支持你正在开发的那个类。
最终测试
完成所有八个类的实现后，需要进行最终测试。这个测试将在一个实际应用程序（例如“Pong”游戏）的上下文中，运行我们开发的操作系统。
测试步骤在项目说明中有详细描述。一旦通过了这个测试，我们就可以认为你的操作系统已经成功构建，并满意地完成了项目12。
总结
本节课中我们一起学习了如何从零开始构建一个操作系统。我们了解了操作系统的API结构，掌握了通过逆向工程策略逐步实现各个模块的方法，并以 Screen 类为例详细说明了开发、编译和测试的完整流程。最终，我们通过在一个完整应用程序中运行来验证整个操作系统的功能。
080：视角 🧭
在本节课中，我们将回顾并总结我们构建的J操作系统，并将其与真实的工业级操作系统进行比较，探讨其设计理念、功能、效率以及未来展望。
概述
我们已经完成了操作系统的构建，这是Nand2Tetris项目最后一个模块的最后一个单元。本节将从宏观视角审视我们的J操作系统，分析它与常规操作系统的核心差异，并评估其设计效率与意义。
J操作系统与常规操作系统的差异
上一节我们完成了操作系统的构建，本节中我们来看看J操作系统与真实世界中的操作系统有何主要区别。
J操作系统提供的功能与工业级系统相比非常有限。例如，我们的操作系统既不支持多线程，也不支持多进程处理。而典型操作系统的核心正是为了处理这些任务而设计的。
同时，我们巧妙地避免了构建文件系统。这得益于Hack平台没有磁盘这一简单事实。显然，如果需要管理海量存储，文件系统是一个绝对必要的抽象层，而操作系统通常支持这种抽象。
以下是其他一些我们未支持的功能：
-
用户通常期望通过命令行界面或窗口系统与计算机交互，而我们的操作系统不包含这些功能。
-
我们还不支持许多其他服务，例如安全性和通信功能。
尽管如此，我们的操作系统仍然弥合了底层硬件与应用程序之间的重要鸿沟。它向应用程序员隐藏了大量复杂、技术性和底层的细节。总体而言，它以相当优雅和清晰的方式完成了这项基础工作。从这个角度看，我们的操作系统为任何想了解设计和实现一个简单操作系统所需知识的人，提供了一个非常好的起点。
开放性与权限机制
了解了功能差异后，我们来看看J操作系统为何如此开放，允许程序员进行任何操作。
首先，这完全符合Nand2Tetris的精神，即一切开放，用户应将硬件和软件系统视为开放的实验室。
然而在现实中，大多数计算机的操作系统代码被视为特权代码。访问操作系统服务和功能需要一个比我们系统中简单的函数调用更复杂的权限机制。此外，在大多数系统中，操作系统函数在一种特殊的保护模式下执行，这种模式还为它们分配了额外的硬件资源，例如时钟周期。
但在我们的Hack平台上，用户级代码和操作系统代码在完全相同的执行级别上运行。与真实的计算机系统相比，这几乎是闻所未闻的。但这再次鼓励了实验和参与的精神。
效率评估
接下来，我们来探讨一个非常重要的问题：J操作系统在效率方面表现如何？
我认为与此问题最相关的两个领域是数学运算和图形处理。在这两个领域，我们都做了相当不错的工作。
首先，我们为乘法和除法提供的算法是高效的。我们的实现方式与其他计算机的主要区别在于，在其他计算机中，这些算法通常在硬件中实现，而不是在软件中。然而，两种实现方法都基于完全相同的算法思想和见解。
具体来说，我们介绍的乘法和除法算法的运行时间是 O(n)，与 n 成正比，其中 n 是必须处理的比特数。更准确地说，运行时间是 O(n) 次加法操作。由于将两个 n 位二进制数相加也需要 O(n) 次比特操作，因此这些算法中任何一个的总运行时间最终都是 n² 或 O(n²) 次比特操作。事实证明，O(n²) 的效率并不差。当然，存在运行时间渐近快于 O(n²) 的乘除法算法，但这些算法只有在需要乘除非常大的数字时才开始显现优势，而在我们的案例中，这并不是真正的问题。
那么图形处理呢？我们提供的画线算法相当高效。然而在大多数系统中，这些图形基元通常由软件和特殊的图形加速硬件组合实现。这些就是所谓的GPU，它们的作用是将中央处理器从执行复杂的高性能图形任务（如绘制3D图像和渲染平滑曲面，这些需要大量计算能力）中解放出来。
在Hack平台中，CPU和其他专用处理器之间没有这种责任分离，所有工作都由CPU独自完成。
总结与展望
总而言之，操作系统是一个巨大的研究和实践领域，尤其是在计算日益分布式、开放化、可移植化，同时面临多种风险的世界中。因此，我们可以预期操作系统的技术水平将出现显著的进步。我衷心希望你们中的一些人将在这些发展中扮演重要角色。
在本节课中，我们一起学习了J操作系统与工业级系统的核心差异，理解了其开放设计的理念，评估了其在数学运算和图形处理方面的效率，并展望了操作系统领域的未来发展方向。
081：更多探索方向 🚀
在本单元中，我们将回顾已构建完成的计算机系统，并探讨如何对其进行优化与扩展。我们将学习优秀设计的重要性，并审视一系列可能的改进方向，包括硬件加速、指令集扩展以及编译器优化等。
课程概述
恭喜你，我们已经从零开始构建完成了一套现代通用计算机系统，包括硬件和软件。既然任务已经完成，我们可以回顾并问自己：如何才能让这台计算机变得更好？如何让它更快、更有用、更通用？这正是我们将在本模块（模块7）中要做的事情。
我们将提出几个扩展和优化的想法，并且我敢打赌你们也能想出类似的想法。这些想法中的每一个都可以成为一个后续的 Nand2Tetris 扩展项目的基础。
优秀设计的重要性
为了开展每一个这样的项目，你必须首先从所谓的“设计”开始。一个好的设计是每一个成功的硬件和软件实现项目的关键。
到目前为止，在本课程中，Nand2Tetris 的设计者是 Noam 和我。我们提供了所有的设计文档，包括所有的 API、标准实现契约、测试程序等。你们扮演了系统开发者的角色，根据我们的设计进行工作。Noam 和我确实非常努力地设计出了架构良好、API 清晰的方案。我们这样做是因为我们相信，实现设计良好的系统是学习（或至少开始学习）如何成为一名系统设计师（也称为系统架构师）的最佳方式。这就是我们要求你们实现所有这些设计的原因。如果你想成为一名诗人，你最好从阅读一些好诗开始。
那么，是什么让一个好的设计变得优秀呢？我们可以从显而易见的东西开始：模块化、简洁性、优雅性、清晰性、美观性。在课程中，我们并没有明确地讨论所有这些事情，因为空谈无益。相反，我们要求你们实现我们的设计，并希望通过这样做，你们能对什么是模块化、简洁、优雅、清晰和美观建立起一种直观的欣赏。
一旦你把这些都做好了，那么下一个设计目标几乎会自动实现。这个目标，可能是任何硬件和软件项目或系统最重要的优点，就是能够以最小的麻烦来修改和扩展系统。这一点非常相关，因为这就是我们想在本模块中做的事情：讨论如何优化和扩展 Hack 系统。令人欣慰的是，我们即将修改的这个系统设计良好。这令人欣慰，因为设计良好的系统自然就适合进行此类修改。因此，我们将能够以一种可管理和可预测的方式完成所有事情。
优化方向探索
上一节我们讨论了优秀设计是系统可扩展性的基础。本节中，我们来看看一些具体的优化和扩展方向。
硬件加速：乘法与除法
目前，Hack 的 ALU 只能进行加法和减法。因此，即使是乘以 2 这样的简单操作也需要调用操作系统函数，这非常低效。当你考虑如何在各种可能的优化项目之间分配精力时，你应该始终考虑影响，即如何获得最大的效益。乘法和除法在计算机程序中频繁发生，因此显然值得尝试优化它们。
让我们专注于如何优化乘法，因为除法的情况非常相似。在单元 6.2（以及书中第12章），我们介绍了一种高效的按位乘法算法。我们当时用 Jack 语言实现了这个算法。现在，如果你想加速乘法，我们可以采用完全相同的算法，但不是将其作为用 Jack 编写的操作系统函数来实现，而是作为一个用 HDL 编写或指定的硬件芯片来实现。
一旦你有了这样一个经过充分测试的芯片，你就可以将其集成到 Hack 的 ALU 中。但这还需要扩展 Hack 的指令集，因为你必须决定一些二进制乘法操作码，否则你将无法告诉 ALU 进行乘法运算。如果你扩展了二进制机器语言，那么你也必须扩展汇编语言，需要想出一些符号助记符来表示乘法。这反过来又要求你修改我们在课程第一部分构建的汇编器。你看，这就是设计的全部内容。你必须决定要做什么，然后你必须实际去做。
因此，将乘法重构到硬件中，可以说，需要进行一次非常漂亮的跨层“手术”，因为它贯穿并影响了我们计算机架构的多个层次。由于这些层次高度模块化且规范明确，每一个修改都可以单独进行和单元测试。
硬件加速：位移操作
我们的 ALU 中缺少的另一个功能是位移操作。位移可以真正加速诸如乘除法等操作，以及处理屏幕上像素的低级图形操作。同样地，如果你想在硬件中实现位移，诀窍在于设计新的芯片和新的指令，以在硬件级别执行左移和右移操作。
一旦我们拥有了这些硬件能力，我们就应该考虑修改我们的翻译器（编译器/VM翻译器）来巧妙地利用它们。例如，当编译器需要编写代码来乘以或除以 2 的幂次方数时，它可以通过生成使用位移操作而不是标准乘法的代码来实现。你看，这就是人们谈论优化编译器时的一个例子。
顺便说一下，在本模块中，当我们说“编译器”时，我们指的是编译器和 VM 翻译器两者。因此，你可能需要修改编译器或 VM 翻译器，或者两者都修改。在任何一个优化项目中，这都是你需要自己弄清楚的事情。
优化 VM 翻译器
VM 翻译器实际上可以通过许多不同的方式进行优化。因为目前它只是简单地将命令从 VM 代码翻译成汇编代码，而没有尝试生成紧凑的代码。因此，即使是最简单的操作，如加 1 或减 1，也会生成好几条汇编指令，而实际上可以用更少的指令完成。所以，这可能是另一个优化项目的例子。
扩展新功能
以上我们探讨了优化现有功能的方向。那么，关于创建新功能呢？例如，为我们的计算机添加大容量存储和网络访问功能如何？这将是我们在下一单元讨论的内容。
总结
在本节课中，我们一起学习了在完成基础计算机构建后，如何思考系统的优化与扩展。我们认识到优秀的设计是实现可扩展性的关键。我们探讨了多个具体的优化方向，包括将乘除法、位移操作等关键功能从软件迁移到硬件实现，以及随之而来的指令集、汇编器和编译器/VM翻译器的协同修改。我们还提到了优化 VM 翻译器代码生成效率的可能性。最后，我们预告了下一单元将探讨为系统添加全新功能（如存储和网络）的设想。这些探索方向为你将所学知识应用于实际项目提供了清晰的路径。
082：更多探索方向 🚀
在本节中，我们将探讨如何为计算机添加大容量存储和网络访问功能，并了解实现这些扩展所需的具体步骤和规划方法。
概述
我们将讨论如何将硬盘和网络接口卡等设备集成到计算机架构中。这涉及硬件修改、操作系统开发以及新芯片的设计与集成。
添加大容量存储 💾
上一节我们介绍了计算机的基本架构，本节中我们来看看如何为其添加大容量存储功能。
我们可以假设已经拥有一个内置的硬盘芯片，例如一个能够持久存储大量比特的闪存单元。利用这个新功能，一个自然的应用是保存和加载Hack程序。
任何此类新功能的添加都需要修改整体架构中的多个层面。
以下是需要修改的主要方面：
-
修改Hack硬件：允许程序驻留在可写的内存空间，而非当前只读的内存区域。
-
指定简单的文件系统：开发一个操作系统类，实现如
加载文件和存储文件等抽象操作。 -
引入命令行界面：此时，引入某种命令外壳或终端窗口将使用户能够访问和操作他们的文件。
正如所见，一项改动往往会引发一系列新的需求。
连接至互联网 🌐
现在，让我们看看如何将Hack计算机连接到互联网。
与处理磁盘类似，我们假设拥有一个内置的网络接口芯片，可以将其集成到硬件模拟器中。这个芯片的设计应使其一端与Hack硬件交互，另一端与您实际PC上的某个套接字交互。
这与当前已实现的键盘芯片的运作方式非常相似，因为键盘芯片与您PC上的实际物理键盘交互。网络接口卡也需要能够处理来自互联网（而非键盘）的比特流。
为了管理这个新设备，我们需要编写一个新的操作系统类，它知道如何使用某种标准通信协议在不同位置之间移动比特。
一旦具备了这些能力，我们就可以开发各种与这个芯片通信的Jack程序，作为通往互联网的网关。例如，使用Jack开发一个基于HTTP的简单网页浏览器会非常酷。
设计与集成内置芯片 🔧
我们讨论的所有扩展，其核心都是将外围设备添加到基础硬件中。所有这些扩展都要求首先设计和集成一个新的内置芯片，就像我们刚才讨论的磁盘和网络接口芯片一样。
那么，如何构建这样的内置芯片呢？
在开发Nand2Tetris模拟器时，我们设计了一个简单且文档完善的接口，用于添加所谓的“内置芯片”。得益于这个接口，模拟的Hack硬件平台是开放且可扩展的。
如果您想构建一个新的内置芯片（例如硬盘，或者如果您对音乐感兴趣，可以构建一个扬声器），那么您应该首先从指定和开发一个独立的Java类开始，该类实现您希望在这个新设备中使用的底层功能。
如果您想了解更多关于如何开发此类Java芯片的信息，可以从Nand2Tetris网站下载模拟器软件并阅读相关文档。我们的代码是开源的（纯Java），欢迎您按需修改和扩展。
项目规划与实施 📝
有一点不言而喻，但我还是要强调一下：我们讨论的任何优化和扩展项目都需要非常仔细、务实和现实的规划。
以下是实施步骤：
-
明确功能目标：首先清晰阐述您希望通过这个新设备或新扩展交付的确切功能。目标不要定得太高，专注于绝对必要的部分，忽略其余。
-
识别需修改的子系统：确定现有架构中（包括硬件和软件）所有需要修改的子系统与API。
-
指定新API并编写测试：指定您将开发的新功能所需的API，并编写一些存根程序来测试这些新功能。
-
开始实际实现：只有在完成所有这些准备工作之后，才应开始着手交付实际实现。
同样需要强调的是，在实现大容量存储、网络接口或任何其他您感兴趣的设备的简化版本之前，您必须先在互联网上阅读相关资料，然后再次确定您的项目绝对需要的最小功能子集，否则您可能会迷失方向。
分享与展望 🤝
最后，我想谈谈分享。如果您构思了一个很棒的项目，并希望与其他学习者分享，我们很乐意知晓。您不一定要与世界分享所有细节，可以只描述您的项目想法、通用方法、规范或任何您想分享的内容，这样其他人就可以从您的设计中受益并构建这个项目，就像我们要求您在本课程中构建我们的设计一样。
在下一个单元，我们将讨论更多在Jack语言层面的扩展以及高级语言的一般概念。我们还将讨论Nand2Tetris课程论坛中经常出现的一个话题：如何物理地构建Hack计算机（或任何其他计算机），而不仅仅是通过模拟。我们将使用一种名为FPGA的卓越硬件技术来实现这一点。
总结
本节课中，我们一起学习了如何为计算机架构添加大容量存储和网络功能。我们探讨了从硬件修改、操作系统开发到内置芯片设计与集成的完整流程，并强调了务实规划和分步实施的重要性。这些扩展为计算机打开了通往更广阔应用世界的大门。
083：更多探索方向 🚀
在本单元中，我们将继续探讨如何优化和扩展Hack计算机的硬件与软件，并介绍一些可供深入探索的实践方向。
上一节我们讨论了Hack计算机软硬件的一些优化思路。本节中，我们来看看更多具体的、可供探索的扩展与实现方案。
软件层面的扩展：Jack语言 🖥️
首先，我们可以从Jack高级语言入手进行改进。在课程第3模块的“视角”单元中，我们曾讨论过Jack语言的一些潜在优化方向。
以下是几个可以改进Jack语言的方面：
-
语法优化：使其对开发者更友好。
-
引入新命令：例如添加
for循环和switch选择语句。 -
扩展类型系统：增强语言的数据类型支持。
-
添加继承机制：为面向对象编程提供更强大的支持。
实现这些改进需要完成一系列修改。首先，必须修改语言的语法规范，例如在文法中定义 for 和 switch 等新命令。随后，需要相应地修改编译器的语法分析器和代码生成器，以处理这些新特性并生成实现其功能的机器码。
这些修改的复杂度各不相同。例如，添加 for 和 switch 语句相对简单。而实现真正的继承机制则更具挑战性，它不仅要求修改编译器，还需要修改底层的虚拟机。
另一个非常有趣且富有挑战性的方向是，实现一门全新的高级语言。这可以是一门现有语言，也可以是你自己设计的新语言。例如，开发一个Scheme语言的解释器，就是一个非常棒的项目。
硬件层面的实现：从虚拟到物理 🔧
关于软件扩展的讨论就到这里，让我们回到底层的硬件。许多学习者常问的一个问题是：如何构建Hack计算机的物理实体？将Hack计算机真正“刻入硅片”需要做些什么？
实现物理构建主要有两种基本途径。
第一种相对“简单”的路径是，在现有设备上模拟Hack/Jack平台。例如，你可以在手机或个人电脑上模拟我们的虚拟机。这需要编写一个VM翻译器，将VM程序翻译成宿主设备（如手机或PC处理器）的指令集。
第二种更“硬核”的途径是，使用真实的硬件从头开始构建一切。要实现这个目标，你需要完成以下三件事：
-
学习硬件描述语言：掌握一种工业级硬件描述语言（如VHDL或Verilog）的子集。
-
重写芯片设计：使用该语言，重写我们在Nand2Tetris课程中编写的所有HDL程序。完成后，你将得到Hack计算机芯片组所需的30多个芯片的VHDL/Verilog实现。
-
部署到可编程硬件平台：将上述HDL程序部署到一个可编程硬件平台上。
例如，现场可编程门阵列（FPGA）板就是这样一种平台。FPGA技术功能强大、应用广泛且价格亲民，一块不错的FPGA板价格远低于100美元。实际上，你甚至可以不花一分钱就在FPGA上构建这台计算机：就像我们在Nand2Tetris中使用基于软件的硬件模拟器一样，你可以在个人电脑上使用免费的、基于软件的FPGA模拟器来完成所有工作，获得的经验同样宝贵。
需要指出的是，上述描述听起来可能过于简单。实际上，FPGA实现项目颇具挑战性。其中一个原因是，它要求你在FPGA中实现所有我们曾视为理所当然的内置设备，例如内存、屏幕和键盘驱动芯片。这些在课程中作为内置芯片提供的部件，都需要在FPGA中自行设计和实现，这既有趣又充满挑战。
好消息是，我们的同事Denny Sidner博士——一位极具天赋的教师和工程师——已经完成了所有这些工作。目前，我们正与Denny合作开发一门新课程，专门教授如何使用真实硬件构建Hack计算机（乃至任何其他计算机）。在未来的某个时刻，我们将推出这门新课程（或许可以称之为Nand2Tetris第三部分），届时你将学习如何用“原子”而非“比特”来构建计算机。
总结 📚
本节课中，我们一起探讨了扩展Hack计算机软件（如改进Jack语言或实现新语言）与硬件（如在FPGA上进行物理实现）的多种可能方向。正如你所见，关于计算机构建的探索远未结束，仍有广阔的空间等待我们去发现和实践。敬请期待未来的更多内容！
084：更多探索方向 🚀
在本节课中，我们将为这门精彩的课程画上一个句号，并探讨课程结束后的学习方向与资源。我们将回顾课程的核心贡献者，并了解如何持续获取最新的项目与工具信息。
课程结束与致谢
朋友们，很遗憾，每一段伟大的旅程都有终点。在此结束之际，我想说两件事。
首先，正如我在上一个单元提到的，关于“Nand to Tetris”项目，我们远未说出最终结论。
因此，如果你想与我们保持联系，并希望了解新课程、酷炫工具、新项目和激动人心的未来活动，欢迎访问Nand to Tetris网站并加入邮件列表。操作非常简单。
幕后功臣：诺姆·尼桑教授
接下来我想谈谈的是我那神秘的联合讲师——诺姆·尼桑教授，他巧妙地避开了本课程的所有讲座。
事实上，当我们开始制作“Nand to Tetris”的在线版本时，我们决定由我——西蒙——负责准备和讲授课程讲座。
但这种单人表演让我处于一个相当不安的境地，因为它可能造成一种错误的印象，即我是“Nand to Tetris”背后的主要人物。
但事实上，你应该知道，本课程中大多数伟大的想法都来自诺姆·尼桑教授杰出的头脑。
诺姆决定在整个课程中保持幕后，这让我想起了一个关于牛顿和莱布尼茨的可爱轶事。这两位伟大的数学家大约300年前分别在德国和英格兰生活和工作。
故事始于莱布尼茨偶然遇到了一个他无法解决的微积分难题。由于他对这个问题毫无头绪，他将其发表在某科学期刊上，并向同行数学家发起挑战，看谁能解决它。他还在脚注中写道，他认为需要大约六个月才能找到解决方案。
但当牛顿在期刊上看到这个问题时，他在晚饭后大约一小时就解决了它。他无法相信莱布尼茨认为这个问题如此困难，因此牛顿怀疑这是某种恶作剧或诡计。他随后将解决方案匿名发送给了莱布尼茨。
现在，让我们把场景从伦敦移到德国汉诺威，想象一下戈特弗里德·威廉·莱布尼茨教授正在处理他的邮件。突然，他找到了对他那个著名的、所谓超级难题的简短而优雅的解决方案，而解决方案的作者并未在任何地方提及。
根据这个故事，莱布尼茨看了一眼解决方案，说道：“我凭爪子就能认出狮子。”换句话说，解决方案上没有名字，但它带有牛顿天才不可磨灭的印记。
现在，你可能会问，这与“Nand to Tetris”有什么关系？在本课程中，我们非常高兴能与大家分享许多优美的架构、算法、API和编程技术。尽管诺姆·尼桑教授在所有这些讲解中身体缺席，但我相信你们都能“凭爪子认出狮子”。
总结与展望
我们希望你们喜欢“Nand to Tetris”课程。我们很感激有机会与大家分享应用计算机科学的美丽与严谨。再次强调，让我们通过“Nand to Tetris”邮件列表保持联系。
就此，再见。
001：引言 🚀
在本节课中，我们将了解《从零开始构建现代计算机》这门课程的整体目标与结构。我们将一起探索如何从零开始，一步步构建出一台功能完整的通用计算机。
大家好，欢迎来到《从零开始构建现代计算机》。我是 Shimon Shoen，我是 IDC Herzliya 的计算机科学教授，也是耶路撒冷希伯来大学的客座教授。
大家好，我是 Norni Sun，耶路撒冷希伯来大学的计算机科学教授，同时也是微软的研究员。我们将共同教授这门课程。
在本单元中，我们首先要做的，是向大家展示这门课程的整体蓝图。
在这门课程中，我们将从零开始，构建一台完整的、通用的、可工作的计算机，包括硬件和软件。
我们将这个宏大的工程分为两门独立的课程。在第一门课程中，我们将构建计算机的硬件部分，这门课程将持续七周。
在后续将提供的第二门课程中，我们将完成整个蓝图，构建运行在你于第一门课程中构建的计算机之上的软件层次结构。
这就是我们在接下来七周里要做的事情：我们将专注于构建计算机的硬件部分，我们称之为 Hack。
这将是一段精彩的旅程，包含 7周、6个项目、1台计算机，并且无需任何预备知识。我们假设你没有任何计算机科学或工程学的基础知识。课程本身将提供你所需的一切。
以上便是我们在《从零开始构建现代计算机》中的第一个单元。接下来，我们将展望前方的道路，更详细地描述我们在这门课程中将要完成的任务。
本节课中，我们一起学习了这门课程的核心目标：从零开始构建一台名为 Hack 的完整计算机。我们了解到，整个学习过程分为硬件和软件两大部分，并且课程设计为无需任何先验知识即可入门。
002：课程路线图 🗺️
在本节课中，我们将要学习本课程的核心思想工具——抽象，并了解我们将如何通过层层构建的方式，从最基础的逻辑门开始，最终完成一台功能完整的计算机。
概述：从“是什么”到“如何做”
我们通常从一门编程课开始学习计算机科学。在第一节课上，你可能会看到一个非常简单的程序，例如打印“Hello World”。你学习它的语法和命令，但程序背后的复杂机制——比如字母如何在屏幕上显示，或者代码如何被计算机理解——通常被隐藏起来，无需你操心。
这种“隐藏”并非教学的缺陷，而是计算机科学最强大的工具：抽象。你只需要关心某个组件做什么（它的接口或规范），而无需关心它如何做（它的实现细节）。这让你能专注于当前的任务，而将底层复杂性交给其他层级处理。
抽象：计算机科学的基石
上一节我们提到了“抽象”这个概念，本节中我们来看看它是如何运作的。
分离关注点
抽象的核心在于分离关注点。一旦我们构建好一个组件（例如一个“蓝色盒子”），我们就可以忘记其内部复杂的实现细节，只记住它简洁的接口（它能做什么）。然后，我们可以基于这个接口去构建更高级的组件（例如一个“绿色盒子”）。
这个过程可以重复多次，形成多层抽象。每一层都相对简单，但层层叠加后，我们就能得到一个极其复杂的系统。
以下是抽象分层构建的示意图：
[ 紫色盒子 ] <- 基于橙色盒子的接口构建
|
[ 橙色盒子 ] <- 基于绿色盒子的接口构建
|
[ 绿色盒子 ] <- 基于蓝色盒子的接口构建
|
[ 蓝色盒子 ] <- 基础实现
课程中的抽象层级
这正是本课程将采用的方法。我们将从非常基础的简单逻辑门开始，逐步构建更复杂的芯片，最终组装成中央处理器（CPU）和完整的计算机。
在课程的第二部分，我们将在这些硬件抽象之上，继续构建更复杂的软件层级。
课程结构：分步构建
基于抽象的思想，本课程的结构设计如下：
-
每周一个抽象层级：每周，我们将专注于实现一个特定的抽象层级。
-
利用已知，构建新知：我们将已完成的底层视为已知且可靠的“黑盒”，只使用其接口，并在此基础上实现新的、更高层级的抽象。
-
测试与验证：每周都会提供测试套件，确保你构建的组件工作正常，为下一周的工作打下坚实基础。
通过这种方式，经过数周的学习，我们将从名为 Nand门 的简单逻辑门开始，最终构建出一台能够运行复杂程序（例如本课程得名的“俄罗斯方块”游戏）的完整计算机。
课程路线图详解
现在，让我们具体看看课程的两个主要部分。
第一部分：硬件构建（7周）
在第一部分，我们将构建计算机的整个硬件平台。
-
起点：从最简单的Nand逻辑门开始。
-
终点：构建出一台能够运行汇编语言程序的计算机。
-
过程：分为七个清晰的步骤，每周完成一个步骤，最终得到一个可工作的硬件平台。
第二部分：软件构建
在第二部分，课程名“从Nand到俄罗斯方块”将得到完整体现。
-
起点：基于第一部分构建好的Hack计算机。
-
目标：在其上逐步添加软件层级，包括编译器、操作系统等。
-
终点：最终我们将能够用高级编程语言（如本课程设计的Jack语言）编写应用程序，并在我们亲手构建的计算机上运行，例如“俄罗斯方块”游戏。
注：本课程的第二部分目前尚未在Coursera平台上线。如果你在完成第一部分后迫不及待想继续，可以参考我们的配套书籍，其中包含了全部内容。
总结
本节课中我们一起学习了计算机科学的核心思想——抽象，以及本课程如何利用多层抽象的分步构建方法。
我们了解到，通过每周专注于一个层级，将已完成的底层视为可靠工具，并在此基础上构建新知，我们就能在14周内，从最微小的Nand门开始，亲手搭建出一台功能完整的现代计算机，从而彻底理解计算机的工作原理，揭开其神秘面纱。
在接下来的两个单元中，我们将更详细地探讨硬件和软件部分的具体路线图。之后，我们将正式启程，开始第一步的构建。
003：03_01_04_单元-0-2-从NAND到Hack 🧱➡️💻
在本节课中，我们将要学习如何从最基础的逻辑门开始，一步步构建出一台名为“Hack”的通用计算机。我们将了解整个课程的结构、使用的工具以及最终的目标。
在上一单元中，Noam 概述了从 Nand 到 Tetris 的整个旅程。在本单元中，我们将聚焦于本课程的核心任务：构建一台名为“Hack”的计算机。
下图以非常概括的方式描绘了这台计算机，它仅包含了其主要组件。它将拥有 ROM、CPU、RAM 以及许多其他芯片。一旦我们构建好这台计算机，我们将把它连接到一个标准键盘和一个显示单元。此时，你就可以开始执行程序，并享受你亲手构建的计算机了。
可以运行哪些程序呢？任何你能想到的程序。你可以编写一个玩《Pong》的程序，或者玩《太空侵略者》、《推箱子》的程序，当然，还有《俄罗斯方块》。这些实际上是之前选修本课程的学生们编写过的程序示例。
这就是本课程的总体蓝图。我基本上是在重复 Noam 之前说过的话。我们从想要编写的程序的大致想法开始。我们编写程序，编译它，进一步将其翻译成机器语言。我们将代码加载到计算机中。计算机将使用我们构建的所有芯片，这些芯片基于基本的逻辑门，而整个系统的底层是硬件本身。
本质上，我们所做的是在一个硬件平台之上构建了一个软件层次结构。正如 Noam 解释的那样，我们决定将这项事业分为两个不同的部分。第一部分称为“从 Nand 到 Tetris 第一部分”，第二部分稍后提供，称为“从 Nand 到 Tetris 第二部分”。在本课程中，我们将只专注于硬件部分，从硬件本身、电子学和逻辑门的最低层级开始，自底向上地进行构建。
因此，我们现在处于应用计算机科学中一切事物的最低层级。这实际上不是计算机科学，而是电气工程、固态物理学等等，涉及许多我和 Noam 都不太了解的知识。因此，我们将对这个硬件进行抽象，转而专注于我们能想到的最基本的逻辑门，它被称为 Nand。
Nand 是一个我可以在 10 秒内描述清楚的东西，我将在后续的某个单元中介绍。但现在，让我们假设它只是一个基本的逻辑门。我们拿这个 Nand 门，并使用一种称为组合逻辑的技术，从中构建出一整套基本的逻辑门，例如 And、Or 等等。
然后，我们将使用这些门，并运用组合逻辑和时序逻辑（这是一种不同的设计技术，需要考虑时间和时钟），从中构建出诸如寄存器、RAM 单元和 CPU 等组件。
接着，我们将利用构建出的这套芯片组，设计出一个完整的计算机体系结构，称为 Hack。
现在，为了能够在这台机器上编写并方便地执行程序，我们还需要引入一个汇编器，并为 Hack 机器语言开发一个汇编器。
我介绍了很多听起来可能非常陌生的概念。不用担心，随着课程的进行，一切都会得到解释。现在，你们中的许多人可能在想，我们究竟要如何实际构建所有这些芯片。
事实证明，如今的硬件工程师并不徒手做任何事情。他们使用计算机来开发计算机。具体来说，他们使用一种称为硬件模拟器的工具来设计、测试和调试他们想要构建的硬件。这也正是你们在本课程中将要做的。
我们在这里看到的是我们的硬件模拟器的截图。这是一个软件，你可以从我们的网站免费下载，然后安装到你的电脑上。你将使用你的电脑和我们提供的软件来完成本课程的所有项目。
让我们举一个例子来说明我们将如何实际操作。这里是一个 Xor 芯片的例子，它是我们将在本课程中构建的大约 30 个不同芯片之一。你在这里看到的是 Xor 如何操作的抽象描述。
本质上，你将接受这个抽象描述，思考它，并结合我们将提供的各种提示和指导，想出一个逻辑图，使你能够使用之前构建的更低层级的门来构建 Xor。
然后，你将采用这个逻辑图，并使用我们将教给你的一种称为硬件描述语言的语言来具体描述它。结果将是一个称为 HDL 程序的东西。你将把这个 HDL 程序与我们提供的一些测试脚本结合起来，然后使用我之前描述的硬件模拟器来调试、测试并完善你的 HDL 程序。
这就是我们为本课程中要构建的每一个芯片所要做的事情。最终的结果将是 Hack 计算机。我们将把这个旅程分为六个不同的项目。
以下是每个项目的简要介绍：
-
项目一：基本逻辑门。在第一周，我们将构建一些基本的逻辑门，总共 15 个，如幻灯片所示。
-
项目二：算术逻辑单元。在第二周，我们将构建一个算术逻辑单元，它是我们稍后构建的 CPU 的核心部件。
-
项目三：内存系统。在第三周，我们将构建内存系统，从寄存器开始，一直到 RAM 和 ROM 单元。
-
项目四：机器语言编程。在第五周我们构建计算机之前，我们将在第四周用 Hack 机器语言编写一些程序，以便了解这台计算机将能做什么。
-
项目五：计算机体系结构。在第五周，我们将利用迄今为止构建的所有芯片组，设计一台实际的计算机。
-
项目六：汇编器。在课程的最后一周，我们将为 Hack 机器语言引入一个汇编器，并以两种不同的方式实际开发它，一种面向有编程背景的人，另一种面向没有编程背景的人。
这些就是你在本课程中将要完成的所有项目。你努力的成果将是一台 Hack 计算机，一台可以运行你想到的任何程序的通用计算机，无论是俄罗斯方块还是其他任何东西。
现在，我相信你们中的许多人想知道，学习这门课程需要具备什么知识。答案是，我们假设你没有任何计算机科学、工程学或数学方面的先验知识。构建计算机和参加本课程所需的所有必要知识都将在课程本身中提供。这是一门自包含的课程。你将在七周激动人心的项目中学到很多东西。
本节课中我们一起学习了从 Nand 门到 Hack 计算机的构建旅程。在下一个单元中，我们将概述从 Hack 计算机到俄罗斯方块的旅程。
004：04_01_05_单元-0-3-从Hack到俄罗斯方块 🎮
在本节课中，我们将了解本课程第一部分的最终目标，并展望第二部分（尚未正式开设）的宏伟蓝图。我们将看到如何从一个简单的逻辑门开始，最终构建出一台能够运行复杂程序（如俄罗斯方块）的完整计算机系统。
课程第一部分回顾 🧱
上一节我们介绍了课程的基本结构。现在，我们来具体看看第一部分的终点。
在课程的第一部分，你将从非常简单的逻辑门开始。正如你所听到的，你将最终构建出一个可以运行任何程序的、可工作的计算机系统。例如，本课程名称中的“俄罗斯方块”就可以在这台计算机上运行。
课程第二部分展望 🔮
那么，第一部分之后还剩下什么？我们将在第二部分做什么呢？
核心问题在于，在我们于本课程中构建完成的计算机上，人们会进行何种编程。在这台计算机上，你也会构建一种可以在其上运行的语言。但这是一种非常低级的汇编语言。如果你查看汇编语言，它看起来并不友好。它肯定不是你在一对一编程入门课程中开始使用的那种语言。它是一种非常低级、非常不方便的语言。
大多数程序员真正希望使用的是高级语言，就像下面这个例子。这是编程入门课程中非常典型的代码。
// 一个典型的高级语言代码示例
class Main {
function void main() {
do Output.printString("Hello World");
do Output.println();
return;
}
}
在这种高级语言中包含了许多特性：丰富的语言结构、循环、数据类型、方法、抽象等等。这些特性在本课程结束时介绍的汇编语言中并不存在。
此外，高级语言还包含许多高级操作。例如，数学运算、输入和输出操作。这些是基本的，也是任何想要编写程序（比如打印“Hello World”并期望它在屏幕上显示）的程序员所期望的。
软件层级的构建 🏗️
事实上，在课程的第二部分，也就是我们处理软件层级的部分，这正是我们要实现的内容。
我们将介绍一种名为 Jack 的高级语言。并且，我们将使用多层抽象为它编写一个编译器。当然，因为构建编译器是一件复杂的事情。同样地，我们还将构建一个标准库，事实上，是一个迷你操作系统，它提供程序员期望的所有高级服务。
一旦你拥有了这两样东西（高级语言和操作系统），那么你基本上就站在了编程入门课程的起点。因为你拥有了一个可以正常使用的高级语言。现在，这有望弥合从计算机构建的基础知识，到作为一名入门计算机程序员所期望获得的编程语言、操作系统和标准库之间的所有鸿沟。
关于第二部分课程 📚
如前所述，Nand to Tetris 的第二部分尚未正式开设。我们计划在未来提供。但如果你等不及，它已经在我们的网站和课程用书中准备就绪。
下一单元预告 🚀
在下一个单元，我们将简要介绍第一个项目，或者实际上是第零个项目。我们只是想确保你已经准备就绪，找到了我们的网站，并且知道如何在 Coursera 上提交练习。一旦我们完成这些，下周我们就将真正开始构建计算机。
本节课总结：本节课我们一起回顾了课程第一部分的终极目标——构建一台能运行“俄罗斯方块”的计算机，并展望了第二部分的核心内容：在硬件之上构建软件层级，包括 Jack 高级语言及其编译器、标准库和迷你操作系统，从而搭建起从硬件到现代软件开发的完整桥梁。
005：布尔逻辑
概述
在本节课中，我们将要学习计算机科学的基础——布尔逻辑。我们将从最抽象的层面开始，了解计算机如何仅使用0和1这两种值，以及如何通过基本的逻辑运算来构建和处理信息。这是理解计算机内部工作原理的第一步。
布尔值：计算机的基石
计算机内部只处理0和1。这是因为使用两种明确的状态最为简单可靠。我们可以用多种方式称呼这对值：开/关、真/假、否/是，或0/1。在本单元中，我们将统一使用0和1。
基本逻辑运算
既然我们只有0和1，我们能对它们做什么呢？答案是进行逻辑运算。以下是三种最基本的运算。
与运算 (AND)
与运算接收两个输入，仅当两个输入都为1时，输出才为1。其真值表如下：
| X | Y | X AND Y |
|—|—|---------|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
在逻辑表达式中，我们通常用 X ∧ Y 或 X && Y 表示。
或运算 (OR)
或运算接收两个输入，只要至少有一个输入为1，输出就为1。其真值表如下：
| X | Y | X OR Y |
|—|—|--------|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
在逻辑表达式中，我们通常用 X ∨ Y 或 X || Y 表示。
非运算 (NOT)
非运算是一元运算，只接收一个输入，并输出其相反值。其真值表如下：
| X | NOT X |
|—|-------|
| 0 | 1 |
| 1 | 0 |
在逻辑表达式中，我们通常用 ¬X 或 !X 表示。
组合逻辑表达式
上一节我们介绍了三种基本运算，本节中我们来看看如何像组合算术运算一样，将它们组合成更复杂的布尔表达式。
例如，计算表达式 NOT(0 OR (1 AND 1))：
-
先计算括号内的
1 AND 1，结果为1。 -
表达式变为
NOT(0 OR 1)。 -
计算
0 OR 1，结果为1。 -
表达式变为
NOT(1)。 -
最终结果为
0。
布尔函数与真值表
一旦我们掌握了如何对具体值进行布尔运算，就可以定义更一般的布尔函数。一个布尔函数接收若干个变量（如X, Y, Z）作为输入，并通过一个布尔表达式为每一组输入值产生一个输出。
例如，我们可以定义一个三输入函数：F(X, Y, Z) = (X AND Y) OR (NOT X AND Z)。
布尔值的一个巨大优势是：对于有限个输入变量，可能的输入组合也是有限的。因此，我们可以通过真值表来完整地描述一个函数。真值表列出了所有可能的输入组合及其对应的输出值。
以下是函数 F(X, Y, Z) = (X AND Y) OR (NOT X AND Z) 的真值表：
| X | Y | Z | F(X,Y,Z) |
|—|—|—|----------|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
布尔表达式和真值表是描述同一布尔函数的两种完全等价的方式。
布尔代数定律
就像普通代数有交换律、结合律一样，布尔代数也有一系列恒等式或定律。这些定律可以帮助我们转换和简化布尔表达式。
以下是几个核心定律：
-
交换律：
-
X AND Y = Y AND X -
X OR Y = Y OR X
-
-
结合律：
-
(X AND Y) AND Z = X AND (Y AND Z) -
(X OR Y) OR Z = X OR (Y OR Z)
-
-
分配律：
-
X AND (Y OR Z) = (X AND Y) OR (X AND Z) -
X OR (Y AND Z) = (X OR Y) AND (X OR Z)
-
-
德摩根定律：
-
NOT(X AND Y) = (NOT X) OR (NOT Y) -
NOT(X OR Y) = (NOT X) AND (NOT Y)
-
-
幂等律：
-
X AND X = X -
X OR X = X
-
-
双重否定律：
NOT(NOT X) = X
所有这些定律都可以通过为等式两边构建真值表并验证其完全一致来证明。
表达式化简实例
现在，让我们运用这些定律来化简一个布尔表达式。假设我们有表达式：NOT( (NOT X) AND (NOT X OR Y) )。
化简步骤如下：
-
对子表达式
(NOT X OR Y)应用德摩根定律，得到(NOT(NOT X)) AND (NOT Y)。 -
根据双重否定律，
NOT(NOT X) = X。表达式变为NOT( (NOT X) AND (X AND NOT Y) )。 -
根据结合律调整与运算顺序：
NOT( (NOT X AND X) AND NOT Y )。 -
我们知道
NOT X AND X恒等于0（矛盾律）。表达式变为NOT( 0 AND NOT Y )。 -
0 AND 任何值 = 0。表达式简化为NOT(0)。 -
最终结果为
1。
通过代数变换，我们将一个复杂表达式化简为了常量 1。另一种方法是直接为原表达式构建真值表，会发现所有输出行都是1，从而得出相同结论。
总结
本节课中我们一起学习了计算机理论的起点——布尔逻辑。我们认识了基本的布尔值（0和1）以及三种核心逻辑运算：与(AND)、或(OR)、非(NOT)。我们学会了如何组合它们形成布尔表达式和函数，并掌握了用真值表完整描述函数的方法。最后，我们介绍了布尔代数的一系列基本定律，并演示了如何利用它们进行表达式的转换与化简。
至此，我们完成了从纯逻辑角度操作0和1的学习。在下一单元，我们将保持这种理论视角，探讨一个关键问题：如何用这些基本运算来构造我们想要的任意布尔函数。这正是设计计算机硬件时必须掌握的技能。而再往后，在第三单元，我们将把视角切换到物理实现，探讨这些抽象的0和1信号如何在计算机内部的真实芯片和门电路中表达。
006：布尔函数综合
概述
在本节课中，我们将学习如何根据给定的真值表，综合出实现该布尔函数的逻辑表达式。这是计算机硬件设计中的核心技能，因为我们需要将高级功能描述转化为由基本逻辑门（如与、或、非）构成的电路。
从真值表到布尔表达式
上一节我们介绍了布尔函数、布尔值、布尔代数和布尔表达式。本节中我们来看看如何从更基本的操作来构造布尔函数。
我们已经知道两种表示布尔函数的方法：布尔表达式和真值表。我们也知道如何从表达式推导出真值表：对输入位的每一种可能取值计算表达式，然后填充真值表。
我们现在要做的是完全相反的过程。我们从一个函数的描述（例如给定的真值表）开始，目标是提出一个能计算相同布尔函数的公式。
为什么需要这样做？这正是我们设计计算机时必须做的事情。我们知道我们希望某个单元做什么，但我们必须用原始门、原始操作来实际构建它。
构造析取范式
让我们看看如何做到这一点。我们继续采用抽象的处理方式，试图找出从原始操作构造布尔函数的基本逻辑方法。稍后，当我们实际讨论构建时，我们将更加注重实践，逐步进行。目前，我们只想确保理解原理。
以下是从真值表构造布尔函数的标准方法，称为构造其析取范式公式。
我们逐行查看真值表，只关注输出值为1的行。例如，这里的第一行输出值为1。我们可以写一个表达式，使其仅在这一行取值为1。具体来说，由于在这一行中，x、y和z的值是0、0和0，如果我们看表达式 (¬x ∧ ¬y ∧ ¬z)，这将是一个布尔函数，一个仅在此行取值为1的布尔函数。
现在我们有了一个布尔函数。我们对每个输出值为1的行做同样的事情，构造另一个布尔函数（另一个子句）。例如，这里有另一个输出值为1的第二行。这次，在这一行中y等于1，而x和z等于0。所以我们在这里写的子句是 (¬x ∧ y ∧ ¬z)。同样，这个表达式仅在此行完全取值为1，在其他所有地方取值为0。
我们对每一个输出值为1的可能行都这样做。现在我们有一堆不同的函数，每个函数仅在其对应的行取值为1，在所有其他行取值为0。
但我们想要的是一个单一的函数，一个单一的表达式，恰好只在所有这些行取值为1，在其他行取值为0。我们如何做到？这很简单。我们只需将它们或在一起。现在我们得到一个单一的表达式，一个单一的布尔函数，它恰好在我们为其构建子句的那些行取值为1，在其他所有地方取值为0。
现在，我们基本上已经将函数构造为一个仅使用与、非和或的布尔表达式。
当然，一旦有了这个表达式，我们可以开始以各种方式操作它。这是将函数写成表达式的一种方式。但如果你仔细观察，你会发现我们可以开始改变它的格式。例如，如果你看前两个子句，一个是 (¬x ∧ ¬y ∧ ¬z)，另一个是 (¬x ∧ y ∧ ¬z)。注意，对于y我们有两种可能性，而x和z的值完全相同。因此，我们可以将这两个子句合并为一个子句，它不关心y，只关心 (¬x ∧ ¬z)。
所以我们得到一个稍微短一些的等价表达式。我们可以做更多的操作。我们暂不深入讨论，但实际上我们可以用许多不同的方式写出相同的表达式。有些会比其他的更短。有些在我们实际在计算机中实现时可能更高效。但关键是，从逻辑上讲，它们都是完全等价的。
你可能会想，如何实际找到与我们刚刚得到的公式等价的最短或最高效的公式？一般来说，这不是一个简单的问题。对人类来说不容易，也没有任何算法能高效地做到这一点。事实上，找到一个与给定表达式等价的最短表达式，甚至验证你给定的表达式是否只是一个常数0或1，这是一个NP完全难题。
布尔函数的完备性
更有趣的是，我此刻真正想关注的是，我们实际上证明了一个非常卓越的数学定理：任何布尔函数，无论有多少变量，无论布尔函数是什么，都可以用仅包含与、或和非操作的表达式来表示。
要理解这是多么卓越，只需想想整数和整数函数。并非每个整数函数都可以只用加法和乘法等算术运算来表示。事实上，大多数函数不能仅用算术运算表示。然而，由于我们在布尔代数中所处的有限世界，每个布尔函数都可以只用与、或和非来表示。
这正是赋予我们基本能力的原因，使我们能够仅用这些可能的门、仅用这些可能的操作与、或、非来实际构建计算机。
基本操作集的简化
但我们真的需要所有这些吗？这里有一个更好的定理：我们实际上并不需要或门。仅用与和非，我们就可以构造任何布尔函数。我们如何证明这一点？我们已经知道，如果我们有或，我们可以做任何事情。我们刚刚看到了这一点。现在我们需要证明的只是我们可以用与和非门实际计算一个或。但我们已经知道如何做到这一点。我们记得德摩根定律，它正好给出了一个仅使用非和与门的或运算公式。
所以现在我们有了一个更卓越的定理：我们只需要这两个基本操作就可以实际计算每一个布尔函数。
我们能更进一步减少吗？我们能放弃，比如说，与门吗？这没有意义，因为非只接受一个值并输出一个值，甚至不允许我们组合任何东西。
我们能放弃非门吗？不太可能，因为与有这样的特性：如果你只输入0，输出将总是0。而有些布尔函数，当你输入0时，输出是1，所以仅靠与本身是不够的。
但事实证明，还有另一种操作，仅靠它本身就足以实际计算一切。让我介绍一下与非函数。与非函数的真值表是：仅当两个输入都为1时输出0，其他所有可能性都输出1。从逻辑上讲，x NAND y 被定义为 ¬(x ∧ y)。
这个布尔函数有什么了不起的？好处在于，我们可以证明以下定理：如果你只有与非门，你已经可以计算每一个布尔函数，你已经可以用仅包含这些与非门的表达式来表示每一个布尔函数。
我们如何证明？我们知道，如果你能做非和与，你就能做一切。所以我们只需要展示如何用与非门做非，以及如何用与非门做与。
以下是如何做非。如果你看看当你把x同时输入到与非门的两个输入端时会发生什么，将其代入上一张幻灯片的真值表，你可以看到 ¬x 实际上由 x NAND x 表示。这是第一部分。
第二部分我们需要展示如何做与。 x ∧ y 结果是 ¬(x NAND y)。但我们如何得到非？我们刚刚看到你可以用与非本身做非。所以现在我们已经有效地减少了，我们不再使用非和与，而只使用与非门。
我们得到了我们惊人的定理：只要你有一个与非门，你就可以计算一切。这正是我们实际去构建计算机时将采用的方法。我们将给你一个基本的、原始的与非门操作，你将基本上只用这些基本的与非操作来构建整个计算机，构建所有要求你构建的复杂逻辑。
总结
本节课中，我们一起学习了如何从真值表综合出布尔表达式，特别是通过构造析取范式的方法。我们探讨了布尔函数表示的完备性，了解到仅使用与、或、非操作就足以表示任何布尔函数。更重要的是，我们学习了如何进一步简化基本操作集，最终发现仅与非一种门电路就具备功能完备性，可以构建出所有其他逻辑功能。这为后续从抽象逻辑转向实际硬件门电路设计奠定了理论基础。从下一节开始，我们将把视角从抽象的逻辑操作切换到实际构建计算机所用的门电路。
007：逻辑门
在本节课中，我们将要学习逻辑门的基本概念，包括其定义、类型以及接口与实现的区别。我们还将了解如何使用基本逻辑门构建更复杂的复合门。
概述
在本周的前两个单元中，我们讨论了布尔函数，但讨论大多是理论性的。从本单元开始，我们将探讨如何实际使用硬件来实现这些布尔函数。具体来说，我们将介绍一种称为门逻辑的通用技术，它大致上是一种使用逻辑门来实现布尔函数的技术。
什么是逻辑门？🚪
逻辑门是一个独立的芯片，或者说是一个非常简单的芯片或基本芯片，其设计目的是提供明确定义的功能，例如“与非”（NAND）功能、“或”（OR）功能等等。
基本逻辑门
以下是三个在每一个数字设计项目中都会出现的经典逻辑门：
-
与门（AND Gate）：当它的两个输入都为1时，输出1；在其他情况下输出0。
-
或门（OR Gate）：当它的任意一个输入为1时，输出1；在两个输入都为0时输出0。
-
非门（NOT Gate）：作为一个转换器工作，将输入取反。
我们可以将这些门组合起来，以创建更复杂的功能，稍后将进行说明。
复合逻辑门
什么是复合逻辑门？复合逻辑门是由基本逻辑门和其他复合逻辑门构成的。简单来说，它是比基本门更复杂的门。在本课程中，我们将开发诸如多路复用器等复合门。显然，你们大多数人还不知道这些术语的含义，不用担心，在接下来的几周课程中，你们会熟悉并实际构建它们。
现在，让我们从本课程中使用的最基本的逻辑门——与非门（Nand） 开始。
以下是与非门的定义。这是我们用来描述与非门的标准图示。它有两个输入（A， B）和一个输出（out），所有值都是二进制的（0或1）。
这个门的功能描述是：如果两个输入都是1，则输出0；在任何其他情况下，输出1。 这里也有一个真值表来描述相同的功能规范。这些描述中的任何一个都可以。综合来看，我们这里得到的是与非门的一个抽象。我们没有说这个东西实际上是如何工作的，我们只是描述了我们可以期望它提供什么样的功能。
构建复合门示例
我们可以使用这些基本门来创建复合门。例如，这里有一个三路与非门，可以看作是简单两路与非门的扩展。构建它的一种方法是使用这个技巧：我们可以取一个与非门的输出，并将其馈送到另一个与非门的一个输入中。如果我们正确连接所有线路，这个门应该能提供所需的功能。
在实现周围的虚线矩形中，我们看到的是这个芯片接口的文档。用户位于虚线矩形之外，因此用户只看到三个输入和输出，如门描述的左侧所示。如果你想深入了解或打开这个黑盒，你必须查看虚线矩形内记录和完成的内容。
接口与实现
基于此，我想就接口和实现的概念说几句。
门的接口就是门的抽象。这是用户思考门应该做什么的方式。接口回答了“做什么”的问题。
同时，如果你想理解芯片是“如何”做它正在做的事情，你必须更深入一层。在这一层，黑盒被打开，你看到芯片实际上是如何构建的，或者你自己去构建它（如果你的工作是实际实现这个抽象的人）。
门的接口是唯一的。只有一种方式来描述门的功能。否则，如果有不止一种方式，要么是你描述得不好，要么是你让用户感到困惑，因为描述门应该做什么的方式应该是唯一且独特的。
同时，可能有几种不同的实现来实现相同的抽象。不同的实现可能更优雅、能耗更低、成本更低或更高等。所以，一个抽象，多种不同的实现。这在计算机科学中非常典型。每当你构建一个大型系统时，都会遇到这种二元性。
电路实现
我们讨论了门的接口和门级实现。现在，让我们谈谈被称为电路实现的东西。
如果需要，我可以使用像这样的硬连线电路来实现这些门。这里有一种特定的图形语言来描述正在发生的事情：当我们想要表示门输出1时，我们假设一个灯泡会亮起；当门输出0时，灯泡会熄灭。
如果我们看这个与门电路的实现，我们会发现，由于这个电路的架构，只有当两个继电器都闭合时，灯泡才会亮起。在任何其他情况下，灯泡都会熄灭。这正是表示与逻辑时我想要的效果。
那么或逻辑呢？同样，如果我必须构建一个或门的电路实现，我可以使用这个特定的架构来实现。在这里，只需要一个继电器闭合电路就能点亮灯泡。同样，这与期望的或电路抽象是一致的。
继续看，这是一个三路与非门的电路实现。我想你可以很容易地说服自己，它将提供所需的功能。
然而，我想提醒你，在本单元早些时候，我们还展示了这个与非门的实现（如果你还记得的话）。因此，我想就这两种设计硬件的不同方法说几句。
本课程的实现方法
我想首先说明，在本课程中，我们不涉及物理实现。因此，关于电路、晶体管、继电器等等的所有讨论，以及你在屏幕左上角看到的内容，都属于电气工程范畴，而不是计算机科学。那些使用电路和类似技术构建这些门的人（其中一些技术要先进和复杂得多）被称为电气工程师。我们在计算机科学中已经有足够多的问题需要担心，所以我们完全不会担心物理实现。
我们在课程中将要使用的所有设计，都将类似于我们在屏幕右下角所做的：我们将从与非门（以及“与”、“或”、“非”门）开始，取现有的逻辑门，并以某种巧妙的方式将它们组合在一起，以生成和产生所需的功能。
总结
本节课中，我们一起学习了逻辑门的初步介绍。在下一单元，我们将向你介绍一种语言，一种称为HDL（硬件描述语言）的编程语言。使用这种语言，你实际上可以构建像本单元中看到的逻辑门，以及未来更复杂的逻辑门和芯片。
008：硬件描述语言入门
在本节课中，我们将学习如何使用硬件描述语言来设计和实现逻辑门。我们将从理解逻辑门的行为描述开始，逐步深入到如何用HDL代码构建一个具体的异或门电路。
从抽象到实现
上一节我们讨论了如何使用逻辑门实现布尔函数。本节中，我们来看看如何实际构建和实现这些逻辑门，我们将使用一种称为硬件描述语言的形式化方法。
一旦你用HDL构建了一个逻辑门，你就可以模拟它、测试它，并最终在硬件中实现它。
定义门的行为
作为门的设计师，你首先要做的是明确所需门行为的完整描述。对于一个简单的异或门，我们需要一个真值表。
以下是异或门的真值表：
| A | B | Out |
|—|—|-----|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
真值表与门电路图一起，提供了理解这个芯片功能所需的一切信息。我们在这里看到的有时也被称为芯片的接口。利用这些信息，你可以开始编写一个HDL文件。
编写HDL接口
一个HDL文件通常从一些自由格式的文档开始，描述门应该做什么。然后我们指定芯片的名称、输入和输出的名称。
这些信息通常是给定的，是芯片“契约”的一部分。你只需按照语法写出即可。接着，你会写下关键字 PARTS，这标志着程序段的开始，你将在这里描述芯片的实际设计。
一个异或门接口的HDL代码框架如下：
/**
* 异或门 (Xor)
* 如果两个输入不同，则输出1；否则输出0。
*/
CHIP Xor {
IN a, b;
OUT out;
PARTS:
// 实现部分
}
构建芯片：从接口到实现
当我们使用这样一个芯片时，我们迄今为止看到的部分被称为门的接口。请注意，这是使用异或门所需的全部信息。然而，如果要构建这个门，那就是另一回事了。现在我们必须打开这个“黑匣子”并实际设计它。
因此，在使用芯片时，我们总是戴着两顶不同的“帽子”。一顶是程序员，他使用芯片，为此我们只需要知道芯片接口。另一顶是芯片构建者，这就是我们现在要做的。
接下来，让我们讨论如何从零开始构建这个芯片。实际上，我们并非完全从零开始。我们可以假设我们已经构建了与门、或门和非门。如果我们已经构建了这些门，或者有人给了我们这些门供我们自由使用，我们就可以开始设计。
设计逻辑图
通过检查真值表，我们可以推导出异或功能可以描述如下：当 (A 且 非B) 或 (B 且 非A) 时，门输出1。这个布尔函数可以从真值表中综合出来。
一旦得出这个见解，下一步就是思考如何用我们已有的基本逻辑门来构建这个布尔函数，并绘制出相应的门逻辑图。
以下是构建异或门的一种可能逻辑图：
-
首先，我们绘制芯片图的边界。边界之外是用户对这个门的视图，即门接口。
-
信号A被复制并同时发送到两个不同的目的地：一个与门和一个非门。信号B也经历同样的处理。
-
我们使用一些现成的门：非门、与门和或门。使用现成的门时，我们必须使用其官方定义的输入和输出名称。
-
接下来，我们关注连接不同芯片部件的内部连线。每条这样的连线都必须被命名，我们需要为其起一个合理的、自描述的名称。
用HDL描述逻辑图
现在，我们可以继续使用HDL来实现这个图。我们回到之前创建的HDL存根文件。存根文件是一个部分HDL实现，通常只描述芯片接口，并带有“实现缺失”或“在此处输入代码”等语句。
现在，我们将专注于该文件的实现部分。基本上，我们开始一次一个芯片部件地描述门电路图。对于我们拥有的每个芯片部件，我们写一条HDL语句来描述该芯片及其所有连接。
以下是实现异或门的HDL代码示例：
PARTS:
// 计算 notA 和 notB
Not(in=a, out=notA);
Not(in=b, out=notB);
// 计算 A and notB
And(a=a, b=notB, out=aAndNotB);
// 计算 notA and B
And(a=notA, b=b, out=notAAndB);
// 最终输出： (A and notB) or (notA and B)
Or(a=aAndNotB, b=notAAndB, out=out);
这个HDL文件不过是我们看到的门电路图的文本描述。再次注意，我们区分了接口和实现。同时，芯片的接口是唯一的，而实现方式通常不唯一。例如，异或门可以用更少的逻辑门来实现。不同的实现可能在成本、部件数量、能耗等方面有所不同。
HDL语言的特点
我想借此机会对HDL做一些一般性的观察。为了方便参考，我将本单元早些时候看到的门电路图（右侧）和其HDL描述（左侧）放在一起。
关于HDL，我们可以说以下几点。首先，HDL中有一些问题与我们通常在其他编程语言中所做的非常相似：
-
我们必须关注HDL程序的良好文档。
-
我们必须为使用的芯片和架构内创建的连接起好的描述性名称。可读性非常重要。
-
我们使用缩进使代码看起来整洁美观。
此外，还有一些是HDL真正独特的地方：
-
HDL是一种功能性或声明性语言。没有过程发生，没有程序执行。它只是门电路图的静态描述。我们假设某个解释器（在我们的案例中是硬件模拟器）会获取此描述并开始工作，但过程性部分不属于HDL代码本身。
-
由于HDL是功能性的，我们可以按任何顺序编写这些HDL语句。通常习惯从左到右描述你的图表，这也使代码更具可读性。
-
每次使用现成的门时，我们都承诺使用该门的接口，即其文档中规定的输入和输出名称。
在我们将在本课程中构建的Hack计算机里，我们约定：对于双输入芯片，几乎总是使用字母 A 和 B 作为输入；对于单输出芯片，使用 out 作为输出。因此，我们会看到许多像 a=a 和 out=out 这样的芯片连接。起初，这些约定可能看起来有点奇怪，但如果你思考一下并参考图表，你会发现这些连接很有意义，并且从编程的角度来看非常方便。
关于HDL的总结
我想以一些关于硬件描述语言的一般性评论作为结束。市面上有很多HDL，但据我所知，最流行的两种是VHDL和Verilog。它们用于大约90%的硬件设计项目，但还有许多其他HDL也可以使用。
我们自己的HDL在精神上与前面提到的工业级HDL（VHDL和Verilog）非常相似，但它是这些HDL的一个非常精简和简单的版本。因此，你可以在阅读教程大约一小时后掌握它，并开始编写自己的HDL代码。最重要的是，我们的HDL连同我们的硬件模拟器，为你提供了构建本课程描述的计算机（以及你可能想用所学知识构建的任何其他计算机）所需的一切。
如果你想了解更多关于HDL的信息，你应该查看教科书中的附录A，并阅读我们Nand2Tetris网站上的HDL生存指南。你可能还想学习硬件模拟器教程，了解如何实际读取HDL描述，并使用模拟器执行这些HDL背后的逻辑。
本节课中我们一起学习了硬件描述语言的基础知识。我们了解了如何从定义芯片接口开始，通过分析真值表设计逻辑电路，并最终使用HDL代码将设计文本化。我们还讨论了HDL作为声明性语言的特点以及良好的编程习惯。在下一单元中，我们将描述如何将你的HDL设计在硬件模拟器的环境中变为现实。
009：硬件仿真 🖥️
在本节课中，我们将学习如何使用硬件仿真器来验证我们编写的HDL代码是否正确。我们将了解交互式仿真和基于脚本的仿真两种方法，并学习如何利用测试脚本、输出文件和比较文件来系统化地测试芯片功能。
概述
上一节我们学习了如何使用HDL实现门逻辑。然而，我们编写的HDL代码并不能保证其正确性。我们无法确定设计的架构是否能实现预期的芯片功能。因此，在本节中，我们将学习如何通过硬件仿真来验证HDL程序是否实现了底层芯片的预期功能。
硬件仿真概览
以下是硬件仿真的大致流程。
我们有一个特定的HDL文件需要测试。我们可以将其加载到一个名为“硬件仿真器”的特殊程序中。我们已编写了此程序并在网站上提供，该程序使用Java编写，旨在模拟和测试HDL文件。
我们将HDL文件加载到程序中，可以交互式地测试该芯片的各种操作，这种模式称为交互式仿真。
或者，我们可以使用一种我们设计的特殊语言（称为测试语言）编写另一个文件。这种语言几分钟就能学会。我们可以编写一组预定的、可重复的测试。这样我们就不必进行交互式操作，可以提前规划如何系统地测试底层芯片。
我们将其写入所谓的测试脚本中，然后将两个独立的文件加载到仿真器中：HDL代码和测试脚本。接着，我们让仿真器开始工作，它会执行测试脚本中的每一步，并根据提供的脚本对HDL代码进行指定的测试。这种操作模式称为基于脚本的仿真。
最后，如果需要，我们可以将仿真输出记录到输出文件中，甚至可以将仿真结果与存储在另一个比较文件中的期望输出进行比较。
正如你所见，硬件仿真实践涉及许多新概念和技术。本节的目的是通过一个贯穿本节的逐步测试示例，使所有这些新信息具体化。
软件工具准备
在本节中，我们将介绍几个软件工具（实际上只有一个工具：硬件仿真器）。我们非常欢迎你暂停视频，在你自己的计算机上调用这个硬件仿真器，并确保我们演示的操作在你的机器上也能完成。
如果你在课程开始时下载了软件套件，那么硬件仿真器应该已安装在你的计算机上，你在讲座中看到的所有操作都可以自己完成。我们鼓励你尽可能多地动手尝试。
具体示例：Xor芯片
让我们开始看一些具体示例。
以下是我将在本节中使用的示例。这是一个描述我们在上一节讨论过的Xor芯片的HDL文件。代码本身你应该很熟悉，尽管理解本节内容并不需要完全理解它。
再次强调，我们编写了这段漂亮的代码，但这绝不意味着代码实际上是正确的。事实上，它很可能包含一些错误，比如语法错误、逻辑错误等等。那么我们如何测试它呢？
我们可以调用硬件仿真器，程序开始运行。我们将HDL文件加载到仿真器中，然后可以在A和B输入端输入0和1，并观察芯片内部的情况。
我们如何观察呢？我们必须告诉仿真器去评估芯片的逻辑。在我们告诉仿真器考虑我们输入的新值并评估芯片逻辑之前，仿真器不会做任何事情。如果我们这样做，仿真器会将这些值（我们输入的0和1或其他值）通过架构进行“管道传输”，最终会有结果从芯片的输出引脚输出。
此时，我们可以检查实际产生的输出。我们可以观察芯片的输出（在本例中是输出引脚out的值）。如果需要，我们还可以检查内部引脚（如notB、notA等）的值。仿真器为我们提供了所有这些强大的功能。
硬件仿真器界面详解
下图是硬件仿真器运行时的截图。仿真器包含或具有几个不同的窗格。
让我们分别讨论每一个窗格。
在屏幕的左下角，我们看到已加载到仿真器中的HDL代码。这是一个静态视图。我们无法在此操作或编辑代码。如果想编辑，必须使用外部文本编辑器修改HDL代码，然后重新加载。所以这个窗格只是让我们了解我们加载到仿真器中的具体内容。
在这里，我们可以与仿真器的输入引脚进行交互。我们可以点击它们并更改值。在这个特定示例中，我们有四种不同的0和1组合可能性（这是一个非常简单的芯片）。
一旦我们这样做了，我们可以点击这个看起来像计算器的图标。点击它，我们基本上就是告诉仿真器根据提供的输入评估芯片的逻辑。此时，仿真器会开始工作，花费一小段时间，然后会有结果输出。
然后我们可以评估芯片的输出（本例中只有一个名为out的输出）。同样，如果需要，我们也可以检查内部引脚的当前值。
总之，这个GUI为我们提供了进行Xor芯片（或任何其他芯片）动手交互式仿真所需的一切。
交互式仿真演示
现在，我想给你一个硬件仿真器实际操作的示例。让我们先演示一下，然后再回到讲座。
这就是硬件仿真器。为了使用它，我们首先需要将一个HDL程序加载到仿真器中。我们通过点击这里的图标来实现。
我们看到我们位于Nand2Tetris文件夹中。在这个文件夹内，我们选择projects，然后在projects中选择Project 0。
我们看到这里有一个HDL文件，让我们选择它。这是我们之前讨论过的Xor.hdl文件。
我们将芯片加载到仿真器中。现在，左下角的窗格显示了我刚刚加载的文件内容。我可以上下滚动。它只是只读显示，无法在仿真器内部更改代码。如果你想更改代码，必须使用外部文本编辑器，然后重新加载你修改并保存的文件。
假设我们对这个文件满意，我想实际模拟芯片逻辑。首先，我查看当前的输入值，我们看到Xor芯片的A和B输入默认值为0。所以，如果需要，我们可以继续将它们中的一个或两个更改为其他值。
让我们将A改为1，也将B改为1。注意，目前还没有任何变化。为了查看芯片对这些变化的响应，我必须重新评估芯片逻辑。我通过点击这里的计算器图标来实现。
点击后，我们看到输出变为0。确实，1 XOR 1的结果是0。如果我们想查看其他可能性，可以再次操作其中一个输入引脚，点击计算器，我们看到Xor现在输出1而不是0。
我们还可以做的另一件事是检查内部引脚的值，这为我们提供了另一个层次的检查，特别是在我们试图调试芯片并理解它为何在某些情况下行为异常时。
这只是使用仿真器时首先要做的事情的简要描述：加载芯片、操作输入引脚、检查输出和内部引脚。这是芯片调试和测试的基础。
最后提醒一下，如果你想更改芯片逻辑，必须使用外部文本编辑器编辑HDL文件，保存新文件，将其重新加载到仿真器中，并重新运行测试以测试新的芯片设计。
基于脚本的仿真
交互式仿真确实很好，但在某些时候可能会变得相当繁琐，特别是当你的设计中有很多错误，每次都需要重复进行同一组测试时。
考虑到这一点，我们很幸运地拥有了测试脚本的概念。
再次以Xor芯片为例（顺便说一下，我允许自己互换使用“芯片”和“门”这两个词，对我来说，门就是一个简单的芯片）。
这是一个为测试Xor门设计的测试脚本示例。让我们逐行浏览这个测试脚本。
测试脚本中的第一条命令指示仿真器将Xor.hdl文件加载到程序中。所以连这一步都自动处理了，我们不需要自己动手。测试脚本会为我们加载程序。顺便说一下，这在重复调试时非常重要，因为你如何使用外部文本编辑器修改门逻辑，然后点击保存，再回到仿真器。所以记住重新加载编辑后的芯片新版本很重要。这就是为什么我们在测试脚本中添加了这个命令。
一旦HDL加载到仿真器中，测试脚本就开始对芯片进行四次不同的测试。分号;代表一个特定测试的结束。
我们将芯片的输入值设置为0和0，评估芯片逻辑，并观察结果。然后我们进行下一个测试，依此类推，直到完成该芯片所有可能的输入组合。
这就是我们进行基于脚本的测试的方式。它有很多好处，首要的是我们不必费力地凭直觉做事，因为一切都是预先确定的。我们有一组可重复的测试，无论何时调试芯片（可能是两周或两个月后），我们都可以一遍又一遍地使用相同的测试。所以很高兴知道我们总是可以重复同一组测试。
总之，我们将尽量始终使用测试脚本。好消息是你真的不必担心如何编写测试脚本，因为我们将为你提供测试所需的所有测试脚本，以测试你将在HDL中设计的芯片。所以你专注于HDL，我们来负责测试你的工作。
记录仿真输出
我们可以做的另一件事是记录仿真的输出。具体来说，我们可以用类似以下命令来增强我们的基本测试脚本。
在测试开始时初始化时，我们可以指示仿真器创建一个输出文件（在本例中我们称之为Xor.out）。在测试过程中，在每个测试结束时，我们告诉仿真器将一组值输出到输出文件，这组值在脚本的前言中确定。
如你所见，脚本的第三行说输出列表是a、b和out。因此，每当仿真器看到output指令时，它就会将a、b和out的当前值写入输出文件。在仿真结束时，我们可以简单地检查输出文件的结果，并确信芯片确实按照预期运行。
事实上，在这个特定示例中，如果你检查仿真产生的输出文件，你会注意到它与Xor门的真值表完全相同。所以看起来这个门的行为是良好的。
脚本仿真演示
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
1
0- 0
已为社区贡献38条内容
所有评论(0)