Dafny: Added Dafny solutions to the VSComp 2010 problems

1 files changed, 79 insertions, 0 deletions

diff --git a/Test/VSComp2010/Problem2-Invert.dfy b/Test/VSComp2010/Problem2-Invert.dfy
new file mode 100644
index 00000000..63da4cb5
--- /dev/null
+++ b/Test/VSComp2010/Problem2-Invert.dfy
@@ -0,0 +1,79 @@
+// VSComp 2010, problem 2, compute the inverse 'B' of a permutation 'A' and prove that 'B' is

+// indeed an inverse of 'A' (or at least prove that 'B' is injective).

+// Rustan Leino, 31 August 2010.

+//

+// In the version of this program that I wrote during the week of VSTTE 2010, I had

+// used a lemma (stated as a ghost method) that I proved inductively (using a loop and

+// a loop invariant).  Here, I have simplified that version by just including an

+// assertion of the crucial property, which follows from the surjectivity of 'A'.

+//

+// The difficulty in proving this program with an SMT solver stems from the fact that

+// the quantifier that states the surjectivity property has no good matching trigger

+// (because there are no function symbols mentioned in the antecedent of that quantifier,

+// only built-in predicates).  Therefore, I introduced a dummy function 'inImage' and

+// defined it always to equal 'true'.  I can then mention this function in the crucial

+// assertion, which causes the appropriate triggering to take place.

+//

+// A slight annoyance is that the loop's modifications of the heap, which is checked

+// to include only the elements of 'B'.  Since 'A' and 'B' are arrays stored at different

+// locations in the heap, it then follows that the elements of 'A' are not modified.

+// However, the fact that the heap has changed at all makes the symbolic expressions

+// denoting the elements of 'A' look different before and after the heap.  The

+// assertion after the loop (which, like all assertions, is proved) is needed to

+// connect the two.

+

+method M(N: int, A: array<int>, B: array<int>)

+  requires 0 <= N && A != null && B != null && N == |A| && N == |B| && A != B;

+  requires (forall k :: 0 <= k && k < N ==> 0 <= A[k] && A[k] < N);

+  requires (forall j,k :: 0 <= j && j < k && k < N ==> A[j] != A[k]);  // A is injective

+  requires (forall m :: 0 <= m && m < N && inImage(m) ==> (exists k :: 0 <= k && k < N && A[k] == m));  // A is surjective

+  modifies B;

+  ensures (forall k :: 0 <= k && k < N ==> 0 <= B[k] && B[k] < N);

+  ensures (forall k :: 0 <= k && k < N ==> B[A[k]] == k && A[B[k]] == k);  // A and B are each other's inverses

+  ensures (forall j,k :: 0 <= j && j < k && k < N ==> B[j] != B[k]);  // (which means that) B is injective

+{

+  var n := 0;

+  while (n < N)

+    invariant n <= N;

+    invariant (forall k :: 0 <= k && k < n ==> B[A[k]] == k);

+  {

+    B[A[n]] := n;

+    n := n + 1;

+  }

+  assert (forall i :: 0 <= i && i < N ==> A[i] == old(A[i]));  // the elements of A were not changed by the loop

+  // it now follows from the surjectivity of A that A is the inverse of B:

+  assert (forall j :: 0 <= j && j < N && inImage(j) ==> 0 <= B[j] && B[j] < N && A[B[j]] == j);

+}

+

+static function inImage(i: int): bool { true }  // this function is used to trigger the surjective quantification

+

+method Main()

+{

+  var a := new int[10];

+  a[0] := 9;

+  a[1] := 3;

+  a[2] := 8;

+  a[3] := 2;

+  a[4] := 7;

+  a[5] := 4;

+  a[6] := 0;

+  a[7] := 1;

+  a[8] := 5;

+  a[9] := 6;

+  var b := new int[10];

+  call M(10, a, b);

+  print "a:\n";

+  call PrintArray(a);

+  print "b:\n";

+  call PrintArray(b);

+}

+

+method PrintArray(a: array<int>)

+  requires a != null;

+{

+  var i := 0;

+  while (i < |a|) {

+    print a[i], "\n";

+    i := i + 1;

+  }

+}