課程要往哪裡去

課程前半部專注在硬體：你已在實驗課做出 Hack CPU 的各個元件 （暫存器、PC、ALU 等）。要理解 Hack 架構，我們必須開始思考軟體。 組合語言、機器碼與架構三者緊密綁在一起， 所以我們先學 Hack 組合語言，再往下鑽。之後的路線圖：

1. 組裝出完整的 Hack CPU（下週！）；

2. 用 C 寫一個 Hack 組譯器（assembler）；

3. 朝 Hack 的高階語言「Minijack」邁進—— 用 C 寫 VM 翻譯器，再寫一個（非常簡單的）編譯器。

Hack 架構總覽

CPU 內部：

• 最複雜的部分是算術邏輯單元（ALU）， 處理 \(+\)、\(-\)、& 等算術與布林運算（第二週做過！）；

• 四個暫存器：\(A\)、\(M\)、\(D\) 與程式計數器（PC）—— PC 存放下一條要擷取的指令位址（第四週的計數器！）。

為什麼需要暫存器？因為每個時脈只能從 RAM 讀一個字（word）。 中間結果若都得寫回 RAM，速度會慢得無法接受—— 所以把最常用的值留在 CPU 內部。

看一個程式跑起來

以下程式計算 \(RAM[0] + RAM[1] + 17\) 並把結果存入 \(RAM[2]\) （\(RAM[i]\) 表示 RAM 位址 \(i\) 的 16 位元字）。 假設初始 \(RAM[0] = 10\)、\(RAM[1] = 42\)。 先別管每條指令怎麼編碼——專注在擷取—執行週期上：

幾個關鍵觀察：

• \(M\) 永遠是 \(RAM[A]\)：改 \(A\) 就等於「換一格記憶體來看」。 讀寫 RAM 都透過 \(M\)，所以先載入位址到 \(A\)、再操作 \(M\) 是 Hack 的基本節奏。

• PC 每條指令後自動加一——除非被跳躍指令改寫。 操縱 PC 就是實作迴圈與條件的方法。

• 程式最後進入無窮迴圈。所有 Hack 程式都這樣收尾—— 因為沒有「halt」指令！ 若不圈住，PC 會繼續前進、執行 ROM 裡的垃圾內容。

Hack 組合語言 I：基礎（The Basics）

一點歷史：從 EDSAC 到個人電腦

為什麼學 Hack 組語？

由於一行組語對應一條指令，世界上沒有「唯一的組合語言」—— 不同架構（x86-64、i386、ARM、MIPS…）各有各的組語。 我們教 Hack 組語不是因為它本身直接有用， 而是它能幫你打好基礎，之後學任何架構的組語都容易。

最佳化過的組語常比編譯出來的程式碼更快。 多數高效能語言（C、C++、Rust）都允許內嵌組語 （如 gcc 的 asm）。

Hack 的暫存器

Hack CPU 有暫存器 \(A\)、\(M\)、\(D\)、PC，各存一個 16 位元字：

\(M\) 的本質：把 \(A\) 的值當指標並解參考（dereference）—— 就像 C 語言的 *p！ 更長期或更大量的儲存，用 RAM。 （寫 PC 的方式與其他暫存器不同——見第 3 章。）

暫存器操作

@[數字] 把數字載入 \(A\)：例如 @42 使 \(A = 42\)。 其餘操作都是「目的地=運算」的形式：

別死背這張表——需要時回來查就好！

第一個程式：add.asm

把 \(RAM[0] + RAM[1] + 17\) 存入 \(RAM[2]\)（即第 1 章追蹤過的程式）：

@0
D=M      // D <- RAM[0]
@1
D=D+M    // D <- D + RAM[1]
@17
D=D+A    // D <- D + 17
@2
M=D      // RAM[2] <- D

注意「@位址 \(\to\) 操作 M」的成對節奏—— 這是 Hack 組語的典型型態。 （所有 Hack 程式都應以無窮迴圈收尾——見第 3 章。）

組譯器的小恩惠：註解與關鍵字

組語勝過機器碼的另一好處：註解。 組譯器會跳過以 // 開頭的行、空行與行首空白； 行中註解（如 A=D // 註解）也可以。

組譯器還會把 @R0 換成 @0、@R1 換成 @1、 ……直到 @R15 換成 @15。

