
MIT团队用E-Graphs实现编译器正确性自动验证
来源标题:Automatic Checking of Compiler Correctness with E-Graphs
MIT CSAIL团队提出一种基于E-Graphs的通用证明自动化工具,可自动完成编译器的形式化验证,论文将于2027年1月在POPL 2027发表。该工具能处理此前从未见过的编程语言编译器定义,据称是首个具备此能力的通用证明自动化工具。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
Adam Chlipala 2026年11月17日 2 2 分享 本文在 Adam Chlipala 教授的博客 Structure and Guarantees 与 CSAIL(即所讨论研究所在的 MIT 实验室)的博客之间交叉发布。 我正处在一个系列文章的最后冲刺阶段,这个系列讲的是利用经过证明的重写规则,一步步构造正确且高效的程序;我认为这是对当今 AI 编码代理被广泛使用的各种方式的一种重要替代方案。此前的例子包括张量程序、数字硬件和底层密码学软件。上一篇文章介绍了 e-graph,这是一种数据结构及一组相关算法,用于高效探索书写代数表达式的许多备选方式。这项技术已被证明对程序验证和程序优化都非常有用。 现在我要给出一个这种方法在实际中应用的例子,来自刚刚出炉的研究。我们即将于明年一月在墨西哥城召开的 POPL 2027 上发表的论文,使用 e-graph 来自动化编译器的形式化验证。这似乎是第一个通用的证明自动化工具的例子:它能够接收一门该工具从未见过的新编程语言的编译器定义,且无需任何仅为引导定理证明而设的额外标注,就能自动证明其正确性。(过去有一些例子适用于固定的编程语言,比如 Cobalt 和 Rhodium。)截至本文写作时,论文的最终版本尚未完全发布,但你可以在一作 Dustin Jamner 的博士论文中找到细节。本科生 Tilek Askerbekov 也对这篇论文有所贡献。 首先我需要跟你说清楚我们谈论的是哪一种编译器。它并不特别像 GCC 或 Clang——那是工业界对这个词最典型的理解。相反,让我欢迎你进入函数式编程语言编译器那个在数学上引人入胜的平行宇宙。我们研究项目所处理的编译器沿袭了经典研究论文《From System F to Typed Assembly Language》的传统。对于这一组想法,我算不上一个不带偏见的评价者——我曾与论文的教职作者 Greg Morrisett 做过博士后,并与他的前博士导师 Bob Harper 做过本科研究。不过,让我们快速看看这类编译器是如何工作的。其思想是,编译被分成多个阶段,程序的每一种中间形式都会在一个可靠的类型系统中接受检查,该系统保证不会发生崩溃——这与经典编译器非常不同,后者会迅速下降到中间语言,在那里所有安全性保障都不复存在。 为了避免无端依赖函数式编程的圈内知识,我将使用一个 Python 示例程序,我们想逐步编译它,直到它变得足够像汇编语言。我们的起始程序是一个很简单的程序。 def square(x): return x * x def compute(x): return square(x + 1) + 3 print(compute(4)) 程序员通常把“一个函数调用另一个函数、后者再调用另一个、如此继续”的能力视为理所当然。这种自由通常是在幕后用调用栈实现的。我们的第一个编译器变换将把调用栈显式化。事实上,调用栈将表现为一条由一等函数组成的链,每个函数调用栈中下一层所对应的函数。这个变换就是转换为续延传递风格(continuation-passing style),其中我们用“续延”来指代我们引入的这些函数。 def square(x, k): k(x * x) def compute(x, k): def after_square(y): k(y + 3) square(x + 1, after_square) compute(4, print) 注意发生了什么:每个函数现在都显式接收一个续延 k 作为参数。在函数原本会返回的地方,它改为用结果调用自己的续延。现在没有函数(除了某些原语)会返回了,这与硬件执行的实际工作方式很好地吻合。调用栈只是一个可选的虚构,之所以让我们觉得自然,是因为我们的大脑进化出了理解具有类似结构的自然语言的能力(这是我以后一两篇文章里会重新爬上去的肥皂箱,用来解释赋予这种虚构过多特殊地位对实际编程的一些弊端)。这个例子在合理性上也多少依赖于尾调用优化,而 Python 实际上并不提供这一优化,但我们姑且假设它提供。 这段代码还有哪些地方仍然离硬件能直接支持的东西太远?after_square 的函数定义随意地提到了外层作用域中的变量 k。术语上说,after_square 是一个捕获了变量 k 的词法闭包。这种机制与硬件中自然实现的机制相去甚远,所以我们还需要一个闭包转换编译阶段,去除对捕获变量的使用,转而把这些变量变成显式的函数参数,打包进一等环境中。我们运行示例的结果是: def invoke(closure, value): code, env = closure code(env, value) def square(env, x, k): invoke(k, x * x) def after_square(env, y): k = env["k"] invoke(k, y + 3) def compute(env, x, k): continuation = (after_square, {"k": k}) square({}, x + 1, continuation) def print_result(env, value): print(value) initial_continuation = (print_result, {}) compute({}, 4, initial_continuation)
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。