如何使用 Python 编写 Lisp 解释器
如何使用 Python 编写 Lisp 解释器
实现一个 Lisp 解释器是理解计算机和编译器工作原理的主要方法。Peter Norvig 的 "Lispy" 项目展示了 Lisp 的 Scheme 方言的一个函数式子集可以通过大约 117 行 Python 3 代码来实现，这证明了 "世界上最强大的语言" 可以用极少量的源代码来定义。
语言解释器的架构
一个语言解释器由两个主要组件组成：解析（parsing）和执行（execution）。该过程遵循线性流水线：Program $\rightarrow$ Parse $\rightarrow$ Abstract Syntax Tree (AST) $\rightarrow$ Eval $\rightarrow$ Result。
解析
解析将字符序列转换为内部表示，通常是抽象语法树（AST）。在 Lispy 中，这被分为两个阶段：
- 词法分析（Tokenization）： 输入字符串被分解为 token（括号、符号和数字）。Lispy 通过在括号周围添加空格并使用 Python 的
str.split来实现这一点。 - 语法分析： token 被组装成嵌套列表结构。
read_from_tokens函数在遇到左括号时递归地构建列表，并将非括号 token 视为原子（整数、浮点数或符号）。
执行（求值）
执行根据语言的语义规则处理 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 的添加需要一种通过环境进行变量管理的复杂方法。
Env 类与词法作用域
为了支持局部变量和嵌套函数，环境被重新定义为一个继承自 dict 的类。每个 Env 实例包含其自身的局部映射以及对 outer 环境的引用。
当引用一个变量时，解释器使用 find 方法首先搜索最内层环境；如果找不到该变量，它会递归地搜索外部环境。这种机制实现了词法作用域，确保程序引用的是它们被定义时所在的环境中的变量，而不是它们被调用时所在的环境中的变量。
程序实现
一个 Procedure 对象存储参数名称、函数体以及它被创建时的环境。当被调用时，它会创建一个新的 Env，将提供的参数绑定到参数名上，并将该程序的原始环境设置为外部作用域。
性能与完整性
Lispy 是为教学清晰度而非生产用途而设计的。其特点包括：
- Size： 极其紧凑，由大约 117 行非空行和 4KB 的源代码组成。
- Speed： 能够在大约 0.003 秒内计算
(fact 100)。 - Limitations： 它缺乏一些标准的 Scheme 特性，包括尾调用优化、
call/cc、字符串、字符、布尔值以及全面的错误恢复。
社区洞察
开发者和教育工作者将实现 Lisp 解释器视为计算机科学的基础练习。正如讨论中所提到的：
"如果你曾经好奇如何编写一种编程语言，这可能是开始学习的最佳资源。"
其他贡献者强调了 Lisp 的树状结构与语言学家用于标注句子结构的短语结构语法之间的同同构性。一些人还指出，虽然 AI 现在可以生成此类代码，但实现解释器的行为本身对于程序员来说仍然是一种 "具有启发性的体验"。