如何在 bubblesort 示例中调用 dafny 中的引理？

Question

如何调用引理作为相等为真的推理。考虑以下 dafny 中的示例，其中我创建了一个引理来表示从 0 到 n 的总和是 n 选择 2。Dafny 似乎可以毫无问题地证明这个引理。我想用那个引理说 bubblesort 中的交换次数有一个从 0 到 n 的总和的上限，这相当于 n 选择 2。在这种情况下，我目前在尝试说它是引理为真。为什么会发生这种情况，我怎么能在给定引理的情况下说相等性为真？

method BubbleSort(a: array?<int>) returns (n: nat) 
  modifies a
  requires a != null
  ensures n <= (a.Length * (a.Length - 1))/2
{
    var i := a.Length - 1;
    n := 0;
    while (i > 0)
      invariant 0 <= i < a.Length
       {
        var j := 0;
        while (j < i)
          invariant j <= i
          invariant n <= SumRange(i, a.Length)
          {
            if(a[j] > a[j+1])
              {
                a[j], a[j+1] := a[j+1], a[j];
                n := n + 1;
              }
              j := j + 1;
          }
          i := i -1;
      }
    assert n <= SumRange(i, a.Length) == (a.Length * (a.Length - 1))/2 by {SumRangeNChoose2(a.Length)};
    assert n <= (a.Length * (a.Length - 1))/2
}

function SumRange(lo: int, hi: int): int
  decreases hi - lo
{
  if lo == hi then hi
  else if lo >= hi then 0
  else SumRange(lo, hi - 1) + hi
}

lemma SumRangeNChoose2(n: nat)
  ensures SumRange(0, n) == (n * (n - 1))/2
{}

Answer 1

您只是遇到了语法错误。在 BubbleSort 的倒数第二行 } 之后不应有分号。此外，应该在下一行的断言之后有一个分号。

修复语法错误后，代码中还有一些更深层次的错误，如缺少不变量等。但它们都可以使用中对你的其他问题的注释来修复。

如何在 bubblesort 示例中调用 dafny 中的引理？

How to invoke lemma in dafny in bubblesort example?

bubble-sort

assertion

dafny