如何在方法的预执行和post-执行状态之间建立联系？

Question

我有以下 zaMap（请在此处查看完整代码：http://rise4fun.com/Dafny/LCaM）：

class zaMap {
  var busybits :array<bool>;
  var keys : array<int>;
  var values : array<int>;

  predicate wellformed ()
    reads busybits, keys, values, this
  {
    busybits != null && keys != null && values != null &&
    keys != values &&
    busybits.Length == keys.Length &&
    keys.Length == values.Length
  }

  // ... more predicates and methods follow


  method put(k : int, v : int) returns (success : bool)
    requires wellformed()
    modifies busybits, keys, values
    ensures !success ==> full()
    ensures success ==> mapsto(k, v)
  {
    var i := findEmpty();
    if (i < 0)
    {
      success := false;
      return;
    }
    assert !busybits[i];
    busybits[i] := true;
    keys[i] := k;
    values[i] := v;
    success := true;
  }
//...

现在我想为 put 方法添加更多规范。例如，我想 ensure，如果 return 值是 success == true，那么在函数调用之前映射是 !full()，或者等效地，如果映射不是 full()，保证put那里。

问题是，在前提条件"requires"中我还不知道它会是什么return，在后置条件"ensures"中我没有原始地图了。人们会怎么做？

Answer 1

您可以使用 old 关键字。让我们看一个例子。以下方法将包含元素 x 的数组的所有位置设置为零，其余部分保持原样。这是代码：

method setToZero(a: array<int>, x : int )
requires a != null;
modifies a;
ensures forall i :: 0 <= i < a.Length && old(a[i]) == x ==> a[i] == 0;
ensures forall i :: 0 <= i < a.Length && old(a[i]) != x ==> a[i] == old(a[i]);
{
  var j := 0;
  while (j < a.Length)
  invariant 0 <= j <= a.Length;
  invariant forall i :: 0 <= i < j && old(a[i]) == x ==> a[i] == 0;
  invariant forall i :: 0 <= i < j && old(a[i]) != x ==> a[i] == old(a[i]);
  invariant forall i :: j <= i < a.Length ==> a[i] == old(a[i]);
   {
    if (a[j] == x) {
      a[j] := 0;
    }
    j := j + 1;
  }
}

如何在方法的预执行和post-执行状态之间建立联系？

How to formulate a connection between pre-execution and post-execution state of a method?

verification

dafny