为什么这个 FStar 函数不被接受？

Question

我想了解为什么不接受此函数作为终止函数：

val while_items: ni: nat -> ni_max: nat -> nw: nat -> bool
let rec while_items ni ni_max nw = 
  (if   ni < ni_max 
   then while_items (ni + nw) ni_max nw 
   else true)

FStar 拒绝并发送以下消息：

（错误）无法证明此递归调用的终止：求解器找到了一个（部分）反例...

这里的绑定问题可能与我在

下的相关问题中的绑定问题不同

FStar能给出反例吗？

Answer 1

此函数不会在所有输入上终止。考虑 ni < ni_max 和 nw=0。不幸的是，F* 没有找到像这样的具体反例。

您可以证明函数终止的一个变体，但您必须明确告诉 F* 什么在减少。在这里，我们在 nat.

上使用有根据的排序

let as_nat (x:int) : nat = if x < 0 then 0 else x
val while_items: ni: nat -> ni_max: nat -> nw: nat{ni < ni_max ==> nw > 0} -> Tot bool
                 (decreases (as_nat (ni_max - ni)))
let rec while_items ni ni_max nw =
  (if   ni < ni_max
   then while_items (ni + nw) ni_max nw
   else true)

Answer 2

如 the tutorial 中所述，默认情况下 F* 使用递减度量，将所有参数按字典顺序排列

val while_items: ni: nat -> ni_max: nat -> nw: nat -> Tot bool (decreases %[ni,ni_max;nw])

这对于证明此函数终止不起作用，因为显然 ni + nw 不小于 ni。

通过正确的减少措施和 nw 为正的先决条件，这确实会通过：

val while_items: ni: nat -> ni_max: nat -> nw: pos ->
  Tot bool (decreases (if ni < ni_max then ni_max-ni else 0))

不完全是原始示例，但那个示例肯定会永远循环 nw=0！无论如何，即使在这个修复之后，这段代码也没有什么意义，而且使用这样的循环对于函数式编程来说并不是惯用的。

最后，F*无法产生反例，最近修复了这个错误信息：https://github.com/FStarLang/FStar/pull/2075

为什么这个 FStar 函数不被接受？

Why isn't this FStar function accepted?

fstar