如何使用 Python 編寫 Lisp 解釋器
如何使用 Python 編寫 Lisp 解釋器
實作一個 Lisp 解釋器是理解電腦與編譯器運作原理的主要方法。Peter Norvig 的 "Lispy" 專案展示了 Scheme 方言的 Lisp 功能子集可以用大約 117 行 Python 3 程式碼來實作，證明了「世界上最強大的語言」可以用極少量的原始碼來定義。
語言解釋器的架構
語言解釋器由兩個主要組件組成：解析（parsing）與執行（execution）。其流程遵循線性管線：Program $\rightarrow$ Parse $\rightarrow$ Abstract Syntax Tree (AST) $\rightarrow$ Eval $\rightarrow$ Result。
解析 (Parsing)
解析將字元序列轉換為內部表示法，通常是抽象語法樹（Abstract Syntax Tree, AST）。在 Lispy 中，這被分為兩個階段：
- 詞法分析 (Lexical Analysis/Tokenization)： 將輸入字串拆解為 token（括號、符號與數字）。Lispy 透過在括號周圍添加空格並使用 Python 的
str.split來達成此目的。 - 語法分析 (Syntactic Analysis)： 將 token 組裝成嵌套列表結構。
read_from_tokens函數會在遇到左括號時遞迴地建立列表，並將非括號的 token 視為原子（整數、浮點數或符號）。
執行 (Execution/Evaluation)
執行會根據語言的語義規則處理 AST。在 Lispy 中，eval 函數根據表達式的類型來決定其值：
- Symbols： 在目前的環境中查找。
- Numbers： 評估為其自身。
- Special Forms： 像
if和define這樣的關鍵字會觸發特定邏輯（例如：條件分支或變數賦值）。 - Procedure Calls： 評估運算元與參數，並將得到的程序應用於參數值。
實作 Lispy 計算器
解釋器的第一個迭代版本「Lispy 計算器」支援五種基本的語法形式：
| Expression | Syntax | Semantics |
|---|---|---|
| Variable Reference | symbol |
回傳變數的值。 |
| Constant Literal | number |
回傳數字本身。 |
| Conditional | (if test conseq alt) |
若 test 為真，則回傳 conseq，否則回傳 alt。 |
| Definition | (define symbol exp) |
將 exp 的值綁定到 symbol。 |
| Procedure Call | (proc arg...) |
評估 proc 與 args，然後套用該程序。 |
擴展至完整的 Lispy：程序與詞法作用域
為了從計算器轉向接近完整的 Scheme 子集，Lispy 引入了 quote、set! 與 lambda。lambda 的加入需要透過環境（environments）來進行複雜的變數管理。
Env 類別與詞法作用域 (Lexical Scoping)
為了支援局部變數與嵌套函數，環境被重新定義為一個繼承自 dict 的類別。每個 Env 實例都包含其自身的局部映射與對 outer 環境的引用。
當引用變數時，解釋器會使用 find 方法先搜尋最內層的環境；若找不到該變數，則會遞迴地搜尋外部環境。這種機制實現了詞法作用域 (lexical scoping)，確保程序引用的是其定義時所在的環境中的變數，而非呼叫時所在的環境。
程序實作
一個 Procedure 物件會儲存參數名稱、函數主體以及其建立時所在的環境。當被呼叫時，它會建立一個新的 Env，將提供的參數綁定到參數名稱上，並將該程序的原始環境設定為外部作用域。
性能與完整性
Lispy 的設計目的是為了教學清晰度，而非生產環境使用。其特性包括：
- 規模： 極其精簡，由大約 117 行非空白行與 4KB 的原始碼組成。
- 速度： 能夠在約 0.003 秒內計算出
(fact 100)。 - 限制： 它缺乏幾種標準的 Scheme 特性，包括尾呼叫優化 (tail-call optimization)、
call/cc、字串、字元、布林值以及全面的錯誤恢復機制。
社群見解
開發者與教育者將實作 Lisp 解釋器視為計算機科學的基礎練習。如討論中所述：
"如果妳曾經好奇如何編寫一種程式語言，這或許是最好的入門資源。"
其他貢獻者強調了 Lisp 的樹狀結構與語言學家用於標註句子結構的短語結構語法（phrase structure grammars）之間的同構性。有些人也指出，雖然 AI 現在可以生成此類程式碼，但實作解釋器的過程對程式設計師而言仍是一次「啟發性的體驗」。