递减参数（什么是程序固定点）

Question

考虑以下固定点：

Require Import Coq.Lists.List.
Import ListNotations.

Inductive my_type: Type:=
| Left: my_type
| Right: my_type
.

Fixpoint decrease (which: my_type) (left right: list my_type) : list my_type :=
match which with
| Left =>
  match left with
  | [] => []
  | a::tl => decrease a tl right
  end
| Right =>
  match right with
  | [] => []
  | a::tl => decrease a left tl
  end
end.

Coq 拒绝以下固定点，因为它无法猜测递减的固定点（有时 left 列表失去了它的头部，有时它是 right 那个）。

这个表明可以通过使用 Program Fixpoint 并指定 {measure ((length left)+(length right))}.

来解决这个问题

我的问题是：

常规 Fixpoint 和 Program Fixpoint 有什么区别？
是否可以在常规 Fixpoint 中显式减少参数？
Next Obligation 目标是什么？

Answer 1

Coq 中的 Fixpoint 命令使用 Coq 的原语 fix 构造递归函数，它检查结构递归以确保终止。这是 Coq 中唯一的递归，所有其他技术最终都会脱糖成某种 fix。

Program Fixpoint 是 Program, which allows writing definitions in a slightly extended language that are then compiled into Coq definitions. Program Fixpoint accepts any recursive function, generates an appropriate proof obligation that shows the function terminates (by decreasing some measure of its arguments on each recursive subcall), and then packages up the definition and termination proof into a Coq definition that structurally decreases an argument. If that sounds magical it basically is, but CPDT 的一个特性，很好地解释了如何进行这种编码。
是的，您可以添加一个 {struct arg} 注释来明确指定 哪个参数在结构上递减 ：Fixpoint decrease (which: my_type) (left right: list my_type) {struct right} : list my_type。这对您的示例没有帮助，因为您的函数通常不会在结构上减少任何一个参数。所有原始 fix 构造都有一个 struct 注释，但 Coq 通常可以在您编写 Fixpoint 时自动推断它。例如，这里是 Nat.add:
```
Nat.add = 
  fix add (n m : nat) {struct n} : nat :=
  match n with
  | 0 => m
  | S p => S (add p m)
  end : nat -> nat -> nat
```
你从 Next Obligation 和 Program Fixpoint 得到两种类型的目标：首先，每个子调用都有一个较小的参数（使用 measure，"smaller"是使用 < on nats 定义的），其次，"smaller" 关系是有根据的；也就是说，它没有无限递减的越来越小的对象序列。我不确定为什么 Program Fixpoint 不会自动为 Nat.lt 执行此操作，因为它应该知道相关定理。请注意，Program 具有比更一般的递归更多的功能，因此它还可以生成与这些功能相关的其他目标，具体取决于您编写的定义。

递减参数（什么是程序固定点）

Decreasing argument (and what is a Program Fixpoint)

termination

coq

totality