(如何编写一个 (Lisp) 解释器 (用 Python)) (2010)
Hacker News 摘要原标题：(How to Write a (Lisp) Interpreter (In Python)) (2010)
这篇文章有两个目的：一是描述计算机语言解释器的一般实现方法；二是使用 Python 3 构建一个包含 Scheme 语言（Lisp 的一种方言）大部分功能的解释器。作者将这个语言和解释器命名为 Lispy。作者曾用 Java 和 Common Lisp 实现过类似的功能，而这次的目标是尽可能简洁地展示艾伦·凯所说的软件领域的麦克斯韦方程组。
学习编译器和解释器非常重要。正如史蒂夫·耶格所说，如果不了解编译器的工作原理，就不了解计算机的工作原理。编译器或解释器可以解决很多实际的编程问题。
Scheme 程序的语法和语义
语言的语法是形成正确语句或表达式的字符排列方式；语义则是这些语句或表达式的含义。例如，在数学表达式中，一加二的语法是 1 + 2，而语义是将加法运算应用于两个数字，结果为 3。计算一个表达式的值被称为求值。
Scheme 的语法与大多数编程语言不同。Java 有大量的语法约定，如关键字、中缀运算符、三种括号、运算符优先级、点符号、引号、逗号和分号。而 Scheme 的语法要简单得多：
1. Scheme 程序完全由表达式组成，没有语句和表达式的区别。
2. 数字（如 1）和符号（如 A）被称为原子表达式，它们不能被拆分。在 Scheme 中，运算符（如 + 和 >）也是符号。
3. 其他内容都是列表表达式：以左括号开头，后跟零个或多个表达式，最后以右括号结束。列表的第一个元素决定了它的含义。如果第一个元素是关键字（如 if），则是特殊形式；如果是其他内容，则是函数调用。
Scheme 的魅力在于其完整语言只需要 5 个关键字和 8 种语法形式。相比之下，Python 有 33 个关键字和 110 种语法形式，Java 有 50 个关键字和 133 种语法形式。这种简单性让 Scheme 语法具有极强的一致性。
语言 1：Lispy 计算器
作者首先定义了一个名为 Lispy 计算器的简化语言。它是 Scheme 的子集，只包含五种语法形式：两种原子形式（变量引用、常量数字）和三种列表形式（if 条件、define 定义、程序调用）。它能完成普通计算器的任务，并支持定义新变量和条件判断。
语言解释器的工作流程
语言解释器分为两个部分：
1. 解析：解析组件接收字符序列形式的输入程序，根据语法的规则对其进行验证，并将程序翻译成内部表示。在简单的解释器中，内部表示是一个树状结构，通常被称为抽象语法树，它反映了程序中嵌套的结构。
2. 执行：根据语言的语义规则处理内部表示，从而进行计算。在 Lispy 中，执行函数被称为 eval。
整个过程可以简化为：程序文本经过 parse 变成抽象语法树，再经过 eval 得到结果。
类型定义
在 Python 实现中，Scheme 的对象表示如下：
• 符号 Symbol 使用 Python 的 str 实现。
• 数字 Number 使用 Python 的 int 或 float 实现。
• 原子 Atom 是符号或数字。
• 列表 List 使用 Python 的 list 实现。
• 表达式 Exp 是原子或列表。
• 环境 Env 使用 Python 的 dict 实现，用于存放变量与值的映射。
解析器的实现
解析通常分为词法分析和语法分析。词法分析器 tokenize 将输入字符串在括号周围添加空格，然后使用 str.split 拆分为记号列表。
语法分析器 parse 调用 tokenize 获取记号，然后由 read_from_tokens 组装抽象语法树。如果遇到左括号，它就开始递归地构建列表，直到遇到匹配的右括号。非括号记号会被转化为数字或符号。
环境
环境是变量名到其值的映射。默认情况下，eval 使用全局环境，其中包含标准函数的名称，如 sqrt、max 以及 + 等运算符。用户可以通过 (define symbol value) 表达式向环境添加新变量。作者利用 Python 的 math 模块和 operator 模块初始化了这个全局环境。
表达式求值的逻辑
eval 函数的实现紧贴语义表：
• 变量引用：根据符号在环境中查找值。
• 常量数字：直接返回数字本身。
• 条件判断：根据 test 表达式的求值结果，决定求值并返回 conseq 还是 alt。
• 变量定义：对表达式求值，并存入环境。
• 程序调用：先对程序部分求值，再对所有参数求值，最后将得到的程序应用于参数列表。
交互：REPL
为了方便使用，作者定义了一个 repl 函数，即读取、求值、打印循环。它允许程序员输入表达式并立即看到结果。同时定义了 schemestr 函数，将 Python 对象转换回 Scheme 格式的字符串。
语言 2：完整的 Lispy
为了让语言更接近完整的 Scheme，作者引入了三种新的特殊形式：
1. 引号 quote：字面意思返回表达式，不进行求值。
2. 赋值 set!：为已存在的变量赋予新值。
3. 过程 lambda：创建一个自定义的过程。
过程与环境的重新定义
为了处理局部变量，Env 被重新定义为 dict 的子类，并增加了一个指向外部环境的属性 outer。
当调用一个过程时，会创建一个新的环境。这个环境包含了过程的参数及其对应的值，而它的外部环境则是该过程被定义时所处的环境。当我们在嵌套环境中查找变量时，会先从最内层开始查找，如果没找到，就向外移动到下一层。这种机制被称为词法作用域。
Procedure 类用于存储参数、主体和环境。当过程被调用时，它会在一个包含局部变量和外部引用的新环境中执行其主体表达式。
通过 make-account 函数的例子可以很好地理解这一点：每次调用该函数都会创建一个带有独立 balance 变量的环境，而内部的 lambda 过程可以访问并修改这个变量。
总结与评价
Lispy 的代码非常精简，除去注释和空行后只有 117 行，源码约 4KB。它在处理计算任务时速度足够快，例如计算 (fact 100) 仅需 0.003 秒。
虽然 Lispy 很小，但它相比标准 Scheme 还有很多缺失：
• 语法上：缺少注释、准引用、布尔值字面量等。
• 语义上：缺少 call/cc 和尾递归优化。
• 数据类型：缺少字符串、字符、布尔类型、向量等。
• 错误恢复：它不处理任何错误，默认程序员不会出错。
作者最后分享了一个真实案例：他在 1984 年写博士论文时，为了解决文本处理器引用标签的问题，通过编写简单的解释器提高了工作效率。这证明了了解解释器工作原理对解决实际问题非常有帮助。