3.1 1958：LISP 與樹行走的直譯器#

直譯器的誕生：一個 `eval` 函式#

1958 年底，Steve Russell 根據 John McCarthy 的論文手寫出了第一個 LISP eval——原本 McCarthy 只把 eval 當作語意的數學定義（「這就是 LISP 程式執行時的樣子」），Russell 說「這段數學可以直接編譯成 IBM 704 的機器碼」，於是世界上第一個直譯器誕生了。

這段歷史揭示了直譯器的本質：直譯器就是「把語言的語意規則直接翻譯成程式碼」。樹直譯器（tree-walking interpreter）不做任何預先轉換，直接在 AST 上遞迴求值。

graph LR
    A[原始碼] --> P[解析]
    P --> T[AST]
    T --> E[eval 遞迴<br/>每執行一次都重新走樹]
    E --> R[結果]

為什麼 LISP 選直譯#

回頭看 1958 年的約束條件，直譯幾乎是必然：

動態型別：變數可以一會兒裝數字一會兒裝列表，靜態編譯（當時的技術）無法為每個變數定死型別與 slot
程式即資料：eval(quote(...)) 要能吃任意執行期構造的程式，編譯好的機器碼做不到
GC 與 cons cell：LISP 的核心資料結構是鏈結串列，需要 GC，而 GC 需要「執行時知道每個值的型別」的標籤機制——直譯器的執行時環境天然提供這些
硬體太弱：當時編譯器技術剛剛萌芽（FORTRAN 才剛證明可行），為動態語言寫編譯器的難度不可想像

代價是每次執行都重新走樹：eval 每碰到一個 Expr::Add 都要 match enum、遞迴、查環境。同樣的程式跑一百次就重複一百次所有「解析」已完成的工作。這個效能瓶頸正是後來位元碼（3.3 節）與 JIT（第 4 章）被發明的直接原因。

MinLang 的完整樹直譯器#

在第 1.3 節骨架的基礎上，把函式、閉包與控制流補齊。先處理「值」的表示——動態語言的第一個設計決策：

// src/value.rs
use std::rc::Rc;

#[derive(Clone)]
pub enum Value {
    Num(i64),
    Bool(bool),
    Fn(Rc<Lambda>),
}

pub struct Lambda {
    pub params: Vec<String>,
    pub body: Expr,
    pub env: Env,          // 閉包捕獲的環境（3.2 節詳解）
}

impl Value {
    pub fn as_num(&self) -> Result<i64, String> {
        match self {
            Value::Num(n) => Ok(*n),
            other => Err(format!("expected number, got {other:?}")),
        }
    }
}

LISP 的做法是每個值帶型別標籤（IBM 704 上 car/cdr 指令操作的字就內含型別位元）；Rust 的 enum 自動做同樣的事——discriminant 就是型別標籤，match 就是帶型別檢查的解包。C 語言直譯器要手動維護 tag+union（忘記檢查 tag 就讀到垃圾），Rust 編譯器強迫你 match 完備。

eval：語意規則的逐條翻譯#

// src/interp.rs
use crate::ast::{BinOp, Expr};
use crate::value::{Lambda, Value};
use std::collections::HashMap;
use std::rc::Rc;

pub type Env = Rc<HashMap<String, Value>>;

pub fn eval(expr: &Expr, env: &Env) -> Result<Value, String> {
    match expr {
        Expr::Num(n) => Ok(Value::Num(*n)),
        Expr::Var(name) => env.get(name).cloned()
            .ok_or_else(|| format!("undefined variable: {name}")),

        Expr::BinOp { op, lhs, rhs } => {
            let l = eval(lhs, env)?.as_num()?;
            let r = eval(rhs, env)?.as_num()?;
            Ok(Value::Num(apply(*op, l, r)?))
        }

        Expr::Let { name, value, body } => {
            let v = eval(value, env)?;
            let mut new_env = (**env).clone();   // 擴充環境
            new_env.insert(name.clone(), v);
            eval(body, &Rc::new(new_env))
        }

        Expr::If { cond, then_e, else_e } => {
            match eval(cond, env)? {
                Value::Bool(true) => eval(then_e, env),
                Value::Bool(false) => eval(else_e, env),
                other => Err(format!("condition must be bool, got {other:?}")),
            }
        }

        Expr::Call { func, args } => {
            let f = eval(&Expr::Var(func.clone()), env)?;
            let f = match f { Value::Fn(f) => f, other => return Err(format!("not callable: {other:?}")) };
            let mut vals = Vec::with_capacity(args.len());
            for a in args { vals.push(eval(a, env)?); }
            call(&f, vals)
        }
    }
}