還有其他這類關鍵字，（很）之後才會用到： \[\texttt{SP} \mapsto 0,\quad \texttt{LCL} \mapsto 1,\quad \texttt{ARG} \mapsto 2,\quad \texttt{THIS} \mapsto 3,\quad \texttt{THAT} \mapsto 4,\] \[\texttt{SCREEN} \mapsto 16384,\qquad \texttt{KBD} \mapsto 24576.\]

用關鍵字改寫 add.asm，可讀性更好：

// D <- RAM[0]
@R0
D=M
// D <- D + RAM[1]
@R1
D=D+M
// D <- D + 17
@17
D=D+A
// RAM[2] <- D
@R2
M=D

較大的恩惠：變數

組譯器也支援 @ 敘述裡的字母變數。 第一次寫 @var 時，組譯器把字串 var 綁定到一個唯一的 RAM 位址（從 16 開始分配）， 之後所有 @var 都替換成該位址。變數區分大小寫。

例：依序使用變數 foo、Foo、FOO， 則 @foo 變成 @16、@Foo 變成 @17、 @FOO 變成 @18。

Hack 組合語言 II：迴圈與條件（Loops and Conditionals）

來自過去的恐懼：goto

到目前為止我們能算 \((RAM[3] + RAM[4])\ \&\ RAM[5]\) 之類的簡單算式， 但還不算「真正的電腦」——只是接了時鐘的計算機。 我們需要迴圈與條件，但 Hack 沒有 if 或 while。 我們先聊點……更古老、更黑暗、更飢餓的東西：goto。

在 C 裡，goto 讓你從程式任何地方「跳」到指定的標籤：

#include <stdio.h>

int main() {
    printf("Hello, World!\n\n");
    goto skip;
    printf("Gotos can skip lines of code.\n\n");
skip:
    return 0;
}

執行第 5 行的 goto skip 時，程式跳過第 6 行的列印， 直接從第 8 行 skip: 之後繼續，回傳 0。

用 goto 做出迴圈與條件

C 的一切流程控制都能用 goto + 單行 if 表達！例如：

int main() {
    int i = 0;
    while (i < 10) {
        printf("%d ", i);
        i++;
    }
    return 0;
}

int main() {
    int i = 0;
loop:
    if (i >= 10)
        goto endloop;
    printf("%d ", i);
    i++;
    goto loop;
endloop:
    return 0;
}

注意右邊的模式：條件反轉（i < 10 變成 i >= 10 跳出）、迴圈尾端無條件跳回開頭。 這正是等一下 Hack 組語的寫法。

Go To Statement Considered Harmful

那為什麼寫程式要用 while 和 else 而不用 goto？

goto 完全不受限制（在函式內）： 你可以在一萬行的函式裡，從 20 個不同地方跳到同一個標籤。 看到迴圈或 if，你確切知道控制流會怎麼走； 看到標籤，程式可能從任何地方跳過來。

C 裡仍有極少數情況 goto 算合理（例如多層迴圈的錯誤處理出口）， 但除非你很清楚自己在做什麼，最好避開。

可怕的真相是：在組語層面， goto 加上單行 if 通常是唯一的流程控制—— 編譯器把你寫的每個 while 都翻譯成跳躍。 結構化程式設計是高階語言給你的抽象，硬體裡不存在。

Hack 的跳躍（jumps）

我們把組語層的 goto 稱為跳躍（jump）或分支（branch）， 以強調每個都對應單一一條機器碼指令。

一樣不用背——用時查表。記住：所有跳躍都跳到 \(A\) 存的位址。

組譯器的幫助：標籤（labels）

每一（非註解）行組語就是一行機器碼。 所以要無條件跳到組語第 100 行（存於 \(ROM[99]\)）， 得寫 @99 加 0;JMP。 （習慣上用 0;JMP 表示「不附帶運算的跳躍」—— 這是慣例，不是規定。）

問題：這樣維護起來是災難。若要刪掉第 1–99 行中的任何一行， 或插入一行呢？整個檔案的跳躍都要改！

解法：跟 C 一樣，組譯器提供標籤。 形如 (Label) 的一行不對應任何機器碼； 若下一行會落在 ROM 位置 100， 組譯器就把所有 @Label 替換成 @100。

