名称: coq-proof-assistant
描述: ‘协助Coq证明开发。使用场景: (1) 程序正确性证明, (2) 数学形式化, (3) 验证编译。’
版本: 1.0.0
标签:
- 证明助手
- coq
- 形式化验证
- 依赖类型
难度: 中级
语言:
- coq
依赖项: []
Coq 证明助手
协助Coq中的交互式证明开发。
使用时机
- 形式化验证
- 程序正确性证明
- 数学形式化
- 验证软件开发
此技能的功能
- 编写证明 - 交互式战术证明
- 构建理论 - 模块、部分
- 处理归纳 - 复杂归纳证明
- 验证 - 类型检查证明
基本战术
(* 基本证明结构 *)
定理 例子 : forall n : nat, n + 0 = n.
证明.
归纳 n.
- (* 基本情况: n = 0 *) 自反性.
- (* 归纳情况: n = S n' *)
简化.
重写 IHn.
自反性.
完成.
(* 常见战术 *)
- intros : 引入假设
- destruct : 案例分析
- induction : 归纳
- rewrite : 使用等式重写
- apply : 应用引理
- exact : 提供精确项
- reflexivity : 证明等式
- simpl : 简化
- unfold : 展开定义
- rewrite : 重写
- assert : 做断言
- remember : 记住表达式
- generalize : 对项泛化
实现示例
列表反转
(* 定义列表反转 *)
固定点 反转 {A : 类型} (l : 列表 A) : 列表 A :=
匹配 l 于
| 空 => 空
| 加入 x xs => 反转 xs ++ 加入 x 空
结束.
(* 证明正确性 *)
定理 反转正确 : forall A (l : 列表 A),
反转 (反转 l) = l.
证明.
归纳 l 为 [| x xs IH ].
- (* 基本情况: l = 空 *) 自反性.
- (* 归纳情况 *)
简化.
重写 <- IH.
重写 <- 应用关联.
简化.
自反性.
完成.
(* 带累加器的更高效版本 *)
固定点 反转追加 {A : 类型} (l 累加 : 列表 A) : 列表 A :=
匹配 l 于
| 空 => 累加
| 加入 x xs => 反转追加 xs (加入 x 累加)
结束.
定义 反转' {A : 类型} (l : 列表 A) := 反转追加 l 空.
引理 反转追加反转 : forall A (l 累加 : 列表 A),
反转追加 l 累加 = 反转 l ++ 累加.
证明.
归纳 l; 引入.
- 简化. 自反性.
- 简化. 重写 IHl. 重写 应用关联. 自反性.
完成.
二叉搜索树验证
(* BST 定义 *)
归纳 bst (键 : 集合) (R : 键 -> 键 -> 命题) : 键 -> 命题 :=
| bst空 : bst 键 R 空键
| bst节点 : forall k v l r,
bst 键 R l ->
bst 键 R r ->
(forall k', 在 键 l k' -> R k' k) ->
(forall k', 在 键 r k -> R k k') ->
bst 键 R k.
(* 插入保留BST *)
引理 bst插入保留 : forall 键 R (H: 严格序 R)
k v (t : bst 键 R k),
bst 键 R (插入 k v t).
证明.
归纳 t; 引入.
- 构造器; 自动.
- 析构 (比较决定 k0 k) 为 [H'|H'|H'].
+ (* k < k0: 在左侧插入 *)
构造器; 自动.
* 应用 IHt1; 自动.
* 引入. 应用 H1. 左; 自动.
+ (* k = k0: 替换 *)
构造器; 自动.
+ (* k > k0: 在右侧插入 *)
构造器; 自动.
* 应用 IHt2; 自动.
* 引入. 应用 H1. 右; 自动.
完成.
编译器验证
(* 简单表达式语言 *)
归纳 表达式 : 类型 :=
| E常量 : nat -> 表达式
| E加 : 表达式 -> 表达式 -> 表达式
| E变量 : nat -> 表达式.
(* 目标: 栈机器 *)
归纳 指令 : 类型 :=
| I推入 : nat -> 指令
| I加 : 指令
| I加载 : nat -> 指令.
定义 程序 := 列表 指令.
(* 编译器 *)
固定点 编译 (e : 表达式) : 程序 :=
匹配 e 于
| E常量 n => I推入 n :: 空
| E加 e1 e2 => 编译 e2 ++ 编译 e1 ++ I加 :: 空
| E变量 x => I加载 x :: 空
结束.
(* 编译器正确性 *)
归纳 栈 : 类型 := 栈 (l : 列表 nat).
归纳 执行 : 程序 -> 栈 -> 栈 -> 命题 :=
| 执行空 : forall s, 执行 空 s s
| 执行推入 : forall n s s',
s' = 栈 (n :: s.(l)) ->
执行 (I推入 n :: p) s s'
| 执行加 : forall n1 n2 s s',
s = 栈 (n2 :: n1 :: s'.(l)) ->
s' = 栈 (n1 + n2 :: s'.(l)) ->
执行 (I加 :: p) s s'.
引理 编译正确 : forall e s,
执行 (编译 e) s (栈 (评估 e :: s.(l))).
证明.
归纳 e; 引入; 简化.
- (* E常量 *) 构造器. 简化. 构造器.
- (* E加 *)
重写 IHe1, IHe2.
构造器. 自反性.
构造器. 自反性.
构造器.
- (* E变量 *) 构造器. 自反性.
完成.
高级战术
(* 自动化 *)
提示 解析 bst节点 bst空.
提示 构造器 bst 执行.
(* 自定义Ltac *)
Ltac 解决_ :=
匹配 目标 于
| [ H : ?P -> ?Q -> ?R |- ?R ] =>
让 H' := 新鲜 在
断言 (H' : P); [|断言 H0 : Q; [|精确 (H H' H0)]]
结束.
(* 复杂结构上的归纳 *)
引理 foo : forall l, P l.
证明.
归纳 l 为 [| x xs IHxs ].
- (* 空 *) ...
- (* 加入 *) ...
(* 在子项上使用IH *)
应用 IHxs.
(* 或在归纳前泛化 *)
泛化 依赖 l.
归纳 x; ...
完成.
(* 结构化大证明 *)
部分 我的部分.
变量 A : 类型.
引理 引理1 : P A.
证明. ... 完成.
引理 引理2 : Q A.
证明. ... 使用 引理1. ...
结束 我的部分.
关键战术参考
| 战术 |
描述 |
intros |
引入变量/假设 |
apply |
应用引理/假设 |
exact |
给出精确项 |
refine |
给出带孔项 |
destruct |
案例分析 |
induction |
归纳 |
rewrite |
重写等式 |
simpl |
简化 |
unfold |
展开定义 |
assert |
做断言 |
cut |
剪切引理 |
inversion |
反转 |
econstructor |
Eapply构造器 |
lia |
线性整数算术 |
omega |
Omega求解器 |
auto |
自动证明搜索 |
eauto |
急切自动 |
tauto |
经典重言式 |
congruence |
等式/同余 |
提示
- 从简单开始，增加复杂性
- 使用
Hint进行自动化
- 用部分结构化
- 使用命名假设
- 先证明引理
- 用
Check检查
相关技能
dependent-type-implementer - 类型理论llvm-backend-generator - 验证编译器hoare-logic-verifier - 验证
经典参考文献
| 参考 |
为何重要 |
| Bertot & Castéran, “交互式定理证明与程序开发” (2004) |
Coq的标准教材；全面的Coq开发 |
| Chlipala, “依赖类型下的认证编程” (2013) |
使用交互式证明的实用Coq开发技术 |
| Pierce et al., “软件基础” (2005-2020) |
在Coq中构建验证软件，卷1-6 |
| Coq证明助手参考手册 |
官方文档 |
| Gonthier & Werner, “四色定理的机器检查证明” (2008) |
大规模证明工程 |
权衡与限制
方法权衡
| 方法 |
优点 |
缺点 |
| 交互式（战术） |
灵活，大证明 |
需要专业知识 |
| 声明式 |
可读，可审计 |
较少自动化 |
| 嵌入式 |
可编程 |
较难维护 |
何时不使用Coq
- 对于简单属性：测试可能更便宜
- 对于自动化验证：考虑SAT/SMT求解器（z3, cvc5）
- 对于生产代码：考虑形式化方法工具（Frama-C, SPARK）
- 对于证明自动化：考虑Lean或Isabelle（更强大的自动化）
复杂性考虑
- 证明复杂性：随属性复杂性扩展；大证明需要结构
- 编译时间：大型开发可能需要数小时编译
- 导出：可提取到OCaml、Haskell、Scheme
限制
- 学习曲线：陡峭；需要理解依赖类型、战术
- 可扩展性：大证明可能变慢且难以维护
- 自动化：比SMT求解器少；需要手动指导
- 提取：代码提取必须验证正确性
评估标准
高质量Coq开发应具备：
| 标准 |
应关注 |
| 正确性 |
证明验证属性 |
| 可读性 |
清晰结构，良好命名 |
| 可维护性 |
易于修改 |
| 自动化 |
适当使用提示 |
| 提取 |
正确提取代码 |
| 性能 |
在合理时间内编译 |
质量指标
✅ 良好：健全证明，清晰结构，良好自动化
⚠️ 警告：不透明证明，命名不佳
❌ 不良：未证明断言，提取错误
研究工具与工件
Coq生态系统：
| 工具 |
学习内容 |
| Coq |
证明助手 |
| MathComp |
数学组件 |
| VST |
验证C |
研究前沿
1. 元编程
实现陷阱
| 陷阱 |
实际后果 |
解决方案 |
| 证明过时 |
更新后损坏 |
使用opam |