返回资讯中心
外部精选
软件工程
#开发者实时流

语言中的证明自动化:如何提升软件质量与可理解性

来源标题:Proof Automation in a Language

随着证明自动化技术的成熟,作者探讨如何利用它改善软件质量和代码可理解性。他指出,能写证明的机器同样能写大量代码,而编程语言设计数十年的积累为这一方向提供了丰富思路。文章列举了值语义等正在考虑的若干设计要素及其组合效果。

Hacker News 最新ragall2026/11/16 · 今天27 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

正如我之前所写,我们现在已经有了证明自动化。既然如此,我认为一个非常及时的问题是:我们如何利用它来提升软件质量?能够写出这些证明的机器,同样也能写出大量代码。于是另一个相关的问题便是:我们如何利用它们来提升软件的可理解性?

如果从零开始着手这些问题,那将是个错误,因为几十年来编程语言设计领域已经积累了大量想法。随着底层成本结构的变化,各种想法的可行性也会随之改变,所以当年没能流行起来的东西,如今可能突然变得很有意义。不过,语言设计涉及大量权衡,各种特性之间的交互有时会出人意料,因此很多工作就像是把一些看似有趣的原料混在一起,放进烤箱,然后问:“这是什么?这是蛋糕吗?”

所以我想让大家尝尝我目前正在思考的一些原料,以及最终的成品。

值语义大致是说,你无法通过另一个名字观察到对某个变量的修改。值语义非常适合对代码进行局部推理,因为如果没有值语义,你就始终不确定可能存在哪些非局部的影响。

当你使用一门语言时,你会本能地知道它什么时候用的是值语义,什么时候用的是引用语义。以 Python 为例:

x = [1] y = x y[0] = 2 print(x)

你大概知道这会打印出 [2]。(不过如果你用 C++ 的 std::vector 写同样的程序,它会打印 [1]!这方面并没有跨语言的统一规范。)

在四行代码的范围内,这无关紧要。但随着共享范围扩大,心智复杂度也随之增加。如果你想跳进一段代码并理解它在做什么,知道不存在这种别名现象,那是一个巨大的优势。

函数式编程通过消除可变性来解决这个问题:如果没有可变性,你当然无法通过另一个变量名观察到修改。但可变性对效率很重要,而要重新获得效率就需要做大量工作。例如,Lean 在某个对象只有一个引用时会进行原地修改。这很棒!但它有个尖锐的边角:看似无害的改动可能意味着某处现在保留了一个隐藏引用,性能就会崩溃。

Rust 声称通过限制引用来同时解决这两个问题,使得你永远不能同时拥有某个东西的可变引用和它的活跃别名。(我们先忽略 Rc<RefCell<T>> 之类的东西。)

Rust 的限制当然大有帮助,但可变值语义(Mutable Value Semantics)认为 Rust 走得太远了,因为它把引用变成了头等公民,即你可以返回引用并将其存储在结构中。头等引用导致了借用检查器的出现,它经历了多次深度重写(从原始版本到 NLL,再到 Polonius)以求完善,还导致了生命周期、DerefMut 等等,以及类型系统整体上多得多的复杂性。

因此,MVS 系统通过进一步限制引用、不允许引用出现在类型系统中,从而避开了所有这些。这些想法始于 Swift,目前由 Hylo 倡导。我找到的最好的入门材料是这个演讲。

在 MVS 系统中,函数可以接受三种参数:不可变、可变和拥有。不可变参数可能是引用或副本;语义上是一样的。可变参数在概念上是在调用时复制进来、函数返回时复制出去,当然这在语义上等同于取一个指针。最后,拥有参数将所有权转移给函数,之后调用者就无法再使用它了。

但类型系统中没有引用,所以函数不能返回或存储它们。然而无法返回引用意味着大量的复制,因此 MVS 系统需要提供一种替代方案。

Hylo 有一套非常巧妙的受限协程系统,灵感来自 Swift。这些协程产出一个值,在调用点,它们的所有参数在该值的存活期间都被锁定。在该存活期结束时,协程继续运行。

一个常见的例子是,协程可以为一个按字节打包的位向量返回一个可变的 bool。然后,当返回值不再被使用、协程继续运行时,它可以把该 bool 的新值写回字节数组。如果没有协程,这是不可能的,因为函数将不得不返回一个指向内存中不存在的 bool 的指针。

刚刚我把这个特性捧上了天,但我应该指出,在我的实验中我实际上并没有包含它,因为它使语义更加复杂,而我把大量的复杂度预算花在了验证上。这就引出了另一个与 MVS 相结合的想法……

如果你想对像 C 这样的语言做形式化验证,那么你需要对堆建模,然后你立刻就会撞上上面提到的别名问题。接着你最终会得到一个分离逻辑,它让你能够对堆中不相交的区域(即它们之间没有别名)建模。一旦你能够谈论独立的堆,你就可以对一个操作于某个堆的函数进行推理,同时保持其余部分不变。

这可以行得通。我(略有所知地)熟悉的例子是 Verified Software Toolchain,它连接到 CompCert 的语义,允许你(用分离逻辑)陈述关于 C 程序的性质,从而一路验证 C 代码到机器码。但它很复杂。

然而!如果你有受限制的引用,那么你就可以从这类系统中去掉大量的复杂性!Aeneas/Charon 是目前这方面的典范,它可以把 Rust 代码的一个子集翻译成 Lean(以及其他语言),然后就可以对其做证明了。由于 Rust 的限制,翻译不需要分离逻辑。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →