本週目標

本週我們要擴充 Hack VM，加入：

• 函式呼叫；

• 正式的編譯期記憶體配置（與函式呼叫同時解決！）；

• 多檔案編譯以支援函式庫（相較之下容易）。

我們也會討論執行期記憶體配置（即 malloc）。 下週就進入高階語言——Jack。

函式應有的行為：案例研究

回想 Programming in C 那個（糟糕的！）遞迴費波那契演算法： \[F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1} + F_{n-2},\] \[\mathrm{fib}(n) = \begin{cases} 0 & \text{若 } n = 0,\\ 1 & \text{若 } n = 1,\\ \mathrm{fib}(n-1) + \mathrm{fib}(n-2) & \text{若 } n \geq 2. \end{cases}\] 投影片的實作加了兩個 static 變數： times_called（總呼叫次數）與 layers_deep（目前遞迴深度），用來觀察函式呼叫的行為。

多檔案編譯

VM 翻譯器收到一個資料夾時，應該：

• 把資料夾內所有 .vm 檔翻譯成一個組語檔；

• 所有 VM 程式碼都必須在函式內；

• 編譯出的程式先照常把 SP 設為 256， 然後呼叫 Sys.vm 裡的函式 Sys.init ——類比 C 的 main（Sys.init 由測試碼提供， 因此各檔案的翻譯順序無關緊要）；

• 檔案 abc.vm 內所有函式的名稱必須以 「abc.」開頭（如 abc.print）—— 防止檔案間名稱衝突；Jack 編譯器會強制執行： 檔案 abc 中名為 xyz 的 Jack 函式 編譯成 VM 函式 abc.xyz；

• 不同檔案中相同的 static 位址或標籤必須編譯到 不同位址——你的 VM 翻譯器已經做到了 （Foo.vm 的 static 5 \(\to\) 組語變數 Foo.5，上週的伏筆在此回收！）。

Jack 與「作業系統」

Jack 附帶 nand2tetris 樂觀地稱為「作業系統」的東西—— 實際上是八個用 Jack 寫的標準函式庫。 （平心而論，OS 的核心就是這個：在此基礎上擴充 Sys 函式庫、 把行程視為函式呼叫，就能蓋出 DOS 那樣的單行程 OS。）

下週寫 Jack 編譯器時會拿到這些函式庫的 Hack VM 版本。 細節見 Nisan and Schocken 附錄 6。皆不列入考試！

自舉（Bootstrapping）

nand2tetris 中這些函式庫其實都是用 Jack 寫的。 用 Jack 程式碼寫 Jack 編譯器是「作弊」嗎？不是！ 讓編譯器能編譯自己叫做自舉，標準做法是：

1. 寫一個暫代的 Jack-to-Hack 編譯器 A—— 直接用 Hack VM／組語寫，或用完全不同的系統寫 （例如在 x86-64 上用 C 寫，即交叉編譯）；

2. 用 Jack 本身寫一個品質更好的編譯器 B；

3. 用 A 把 B 編譯成 Hack 機器碼；

4. 用 B 重新編譯 B 自己；

5. 把 A 扔掉，從此使用 B。

即使不交叉編譯，目標也是盡量少寫低階程式碼。 「OS」函式大多直截了當，除了 Memory.vm 沒有新的架構概念——但想練組語／VM 的話它們是好習題！

一般的函式實作：呼叫框架（Frames）

本章討論任何語言（例如 C）如何實作函式， 下一章再回到 Hack VM 的具體做法。

四個子目標

堆疊無所不在

在任何語言、（幾乎）任何架構上，達成這些目標的最佳方式 都用堆疊。Hack 的特殊之處在於堆疊只存在於 VM 層、不存在於組語層。這很不尋常！ARM 與 x86-64 都有：

• 擔任堆疊指標 SP 角色的暫存器（如 ESP）；

• push／pop 組語指令；

• call、ret、enter、leave 指令，直接完成本章討論的大部分工作。

