Nand2Tetris I - Machine Language

Posted on 繁/简： set

(胡言乱语时刻) 学习的越深入，越感觉到计算机真是神的造物；阴与阳，黑与白，假与真，0 与 1：吟唱着二进制神谕的摩西缓缓举起手杖，混沌的芯片与电路之海顷刻间分开，一条平坦的道路向应许之地延伸。

神的语言 (machine language) 太简单又太复杂，远非人类贫瘠的大脑能够理解；但人类又觊觎祂全知全能的伟力 (Church-Turing Thesis)，遂亵渎地创造了自己简陋的语言 (assembly language) 来对神谕加以解读。

见此情形，神曰：「看哪，他們都是一樣的人，說着同一種語言，如今他們既然能做起這事，以後他們想要做的事就沒有不成功的了。」为了惩罚人类的僭越，神把他们的语言打乱 (programming languages)；愚钝的人类从此无法互相理解，并都宣称自己使用的语言是最好的。这就是巴别塔倒塌的故事了。


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


Machine Language

A machine language is an agree-upon formalism, designed to code low-level programs as series of machine instructions.

Machine language is the most profound interface in the overall computer enterprise - the fine line where hardware and software meet.

This is the point where the abstract thoughts of the programmers, as manifested in symbolic (binary) instructions, are turned into physical operations performed in silicon.

上面这段对机器语言的描述太精髓了，我无力进行翻译或总结。

在前几节里我们构造了一系列重要的元件，包括 ALU 与 memory chips；这些硬件构成了计算机的 hardware platform。我们常常认为机器语言是为了向 hardware platform「发号施令」而设计的；但其实并不尽然。

machine language 与 hardware platform 是一体两面的。

  • It's true that the machine language is designed to exploit a given hardware platform.
  • It's also true that the hardware platform is designed to fetch, interpret, and execute instructions written in the given machine language.

machine language 与 hardware platform 从不同的角度描述计算机的底层实现，但终究殊途同归。

  • constructive : how hardware platform is built from low-level chips? (第一节)
  • abstractly : What is the given machine language's capabilities? (本节)


Hardware Platform

A machine language can be viewed as an agreed-upon formalism, designed to manipulate a memory using a processor and a set of registers.

Memory

memory 通常用于指代计算机中用于存储数据与指令的硬件设备，包括 RAM 与 ROM，中文语境下通常称其为「内存」或「记忆体」。

memory structure: A continuous array of cells of some fixed width (每个 cell 对应一个 register), also called words or locations, each having a unique address.

An individual word (representing a data item or an instruction) is specified by supplying its address, with the notation Memory[address], RAM[address], or R[address] for brevity.

Processor

Processor 即我们熟知的 Central Processor Unit (CPU)，它负责执行一系列 elementary operations:

  • Arithmetic and logic operations. (通过 ALU)
  • Memory access operations.
  • Control (branching) operations.

这些 operations 的 operants 来自 registers 或 selected memory locations；同样，经过 processor 计算之后的结果 results 也将储存到 registers 或 selected memory locations 中。

那么 instructions 又从哪来？答案是 instruction memory: instruction memory is a read-only device (例如 ROM), programs are loaded into it using some exogenous means.

我们不妨想象这个情形：

  • memory 分为两个部分，data memory 与 instruction memory。
  • processor 拥有 data memory 的 read/write 权限与 instruction memory 的 read 权限。

如何更改只读的 instruction memory？e.g., If the instruction memory is implemented in a ROM chip pre-burned with some program. Loading a new program is done by replacing the entire ROM chip.

Register

register 是 memory chips 的基本组成部分；但我们这里提到的 register 与这个意义无关。在讨论 hardware platform 时，register 特指 CPU 所配备的一系列快速储存器，有时也叫 cache (快存)。

它的出现是为了解决 processor 对 memory 的直接访问速度过慢的问题。

Located in the processor's immediate proximity, registers serve as a high-speed local memory, allowing the processor to manipulate data and instructions quickly.

registers 使 processor 本身也具备了少量记忆的功能；就像程序中的临时变量一样，registers 的存在能够最小化 memory access 命令的数量，从而加速程序执行。

在本节课将要实现的 Hack computer 中，我们将关注两个 CPU registers 与一个对应的 memory register：

  • D register: solely store data value.
  • A register: both a data register and an address register .
  • M register: M register 由 A 指定，M \(\leftarrow\) \(RAM\)[A].


Assembly Language

注意，计算机是符合 von Neumann architecture [stay tuned] 的；简单来说就是 data 与 instructions 是平等的，均能被计算机所存储 (stored-program concept)。

若想被计算机所存储，instructions 必须以 binary value 的形式存在；又因为 instructions 是被 machine language 所描述的，我们不难归结出 machine language 的本质：a series of coded binaries.

例如，对于二进制串 1010001100011001，我们赋予其如下意义 (每 4 bits 为一组)：

  • 1010: 表明该 instruction 的类型为 addition。
  • 0011: processor 应将执行完该 instruction 后的结果储存至 \(R\)[3] 中。
  • 0001: 第一个 operant 的值为 \(R\)[1]。
  • 1001: 第二个 operant 的值为 \(R\)[9]。

Under the formalism，我们将一个普通的 16-bit 二进制串编码成了 hardware platform 能够理解的机器语言。对应的 hardware platform 在读入这一 instruction 过后，将会执行 \(R\)[3] = \(R\)[1] + \(R\)[9]。

但人类难以理解以二进制编码形式存在的机器语言；很自然的，我们需要一套 human-readable 的体系来描述机器语言。于是人类引入了一系列 symbolic notation：这就是所谓 assembly language 的由来了。

Assembly language (or simply assembly) is a mnemonic for machine language.

