提问人:ZihaoZhang 提问时间:11/4/2023 更新时间:11/6/2023 访问量:43
如何解决 Dafny 中 let-such-that 表达式中的未确定问题?
how to solve the undetermined issue in a let-such-that expression in Dafny?
问:
下面是一个示例:
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”吗?有什么方法可以获取集合中的元素吗?
答:
0赞
James Wilcox
11/4/2023
#1
在低于 4.0 的 Dafny 版本中,表示 .因此,您应该将函数标记为 .function
ghost function
ghost
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
:|
上一个:MongoDB 查找集差异
评论