所以這些操作在 Hack 組語又慢又笨重 （一句 push local 5 展開成十多條指令）， 在現代 CPU 上卻非常快。 （MIPS 沒有原生 push/pop，但有 jal 與 jr 指令分擔函式呼叫的大部分負擔。）

目標 1：程式流程

假設我們有堆疊可用。

• 呼叫時：把返回位址推上堆疊， 然後跳到函式開頭；

• 返回時：從堆疊彈出返回位址，跳過去。

要跳去哪裡的位址怎麼知道？交給組譯器！ 標籤是任何組語都有的功能，這問題它們早就解決了。

// main 的程式碼
@label0
[把位址 (label0) 推上堆疊]
[跳到 (foo)]
(label0)
// 停機

(foo)
@label1
[把位址 (label1) 推上堆疊]
[跳到 (bar)]
(label1)
// 更多程式碼
[彈出返回位址並跳過去]

(bar) ... (baz) ...   // 同樣模式

目標 2：記憶體配置

在 C 中，每一個變數的大小都能在編譯期算出。 看起來長度在執行期才決定的東西（字串、陣列）其實是 指標——永遠 64 位元長。它們指向的記憶體 要嘛編譯期就固定大小（char *out = "Hello world!";、 int myArray[100];）， 要嘛由程式設計師用 malloc／free 明確配置。

因此，一個在語意分析階段（即解析之後）為函式的區域變數 建符號表的 C 編譯器，會提前確切知道每次呼叫 該函式要配多少空間。引數同理。所以編譯器需要：

• 每次函式被呼叫時，為已知數量、已知大小的 local／argument 變數找空間；

• 實作 malloc 與 free——這種記憶體 與函式呼叫無關，不需額外處理（見第 4 章！）。

合併目標 2 與 3：用堆疊配置一切

假設呼叫函式 \(f\) 需要 10 個字的區域變數、7 個字的引數、 5 個字的狀態（含相關暫存器與返回位址）， 這些資訊存在符號表裡。

投影片以 main \(\to\) threemin \(\to\) min 的 C 程式為例（求三數最小值）： 編譯器為每個函式存一張符號表 （threemin 的表：引數 a,b,c 位移 0–2、 區域變數 x,y,z 位移 3–5）， 執行時堆疊隨呼叫長高（main 的 x,y,z 在底部， 每次呼叫疊上「引數＋舊狀態」），隨返回縮回—— SP 與 OSP 一路記錄了「目前這層」的範圍。 注意這只是 C 函式呼叫的一種可能實作； 實際的編譯器會為了最佳化把堆疊排得稍有不同 （甚至把整個函式呼叫最佳化掉）。

術語

目標 4：static 變數

這個簡單——給每個 static 變數一塊獨立於堆疊的記憶體 （Hack VM 就是 static 段），用符號表記錄對應關係， 然後在呼叫／返回流程中別去動它。 同理，堆疊上的工作儲存（算術暫存值）也不需特別處理—— 呼叫時自然保留、返回時自然恢復。

非 C 語言表面上常模糊堆疊與堆積的界線 （允許變長陣列、自動釋放記憶體）， 但底層運作大致與 C 相同——一些變數放堆疊、 另一些放堆積，並呼叫 malloc／free 的類似物。

Hack VM 的函式：語法與實作

函式語法

上一章重度依賴語意分析階段建立的符號表。 Hack VM 的語法設計完全避開了符號表的需要！

從呼叫者的角度看，call 就像一個「吃掉 \(x\) 個值、 吐回一個值」的超級運算子——與 add 吃 2 吐 1 同構。 這讓函式呼叫能無縫嵌進運算式編譯（RPN）中。

實作 call：搭建新框架

假設 VM 翻譯器看到 call myFunc 2 （呼叫前，堆疊頂已有兩個引數值）。產生的組語必須依序：

1. 產生一個返回標籤（例如 auto$57， 不可與其他標籤衝突），把該位址推上堆疊， 供之後的 return 跳回；

2. 把 LCL、ARG、THIS、THAT 推上堆疊，保存目前的值；

3. 把 ARG 設到（舊）堆疊頂往下數 2 個值的位置—— 那兩個引數原地變成新函式的 argument 段；