完整範例：Sum.asm

Sum.asm 把 \(0 + 1 + \cdots + RAM[0]\) 的總和輸出到 \(RAM[1]\)：

// sum = 0, i = 1
@sum
M=0
@i
M=1
(LOOP)
    // if i - RAM[0] > 0, goto END
    @i
    D=M
    @R0
    D=D-M
    @END
    D;JGT
    // sum = sum + i
    @i
    D=M
    @sum
    M=M+D
    // i = i + 1
    @i
    M=M+1
    // goto LOOP
    @LOOP
    0;JMP
(END)
    // 慣例的收尾無窮迴圈
    @END
    0;JMP

逐段解說：

1. 初始化：變數 sum（組譯器分配位址 16）設 0、 i（位址 17）設 1。

2. 迴圈條件：算 \(D = i - RAM[0]\)；若 \(D > 0\)（即 \(i > RAM[0]\)） 跳去 END。注意這正是 goto 版 while 的條件反轉模式。

3. 迴圈主體：\(sum \mathrel{+}= i\)、\(i \mathrel{+}= 1\)， 然後無條件跳回 LOOP。

4. 收尾：(END) 處自我跳躍的無窮迴圈。 最後把 sum 搬到 \(RAM[1]\) 的步驟可插在 (END) 之前 ——完整版見練習 6 的變形。

（實際課程影片中的版本把結果直接累加在 \(RAM[1]\)，兩種寫法等價； 上面的版本多用了變數，展示變數與標籤如何合作。）

什麼才算「真正的」電腦？

為什麼要在乎？因為 Church–Turing 論題說： 只要一個計算問題可解，就存在一台精心設計的圖靈機能解它—— 把輸入寫上紙帶、跑到停機、讀紙帶得輸出。

Hack 組合語言 III：輸入與輸出（Input and Output）

記憶體映射 I/O

Hack 唯一的輸入週邊是鍵盤、唯一的輸出週邊是螢幕。

Hack 有 32KB 實體記憶體、以 16 位元字為單位， 所以位址需要 \(2^{18} / 2^4 = 2^{14}\) 位元表示： 位址空間 0x0000 到 0x3FFF。整張記憶體地圖：

• 寫入 0x4000–0x5FFF 的任何值都會顯示在螢幕上；

• 若鍵盤有鍵被按住，其代碼會出現在 0x6000。

鍵盤輸入

關鍵字 KBD 映射到 0x6000（\(= 24576\)）， 方式跟 R1 映射到 0x0001 一樣。 例如按住「d」時，@KBD 會把 24576 載入 \(A\)、 此時 \(M = 100\)（「d」的代碼）。 沒有按鍵時，0x6000 內容為 0。

常用按鍵代碼（節錄自 Nisan & Schocken 附錄 5）：

螢幕輸出

Hack 的解析度是 \(512 \times 256\)：256 列、每列 512 個像素。 像素依「書寫順序」編號——由左至右、由上至下。

還有第三種寫法——直接把位址的二進位結構拆開： \[\underbrace{010}_{\text{固定前綴}}\; \underbrace{rrrrrrrr}_{r\ \text{的 8 位元}}\; \underbrace{ccccc}_{c\ \text{的前 5 位元}}\] 為什麼三種寫法等價？ 0x4000 \(= 010\,00000000\,00000_2\)； \(32r\) 恰好把 \(r\) 左移 5 位； \(c / 16\)（整數除法）就是 \(c\) 的 9 位元中丟掉最低 4 位後剩下的前 5 位。 把三段接起來，正是上面的位元佈局。 （\(c \bmod 16\) = \(c\) 的最低 4 位元 = 字內的位元編號。）

陷阱與技巧

實用技巧：

• CPU 模擬器可以切換以十六進位或二進位顯示暫存器與記憶體 （比十進位好對照位元圖樣）。

• 關鍵字 SCREEN 映射到 0x4000： @SCREEN 加 M=1 就把第一個像素塗黑。

• 螢幕記憶體可讀也可寫！若左上 16 個像素全黑， @SCREEN 加 D=M 會把 0xFFFF 存入 \(D\)。

完整範例：Fill.asm

Fill.asm：把整個螢幕塗黑；但只要有任何鍵被按住，改塗白。 無限輪詢（poll）鍵盤：

