CODEWITHSUNDEEP
dafny
Attila Karoly
Attila Karoly

Reputation: 1021

Dafny simple assertion does not hold

In exercise_1a what could be done to make the assertion cnt > 0 valid?

method exercise_1a(n: int)
    requires n > 0
{
    var idx := 0;
    var cnt := 0;

    while idx < n
        decreases n - idx
    {
        idx := idx + 1; 
        cnt := cnt + 1;
    }

    assert idx > 0; // valid
    assert cnt > 0; // *** invalid ***
}

Surprisingly, this version invalidates the assertion idx > 0, as well:

method exercise_1b(n: int)
    requires n > 0
{
    var idx := 0;
    var cnt := 0;

    while idx < n && cnt < n
        decreases n - idx
        decreases n - cnt
    {
        idx := idx + 1; 
        cnt := cnt + 1;
    }

    assert idx > 0; // *** invalid ***
    assert cnt > 0; // *** invalid ***
}

Upvotes: 2

Views: 785

Answers (1)

smithjonesjr
smithjonesjr

Reputation: 981

In your first snippet of code, when the while loop exits, all Dafny knows is that !(idx < n). Therefore, it can infer that idx > 0. However, Dafny doesn't know anything about the cnt variable at this point, so your second assertion fails.

In the second snippet of code, when the while loop exits, all Dafny is knows is that !(idx < n && cnt < n) (again, the negation of the condition on the while loop). This is equivalent to idx > n || cnt > n. From there, Dafny could infer idx > 0 || cnt > 0, but it wouldn't be able to prove either idx > 0 or cnt > 0 on its own.

To fix this, you need to add some relation between the variables cnt and idx that Dafny could check and then use.

    while idx < n && cnt < n 
        decreases n - idx 
        decreases n - cnt 
        invariant idx == cnt 
    {   
        idx := idx + 1;  
        cnt := cnt + 1;
    }

The extra invariant line tells Dafny check that idx == cnt will hold across every iteration of the loop, and then it can use that fact at the end. However, Dafny would not know to bring the fact idx == cnt under consideration unless you tell it to do so.

(As a side note, you'll see that Dafny is able to determine, on its own, that n > 0 holds at the end of the while loop, even while you don't specify it explicitly as in invariant. This is because n is not modified in the body of the while loop, so Dafny will automatically carry across the fact that n > 0 from the beginning.)

Upvotes: 3

Related Questions