在 Dafny 中，如何修复除法的 "value does not satisfy the subset constraints of 'nat'" 错误？

Question

method Div(n: nat, d: nat) returns (q: nat)
  requires d > 1
{
  q := n / (d - 1);
}

产生此错误：

Dafny 2.1.1.10209
stdin.dfy(4,9): Error: value does not satisfy the subset constraints of 'nat'

Dafny program verifier finished with 0 verified, 1 error

第4行第9列是/符号，表示除法。

断言 d - 1 != 0 没有帮助。

这个错误是什么意思？我怎样才能说服 Dafny 这没关系？

Answer 1

我认为问题是(d - 1)的类型是int。

这修复了它：

let d1: nat = d - 1;
q := n / d1;

我对这段代码的意图是所有操作都应该是 nat 算术运算。达夫尼有其他想法。这是我认为正在发生的事情（提前推测）：

Dafny 有一个初始类型推理过程发生在之前证明者运行。该算法无法使用断言和前提条件；它只会对它们进行类型检查。 "know" 不能保证 d - 1 为正，甚至 d > 1.
所以对于 Dafny 的类型检查器来说，当 d 是 nat 时，d - 1 必须是 int。 nat减去nat的结果可能是负数。
鉴于此，这个程序的类型是否正确并不明显。但没关系！ Dafny 的类型推断正好可以推迟对这一点的判断。它允许 n / (d - 1) 在这里用作 nat，并注明让证明者检查 n / (d - 1) 的值确实保证落在 nat 中其类型的子集 int.
令人惊讶的是，证明者无法处理这个问题。我通过更改 return 类型进行检查，以便类型检查顺利通过：
```
method Div(n: nat, d: nat) returns (q: int)
  requires d > 1
  ensures q >= 0
{
  q := n / (d - 1);
}
```
果然，Dafny 2.1.1.10209 无法证明后置条件。

Answer 2

错误消息表明 Dafny 无法证明分配给 q 的值确实是 nat，这是 q 类型所要求的。这很奇怪，因为您的股息和除数都是非负数。验证者通常非常擅长线性算术，但您的示例超出了线性算术（因为除数不是文字常量），然后验证者更加古怪。

玩弄它，我的猜测是分母中的减法以某种方式进行了预处理，这使得验证者很难应用它对非线性除法的了解。我能够通过给术语 d - 1 一个名称来找到解决方法，如下所示：

method Div(n: nat, d: nat) returns (q: nat)
  requires d > 1
{
  var y := d - 1;
  q := n / y;
}

鲁斯坦

在 Dafny 中，如何修复除法的 "value does not satisfy the subset constraints of 'nat'" 错误？

In Dafny, how can I fix the "value does not satisfy the subset constraints of 'nat'" error on division?

formal-verification

integer-division

dafny