(POLL)
    // 依鍵盤狀態決定顏色：預設黑 (-1)
    @KBD
    D=M
    @BLACK
    D;JEQ      // 沒有按鍵 (KBD=0) -> 塗黑
    @colour    // 有按鍵 -> 塗白 (0)
    M=0
    @FILL
    0;JMP
(BLACK)
    @colour
    M=-1       // 全 1 = 16 個黑像素
(FILL)
    // i 從螢幕最後一個字往回塗到第一個字
    @8191
    D=A
    @i
    M=D
(FILLLOOP)
    // addr = SCREEN + i
    @i
    D=M
    @SCREEN
    D=D+A
    @addr
    M=D
    // RAM[addr] = colour
    @colour
    D=M
    @addr
    A=M        // 把 A 設成 addr 的內容：指標！
    M=D
    // i = i - 1；若 i >= 0 繼續塗
    @i
    MD=M-1
    @FILLLOOP
    D;JGE
    // 塗完整個螢幕，回去重新讀鍵盤
    @POLL
    0;JMP

值得注意的三件事：

1. 輪詢迴圈：程式永不停止， 每塗完一輪就回 POLL 重讀 KBD—— 這是沒有中斷（interrupt）機制時的標準做法。

2. 指標寫法：A=M 把「變數 addr 存的位址」 載入 \(A\)，下一行的 M 就是那個位址的內容—— 等同 C 的 *addr = colour。 這正是第 2 章說「變數行不通」時（大量、動態位置）的替代方案。

3. 螢幕共 \(8192\) 個字（0x4000–0x5FFF）， 所以 i 從 \(8191\) 遞減到 \(0\)。 一次寫一個字 = 一次塗 16 個像素。

綜合練習題（附詳解）

練習 1：擷取—執行追蹤

初始 \(RAM[0] = 7\)、\(RAM[1] = 3\)，其餘為 0。逐條追蹤下列程式， 寫出每條指令後的 \(A\)、\(D\) 與相關 RAM 內容：

@0
D=M
@1
D=D-M
@3
M=D

練習 2：哪些指令合法？

判斷下列每條指令是否為合法的 Hack 組語，不合法者說明原因： D=D+M、D=A+M、M=D+D、AMD=D|M、 DAM=D+A、D=17、A=A+1、M=-M、 @-5、D=M;JGT。

練習 3：直線程式

寫出計算 \(RAM[2] = RAM[0] - RAM[1] + 5\) 的 Hack 組語（含收尾）。

@R0
D=M      // D = RAM[0]
@R1
D=D-M    // D = RAM[0] - RAM[1]
@5
D=D+A    // D = D + 5
@R2
M=D      // RAM[2] = D
(END)
@END
0;JMP

練習 4：變數的位址分配

一支程式依序首次使用變數 count、Count、tmp， 之後再次出現 @count。問四次 @ 各被替換成什麼？ 若程式同時也用了 @R7 與標籤 (LOOP)（位於 ROM 位置 12）， 它們又如何處理？

練習 5：if／else

寫出組語實作： 若 \(RAM[0] > 0\) 則 \(RAM[1] = 1\)，否則 \(RAM[1] = 0\)。

@R0
D=M
@POS
D;JGT      // RAM[0] > 0 -> 跳去 POS
// else 分支
@R1
M=0
@END
0;JMP      // 跳過 then 分支！
(POS)
@R1
M=1
(END)
@END
0;JMP

練習 6：迴圈——乘法

Hack 沒有乘法指令！用重複加法寫出 \(RAM[2] = RAM[0] \times RAM[1]\) （假設 \(RAM[1] \geq 0\)）。

// RAM[2] = 0; i = RAM[1]
@R2
M=0
@R1
D=M
@i
M=D
(LOOP)
// if i == 0, goto END
@i
D=M
@END
D;JEQ
// RAM[2] += RAM[0]
@R0
D=M
@R2
M=M+D
// i--
@i
M=M-1
@LOOP
0;JMP
(END)
@END
0;JMP

練習 7：為什麼 A=A+D;JMP 未定義？

解釋此指令的問題，並給出安全的等價寫法（跳到 \(A + D\)）。

A=A+D     // 先更新 A（這條不跳）
0;JMP     // 再無條件跳到（新的）A

