CODEWITHSUNDEEP
insertinductionformal-verificationloop-invariantdafny
pmpc
pmpc

Reputation: 493

Dafny insert method, a postcondition might not hold on this return path

I have an array "line" which has a string contained in it of length "l" and an array "nl" which has a string contained in it of length "p". Note: "l" and "p" don't necessarily have to be the length of each correspondent array.The parameter "at" will be position where the insertion will be made inside "line". Resuming: An array of length "p" will be inserted into "line", moving all chars of "line" between position (at,i,at+p),'p' positions to the right in order to make the insertion.

My logic for the ensures is to check if the elements inserted in "line" have the same order and are the same that the chars contained in "nl".

Here is the code:

method insert(line:array<char>, l:int, nl:array<char>, p:int, at:int)
  requires line != null && nl != null;
  requires 0 <= l+p <= line.Length && 0 <= p <= nl.Length ;
  requires 0 <= at <= l;
  modifies line;
  ensures forall i :: (0<=i<p) ==> line[at+i] == nl[i]; // error
{
  var i:int := 0;
  var positionAt:int := at;
  while(i<l && positionAt < l)
    invariant 0<=i<l+1;
    invariant at<=positionAt<=l;
  {
    line[positionAt+p] := line[positionAt];
    line[positionAt] := ' ';
    positionAt := positionAt + 1;
    i := i + 1;
  }

  positionAt := at;
  i := 0;
  while(i<p && positionAt < l)
    invariant 0<=i<=p;
    invariant at<=positionAt<=l;
  {
    line[positionAt] := nl[i];
    positionAt := positionAt + 1;
    i := i + 1;
  }
}

Here are the errors that i am receiving.

Thanks.

Upvotes: 2

Views: 2529

Answers (1)

lexicalscope
lexicalscope

Reputation: 7328

I suspect that your algorithm is not correct, because it does not seem to take into account the fact that shifting the characters starting at position at by p places might write them over the end of the string in line.

My experience has been that in order to be successful with verification

  1. Good standards of code development are crucial. Good variable naming, code formatting, and other code conventions are even more important than usual.
  2. Writing code that is logically simple is really helpful. Try to avoid extraneous extra variables. Try to simplify arithmetic and logical expressions wherever practical.
  3. Starting with a correct algorithm makes verification easier. Of course, this is easier said than done!
  4. It is often helpful to write out the strongest loop invariants you can think of.
  5. Working backwards from the postcondition is often helpful. In your case, take the postcondition and the negation of the final loop condition - and use these to work out what the invariant of the final loop must be in order to imply the postcondition. Then work backwards from that to the previous loop, etc
  6. When manipulating arrays, using a ghost variable which contains the original value of the array as a sequence is very often an effective strategy. Ghost variables do not appear in the compiler output so will not effect the performance of your program.
  7. It is often helpful to write down assertions for the exact state of the array, even if the postcondition only requires some weaker property.

Here is a verified implementation of your desired procedure:

// l is length of the string in line
// p is length of the string in nl
// at is the position to insert nl into line
method insert(line:array<char>, l:int, nl:array<char>, p:int, at:int)
  requires line != null && nl != null
  requires 0 <= l+p <= line.Length // line has enough space
  requires 0 <= p <= nl.Length // string in nl is shorter than nl
  requires 0 <= at <= l // insert position within line
  modifies line
  ensures forall i :: (0<=i<p) ==> line[at+i] == nl[i] // ok now
{
  ghost var initialLine := line[..];

  // first we need to move the characters to the right
  var i:int := l;
  while(i>at)
    invariant line[0..i] == initialLine[0..i]
    invariant line[i+p..l+p] == initialLine[i..l]
    invariant at<=i<=l
  {
    i := i - 1;
    line[i+p] := line[i];
  }

  assert line[0..at] == initialLine[0..at];
  assert line[at+p..l+p] == initialLine[at..l];

  i := 0;
  while(i<p)
    invariant 0<=i<=p
    invariant line[0..at] == initialLine[0..at]
    invariant line[at..at+i] == nl[0..i]
    invariant line[at+p..l+p] == initialLine[at..l]
  {
    line[at + i] := nl[i];
    i := i + 1;
  }

  assert line[0..at] == initialLine[0..at];
  assert line[at..at+p] == nl[0..p];
  assert line[at+p..l+p] == initialLine[at..l];
}

http://rise4fun.com/Dafny/ZoCv

Upvotes: 3

Related Questions