揭開語言實作的神秘面紗：從 7 行 Lambda Calculus 到函數式解釋器

實作一種程式語言通常被視為一項艱鉅的任務，只有編譯器工程師和博士才能勝任。然而，從核心來看，這個過程是對計算本質的理解練習。透過將語言簡化到其絕對核心，我們可以看到數學符號與可運行的解釋器之間的差距其實小得令人驚訝。

本指南探討了基於 lambda calculus 的函數式、圖靈完備語言的實作，並利用了在 Structure and Interpretation of Computer Programs 等經典著作中發現的可擴展 eval/apply 設計模式。

基礎：Lambda Calculus

由 Alonzo Church 在 20 世紀初開發的 lambda calculus 是一個用於表達計算的極簡系統。它並非現代意義上的「程式語言」——它缺乏內建的數字、布林值或 I/O——但它是圖靈完備的。這意味著任何圖靈機可計算的函數都可以用 lambda calculus 表達。

該系統僅依賴三種類型的表達式：

  1. 變數引用 (Variable References)：指向一個值的名稱。
  2. 匿名函數 (Abstractions)：寫作 (λ v . e)，其中 v 是參數，e 是返回的表達式。
  3. 函數調用 (Applications)：寫作 (f e)，其中函數 f 被應用於參數 e。

實現圖靈完備性

在沒有顯式迴圈或遞迴的情況下，如此稀疏的系統如何處理複雜邏輯？lambda calculus 採用了兩種主要的「技巧」：Church encodings（將整數和布林值等數據表示為函數）以及 Y Combinator（在匿名函數中實現遞迴）。

該系統威力的一個顯著例子是「Omega」程式：((λ f . (f f)) (λ f . (f f)))。這個程式永遠不會終止，證明了 lambda calculus 可以表達任何通用語言中常見的無限迴圈。

7 行解釋器

使用 R5RS Scheme，我們可以用僅僅七行程式碼來實作一個 lambda calculus 的指稱性解釋器 (denotational interpreter)。Scheme 在這裡是一個理想的選擇，因為其 read 函數會自動處理詞法分析和將其解析為 s-expressions。

; eval takes an expression and an environment to a value
(define (eval e env) (cond
  ((symbol? e)       (cadr (assq e env)))
  ((eq? (car e) 'λ)  (cons e env))
  (else              (apply (eval (car e) env) (eval (cadr e) env)))))

; apply takes a function and an argument to a value
(define (apply f x) 
  (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))

; read and parse stdin, then evaluate:
(display (eval (read) '())) (newline)

運作原理：Eval/Apply 模式

該架構依賴於兩個相互遞迴的函數：

  • eval：將 Expression 和 Environment 映射到 Value。
  • apply：將一個 Value (函數) 和另一個 Value (參數) 映射到一個新的 Value。

在此實作中，使用了一個 Closure 來「封閉」一個開放項。它將 lambda 表達式與定義其自由變數的環境配對，確保函數無論在何處被調用，都能攜帶其上下文。

擴展規模：構建更豐富的語言

雖然 7 行版本僅是概念驗證，但 eval/apply 模式是可擴展的。透過擴展 eval 函數以處理更多表達式形式，我們可以構建功能更強大的語言。在 Racket 中使用 100 行的實作可以引入：

  • Constants：數字和布林值字面量。
  • Primitive Operations：加法、減法和比較。
  • Control Flow：if 條件判斷和 begin 序列化。
  • Variable Bindings：用於本地綁定的 let 和用於遞迴綁定的 letrec。
  • State：用於變數變異的 set!。

透過將語法設計（程式碼如何編寫）與語義設計（程式碼如何如何被求值）分離，開發者可以透過簡單地構建一個輸出 s-expressions 的解析器來進行實驗，從而讓解釋器處理這些 s-expressions。

技術觀點與評論

實作這些概念通常會引發關於函數式極簡主義實用性的爭論。有些人認為，在 Lisp 類語言中實作 lambda calculus 是本質上「在 Lisp 中實作 Lisp」，這暗示著簡短是因為宿主語言的內在性質，而非目標語言的簡潔性。

然而，其他人指出，這項練習不僅僅是關於程式碼——它關乎於揭開計算的「魔法」神秘面紗。正如一位貢獻者所言：

"Building an ALU with LEDs and logic gates should be part of any curriculum... People should have a sense that yes, it's complex, but it's also NOT magic."

此外，lambda calculus 也延伸到了高階解釋器之外。在 Binary Lambda Calculus (BLC) 中，項 (terms) 被表示為位元，這使得自解釋器 (self-interpreters) 可以變得極其精簡——有時甚至比這裡提供的 7 行 Scheme 程式碼還要小。

結論

無論你是為了好玩而構建一個玩具語言，還是正在設計一個生產級別的編譯器，從 lambda calculus 開始都能提供對值、環境和函數如何交互作用的基本理解。eval/apply 模式作為一個可擴展的藍圖，評估證明了即使是最複雜的程式語言，也是建立在幾個簡單、遞迴的基礎之上。

Sources