LispE源码解析(三):元素池、执行栈与惰性求值机制拆解

原创2026-11-16 17:47:571,453 阅读

LispE源码解析(三):元素池、执行栈与惰性求值机制拆解

LispE 是一个功能完整的 Lisp 解释器,内置数据结构、模式编程与 Haskell 风格的惰性求值。本文基于 LispE 源码,带你完整拆解它的三大核心运行时机制:元素池(pool)、执行栈(execution stack)与惰性求值(lazy evaluation)。即使你只学过一点 C++ 和 Lisp 基础,也能看懂这套设计是如何让解释器"又快又稳"的。

LispE在浏览器中运行的演示界面

元素池:告别频繁的 new/delete 🧹

LispE 中所有运行时对象(数字、字符串、列表、函数……)都继承自同一个基类 Element,它的实现见 elements.h。每个 Element 只带两个关键字段:

  • type:标记对象种类(整数、浮点、列表、字典……)
  • status:引用计数 + 状态位(可销毁 s_destructible、受保护 s_protect、常量 s_constant)

status 归零时对象才会被 delete,这是典型的引用计数内存管理。但问题在于:解释器每秒可能创建成千上万个临时对象,new/delete 的开销不小。LispE 的解法是对象池。

在主类 lispe.h 中,你可以看到一大片池成员:

  • 标量池:integer_pool、number_pool、float_pool、string_pool、complex_pool
  • 容器池:list_pool、set_pool、dictionary_pool、tree_pool
  • 特殊池:quoted_pool(引用值)、return_pool、无穷 range 池等

每个池本身又是一个对象池数组——解释器构造时通过 initpools() 一次性预分配 25 个池对象(如 new Listpool(this)、new Integerpool(this, 0)),之后不断循环复用。以 Floatpool 为例(见 elements.h),它重写了 decrement() 和 release():引用计数归零时不销毁自己,而是回到池中等待下一次赋值,相当于"对象回收站"。

此外还有一组 unordered_map 形式的常量池(const_integer_pool、const_number_pool、const_string_pool):同一个字面量(比如字符串 "hello")只会在内存中存在一份,多处引用共享同一对象,既省内存又让比较更快。

LispE链表元素结构示意图:car与cdr

执行栈:函数调用如何层层展开 📚

LispE 的执行栈由两部分组成(lispe.h):

vecte<Stackelement*> stack_pool;       // 栈帧回收池
vecte<Stackelement*> execution_stack;  // 真正的执行栈

每层栈帧是一个 Stackelement(stack.h),包含:

  • variables:本层的局部变量表(binHash<Element*>,键是编译期分配的 label 编号)
  • status:配合 variables 恢复变量原有状态
  • function:当前正在执行(或刚进入)的函数
  • instance:对象方法调用时的类实例

调用发生时,push() 从 stack_pool 中取出一个空闲栈帧复用;函数返回时,removeStackElement() 清空该帧并放回池中——和元素池异曲同工,避免反复分配栈帧对象。

两个值得注意的细节:

  1. 栈深保护:provideStackElement 会在栈深达到 max_stack_size(默认 50000)时抛出 stack overflow 错误,防止无限递归拖垮进程。
  2. 变量作用域即栈查找:查找一个变量时,解释器从栈顶逐层向下搜索(lispe.h),直到最底层的全局帧,这天然实现了 Lisp 的块级作用域——内层赋值自动"遮蔽"外层同名变量。

Stackelement 里大量的 recording*、reset_in_stack 方法都围绕引用计数做文章:把新值记入变量表时 increment(),被替换或出栈时 decrement(),保证任何时刻对象的引用计数与"引用它的位置数"严格一致。

惰性求值:把计算推迟到需要的时刻 ⏳

LispE 的"惰性"体现在三个层次:

1. 惰性单元 Force elements.h 中定义了 Force 类(类型为 t_forced):它包裹一个"待求值"的元素,直到被真正使用时(duplicate()),才解包返回内部元素并丢弃外壳——这正是 Haskell 中 thunk 的思想。配套的 force 指令(eval.cxx)在求值后把结果包成 Force,目前主要用于线程参数场景,让值在"传递时冻结、消费时激活"。

2. 编译期固化的代码对象 LispE 会把调用代码编译成 Listincode 及其子类(如 List_infix_eval、List_switch_eval,见 listes.h)。这些代码对象带有 s_constant 状态:不占用引用计数、不参与垃圾回收,可安全地长期驻留在池中反复调用。"何时求值、求值几次"由代码对象自己决定,而不是解释器逐 token 即时求值——这就是惰性调度的一层体现。例如中缀表达式经 straight_eval 通道(straight_eval.cxx)按自身语义组织求值顺序,而非一律从左到右。

3. 按需求值的组合子 map、filter、range 这类高阶函数返回的往往是"描述"(无穷序列池 rangenumber_pool 就是为无穷 range 准备的),实际计算推迟到元素被真正访问的那一刻。

三大机制如何协作 🔗

把视角拉远,一次 (f a b) 调用大致经历:

  1. 参数 a、b 求值得到 Element,从元素池取/复用对象;
  2. push() 从栈帧池取栈帧,把参数 record 进 variables,压入 execution_stack;
  3. 函数体内按需求值,惰性包装(Force/代码对象)决定哪些计算被推迟;
  4. 返回时 removeStackElement() 回收栈帧,临时对象引用计数归零后回到池中。

给源码读者的路线图:

模块 文件 看点
元素基类与状态位 include/elements.h 引用计数、s_constant 常量模式
池的声明与初始化 include/lispe.h initpoolsize/initpools
栈帧结构 include/stack.h 变量记录与状态恢复
栈的压入/回收 include/lispe.h stack_pool 复用逻辑
惰性单元 include/elements.h Force/t_forced
编译后代码对象 include/listes.h Listincode 家族

下一篇我们可以顺着 Listincode 继续深入编译与模式匹配机制,欢迎继续追踪源码!

登录后查看全文
lispe