在 Coq 中允许潜在的无限循环

Question

我请求你的帮助是因为我想知道是否可以允许在 Coq 中定义潜在的无限固定点，只是为了检查当前定义是否最终产生输出。

我已经尝试了新的 Unset Guard Checking 命令，我想禁用的正是减少参数检查（因为我实际上有错误 cannot guess decreasing argument of fix。

我知道在 Coq 中禁用这个特性有点遗憾，但这只是为了得到一个小的实用函数来检查当前定义是否正确，以确保提供一个递减的参数将在进一步开发中工作。

Answer 1

Unset Guard Checking 确实禁用递减参数检查。您可能必须明确指定您希望系统使用 {struct foo} 减少的参数，就像这个例子一样。

Unset Guard Checking.

Fixpoint y {A} (f : A -> A) {struct f} : A := f (y f).

但是，如果您没有充分的理由，定义可能无限函数的更好方法是添加一个参数以强制终止。

Fixpoint y_opt {A} (lim : nat) (f : A -> A) : option A :=
  match lim with
  | O => None
  | S lim' =>
    match y_opt lim' f with
    | None => None
    | Some x => Some (f x)
    end
  end.

在 Coq 中允许潜在的无限循环

Allow potentially infinite loops in Coq

recursion

functional-programming

coq

coqide