提问人:MogicFrog 提问时间:8/9/2023 最后编辑:MogicFrog 更新时间:8/15/2023 访问量:53
Dafny 逐个函数未能证明正确的后置条件
Dafny function-by-method fails to prove correct post-conditions
问:
我的代码只包含子句,但我需要旅行一些集合。根据官方文档,我使用代码来旅行我的集合:function
var node_set := tree_nodes(t);
var result := 0.0;
while node_set != {}
decreases |node_set|
// some invariants here, omitted
{
// some statements here, omitted
}
但是我想用类型保留我的代码,所以我从这里使用。
使代码看起来像function
function-by-method
function tree_height(t: Tree) : (h: real)
// some ensures here, omitted
{
match t
case Empty => 0.0
case Node(_, _, _, _, _) =>
// code omitted here
}by method{
match t
case Empty =>
{
h := 0.0;
return;
}
case Node(_, _, _, _, _) =>
{
// code to travel sets omitted here
h := result;
return;
}
}
但达夫尼表示,后期条件无法维持。但是,我将两个部分(函数体和方法体)拆分在一起,例如
function tree_height(t: Tree) : (h: real)
// some ensures here, omitted
{
match t
case Empty => 0.0
case Node(_, _, _, _, _) =>
// code omitted here
}
和
method test(t: Tree) returns (h: real)
// some ensures here, omitted
{
match t
case Empty =>
{
h := 0.0;
return;
}
case Node(_, _, _, _, _) =>
{
// code omitted here
h := result;
return;
}
}
这样,函数和方法都通过了验证。函数体和方法体中的语句与逐个方法的语句相同。
有人知道为什么吗?
还是一些旅行方式?function
现在我找到了另一个简单的例子,它也有同样的问题:
function setToSequence(s: set<int>) : (r: seq<int>)
ensures multiset(s) == multiset(r)
{
[]
} by method{
var copy := s;
r := [];
while copy != {}
decreases |copy|
{
var k: int :| k in copy;
r := r + [k];
copy := copy - {k};
}
}
method t(s: set<int>) returns (r: seq<int>)
{
var copy := s;
r := [];
while copy != {}
decreases |copy|
{
var k: int :| k in copy;
r := r + [k];
copy := copy - {k};
}
}
答:
by-method 子句旨在添加函数的有效实现(请注意,自 Dafny 4 以来,函数默认是非幽灵的)。函数部分和方法部分应该给出相同的结果。这就是达芙妮所抱怨的。在 setToSequence 中,函数部分仅生成 [],这通常与方法部分生成的不相同。这回答了您为什么不验证的问题。
这与你访问场景中所有元素的方式(在场景中旅行)有关吗?部分地。您的技术与:|操作员很好。然而,它是不确定的。结果是 setToSequence 的函数和方法部分(几乎)永远不会给出相同的结果。我不认为可以在这里使用逐个方法的函数声明。除非你通过对元素进行排序来提出一个确定性的定义,但这将是不切实际的,并且有效的方法定义的想法将被击败。相反,您可以使用单独的定义并添加一个引理,说明它们产生相同的多集(但不是相同的序列)。
关于树的更大例子,这让我感到困惑。当树被反射时,节点的node_depth可能会发生变化。例如,请参阅以下验证代码。
var u := Node(3, Empty, Empty);
var t := Node(1, Node(2, u, Empty), u);
assert node_depth(t, u) == 2.0;
var t' := Node(1, u, Node(2, u, Empty));
assert node_depth(t', u) == 1.0;
由于两棵树的max_depth_node都是 u,因此 t 的树高为 2.0,而 t' 的高度为 1.0。这不是人们对树高定义的期望。因此,我没有进一步研究这个例子。
评论
t
t'
评论