pub fn call(f: &Rc<Lambda>, args: Vec<Value>) -> Result<Value, String> {
    if args.len() != f.params.len() {
        return Err(format!("expected {} args, got {}", f.params.len(), args.len()));
    }
    let mut env: HashMap<String, Value> = (**f.env).clone();
    for (p, v) in f.params.iter().zip(args) {
        env.insert(p.clone(), v);
    }
    eval(&f.body, &Rc::new(env))
}

fn apply(op: BinOp, l: i64, r: i64) -> Result<i64, String> {
    match op {
        BinOp::Add => Ok(l.wrapping_add(r)),
        BinOp::Sub => Ok(l.wrapping_sub(r)),
        BinOp::Mul => Ok(l.wrapping_mul(r)),
        BinOp::Div if r == 0 => Err("division by zero".into()),
        BinOp::Div => Ok(l / r),
        BinOp::Lt => Ok(((l < r) as i64).into()),
        BinOp::Eq => Ok(((l == r) as i64).into()),
    }
}

這 60 行就是直譯器的全部。每一個 match 臂對應一條語意規則——McCarthy 論文裡 LISP 的 eval 規則與此一一對應，這不是巧合：Rust 的 pattern matching 就是用來寫語意的。

效能分析：為什麼樹直譯慢#

寫個測量程式，跑一個 1000 次迭代的迴圈模擬：

// sum = 0; i = 0; 迴圈 1000 次 sum += i（用遞迴模擬，MinLang 暫無 while）
// let loop = fn(n, acc) { if n == 0 { acc } else { loop(n - 1, acc + n) } };
// loop(1000, 0)

在樹直譯器上，每一次 n - 1 的執行都要：

match Expr::BinOp（enum discriminant 檢查）
遞迴 eval 左右子樹（函式呼叫開銷，非尾呼叫）
對 Expr::Var 再查 HashMap（字串 hash + 比較）
(**env).clone() 複製整個環境 map

第 3、4 點是大頭：CPython 慢的最大原因之一就是每一次變數存取都是字典查詢。歷代解法：

解法	年代	原理	本書位置
環境鏈 + frame 指標	1960s-	避免複製 map，用鏈結串列查詢	3.2 節
名字 → slot 索引	1966 BCPL	前端解析一次名字，執行期用整數索引	3.3 節
內聯快取	1984 Smalltalk	快取「上次這個名字查到的位置」	第 4 章
JIT 熱點編譯	1989-	直接編掉直譯迴圈	第 4 章

直譯器的價值：啟動快、可互動#

慢不是直譯器的全部——它也有編譯器給不了的東西：

即時性：輸入一行立即執行（REPL 的基礎），不需要等到整個程式編完
可檢查性：執行到一半可以中斷、檢視環境、單步——直譯器的一切狀態（AST、env、PC）都是普通資料結構
可移植性：只要 Rust 編譯得到的地方，直譯器就能跑，不需要平台後端

CPython、Ruby、Shell、瀏覽器初期 JS 引擎都停在這個模式。它們後來的演化路徑（→ 位元碼 → VM → JIT）會在第 3.3、4、5 章逐段實作。

習題#

把 Let 的 (**env).clone() 改成「每層只存一個綁定的環境鏈」，寫測試比較兩者在深層巢狀下的效能。
為什麼 If 的條件必須是 Bool 而不能接受任何值？LISP 的慣例（0 與 nil 為假）會讓實作簡化還是複雜化？
設計一個故意讓樹直譯器指數變慢的 MinLang 程式（提示：重複遞迴同一子運算式，如 naive fib）。