CODEWITHSUNDEEP
dafny
Attila Karoly
Attila Karoly

Reputation: 1021

Dafny rejects a simple postcondition

Below is a first attempt to prove various simple theorems, in this case about parity. Dafny /v. 1.9.9.40414/ verifies that adding 2 to an even number yields an even number but does not accept either of the commented out conditions.

function IsEven(a : int) : bool
requires a >= 0
{
    if a == 0 then      true 
    else if a == 1 then false 
    else                IsEven(a - 2)
}

method Check1(a : int)
requires a >= 0
ensures IsEven(a) ==> IsEven(a + 2)
//ensures IsEven(a) ==> IsEven(a + a)
//ensures IsEven(a) ==> IsEven(a * a)
{
}

As I have just started to study this wonderful tool, my approach or the implementation might be incorrect. Any advice would be appreciated.

Upvotes: 0

Views: 629

Answers (1)

James Wilcox
James Wilcox

Reputation: 5663

There are few different things going on here. I will discuss each of the three postconditions in turn.

The first and second postconditions

Since IsEven is a recursively defined predicate, in general, facts about it will require proofs by induction. Your first post condition is simple enough to not require induction, which is why it goes through.

Your second postcondition does require induction to be proved. Dafny has heuristics for automatically performing induction, but these heuristics are only invoked in certain contexts. In particular, Dafny will only attempt induction on "ghost methods" (also called "lemmas").

If you add the keyword ghost in front of method in Check1 (or change method to lemma, which is equivalent), you will see that the second postcondition goes through. This is because Dafny's induction heuristic gets invoked and manages to complete the proof.

The third postcondition

The third postcondition is more complex, because it involves nonlinear arithmetic. (In other words, it involves nontrivial reasoning about multiplying two variables together.) Dafny's underlying solver has trouble reasoning about such things, and so the heuristic proof by induction doesn't go through.

A proof that a * a is even if a is even

One way to prove it is here. I have factored out IsEven(a) ==> IsEven(a * a) into its own lemma, called EvenSquare. I have also changed it to require IsEven(a) as a precondition, rather than put an implication in the postcondition. (A similar proof also goes through with the implication instead, but using preconditions on lemmas like this instead of implications is idiomatic Dafny.)

The proof of EvenSquare is by (manual) induction on a. The base case is handled automatically. In the inductive case (the body of the if statement), I invoke the induction hypothesis (ie, I make a recursive method call to EvenSquare to establish that (a - 2) * (a - 2) is even). I then assert that a * a can be written as the sum of (a - 2) * (a - 2) and some offset. The assertion is dispatched automatically. The proof will be done if I can show that the right hand side of this equality is even.

To do this, I already know that (a - 2) * (a - 2) is even, so I first invoke another lemma to show that the offset is even, because it is twice something else. Finally, I invoke one last lemma to show that the sum of two even numbers is even.

This completes the proof, assuming the two lemmas.

Proofs of the two lemmas

It remains to show that twice anything is even, and that the sum of two even numbers is even. While not completely trivial, neither is as complex as EvenSquare.

The lemma EvenDouble proves that twice anything is even. (This is in fact a stronger version of your second postcondition. Your second postcondition says that doubling any even number is even. In fact, doubling any (non-negative, under your definition of evenness) number at all is even.) The proof of EvenDouble proceeds by (manual) induction on a. The base case is handled automatically. The inductive case only requires explicitly invoking the induction hypothesis.

The lemma EvenPlus is almost proved automatically by Dafny's induction heuristic, except that it trips over a bug or some other problem which causes a loop in the solver. After a little debugging, I determined that the annotation {:induction x} (or {:induction y}, for that matter) makes the proof not loop. These annotations tell Dafny's heuristics which variable(s) to try to induct on. By default in this case, Dafny tries to induct on both x and y, which for some reason causes the solver to loop. But inducting on either variable alone works. I'm investigating this problem further, but the current solution works.

Upvotes: 1

Related Questions