揭秘语言实现：从 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 实现一个指称性解释器。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 以供解释器处理的解析器即可。

技术视角与评论

实现这些概念通常会引发关于函数式极简主义实用性的辩论。有人认为，在类 Lisp 语言中实现 lambda calculus 实际上是在“用 Lisp 实现 Lisp”，这表明其简洁性是宿主语言的固有特性，而非目标语言的简单性。

然而，其他人指出，这项练习不仅仅是为了代码——它是为了揭示计算的“魔法”。正如一位贡献者所言：

"构建一个带有 LED 和逻辑门电路的 ALU 应该成为任何课程的一部分... 人们应该意识到，是的，它很复杂，但它也并非魔法。"

此外，lambda calculus 甚至可以扩展到高层解释器之外。在 Binary Lambda Calculus (BLC) 中，项被表示为比特，这允许实现极其紧凑的自解释器——有时甚至比这里提供的 7 行 Scheme 代码还要小。

结论

无论你是在为了乐趣构建一个玩具语言，还是在设计生产级别的编译器，从 lambda calculus 开始都能让你对值、环境和函数是如何交互的提供根本性的理解。eval/apply 模式作为一个可扩展的蓝图，证明了即使是最复杂的编程语言，也是建立在少数几个简单的、递归的基础之上。

Sources