通过两个实现对阶乘程序进行 Coq 验证

Question

我是 coq 的新手，我正在尝试验证 factorial 程序的功能。

根据我的理解，我应该做的是遵循标准的Hoare Logic范式，从前置条件出发，计算循环不变量，推理后置条件。像这样：

{{ X = m }} 
{{  FOL 1 }}
Y ::= 1;;
{{  FOL 2   }}
WHILE !(X = 0) DO  
    {{ FOL 3    }}
    Y ::= Y * X;;
    {{ FOL 4   }}
    X ::= X - 1
   {{ FOL 5  }}
END
{{ FOL 6 }}
{{ Y = m! }}

这里是 "first order logic" 的 FOL 个标准。

然而，令我意外的是，似乎在用coq验证factorial程序时，通常的做法是定义如下两个函数fact和fact_tr:

Fixpoint fact (n:nat) :=
match n with
| 0 => 1
| S k => n * (fact k)
end.

Fixpoint fact_tr_acc (n:nat) (acc:nat) :=
match n with
| 0 => acc
| S k => fact_tr_acc k (n * acc)
end.

Definition fact_tr (n:nat) :=
fact_tr_acc n 1.

并在未来证明这两个函数的等价性：

Theorem fact_tr_correct : forall n:nat,
fact_tr n = fact n.

我从here and 那里学到了这种方法。

所以这是我的问题：

有人可以说明这种 "equality-based" 验证方法背后的动机吗？它们在概念上仍然类似于基于 Hoare Logic 的标准推理吗？
不过，我可以使用 coq 来验证 factorial 程序遵循基于 "standard" Hoare logic 的方法的正确性吗？通过指定前置条件、后置条件和归纳推理整个程序来说。

Answer 1

请注意 Coq 程序的底层语言属于 (dependently-typed) 函数式 语言家族，而不是命令式语言。大致上，没有状态和语句，只有表达式。

"equality-based" 方法背后的动机是 简单的 功能程序可以作为规范。 fact 当然很简单——Coq 通过其基本递推关系代表 definition of factorial。换句话说，fact 是一个参考实现，即在这种情况下，它显然是正确的实现。而 fact_tr_acc 是一个优化的，其正确性与我们希望建立的规范有关。

是的，你仍然可以验证命令式factorial程序的正确性。例如。 Software Foundations series shows how to encode imperative programs in Coq and verify their correctness using Hoare logic. See, in particular, the factorial exercise.

通过两个实现对阶乘程序进行 Coq 验证

Coq verification of factorial program through two implementations

functional-programming

coq

verification