Lambda MicroEgg
4 days ago
- Lambda MicroEgg是一个支持良好作用域、alpha感知绑定的egraph，构建在Max的microegg之上，并添加了高阶Miller模式和无捕获替换等功能。
- 它使用提升技术来表示上下文，使alpha等价项能够哈希共享到相同内存，并高效处理绑定。
- 该工具支持一阶和高阶应用，对高阶应用使用柯里化的“app”表示，显示了性能权衡。
- Miller模式用于高阶匹配，允许变量应用于绑定变量，实现为了简化而将其限制为有序模式。
- 系统展示了实际应用，如AC饱和、β归约以及求和和map/comp融合的重写规则。
- 当前限制包括仅支持最多7个变量，这是由字节窃取Id编码导致的，并且在微基准测试中，该工具比egg慢约3倍。
- 作者在开发过程中使用了AI协助，并强调了其对影响的兴奋和担忧。