FEXPRs 与 vtable：LispE 解释器的工作原理深度解读

背景

在计算机科学的历史长河中，解释器（Interpreter）与编译器（Compiler）之间的对立曾是一个经典且令人头疼的悖论。传统观点认为，解释器保留了源代码的原始形态，从而赋予了程序极高的灵活性和可塑性，但代价是难以进行机器层面的优化；相反，编译器生成高效的二进制文件，虽然优化空间巨大，但代码被“冻结”在特定机器架构上，失去了灵活性。

对于 Lisp 这种语言而言，这种二元选择尤为尴尬。Lisp 的核心魅力在于其同源性（Homoiconicity），即代码即数据。如果为了追求极致优化而牺牲了同源性，那就失去了 Lisp 的灵魂。然而，早期的 Lisp 实现曾面临另一个难题：FEXPR（Function Expression）。在 Lisp 1.5 和 MacLisp 等早期方言中，存在两种运算符：EXPR（普通函数，参数在调用前求值）和 FEXPR（接收未求值的原始参数，由函数自身决定何时求值）。

FEXPR 虽然提供了极高的表达力（如 if、quote 等均可实现为 FEXPR），但它带来了致命的性能瓶颈：由于求值逻辑在运行时由 FEXPR 动态决定，静态分析器无法知晓代码结构，导致无法进行内联、优化或早期解析。Kent Pitman 在 1980 年的文章中指出，这种不透明性使得编译器无法工作，因此历史悠久的 Lisp 系统最终摒弃了用户定义的 FEXPR，转而使用 Special Forms（特殊形式）来保留可编译性。

LispE 试图打破这一僵局。它提出了一种看似矛盾的设计：LispE 是一个编译对象的解释器。它拒绝在“灵活但低效”与“高效但僵化”之间做选择，而是通过一种独特的机制，将两者统一起来。

核心内容

LispE 的核心创新在于建立了一个简单的等价关系，将函数式编程的语义映射到 C++ 的对象模型上。其核心论点可以概括为以下两个等价式：

1. 数据（Datum）: $f() \iff F.eval()$
2. 指令（Instruction）: $f(a_1, ..., a_n) \iff F(a_1, ..., a_n).eval()$

其中，$F$ 是一个从通用基类 Element 派生的类的实例，它持有其参数作为子节点，而 eval 是一个在整个类层次结构中统一且无参数的方法。

1. 对象即指令：AST 的持久化

LispE 将语言的每一条指令都转化为一个派生类，该类暴露出一个 eval 方法。所有类都继承自一个名为 Element 的基类。这意味着，Lisp 的抽象语法树（AST）不再是一堆待解析的文本或临时的数据结构，而是被转化为 C++ 对象。

• AST 存活：AST 在内存中保持活跃，每个节点都是一个 C++ 对象。
• 极致优化：由于节点是 C++ 对象，可以利用 C++ 的全部 arsenal（如虚函数表 vtable、内联、缓存友好性等）进行优化。
• 统一接口：无论节点是原子、列表还是复杂表达式，它们都通过统一的 eval() 接口进行交互。

2. 函数应用的两种解读

传统函数应用 $f(a_1, ..., a_n)$ 通常被理解为函数式语义：将值 $a$ 应用于函数 $f$。而在 LispE 的对象式解读中，这被重新定义为：构建一个持有参数 $a$ 的对象 $F$，并向其发送 eval 消息。

这两种解读并非仅仅是类比，而是同一行为的不同记法。LispE 反转了通常的层级观念：通常我们认为对象是实现函数的手段（将 $f$ 实例化为 $F$ 以便传递）；而 LispE 认为，$f(a_1, ..., a_n)$ 只是表层语法，其底层形式是 $F(a_1, ..., a_n).eval()$。Lisp 的 (op . args)、C++ 的 F(args) 和数学家的 $f(args)$ 都是 Element(args).eval() 的不同拼写。

3. 数据是退化的指令

在 LispE 中，数据（Datum）与代码（Code）没有本质区别。数据被视为一种特殊的指令，其求值规则是恒等映射（Identity）：$X.eval()$ 返回 $X$ 本身。

• 零元情况：数据是零元指令的特例，即没有子节点的指令，其 eval 返回实例自身。
• 同源性实现：这实现了 C++ 层面的同源性。不需要标签来区分“代码”单元格和“数据”单元格，因为数据本身就是“最小化的代码”，即求值结果为自身的固定点（Fixed Point）。
• 统一结构：一个指令本质上是一个 std::vector<Element*>，每个单元格都是知道如何自我求值的 Element。

4. 不可变性：等价性的前提

上述等价关系成立的唯一严格条件是：$F$ 必须是不可变的（Immutable）。

• 引用透明性：函数应用 $f(a_1, ..., a_n)$ 在多次求值时应产生相同结果。如果 eval 修改了对象 $F$ 或其子节点，第二次调用将看到不同的状态，等价性将崩溃。
• 纯函数语义：如果 eval 产生副作用，它就不再是函数，而变成了过程，整个构造将退化为命令式编程。
• 解释器纯度：需要注意的是，这种纯度是解释器本身的属性，而非被解释程序的属性。LispE 的解释器方法是纯函数，但它执行的程序可以是纯的也可以是含副作用的。

5. 性能优势：状态与指令分离

由于 $F$ 是不可变的，实例在 AST 中持久存在。

• 一次编译，多次执行：对于表达式 (* a b)，对象 $F$ 是一个稳定的 AST 节点。循环执行一千次，实际上是向同一个实例发送一千次 eval 消息。
• 上下文分离：指令本身是无状态的（Stateless），不持有可变状态。所有状态（如变量绑定）都存储在栈（Stack）中，位于指令之外。eval 是一个纯函数，它读取不变的指令 $F$，并推进变化的上下文（栈）。
• 对比朴素解释器：朴素解释器每次执行都需要重新解析或决定形式，而 LispE 的形式在类型层面被“冻结”，重新执行时形式不变，仅上下文变化。

6. 技术实现：vtable 分发

eval 方法不接受参数（参数在构造时已记录为子节点），且在整个层次结构中签名统一。这种统一性使得 C++ 的虚函数表（vtable）分发成为可能：一个虚方法，一个签名，每个类重写它。

在输入阶段，LispE 将每个形式 (op ...) 编译为 List 的子类实例：

• (cons a b) -> List_cons_eval 实例
• (+ a b) -> List_plusn 实例
• (defun f ...) -> 编译为对 List_function_eval 的调用
• (defpat p ...) -> 编译为相应的模式匹配实例

关键要点

• LispE 的悖论解决方案：LispE 通过成为“编译对象的解释器”，解决了 Lisp 在灵活性（解释器）与性能（编译器）之间的两难困境，同时保留了同源性。
• 核心等价式：函数应用 $f(args)$ 等价于对象方法调用 $F(args).eval()$。数据是零元指令的特例，其 eval 返回自身。
• 不可变性至关重要：为了保证等价关系的成立和引用透明性，AST 节点（$F$）必须是不可变的。eval 是纯函数，副作用仅通过外部上下文（栈）体现。
• 性能机制：由于指令不可变且状态与