如何用 Python 编写一个 (Lisp) 解释器

背景

在计算机科学领域，理解编译器（Compiler）和解释器（Interpreter）的工作原理被视为掌握计算机底层逻辑的关键。正如 Steve Yegge 所言：“如果你不知道编译器是如何工作的，那你就不懂计算机是如何工作的。”编译器能够解决一系列核心计算问题，而解释器同样具备这些能力。

本文源自 Hacker News 社区讨论的经典教程《How to Write a (Lisp) Interpreter (In Python)》。其核心目标是指导读者使用 Python 语言，从零开始构建一个能够运行 Scheme 语言子集的解释器。Scheme 是一种 Lisp 方言，其语法设计极简，非常适合用于教学和理解编程语言的核心机制。通过构建这个名为 "Lispy" 的解释器，读者可以深入理解程序从源代码到执行结果的完整生命周期，包括词法分析、语法解析、抽象语法树（AST）构建以及环境求值等关键步骤。

核心内容

构建解释器的过程主要分为两个阶段：定义简化语言并实现解析，然后扩展至接近完整的 Scheme 语言并实现求值。整个流程遵循经典的 Program -> Parse -> AST -> Eval -> Result 模式。

1. Scheme 语法基础

与 Java 等拥有复杂语法（关键字、中缀运算符、多种括号、运算符优先级等）的语言不同，Scheme 的语法极其简洁：

• 表达式唯一性：Scheme 程序完全由表达式（Expressions）组成，没有语句（Statements）与表达式的区别。
• 原子表达式：数字（如 1）和符号（如 A）被称为原子表达式，不可分割。值得注意的是，在 Scheme 中，运算符（如 + 和 >）也是符号，处理方式与变量名 A 或函数名 fn 相同。
• 列表表达式：除原子外，其余均为列表表达式，格式为 ( 后跟零个或多个表达式，最后以 ) 结尾。列表的第一个元素决定其含义：
  • 以关键字开头（如 (if ...)）为特殊形式（Special Form），含义取决于关键字。
  • 以非关键字开头（如 (fn ...)）为函数调用。

2. 解析阶段（Parsing）

解析器的任务是将字符序列转换为内部表示（通常是抽象语法树 AST）。

• 词法分析（Tokenization）： 首先通过 tokenize 函数将输入字符串转换为令牌列表。由于 Scheme 使用空格分隔元素，实现方式是将 ( 和 ) 前后加上空格，然后按空格分割。

  def tokenize(chars: str) -> list:
      return chars.replace('(', ' ( ').replace(')', ' ) ').split()
  

  例如，程序 "(begin (define r 10) (* pi (* r r)))" 会被转换为令牌列表。

• 语法解析（Parsing）： parse 函数调用 read_from_tokens 递归构建 AST。

  • 如果遇到 (，则开始构建子表达式列表，直到遇到匹配的 )。
  • 如果遇到非括号令牌，则通过 atom 函数判断其类型：尝试转换为 int，失败则尝试 float，若仍失败则视为 Symbol（字符串）。
  • 最终返回嵌套的 Python 列表结构，即 AST。

  示例输出：

  >>> parse("(begin (define r 10) (* pi (* r r)))")
  ['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]
  

3. 执行阶段（Execution）

执行阶段通过 eval 函数处理 AST，依据语义规则进行计算。为此，需要建立一个全局环境（Environment），即变量到值的映射。

• 环境初始化： 使用 standard_env 函数初始化全局环境，导入 Python 的 math 模块（提供 sin, cos, pi 等）和 operator 模块（提供 add, sub 等），并定义 Scheme 的基本内置过程（如 +, -, if, define, car, cdr 等）。

• 求值逻辑（Eval）： eval(x, env) 函数根据表达式类型进行递归求值：

  1. 符号（Symbol）：如果是变量引用，从环境中查找其值。
  2. 数字（Number）：如果是常量，直接返回。
  3. 特殊形式 if：先求值测试条件 test，若为真则求值 conseq，否则求值 alt。
  4. 特殊形式 define：求值表达式 exp，并将结果绑定到环境中的 symbol。
  5. 过程调用（Procedure Call）：
     • 求值第一个元素（过程/函数）。
     • 递归求值剩余元素（参数）。
     • 调用过程并返回结果。

  代码逻辑如下：

  def eval(x: Exp, env=global_env) -> Exp:
      if isinstance(x, Symbol):
          return env[x]
      elif isinstance(x, Number):
          return x
      elif x[0] == 'if':
          (_, test, conseq, alt) = x
          exp = (conseq if eval(test, env) else alt)
          return eval(exp, env)
      elif x[0] == 'define':
          (_, symbol, exp) = x
          env[symbol] = eval(exp, env)
      else:
          proc = eval(x[0], env)
          args = [eval(arg, env) for arg in x[1:]]
          return proc(*args)
  

4. 交互循环（REPL）

最后，实现一个读取-求值-打印循环（REPL），允许用户交互输入 Scheme 代码。

• repl 函数循环等待用户输入。
• 调用 parse 解析输入，调用 eval 执行。
• schemestr 辅助函数将 Python 对象（如列表）转换回可读的 Scheme 字符串格式，以便打印结果。

通过这一系列步骤，一个简单的 Scheme 解释器得以运行，能够计算圆面积、处理条件判断以及定义过程（Lambda）。

关键要点

• 极简语法的力量：Scheme 仅由表达式和列表构成，去除了语句与表达式的区分，使得语法解析器极其简单，专注于核心逻辑而非语法糖。
• AST 的核心地位：解释器将源代码解析为抽象语法树（AST），AST 是连接词法/语法分析与语义执行的桥梁。在 Python 中，AST 被自然地表示为嵌套列表。
• 递归下降解析：read_from_tokens 展示了典型的递归下降解析器实现，通过递归处理嵌套的括号结构，优雅地构建了树形结构。
• 环境（Environment）作为状态容器：解释器通过字典（Dict）模拟环境，管理变量绑定。eval 函数始终在特定环境中查找变量值，这是实现作用域的基础。
• 统一的数据结构：在 Scheme 中，代码即数据（Homoiconicity）。列表既代表数据结构，也代表代码结构。Python 的列表完美映射了这一特性，使得解释器实现代码与数据结构高度一致。
• 特殊形式与函数调用的区别：解释器必须区分特殊形式（如 if, define）和普通过程调用。特殊形式拥有特殊的求值规则（如 if 只求值分支之一），而普通过程调用则先求值所有参数。
• Lambda 的本质：Lambda 表达式在求值时创建一个过程对象，该对象捕获其定义时的环境（闭包），从而支持高阶函数和动态作用域。

意义与影响

编写一个 Lisp 解释器是计算机科学教育中的“圣杯”项目之一，其意义远超技术实现本身：