Lambda MicroEgg 是一个基于 S 表达式的小型重写工具,其核心是将等式图(e-graph)的思想提升到新的应用场景。等式图会同时存储一个表达式的多种等价形式;重写规则会加入替代形式,引擎随后可以提取出更简单或其他方面更有用的形式。这里的难点在于作用域:在 lambda 表达式中,变量名属于最近的绑定器,因此重写绝不能意外地让它引用错误的变量。
放置在介绍 Lambda MicroEgg 与等式图的开篇说明之后,此处正式引出该项目本身。
该项目以通用方式表示绑定器。`(@sum x BODY)` 和 `(@lam x BODY)` 都使用相同的内部 `Binder(Symbol, Id)` 结构;`lam` 只是 lambda 演算中的惯用符号。重写规则的右端也可以通过 `#subst` 请求显式替换,从而降低将一个项移到不同绑定器范围时捕获自由变量的风险。
匹配被有意限制为 Miller 模式,这是一种可处理的高阶模式。在 `{?a x}` 这样的模式中,元变量 `?a` 可以表示包含不同绑定变量 `x` 的主体,但不能捕获无关变量(例如 `y`)。这一限制使带作用域的匹配比完整高阶匹配更容易实现,因为完整高阶匹配可以编码不可判定问题。一个提供的 beta 归约示例将 `[((@lam x {?body x}) ?e)]` 重写为 `[{?body ?e}]`,并通过将恒等函数应用于 `42` 提取出 `42`。
该实现还使用细化(thinning)注解来跟踪项如何在不同变量上下文之间移动。作者报告称,alpha 等价项——即仅通过一致的变量重命名而有所区别的项——会哈希同构到同一个内部表示,而通过弱化(weakening)相关的项可以共享部分更深层的内存。这是该项目的一项设计声明,并非独立基准测试结果。
主要权衡在于性能与表达能力。作者的页面报告称,一次高阶饱和运行比使用 `egg` 的类似运行更慢,而且从一阶应用切换到高阶应用也增加了成本。Lambda MicroEgg 支持有序 Miller 模式,因此如果非线性模式以不同参数顺序使用同一个元变量,该模式会被拒绝,而不是被静默处理。仓库描述了命令行和 WebAssembly 演示入口,但该项目并未证明更广泛的采用、正确性保证或生产环境性能。