如何解决 Dafny 中 let-such-that 表达式中的未确定问题?

how to solve the undetermined issue in a let-such-that expression in Dafny?

提问人:ZihaoZhang 提问时间:11/4/2023 更新时间:11/6/2023 访问量:43

问:

下面是一个示例:

function intsetmax(s:set<int>):int
  requires |s| > 0
  ensures  var m := intsetmax(s);
           m in s && forall i :: i in s ==> m >= i
{
  var x :| x in s;
  if |s| == 1 then
    assert |s - {x}| == 0;
    x
  else
    var sy := s - {x};
    var y := intsetmax(sy);
    assert forall i :: i in s ==> i in sy || i == x;
    if x > y then x else y
}

函数“intsetmax”想要在集合中查找 max 元素,但它显示一个错误“要编译,let-such-that 表达式的值必须唯一确定”,因为语句“var x :|x 在 s 中”。

此代码适用于低于 4.0 的 Dafny 版本,但它报告 4.0 错误。

那么,如何解决呢?我必须将函数设置为“ghost”吗?有什么方法可以获取集合中的元素吗?

设置 dafny 语言形式 方法

评论


答:

0赞 James Wilcox 11/4/2023 #1

在低于 4.0 的 Dafny 版本中,表示 .因此,您应该将函数标记为 .functionghost functionghost

0赞 redjamjar 11/6/2023 #2

就个人而言,我认为这是 Dafny 编译器中的一个错误(即您可以在 a 中编译这样的语句)。我假设该错误是在从 Dafny 3 切换到 Dafny 4 时引入的。在此处查看更多详细信息。method

评论

0赞 Rustan Leino 11/10/2023
不同之处在于,in a 是不确定的。这使得编译变得容易。函数必须是确定性的,所以如果你想编译,编译器必须确保你总是得到相同的值,这在运行时可能非常昂贵。有关详细信息,请参阅 easychair.org/publications/paper/dM:|method:|