練習 8：跳躍條件判讀

設 \(D = -3\)。下列指令各會不會跳？ D;JGT、D;JLE、D;JNE、D;JEQ、 D+1;JLT、0;JMP。

練習 9：螢幕位址計算

(a) 求第 \(r = 100\) 列、第 \(c = 200\) 行像素對應的 RAM 位址與位元編號。 (b) 若要把該像素塗黑但不動同字的其他 15 個像素， 該怎麼做（文字說明即可）？

@256
D=A        // D = 遮罩 0000000100000000
@19596
M=D|M      // 只把第 8 位設 1，其他位不變

練習 10：15 位元的限制

(a) 為什麼 @65535 無法把 0xFFFF 載入 \(A\)？ (b) 給出兩種把 0xFFFF 放進 \(RAM[\texttt{SCREEN}]\) 的寫法。 (c) 想載入 \(40000\)（超過 15 位元範圍的正數）該怎麼辦？

@SCREEN
M=-1       // 2 的補數 -1 = 全 1 = 0xFFFF

@0
D=!A       // D = NOT 0 = 0xFFFF
@SCREEN
M=D

@20000
D=A
@20000
D=D+A      // D = 40000（以 2 的補數位元圖樣存在）

練習 11：等待按鍵

寫一段組語：忙等（busy-wait）直到使用者按下任意鍵， 然後把按鍵代碼存入 \(RAM[0]\)。 再改成：等待使用者按下「空白鍵」（代碼 32）才繼續。

(WAIT)
@KBD
D=M
@WAIT
D;JEQ      // KBD == 0（沒按鍵）就繼續等
@R0
M=D        // 存下按鍵代碼

(WAIT)
@KBD
D=M
@32
D=D-A      // D = KBD - 32
@WAIT
D;JNE      // 不是空白鍵（差值非 0）就繼續等

練習 12：觀念題——圖靈完備

(a) 敘述 Church–Turing 論題與「圖靈完備」的意義。 (b) Hack 少了跳躍指令還會是圖靈完備的嗎？為什麼？ (c) 停機問題告訴我們什麼？ (d) 嚴格來說，真實的 Hack 電腦是圖靈完備的嗎？

附錄：速查表

Hack 組語速查

dest（按 \(A\)、\(M\)、\(D\) 順序）： M、D、MD、A、AM、 AD、AMD。

comp 可用運算： 0、1、-1； D、A、M； !D、!A、!M； -D、-A、-M； D+1、A+1、M+1； D-1、A-1、M-1； D+A、D+M；D-A、D-M； A-D、M-D； D&A、D&M；D|A、D|M。

jump：JGT（\(>0\)）、JEQ（\(=0\)）、 JGE（\(\geq 0\)）、JLT（\(<0\)）、 JNE（\(\neq 0\)）、JLE（\(\leq 0\)）、JMP（永遠）。

延伸補充：機器碼格式（下週預告）

• A-指令：0vvvvvvvvvvvvvvv—— 第一位 0，後 15 位是數值。

• C-指令：111a cccccc ddd jjj—— 固定前綴 111； a 位選擇 ALU 第二運算元用 \(A\) 還是 \(M\)； 6 個 c 位是 ALU 控制位（第二週的 zx/nx/zy/ny/f/no！）； 3 個 d 位指定目的地 \(A\)/\(D\)/\(M\)； 3 個 j 位編碼跳躍條件。

這解釋了語法限制的硬體根源： comp 表就是 ALU 控制位能編出的函數集； dest 恰好 3 位對應 3 個暫存器；jump 恰好 3 位對應 \(<, =, >\) 三個旗標的組合。

預定義符號

記憶體地圖

名詞中英對照

參考資料

• John Lapinskas, The fetch-execute cycle／ Hack assembly I–III（5-1 至 5-4）， COMSM1302, University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems （nand2tetris），Ch. 4（Machine Language）與附錄 5（鍵盤代碼）.

• Edsger W. Dijkstra, Go To Statement Considered Harmful, Communications of the ACM, 1968.

• Wikipedia：Hack computer、EDSAC、 Turing machine、Church–Turing thesis、 Halting problem.

• Randall Munroe, xkcd #292 goto（迅猛龍漫畫）.