4. 把 LCL 設為新的堆疊頂—— 這將是新函式 local 段的起點；

5. 跳到函式標籤（由 function 定義處產生）。

注意步驟 1 推返回位址時還不必更新 SP （之後一起做更容易）。

實作 function：接手

VM 翻譯器看到 function myFunc 3 時，產生的組語必須：

1. 以一個標籤開頭，每次呼叫都跳到這裡。 為免使用符號表，這個標籤必須只從函式名就能導出 （這樣 call 端也能生成同一個標籤）；

2. 把 SP 設為 \(\texttt{LCL} + 3\) （local 段長度來自 function 指令）；

3. 把 local 0、local 1、local 2 初始化為零；

4. 繼續執行函式本體的第一行。

實作 return：拆除框架

函式執行到 return 時，堆疊頂是返回值， 下面可能還有工作堆疊殘值、local 段、呼叫框架、argument 段。 產生的組語必須：

1. 把返回位址暫存起來（例如存到 R13） ——它在 \(RAM[\texttt{LCL} - 5]\)；

2. 把返回值複製到新工作堆疊的位置， 即目前 ARG 指的位址—— 覆寫 argument 0，返回值恰好出現在 呼叫者期望的堆疊頂；

3. 把 SP 設為 \(\texttt{ARG} + 1\) （新工作堆疊的頂端再上一格）；

4. 從目前 LCL 往下數， 依序恢復舊的 THAT（\(\texttt{LCL}-1\)）、 THIS（\(\texttt{LCL}-2\)）、 ARG（\(\texttt{LCL}-3\)）、 LCL（\(\texttt{LCL}-4\)）；

5. 跳到返回位址——SP 以上的一切等同被丟棄。

妙處：這段程式碼從頭到尾不需要知道 呼叫的是哪個函式、從哪裡呼叫的！ 一切資訊都藏在堆疊上相對於 LCL、ARG 的固定位置。 這正是遞迴「免費」成立的原因—— 每一層呼叫的框架結構完全相同，機器只是機械地搭建與拆除。

初始化

程式一開始 LCL 和 ARG 怎麼設？ 記住多檔案 Hack VM 程式以呼叫 Sys.init 開始—— 呼叫之前它們的值根本不重要， 呼叫之後它們就照一般機制被正確設定了。 官方 Sys.init 的預設行為： 呼叫其他函式庫的初始化函式 \(\to\) 呼叫 Main.main （編譯自 Jack 時它就是 C 的 main 的對應物）\(\to\) 進入無窮迴圈。

堆積記憶體配置：malloc 與 free

兩個關鍵函式

堆疊配置威力強大，但只適用於編譯期已知大小的變數。 要以 C 的方式處理執行期記憶體配置，需要寫兩個函式 （C 叫 malloc／free， Jack 叫 Memory.alloc／Memory.deAlloc）：

以下用高階語言的視角逐步檢視四個漸進改良的演算法， 著重演算法本身而非程式碼。

嘗試 1：只進不出（bump allocator）

• \(RAM[\texttt{0x800}]\) 存一個指標， 指向第一個未配置的位址；

• alloc(size)：回傳 \(RAM[\texttt{0x800}]\)， 然後把它加上 size；

• deAlloc：什麼都不做。

這是 Nisan and Schocken 12.1.3 的「basic」演算法。 問題顯而易見：記憶體永遠不會回收—— 長時間執行的程式遲早耗盡堆積。 但它極快（一次加法），實務上真的用於 生命週期短暫的場合（如編譯器單趟處理的 arena allocator）。

嘗試 2：把資訊存進段裡（單向自由串列）

我們顯然需要記錄「有哪些自由／已用的段、多長」。 但那是一個大小未知的串列……這不正是我們要解決的問題嗎？ 點子：把這些資訊存在段自己裡面！

投影片追蹤了一長串 alloc／deAlloc： 從一整塊 0x37FE 字的自由段開始， 三次 alloc(0xDFF) 依序切出三段， 釋放再配置時 first-fit 會重用夠大的自由段並再切割。 一切運作正常……直到出現這個場景：

