
Lean 4 中形式化验证的 DEFLATE 实现 lean-zip 发布,代码与证明均由 AI 完成
来源标题:Lean-zip: A formally verified DEFLATE implementation in Lean 4
lean-zip 提供了纯 Lean 编写的 DEFLATE 编码器和解码器,并证明两者互为逆运算:对任意输入和压缩级别,解压结果都等于原始数据,这一证明经 Lean 内核检验。证明由约 32k 行代码、超过 1100 条定理构成,CI 会在每次改动时重新校验。实现和形式化验证均由监督较松的 AI 编码代理完成。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
Lean 4 中一个经过形式化验证的 DEFLATE 实现。
lean-zip 包含一个纯 Lean 的 DEFLATE 编码器和解码器,Lean 的内核会检查二者互为逆运算。我们已证明,对于任意可能的输入,压缩都不会损坏你的数据,并且该证明由 Lean 内核认证:
/-- 对 compress 的输出进行解压会返回原始数据,
对任意输入和任意压缩级别均成立。 -/
theorem zlib_decompressSingle_compress (data : ByteArray) (level : UInt8)
(maxOutputSize : Nat) (hsize : data.size ≤ maxOutputSize) :
ZlibDecode.decompressSingle (ZlibEncode.compress data level) maxOutputSize = .ok data
该定理建立在关于 DEFLATE 算法的更低层定理之上,即 inflate (deflateRaw data level) = .ok data,并依赖于 Zip/Spec/ 中约 32k 行证明里的 1,100 多个定理。其中没有 sorry,且 CI 会在每次改动时重新检查这些证明。
令人惊讶的是,无论是实现还是验证,都完全由监管较为宽松的 AI 编写:编码智能体认领 issue,在各自的 git worktree 中工作,并提交 pull request;除非往返证明仍然通过,否则这些 PR 无法合并。完整的开发历史,包括智能体所依据的计划、每次会话的进度日志和基准测试装置,都保存在 pre-split tag 中。
(简短版本,包括标题中的时间竞赛——lean-zip 压缩 212 MB 的 Silesia tar 比 miniz_oxide 更小且更快,级别 6 下为 4.57s 对 5.77s——见博客文章 “Why Lean is faster than Rust”。)
Silesia 语料库。
x = 压缩比(← 越小越好),y = 吞吐量(MB/s,对数刻度);每个编解码器的各压缩级别由其可达的混合前沿连接——即通过混合两个相邻级别可达到的压缩比/速度点——因此越靠左上越好,并且在匹配压缩比下进行比较才是诚实的(在这个对数轴上,直线段会夸大可达速度)。参考曲线固定在最终仪表盘上;红色曲线是纯 Lean 编解码器回放项目 git 历史中每一次仪表盘刷新,每帧一个提交,并为每个级别留下淡淡的轨迹。仪表盘冻结于 2026 年 8 月;完整方法、解码基准、逐文件热图和测试装置位于 lean-zip-benchmark 中,该图表的静态版本已提交在此处。
一旦正确性成为一条定理,你就可以雄心勃勃且激进地进行优化。加入惰性匹配,接入代价模型最优解析,在符号统计发生漂移的地方拆分块,将匹配器的链状态拆箱为扁平数组,把简洁的 fold 换成逐字比较器,而义务 inflate (deflate x) = x 要么仍然成立,要么构建变红。优化无法悄悄牺牲正确性,因为这里的正确性不是对某些输入进行采样的测试套件;它是内核坚持要求的关于所有输入的陈述。
这使得优化工作可以安全地交给机器。lean-zip 的很大一部分,包括那张图背后几乎所有的性能工作,都是由自主工作的编码智能体编写的,而且除非往返证明仍然通过,否则 PR 无法合并。证明就是棘轮。
而且它奏效了。在上图中,我们看到 lean-zip 的性能(红色原生曲线)。注意 y 轴是对数刻度,因此垂直差距是乘性的速度因子。在匹配压缩比下比较(Silesia 上的等文件几何平均),lean-zip:
这个编解码器最初比图表上的其他所有东西都慢得多——上面的动画回放了这一攀升过程,每次一个仪表盘刷新。差距的缩小并非源于某个聪明的人类洞见,而是源于一长串小的、逐个验证的步骤。这就是 Gwern 的 “Lean software scaling laws” 背后的赌注:可形式化验证的语言可能从更差的基线开始,但扩展性更好,因为经过验证的代码是自动化优化可以安全复利的基底。
作者欣然承认自己在性能工作方面是个业余者,而这正是重点:她不必成为专家,只需让证明保持绿色。如果你知道如何让 DEFLATE 更快,证明正等着接住你的错误;非常欢迎贡献。
require "kim-em" / "lean-zip"
该编解码器是纯 Lean:不需要系统库。
import Zip
-- Zlib 格式(RFC 1950)
let compressed := Zip.Native.ZlibEncode.compress data (level := 6)
let original ← IO.ofExcept (Zip.Native.ZlibDecode.decompress compressed)
-- Gzip 格式(RFC 1952,兼容 gzip/gunzip)
let gzipped := Zip.Native.GzipEncode.compress data (level := 6)
let original ← IO.ofExcept (Zip.Native.GzipDecode.decompress gzipped)
-- 原始 DEFLATE(RFC 1951,无头部/尾部)
let deflated := Zip.Native.deflateRaw data (level := 6)
let original ← IO.ofExcept (Zip.Native.InflateBuf.inflate deflated)
级别 0 输出存储(未压缩)块;级别 1(最快)到 10(精确的动态规划最优解析)进行压缩,高于 10 的级别按 10 处理。每个解码器都接受一个 maxOutputSize 上限(默认 1 GiB)作为 zip 炸弹防护;与典型的 C API 不同,没有无限制模式——0 表示零字节。
CRC-32 和 Adler-32 也有经过验证的实现(Zip.Native.Crc32、Zip.Native.Adler32),每个都证明与其规范相等。
Zip/Native/:纯 Lean 实现
Zip/Spec/:形式化规范和正确性证明
ZipTest/:原生实现的单元测试
conformance/:仅开发用的子包,用于针对系统 zlib 测试原生编解码器(通过 lean-zlib)——翻译验证以及双向 RFC 互操作,外加一个确定性模糊测试装置
c/:四个小的临时原语(字大小的读取、原地复制),Lean 核心尚未暴露这些。每个都有一个纯 Lean 参考实现;证明是关于参考实现的,并且信任 C 实现与其匹配(在运行时由一致性扫描进行交叉检查)。总之
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。