参考文档 / ZLIB × LEAN
完成的结论依靠什么
状态页把一项结论称为完成,是指存在一条 Lean 定理,它的命题恰好就是这个目标,并且通过了本项目的每一项检查。本页说明这意味着什么:一项完成的结论有四件事成立,对仓库的每次改动都就这四件事作检查,而其中没有一件证明了 Lean 文本正确地描述了 C。
一项完成的结论有哪些事成立
- Lean 内核检查了证明。 内核是 Lean 核心的一个小程序,它接受或拒绝一个证明项。构建库时它检查每个证明。没有任何证明使用
sorry、native_decide,或者其他不经内核检查就直接采信结果的构造。 - 只使用三条标准公理。 证明和它依赖的一切,除
propext、Classical.choice和Quot.sound之外不使用任何公理。没有为本项目添加公理。 - 定理的类型恰好就是目标。 目标是一个 Lean 定义,定义的是一个命题,它与证明分开书写。使目标完成的那条定理,类型就是这个命题,不是更弱的命题,也不是相近的命题。范围更窄的引理不算数。
- 前提写在命题里。 一条定理写明它用到的每一个前提。前提比
zlib.h允许的范围窄的地方,都列在偏离记录中。
每次改动检查什么
对仓库的一次改动,只有在改动后的源码满足下面全部各项时才被接受。
- 整个库能构建。 内核检查每个证明。警告即错误,所以一处
sorry(被直接承认、未经证明的步骤)会使构建失败。 - 结论与它们的目标一致。 在同一次构建中,一项检查逐条查看结论列表。每个已完成目标的定理,类型恰好就是这个目标。它除三条公理外不依赖任何公理,检查会追踪定理依赖的一切。库中写出的每个目标,要么已证明,要么列为未完成;每个必需的目标都已证明。这项检查本身也在小例子上测试过:它拒绝类型不对的定理、多出的公理、未列出的目标,以及没有定理的必需目标。
- 没有漏掉函数。 必需的目标与固定版本的
zlib.h作对照:目标构建中每个有文档的函数的安全目标都在其中。 - 没有绕过内核的东西。 源码中没有被禁止的构造,也不设置任何关闭或削弱内核检查的选项。编译好的库也被检查:其中没有声明是公理,也没有声明是
opaque、extern或implemented_by,没有声明使用三条之外的公理;除了列出的由编译器生成的辅助声明,没有声明是unsafe或partial。 - 补丁能打上固定版本的 zlib。
- 翻译在测试输入上仍与 C 一致。 翻译、运行时、补丁或测试有改动时,差分测试重新运行,其中的 C 用 AddressSanitizer 和 UndefinedBehaviorSanitizer 构建。
一次构建只复用由已被接受的源码构建出的编译模块,从不复用来自待审改动的模块。
有一项检查不是每次改动都做:独立的重放,即内核在全新的环境中把编译好的结论及其依赖的一切重新检查一遍。读者可以用 lake env leanchecker --fresh ZlibF.Results 运行它。
不是证明的证据
这些定理说的是 C 的一份 Lean 翻译,翻译是手工逐语句完成的。差分测试在许多输入上把这份翻译与真实的 C 作比较,其中的 C 用 AddressSanitizer 和 UndefinedBehaviorSanitizer 构建。它们是忠实性的证据,不是证明。
信任什么
一项完成的结论是否说出了关于真实 zlib 的事实,还取决于内核不检查的东西:Lean 内核本身、内存与故障的运行时模型、手工翻译、选定的源码及其补丁、外部世界的模型,以及各个目标的命题。可信基础逐项列出它们,并说明相信每一项的理由。模型的限制列出模型可能与 C 不同的地方。