致命問題：相鄰的兩個自由段永遠不會合併。 釋放兩個相鄰的 0x6FF 字段之後， 串列裡有兩個相鄰的小自由段—— 但 alloc(0xE00) 仍然失敗， 儘管總自由空間綽綽有餘！段一旦被切小，就永遠回不去。

嘗試 3：釋放時合併（coalescing）

我們想在釋放時把段與記憶體上相鄰的自由段合併 （這個過程叫合併／聚結（coalescing））。 但自由串列不是照位址排序的，順著串列找鄰居太慢—— 需要存更多資訊讓它變快。

現在釋放兩個相鄰段時它們自動合併回大段， 嘗試 2 的問題解決了。

碎片化（Fragmentation）

即便有合併，錯誤順序的 alloc／deAlloc 仍會出問題： 配置一大堆小段、再隨機釋放其中一半，就會得到 「自由、已用、自由、已用……」相間的棋盤格局—— 一半的記憶體是自由的，卻連稍大一點的段都配不出來！ 這個問題叫碎片化，同時影響記憶體與檔案系統。

某種意義上有個簡單解法：把每個已用段按位址遞增順序 deAlloc 再重新 alloc，順便把資料搬到新位置。 用演算法 3 或 4，最後自由空間必然合併成一段。 這叫重組（defragmentation），慢一點但保證有效。

alloc 內部能做的，是靠慎選回傳值來延緩碎片化：

• first-fit（目前用的）：回傳第一個夠大的 自由段。快，但容易碎片化。

• best-fit：掃過整條自由串列， 回傳大小最接近需求的段。碎片化較少，但非常慢。

能不能讓 best-fit（或接近它的東西）變快？

嘗試 4：分箱（Bins）

不存一條自由段的雙向串列，而是存十條，稱為箱！

想更講究，可以把雙向串列換成平衡二元搜尋樹 （如 2-3-4 樹），快速選出 best-fit 的段！ （現代的 malloc 實作確實會把箱排序——值得這個負擔……）

綜合練習題（附詳解）

練習 1：呼叫時的堆疊

執行 call f 2 前，\(SP = 310\)（堆疊頂兩個值是引數）。 (a) call 的組語做完五個步驟後，\(SP\)、\(ARG\)、\(LCL\) 各是多少？ (b) 接著執行 function f 4 之後 \(SP\) 是多少？

練習 2：返回時的堆疊

延續練習 1：函式執行完，堆疊頂（\(RAM[SP-1]\)，設 \(SP = 320\)） 是返回值 99。寫出 return 的每一步對 \(SP\)、\(ARG\)、\(LCL\) 與相關 RAM 的影響。

練習 3：寫一個 VM 函式

Hack VM 沒有乘法指令。寫函式 Math.mult， 接收兩個引數 \(a\)、\(b\)（\(b \geq 0\)），用重複加法回傳 \(a \times b\)。 提示：local 0 當累加器、local 1 當計數器。

function Math.mult 2      // local 0 = 累加, local 1 = 計數
label LOOP
push local 1
push argument 1
lt                        // 計數 < b ?
not
if-goto END               // 否則離開
push local 0
push argument 0
add
pop local 0               // 累加 += a
push local 1
push constant 1
add
pop local 1               // 計數++
goto LOOP
label END
push local 0              // 返回值上堆疊
return

練習 4：遞迴為什麼可行

(a) return 的組語裡，哪些資訊讓它不需要知道 「我是誰、誰呼叫我」？ (b) 遞迴呼叫 fib(4) 時（fib 定義同 1.2 節）， 最深時全域堆疊上同時有幾個 fib 的呼叫框架？

練習 5：多檔案規則

(a) 為什麼 Foo.vm 與 Bar.vm 裡的 static 0 必須映射到不同 RAM 位址？ (b) 為什麼所有函式名必須帶檔名前綴？ (c) 為什麼從 Sys.init 開始執行讓「檔案翻譯順序無關」？

練習 6：局部變數為何清零

