Rocq 证明器是一种交互式证明助手,用于表述数学定义、为计算系统编写规约,以及构造可由计算机检验的证明。它原名 Coq,将依赖类型编程语言、证明开发环境和检验证明有效性的内核结合在一起。其主要用途包括数学的形式化、编程语言理论研究,以及软件的形式验证。
该系统以归纳构造演算为基础。在这一逻辑框架中,命题可以表示为类型,证明则表示为具有相应类型的项。用户通常通过称为“策略”的命令间接构造这些项,再由内核检验最终结果。这种分离设计既支持复杂的自动化,又无须将每一种证明搜索过程都视为逻辑有效性的可信来源。
Rocq 源于法国在 20 世纪 80 年代开展的研究,支持过的项目涵盖四色定理、奇数阶定理,以及经验证的编译和密码软件。它的重要性不仅在于这些成果,也在于它提供了可复用的方法,将精确规约、可执行程序与数学证明联系起来。
起源、发展及从 Coq 到 Rocq 的更名
Rocq 起源于法国 Inria 开展的类型论与交互式定理证明研究,最初以 Coq 为名,于 1984 年开始开发。Thierry Coquand 和 Gérard Huet 提出了构造演算,为该系统的逻辑基础提供了重要支撑;Christine Paulin-Mohring 则在引入归纳定义方面发挥了核心作用。这些进展将逻辑基础研究与构建实用的计算机化证明环境这一实际任务联系起来。
构造演算在一个紧凑的形式框架中融合了高阶函数、依赖类型和多态性。在此基础上加入归纳构造后,定义常见的数学对象和计算对象就方便了许多,例如自然数、列表、语法树,以及由推理规则描述的关系。这一点十分重要,因为证明助手不仅需要表达能力强大的基础演算,还需要直接支持在实际证明中反复出现的各种结构。
在 20 世纪 90 年代和 21 世纪头十年,Coq 逐步发展出更丰富的规约语言、更强的自动化能力、模块机制,以及规模可观的库生态。Yves Bertot 和 Pierre Castéran 于 2004 年出版的《交互式定理证明与程序开发》(Interactive Theorem Proving and Program Development)一书,记录了一套当时已相当成熟的、将形式化数学与程序验证相结合的方法。后续发展还包括更强大的隐式推断机制、类型类、宇宙多态性,以及可扩展的证明自动化机制。
大型应用影响了系统的演进。Georges Gonthier 于 2005 年完成的四色定理形式化证明表明,一项重要的计算机辅助数学论证可以在证明助手内部重建。Xavier Leroy 的 CompCert 项目则展示了如何利用同一环境,支持构建一个具有实际用途且经过验证的编译器。围绕这些工作发展起来的数学库,也改变了用户组织抽象与自动化机制的方式。
项目于 2024 年宣布更名为 Rocq,并在 2025 年以新名称发布了 9.0 版。Rocq 是 Coq 的延续,而非一个与之无关的证明助手,因此,早期的论文、书籍、库和证明成果仍然是理解它的重要基础。在迁移过程中,Coq 时代的命令、软件包名称和术语可能继续保留,因此,这个历史名称仍广泛出现在其生态系统中。
该系统主要以 OCaml 实现,并作为开源软件发布。参与开发的维护者和贡献者来自研究机构及更广泛的用户社区。与其他历经长期发展的语言实现一样,对精化处理、库和自动化机制的改动都需要注意兼容性,因为证明脚本可能依赖底层数学定理之外的实现细节。
逻辑基础与依赖类型
Rocq 的核心逻辑是归纳构造演算,这是一种带类型的演算,在 λ演算的基础上加入了依赖积、归纳定义和宇宙层级。其核心组织原则是柯里—霍华德对应:命题对应于类型,证明对应于项。要证明命题 ,用户需要构造一个项 ,使类型判断 得到系统认可。
在这种解释下,蕴含具有函数类型的结构。 的证明是一个函数,它将 的证明映射为 的证明。全称量化则用依赖积表示:
该类型的项将类型 的每个对象 映射为 的证明。合取、析取和存在量化可以用归纳定义的命题表示,其构造子规定了如何引入证明。因此,证明规则成为对带类型的项进行的普通操作,而不再是独立于这些操作之外的一层非形式化论证。
依赖类型允许类型引用某个值。例如,向量类型可以记录其长度:由三个自然数组成的向量与由四个自然数组成的向量便具有不同的类型。这使得规格能够通过构造本身排除某些无效状态。一个拼接长度分别为 和 的向量的函数,可以返回长度为 的向量;这一关系直接体现在函数的类型中,而不只是写在文档里。
Rocq 区分不同的逻辑类,其中主要包括用于命题的 Prop,以及用于计算数据和数学数据的 Type 宇宙层级。宇宙层级可防止不受限制的自指,避免由此导致类型系统不一致。粗略地说,如果一个类型属于某个宇宙,那么该宇宙本身就属于更高一层的宇宙。精化器会自动处理许多宇宙约束,而显式的宇宙控制机制则为高级库设计提供支持。
默认逻辑是构造性的。对于任意命题,系统并不自动提供排中律 的一般性证明。经典逻辑原则可以被显式假定,也可以通过库引入,但对这些原则的使用会成为定理逻辑依赖的一部分。同样的区别也适用于函数外延性等原则;函数外延性将对每个输入都给出相同结果的函数视为相等。
这一基础并不意味着每个合式命题都是可判定的。它提供的是用于陈述命题的精确语言,以及可供检查的证明表达方式。发现证明仍可能需要深刻的人类洞见,而有些断言无法从选定的一组假设中证明。该逻辑框架将这些问题与一个范围更窄的任务区分开来:检查所给出的证明是否遵循规则。
定义、计算与规约
其主要规约语言传统上称为 Gallina,将带类型的函数式编程与陈述命题的机制结合起来。用户可以定义常量、函数、归纳数据类型和关系。这些定义可以描述可执行的算法、抽象数学结构,或另一种编程语言的语义。因此,同一个环境可以同时容纳程序、程序的预期行为,以及将二者联系起来的证明。
归纳定义通过构造子来规定对象。自然数有表示零和后继的构造子;列表有表示空列表和向列表添加元素的构造子。Rocq 会根据归纳声明提供分类讨论和归纳推理的原理。归纳定义的关系在描述判断时也起着类似作用:求值关系可以描述表达式如何执行,而类型关系可以描述哪些程序符合某种语言的类型系统。
函数通常通过模式匹配和递归来定义。为了保持预期的逻辑性质,递归定义必须满足终止性条件。结构递归函数通常会对输入中可识别的某个子组成部分调用自身,例如列表的尾部。更复杂的算法则可以采用良基递归,以某种递减关系为递归调用提供依据。余归纳定义支持可能无限延续的行为,但余递归构造必须满足守卫性条件。
计算直接参与证明检查。函数应用于参数、或对已知构造子进行模式匹配等表达式,都可以按照演算规则进行归约。如果这些计算得到相同结果,两个类型就可能被判定为定义相等。这不同于命题相等,后者本身是一条需要证据的陈述。要高效地使用 Rocq 编程,很大一部分工作就是合理组织定义,使有用的等式能够通过计算成立。
例如,如果加法对第一个参数进行递归,那么只需展开定义,就能直接得到等式 。而等式 通常需要对 进行归纳。这两个陈述在数学上的对称性,并不意味着它们具有相同的计算行为。这类选择会影响证明的长度、自动化程度,以及后续接口的使用便利性。
规约不必将每一项性质都纳入依赖类型。一个形式化开发项目可以定义普通函数,再单独证明其正确性;也可以返回一个值,并同时附上该值满足某个谓词的证据。模块和抽象接口也可以通过声明的定律来隐藏实现。这些风格各有取舍:更强的类型能够更早地防止误用,而独立的正确性定理则可能使程序更容易执行、提取,或与常规软件集成。
交互式证明、策略与自动化
典型的证明始于一个定理陈述,以及一个包含若干假设和一个或多个目标的交互式证明状态。策略用于变换这一状态。有些策略引入变量或假设;另一些则应用已有引理、拆分合取命题、进行分类讨论或运用归纳法。执行完毕的策略脚本会生成一个可由内核检查的证明项。因此,脚本是构造证明依据的方法,而不只是非形式化推理过程的记录。
下面这个简短的例子展示了定义、归纳法与自动化之间的联系:
Theorem add_zero_right : forall n : nat, n + 0 = n.
Proof.
intro n.
induction n as [| n IH].
- reflexivity.
- simpl. rewrite IH. reflexivity.
Qed.
这里,intro 引入被量化的自然数,induction 生成基础情形和后继情形,IH 则是归纳假设的名称。化简展开加法的递归结构,随后通过重写,利用归纳假设替换相应的子表达式。最后的等式通过计算即可成立。
传统的策略语言 Ltac 允许用户利用模式匹配、回溯以及对证明状态的控制来组合证明过程。Ltac2 则提供了另一种方案,采用结构更清晰的语言和类型约束。这些机制支持为特定库或应用定制可复用的自动化过程。项目只需将反复出现的证明模式编码一次,就不必在数百个引理中重复底层步骤。
内置及库提供的自动化工具可处理多种不同任务。auto 等策略利用假设和已注册的引理搜索证明。lia 处理线性整数算术中适用的目标。ring 对所支持的代数结构中的多项式表达式进行规范化,而 field 则处理适用的有理表达式等式,并生成相应的附加条件。这些都是专用过程,而不是解决任意数学问题的通用机制。
一种影响尤为深远的方法是反射式证明。这种方法不为每一个细小的计算步骤构造冗长的推导,而是在形式化开发中先证明一个关于检查过程的一般性定理,再对当前问题的表示运行该过程。例如,多项式表达式是否相等,可以归约为其规范化表示是否相等。推理的可信性来自一般性的正确性证明和经过检查的计算。
自动化既有收益,也有工程成本。大范围的证明搜索可能速度缓慢,也可能对可用引理的变化十分敏感。依赖自动生成的名称或化简过程中的偶然结果的脚本,可能变得脆弱。结构化的证明语言和精心设计的引理接口能够减少这些依赖。与主要围绕自主搜索设计的自动定理证明系统不同,Rocq 将交互、领域专用过程和显式的证明架构视为同一工作流程中相互补充的组成部分。
内核检查、假设与信任范围
Rocq 将证明构造与证明检查分离。语法解析、记号、隐式参数推断、策略和插件让系统易于使用,而内核则负责验证核心声明。它检查证明项是否具有所声称的类型、归纳声明是否满足必要条件,以及定义是否符合演算系统的规则。与完整的交互环境相比,这种设计将逻辑上的信任集中在一个更小的组件中。
当自动化过程复杂时,这一区分尤为重要。策略可能因编程错误而失败、陷入循环,或产生不合适的候选证明。不过,如果策略提供的是普通证明项,那么仍须由内核接受该证明项,定理才能成立。因此,证明搜索中的错误并不必然意味着逻辑可靠性存在错误。对于会扩大受信任检查机制范围的扩展或执行路径,则需要另行考量。
不过,可信计算基的范围并不止于对内核的抽象描述。实际的检查依赖于内核的实现、所用的编译器和运行时,以及执行它的硬件。对于优化后的求值机制和接入的外部工具,也需要关注其结果如何得到确证。小型内核缩小了关键逻辑机制的范围,却不能据此断言整个计算平台都不会存在缺陷。
假设也是信任边界的一部分。Rocq 允许使用显式公理,这在基于特定原理研究某种理论,或将某个组件与其环境分离时可能很有用。同样,以 Admitted 结束一个尚未完成的证明,留下的是一项假设,而不是给出推导。Print Assumptions 等命令有助于查看某个定理所依赖的假设。仅仅出现 Qed 并不能说明一项形式化开发不含公理,因为其证明可能使用了先前假定的命题。
还必须区分一致性与是否切合实际需求。即使一个定理完全通过了检查,它所形式化的也可能是错误的需求。关于处理器数学模型的证明,本身并不能表明某个具体的物理处理器实现了该模型。经过验证的协议仍可能依赖某些环境假设或对手假设,而这些假设在部署时未必成立。这些属于规约与建模问题,而非内核检查的失误。
对编译后的形式化开发成果进行独立检查,可以提供额外的验证步骤;Rocq 生态中就有一个传统上称为 coqchk 的独立检查器。这类检查无须重新执行原始策略脚本,即可检验形式化产物。它无法消除所有共同依赖的实现层面假设,但进一步凸显了可重复验证的证明对象与最初构造它的交互过程之间的区别。
库、代数结构与可复用的形式化知识
Rocq 的实际应用范围在很大程度上取决于库。基础库提供自然数、整数、列表、有限映射等常见对象,以及算术方面的基本结论。更大型的库则提供数学理论、程序逻辑、语义模型和自动化工具。复用之所以重要,是因为新的证明很少仅从底层演算出发:即使是关于某个算法的一条简短命题,也可能依赖数百个定义和引理。
数学组件是与 Rocq 密切相关、最具影响力的数学生态系统之一。它源于大型形式化证明的相关工作,尤其是四色定理和奇数阶定理项目。其各个库围绕精心设计的接口来组织有限结构、代数及相关数学内容。配套的 SSReflect 证明语言强调以可控方式变换证明状态,并注重计算与逻辑推理之间的紧密联系。
其中一项独特技术是小规模反射,它将逻辑命题与可计算的布尔测试系统地联系起来。对于适当的可判定性质,布尔判定过程可以提供便捷的计算接口,而反射引理则将其结果与相应命题关联起来。这样就能把有限搜索、分情况讨论与通常的数学论证结合起来,而不必反复重建这两种表示之间的联系。
代数结构的管理是另一个核心问题。同一个对象可能具有几种相互关联的结构:整数既构成加法群,也构成环,而域还具有彼此相容的运算及相应定律。典范结构使 Rocq 能够根据上下文推断出某些带结构的对象。类型类则提供了另一种确定结构化参数的机制。这些机制的推断行为各不相同,库对机制的选择会影响记号、精化过程,以及扩展之间的组合方式。
其他重要的库面向不同领域。Coquelicot 围绕广义极限及相关构造发展实分析。Flocq 对浮点运算进行形式化,其中包括与 IEEE 754浮点运算标准有关的性质。Iris 提供了一个高阶并发计算分离逻辑框架,支持对共享可变状态的程序进行模块化推理。Verified Software Toolchain 则提供工具和程序逻辑,结合 CompCert 的语义基础设施来验证 C 程序。
库之间并不会自动实现互操作。两个项目可能以不同方式定义实数,采用不同的有限映射接口,或依赖不同的逻辑假设。即使数学对象彼此等价,也可能需要大量衔接工作。因此,库的架构设计不只是收集正确的引理,还需要稳定的命名、明确的依赖关系、兼容的抽象,以及有关计算的约定。
这些问题使库的维护成为形式化工作的重要组成部分。接口的变化可能影响许多下游证明,而设计良好的抽象则能让实现和证明自动化机制不断演进,同时不必修改用户的定理陈述。
形式化数学与里程碑式证明
Rocq 已被用于重构一些数学论证;这些论证因规模庞大或涉及大量计算,难以用传统方式核查。形式化用证明检查器可以检验的定义和推导,取代非形式化的推理链。这并不意味着不再需要数学判断:选择定义、寻找合适的引理以及管理抽象层次,仍然是核心工作。不过,形式化确实能让论证中的缺漏和隐含的依赖关系更容易显现出来。
四色定理指出,任何平面地图都可以用至多四种颜色着色,使共用一段边界的区域颜色不同。肯尼斯·阿佩尔和沃尔夫冈·哈肯于 1976 年借助大量计算机计算证明了这一定理。乔治·贡捷在本杰明·维尔纳的重要贡献下,于 2005 年完成了该定理的形式化证明,在 Coq 中重构了后来提出的一种组合数学证明方法。这项工作的一大成就,是将大规模计算与严谨且经过核验的数学论证衔接起来,而不是把独立程序的输出当作充分证据。
奇数阶定理由沃尔特·费特和约翰·G. 汤普森于 1963 年证明,指出每个奇数阶有限群都是可解群。贡捷领导的团队于 2012 年完成了该定理的形式化,并于 2013 年公开发表了相关文献。与一个简短、独立的定理不同,这个项目需要为有限群论及其所依赖的代数知识建立庞大的基础设施。它表明,在大规模形式化工作中,可复用的库和设计规范的数学接口至关重要。
这些项目展现了计算所扮演的不同角色。在四色定理中,经过验证的有限情形检查是处理大量情形的关键。在奇数阶定理中,主要挑战则是如何组织漫长而抽象的论证。两者都需要精确的编码,但在证明工程上面临的问题有所不同。定理证明器必须兼顾计算归约和概念性的数学结构,而不能只偏重其中一种方式。
Rocq 也成为同伦类型论的重要研究环境。这一领域的研究将类型解释为空间,将等式证明解释为路径,从而为数学基础提供了新的思路。2013 年出版的《同伦类型论》一书,也伴随着大量使用 Coq 开展的形式化工作。相关库可能会扩充底层假设,例如引入单价性公理,因此必须区分这些库所采用的基础设定与系统的默认逻辑。
形式化往往会揭示,一个看似初等的命题,其实依赖于如何处理相等性、商对象、有限性或表示方式等问题。反过来,一旦将这些选择系统地组织成库,后续定理的陈述和复用就可能变得更容易。由此得到的成果不仅是某个结论的证明凭证,更是一套明确呈现的数学基础设施,后续工作可以在此之上继续构建。
经过验证的软件、编译与可执行程序提取
在软件验证中,Rocq 用于定义程序行为,并证明实现满足指定的性质。这些性质涵盖功能正确性(即产生所需结果)、内存安全、不同实现之间的精化关系,以及可观察行为的保持。证明针对的是经过精确建模的程序及其环境,因此,如何解读证明,取决于语义和规约涵盖了哪些内容。
由 Xavier Leroy 发起的 CompCert编译器 是一个突出的例子。它是一个经过验证的优化编译器,支持 C 语言中相当大的一部分。其核心成果证明了各编译阶段的语义保持性,在指定条件下,将源程序的行为与生成代码的行为联系起来。这项工作并非仅仅证明每项优化看起来合理,而是通过形式化确立的语义关系,将各项变换衔接起来。
编译器的正确性并不意味着编译出的每个程序都是正确的。编译器可能忠实地保留了某个程序的行为,但该程序本身却不符合其预期的应用需求。源语言中的未定义行为、与外部函数的交互,以及对执行过程的假设,也都会影响定理的适用范围。因此,CompCert 的成就虽然有明确的边界,却十分重要:它缩小了在源代码层面经过验证的论证与编译器生成的机器代码之间的差距。
Rocq 通过分离逻辑支持程序验证;分离逻辑能够以组合式的方式推理可变内存。Verified Software Toolchain 将这一方法应用于 C 语言,使规约能够描述内存区域的所有权以及所存储值之间的关系。这对于操作指针的代码尤其有用,因为证明不仅必须约束数值结果,还必须约束别名关系以及对已分配对象的访问。
从证明走向软件的另一条途径是程序提取。Rocq 可以将计算性定义转换为 OCaml 或 Haskell 等语言,同时擦除证明内容,以及提取过程判定为与计算无关的其他信息。这样就可以在开发程序的同时构建其正确性证明,随后在证明助手之外执行该程序。对于以函数式风格表达的算法,程序提取尤其自然。
提取所得软件的可信性基础与经过核验的定理并不相同。其执行还依赖于提取机制、目标语言的编译器和运行时,以及任何人工提供、用于替代所提取操作的实现。在源定义上确立的性质,并不会自动保证部署后的可执行程序在各个方面都得到验证,尤其是在引入外部代码或底层接口时。
密码学领域的工作提供了更多例子。Fiat Cryptography 使用形式化方法和代码生成技术,从数学规约推导算术运算的实现。相关工作还对协议安全性或概率算法进行推理。这类证明可以确立精确的代数性质或安全性质,但要抵御侧信道攻击,还需要额外的模型:仅有功能正确性,并不能证明执行时间、内存访问或功耗不会泄露秘密信息。
开发工具、局限性与研究方向
Rocq项目通常由包含定义、定理陈述和证明脚本的源文件,以及编译产物和构建元数据组成。在用户逐步浏览和执行文档时,交互式编辑器会显示当前的证明目标与系统响应。CoqIDE和基于Emacs的Proof General都是历史悠久的交互界面;基于语言服务器的工具(包括Rocq/Coq LSP生态系统)则支持与Visual Studio Code等编辑器集成。这些界面有助于查看和跟踪证明状态,但不能替代内核验证。
项目规模的开发工作不仅需要数学专长,也需要常规的软件工程实践。版本控制、自动化构建、依赖版本锁定和回归检查有助于确保证明的可复现性。通过opam进行的OCaml包管理,长期以来一直是分发证明助手及其库的重要方式。由于精化过程和策略的行为可能随版本变化,即使定理陈述在数学上没有改变,项目仍可能需要维护。
性能涉及多个方面。证明搜索可能开销很大;精化过程可能需要花费时间来解析隐式参数、结构实例和宇宙约束;证明检查也可能需要大量计算。庞大的证明项和编译产物会占用内存与存储空间。不透明定理声明、模块化接口和基于反射的方法可以降低某些特定开销,但工作流程中某一环节的改进并不一定能加快其他环节。
主要的局限并非表达能力不足,而是将非形式化问题转化为有效的形式化表示所需付出的努力。数据结构、归纳原理和抽象边界的选择,可能决定一个证明是否仍然易于处理。强大的自动化在发展成熟的领域内很有帮助,但新的论证往往需要新的引理和重新设计的定义。因此,学习该系统既涉及数学,也涉及理解其精化器和策略的行为。
Rocq是更广泛的证明助手领域中的一员,同属这一领域的还有Isabelle、HOL系列系统、Agda和Lean证明助手。这些系统在基础逻辑、计算的处理方式、自动化和库的组织与使用传统方面各不相同。在这些系统之间转换定理,并不只是更改语法:定义和逻辑假设可能有所不同,证明对象也可能依赖互不兼容的推理规则。因此,证明交换研究既关注数学含义,也关注底层的检查格式。
一个活跃的研究方向是利用机器学习和大语言模型来推荐引理、生成策略序列或引导搜索。系统架构中的关键区分依然不变:生成的文本只是候选证明,不能仅因看起来令人信服就成为正确性的证据。如果一个候选证明能够转化为经过完整检查的推导,Rocq就可以在该项目明确列出的假设之下验证它。选择恰当的规约、防止引入非预期的假设,以及评估定理是否准确刻画了预期问题,仍然是需要另行完成的任务。