举例来说，我们将 1010 符号化为 ADD，接下来的几个地址则对应为 R3, R1, R9；这样，instruction \(R\)[3] = \(R\)[1] + \(R\)[9] 能被 assembly language 描述为 ADD R3, R1, R9.

人类不光擅长读 symbolic notation，还擅长写由这些 symbolic notation 组成的程序；assembly language 是一个真正意义上的 programming language。这就是 symbolic abstraction 的力量。

至此，红海分开，道路显现：人类用 assembly language 写就的程序，经 assembler 按照特定的 mapping rules 翻译成 machine language，被 hardware platform 读取后终于转化为硅晶间的微小电流。


Basic Instructions

我们将用 assembly language 来描述两个基本的 instructions: A-Instruction 与 C-Instruction.

The A-Instruction

The A-instruction is used to set the A register to a 15-bit value (address).

1
2
@value                       // Where value is either a non-negative decimal number
                             // or a symbol referring to such number.

这个指令与 A 作为 address register 的身份密切相关。因此，在该命令执行完之后我们一般会对 A 中储存的地址所对应的 register - M 进行操作。(M = \(R\)[value])

The C-Instruction

The C-instruction is the programming workhorse of the Hack platform - the instruction that gets almost everything done. The instruction code is a specification that answers three questions:

  • what to compute? (comp)
  • where to store the computed value? (dest)
  • what to do next? (jump)

Along with the A-instruction, these specifications determine all the possible operations.

1
2
3
dest=comp; jump               // Either the desk or jump fields may be empty.
comp; jump                    // If dest is empty, the "=" is omitted;
dest=comp                     // If jump is empty, the ";" is omitted;
  • dest: 将结果储存至 register (A, D) 或 data memory (M) 处。
  • comp: 支持常数 0, 1, 与 -1 和 A, D, M 三个 register 所储存的值之间任意的算数或逻辑运算。
  • jump: 支持 conditional jump 与 unconditional jump，可以跳跃到程序的任意一行执行 (类似 goto)。

在正常情况下，程序是一行一行执行的，每一行对应一个 instruction，而 jump 可以改变程序的执行流程。其底层实现是 system counter 元件 (可以看出 system counter 指向 instruction memory 的地址)。

conflicting uses of the A register. 之前我们提到，A register 既是 data register，又是 address register。因此 A 中储存的值的含义可能有三种：

  • data: 一个平平无奇的 data。
  • address: 指向 data memory，是 M register 的地址。
  • address: 指向 instruction memory，是程序下一步将会 jump 到的地址。

为了避免语义冲突，在可能会进行 jump 的 C-instruction 中我们尽量避免引用 M register。


Symbols

Assembly commands can refer to memory locations (addresses) using either constants or symbols. Symbols are introduced into assembly programs in the following three ways:

  • Predefined symbols.
    • Virtual registers: R0 to R15 refer to RAM addresses 0 to 15 respectively.
    • Predefined pointers: SP, LCL, ARG, THIS and THAT refer to RAM addresses 0 to 4.
    • I/O pointers: SCREEN and KBD refer to RAM addresses 16834 (0x4000) and 24576 (0x6000).
  • Label symbols.
  • Variable symbols.

label symbols 与 variable symbols 均属于 user-defined symbols。其中，label symbols 作为 jump 命令的补充，使得 assembly language 程序的可读性进一步提高。语法和 goto 很类似：

1
2
3
4
(JUMP_HERE)

@JUMP_HERE
0; JMP            // or other conditional jump

assembler 将自动把 JUMP_HERE symbol 解析为 (JUMP_HERE) 下一行的行数：在这个例子中是 2。

结合 conditional jump 与 label symbols，我们能在 assembly language 中实现简单的 while-loop。最常见的例子是程序末尾的死循环：这是为了阻止潜在的 no-operation (NOP) attack.

1
2
3
(END)
@END
0; JMP

variable symbols 与 label symbol 唯一的区别是它没有 () 标记。variable symbols 将在 data memory 中申请一个 register；此后，所有对该 variable symbol 的引用都将被 assembler 解析为该 register 的地址。

1
2
@VAR
M=0            // VAR=0


I/O Devices

这里我再一次感受到计算机底层结构的统一性：例如键盘，屏幕这样的输入输出设备，其底层实现与 memory 大同小异：我们仍然可以将其视作 a continuous array of fixed-width registers.

以下例子中的具体数据是以本课程中的 Hack computer 为标准的，但其涉及到的原理是共通的。

Screen

Hack computer 拥有一个 256x512 (131072 pixels) 的黑白屏幕。其底层实现是由 SCREEN 标记的 base address 16384 开始的 8K memory map。(\(8192 \times 16 = 131072\))。

第 \(r\) 行第 \(c\) 列的某个 pixel 位于 \(RAM[16384+r\cdot32+c/16]\) 中 word 的第 \(c\%16\) 个 bit 上 (从 LSB 到 MSB)。e.g., 屏幕最左上角的 pixel 位于 \(RAM[\)SCREEN\(]\) 的第一个 bit 上。

黑色的 pixel 对应 bit 1，白色的则对应 bit 0。假设屏幕一开始为空，若我们想将左上角的 pixel 改为黑色：

1
2
@SCREEN
M=1

Keyboard

Hack computer 的键盘用一个 register \(RAM[\)KBD\(]\) 即可实现。

  • A key is pressed on the physical keyboard: its 16-bit ASCII code appears in \(RAM[24576]\).
  • No key is pressed: the code \(0\) appears in this location.


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info:

Lecturer: Prof. Shimon Shocken, Prof. Noam Nisan.

Course textbook:

(Nisan N., Schocken S., 2008) The Element of Computing Systems: Building a Modern Computer from First Principles.

-----------------------------------そして、次の曲が始まるのです。-----------------------------------