Dafny 逐个函数未能证明正确的后置条件

Dafny function-by-method fails to prove correct post-conditions

提问人:MogicFrog 提问时间:8/9/2023 最后编辑:MogicFrog 更新时间:8/15/2023 访问量:53

问:

我的代码只包含子句,但我需要旅行一些集合。根据官方文档,我使用代码来旅行我的集合: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
      }

但是我想用类型保留我的代码,所以我从这里使用。 使代码看起来像functionfunction-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};
  }
}
函数 方法 设置 dafny

评论

1赞 James Wilcox 8/9/2023
如果你能发布一个完整的最小示例,你就更有可能获得帮助。我对问题可能是什么有一些想法,但如果没有一个完整的例子,我无法检查我的想法是否正确。
0赞 MogicFrog 8/9/2023
示例代码在这里。为了更好地理解,我还在这里添加了一些评论。

答:

1赞 Kees Huizing 8/15/2023 #1

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。这不是人们对树高定义的期望。因此,我没有进一步研究这个例子。

评论

0赞 MogicFrog 8/15/2023
谢谢你的回答。我完全理解。我发现解决这个问题的一种方法是将所有函数都改为幽灵函数,所以非确定性运算符:|可以使用。令人困惑的代码已被简化,因此其他部分被我删除了。实际上,这些树都是二进制搜索树,因此一个节点最多会出现一次。构造,在完整版本代码中是不允许的。tt'
0赞 Kees Huizing 8/15/2023
明白了。当所有节点都不同时,没有问题。事实上,随着:|在幽灵函数中,可以证明美好的事物。