(a) Hack VM 規定 function 要把 local 段清零， 講師推測的理由是什麼？ (b) C 不清零區域變數。寫出一段 C 程式， 其行為因此不可預測。

int f(void) {
    int x;          // 未初始化：值 = 堆疊上的殘留垃圾
    return x + 1;   // 未定義行為
}

練習 7：嘗試 1 與嘗試 2

堆積為 \(RAM[\texttt{0x800}]\)–\(RAM[\texttt{0x3FFF}]\)。 (a) 用嘗試 1：初始指標 0x800，依序執行 alloc(0x100)、alloc(0x200)、 deAlloc(0x800)、alloc(0x100)。 寫出每次的回傳值與指標變化。 (b) 用嘗試 2（負擔 1 字）：初始一整塊自由段在 0x800（可用大小 0x37FE）。 執行 alloc(0x100) 後，自由串列長什麼樣？

練習 8：嘗試 2 的致命缺陷

用嘗試 2，堆積中相鄰兩段： \(A\)（基底 0x800，可用 0x6FF）與 \(B\)（基底 0xF00，可用 0x6FF），兩者都已配置， 其餘記憶體都已用完。依序執行 deAlloc(A)、deAlloc(B)、alloc(0x800)。 結果如何？為什麼？

練習 9：嘗試 3 的合併

用嘗試 3（負擔 3 字：首 size、狀態、尾 size； 自由段另用第三、四字存 next/prev）。 記憶體中依序有三段：\(P\)（已用）、\(Q\)（已用）、\(R\)（自由）。 現在呼叫 deAlloc(Q)。 (a) 演算法如何找到 \(P\) 與 \(R\)？ (b) 合併後自由串列發生什麼事？ (c) 為什麼自由串列要雙向？

練習 10：碎片化

堆積共 0x1000 字（忽略負擔）。程式配置了 16 段、 每段 0x100 字，然後釋放第 1、3、5、…、15 段 （隔一個放一個）。 (a) 現在自由空間共多少？最大的單次 alloc 能要多少？ (b) 為什麼「重組」能解決卻不能由 deAlloc 自動執行？ (c) first-fit 與 best-fit 在這個格局下有差別嗎？

練習 11：分箱

用嘗試 4 的箱配置（4.6 節的範圍表）。 (a) 可用大小 0x30 的自由段屬於哪個箱？ (b) alloc(0x20) 從哪個箱開始掃？若空手而歸，下一步？ (c) 分箱如何同時逼近 first-fit 的速度與 best-fit 的品質？

練習 12：綜合追蹤

下列 VM 程式從 Sys.init 開始執行 （bootstrap 已設 \(SP = 256\)）：

function Sys.init 0
push constant 6
push constant 7
call Foo.addOne 2
label HALT
goto HALT

function Foo.addOne 1
push argument 0
push argument 1
add
push constant 1
add
return

(a) call Sys.init 完成、進入 Sys.init 本體時 \(SP\)、\(LCL\)、\(ARG\) 是多少？ (b) Foo.addOne 的 return 執行後， 堆疊頂是什麼值、\(SP\) 是多少？

附錄：速查表

函式指令總表

call／function／return 的實作配方

框架內相對 LCL 的位置： \(LCL-1\) 舊 THAT、\(LCL-2\) 舊 THIS、\(LCL-3\) 舊 ARG、 \(LCL-4\) 舊 LCL、\(LCL-5\) 返回位址。

四種堆積配置演算法對照

名詞中英對照

參考資料

• John Lapinskas, Extending Hack VM／ Functions in general／ Functions in Hack VM: Syntax and implementation／ Heap memory allocation: malloc and free（10-1 至 10-4）， COMSM1302, University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems （nand2tetris），Ch. 8（Virtual Machine II）、 Ch. 12.1（Memory Management）、附錄 6.

• System V Application Binary Interface, AMD64 Architecture Processor Supplement（x86-64 呼叫慣例、紅區）.

• Doug Lea, A Memory Allocator（dlmalloc 設計文件： 邊界標記、128 個箱、立即合併）.

• Eli Bendersky, Stack frame layout on x86-64 （框架指標省略與紅區的實務討論）.