跳轉到

2.1 堆疊機架構與指令集（Pascal P-code 1970年代）#

為什麼是堆疊？#

在虛擬機 ISA 的設計光譜上，最古老的選擇是堆疊式架構：運算元不放在暫存器，而是放在一個運算堆疊（operand stack）上，所有指令隱含地從堆疊頂端取運算元、把結果推回堆疊。這個選擇有深刻的歷史與工程理由：

  1. 指令編碼極小：指令不需要運算元欄位，IADD 一個位元組就夠了。在 1960-70 年代，記憶體與傳輸頻寬極其昂貴，程式碼體積直接影響成本。
  2. 編譯器產生碼容易：表達式求值的後序遍歷天然對應堆疊指令序列，編譯器前端不需要做暫存器配置（register allocation）這個困難的最佳化就能產生正確程式碼。
  3. 實作簡單：虛擬機的直譯器只需維護一個堆疊指標，指令語義極為規律。

堆疊機的理論根源可追溯到 1960 年代的 Burroughs B5000（硬體堆疊機）與捕獲式遞迴語言學的後綴表示法（波蘭表示法的變體）。而把它變成「虛擬機」而非硬體的關鍵人物是 Niklaus Wirth 與他的學生：蘇黎世聯邦理工學院（ETH Zürich）在 1973-1975 年間發展出 Pascal-P 編譯器（Urs Ammann 等人實作），其目標語言 P-code 便是一個堆疊式虛擬機的指令集。Wirth 的動機是 Pascal 的推廣：與其為 IBM 370、CDC 6000、PDP-11 各寫一個後端，不如只寫一個 P-code 產生器，再讓每個平台移植一個小直譯器（P-code 直譯器只有幾千行 Pascal）。這個「自舉移植法」——用 P-code 版編譯器在目標機上重建原生編譯器——讓 Pascal 在 1970 年代後期以驚人的速度散布到全球大學，也直接啟發了後來 UCSD Pascal 的 P-System（1978，Apple II 上風行一時）與 1990 年代 Java 的設計。

一個最小堆疊機的指令集#

以下是一個經典的教學堆疊機（源自 Wirth 的 PL/0 與 P-code 傳統）的指令集子集：

指令 語義
LIT n push 常數 n
LOD l,a push 變數（層差 l、位移 a）的值
STO l,a pop 存入變數
OPR op 算術/邏輯/返回運算
CAL l,a 呼叫程序（層差 l、入口 a）
INT n 配置 n 個字的活動記錄
JMP a / JPC a 無條件/條件跳躍

表達式 (a+b)*c 編譯為：

LOD  a      ; push a
LOD  b      ; push b
OPR  2      ; 加法：pop b, pop a, push a+b
LOD  c      ; push c
OPR  4      ; 乘法
STO  t      ; 存入 t

虛擬機實作：直譯器虛擬碼#

堆疊機直譯器的核心是一個 fetch-decode-execute 迴圈。以 Pascal 風格描述（模擬 Wirth 原始設計）：

var pcode: array of Instr;  // 指令陣列
    s: array[1..STACKMAX] of integer;  // 運算堆疊
    pc, sp: integer;

repeat
  instr := pcode[pc]; pc := pc + 1;
  case instr.op of
    LIT: begin sp := sp+1; s[sp] := instr.a end;
    LOD: begin sp := sp+1; s[sp] := base(instr.l) + instr.a 的內容 end;
    STO: begin base(instr.l)+instr.a 的內容 := s[sp]; sp := sp-1 end;
    OPR:
      case instr.a of
        2: begin s[sp-1] := s[sp-1] + s[sp]; sp := sp-1 end;
        4: begin s[sp-1] := s[sp-1] * s[sp]; sp := sp-1 end;
        ...
      end;
    CAL: 儲存返回位址與動態鏈，建立新活動記錄，pc := instr.a;
    INT: sp := sp + instr.a;  // 開活動記錄空間
  end
until 指令為 return;

注意 CAL/INT/OPR 0（返回）共同實作了程序呼叫慣例：每個活動記錄（activation record）含靜態鏈（static link，支援詞法作用域的層差定址）、動態鏈（dynamic link，返回後恢復 sp）、返回位址與區域變數。這正是編譯器教科書中「執行時期環境」一節的具體化——虛擬機與編譯器在此深度耦合：P-code 的指令集形狀直接決定了 Pascal 編譯器可以做什麼樣的作用域與遞迴。

堆疊機的代價與後續演化#

堆疊機的弱點同樣明顯：每個運算都要多一次 push/pop，指令數量遠多於暫存器機；而且堆疊頂端是資料相依的瓶頸，難以做指令層平行優化。測量上，同一段程式堆疊機的動態指令數約為暫存器機的 1.5～2.5 倍（這正是後來 Android 從 Dalvik 轉向、以及 JVM 以 JIT 把堆疊碼先轉成暫存器碼再執行的原因——見 3.1 與 4 章）。但堆疊機犧牲的是「直譯效率」，換到的是位元碼小、驗證容易、實作簡單。歷史的折衷方案非常有趣：JVM 保留堆疊位元碼作為發行格式（小檔案、易驗證），但在 JIT 階段把堆疊碼轉換為 SSA 形式的暫存器碼來優化——堆疊形式成為「分發格式」，而非「執行格式」。這個「分發用堆疊碼、執行用暫存器碼」的分工，是 1970 年代 P-code 的設計者所始料未及的。

小結#

P-code 確立了堆疊式虛擬機的標準配方：小指令編碼、後序表達式編碼、以活動記錄支援程序與詞法作用域、以小型直譯器換取可攜性。它的精神後裔包括 JVM 位元碼、CPython 位元碼與 .NET CIL。理解堆疊機，等於理解了「位元碼 = 一種設計給軟體直譯的中間表示」這個觀念的源頭，也是編譯器課程中目標碼生成與執行時期環境兩章之間的橋樑。