CODEWITHSUNDEEP
sortingassertswapproofdafny
dafny
dafny

Reputation: 1

Dafny sorting using swap proof

I need to prove this sorting algorithm using Dafny:

method SomeSort(a: array<int>, A: multiset<int>)
    {
    var i := 0;
    while i != a.Length
    {
        var j := 0;
        while j != a.Length
        {
            if a[i] < a[j]
            {
                a[i], a[j] := a[j], a[i]; // swap
            }
            j := j+1;
        }
        i := i+1;
    }
}

I tried to do the following asserts, and the assert after the swap is problematic (Error: assertion might not hold). I need to use lemmas to make it work.. can anyone help me understand how to prove it?

predicate Sorted(q: seq<int>)
{
    forall i,j :: 0 <= i <= j < |q| ==> q[i] <= q[j]
}

predicate Inv(q: seq<int>, i: nat, A: multiset<int>)
{
    i <= |q| && Sorted(q[..i]) && multiset(q) == A
}

method {:verify true} SomeSort(a: array<int>, ghost A: multiset<int>)
    requires multiset(a[..]) == A
    ensures Sorted(a[..])
    ensures multiset(a[..]) == A
    modifies a
{
    var i := 0;
    while i != a.Length
        invariant Inv(a[..],i,A) 
        decreases a.Length-i
    {
        var Vi0 := a.Length-i;
        var j := 0;
        while j != a.Length
            invariant Inv(a[..],j,A)
            decreases a.Length-j 
        {
            var Vj0 := a.Length-j;
            assert Inv(a[..],j,A);
            assert Vj0 == a.Length-j;
            assert j != a.Length;
            if a[i] < a[j]
            {
                assert Inv(a[..],j,A);
                assert Vj0 == a.Length-j;
                assert j != a.Length;
                a[i], a[j] := a[j], a[i]; // swap
                **assert j+1 < a.Length;**
                assert Inv(a[..],j+1,A);
                assert 0 <= a.Length-(j+1) < Vj0;
            }
            assert Inv(a[..], j+1, A);
            assert 0 <= a.Length-(j+1) < Vj0;
            j := j+1;
            assert Inv(a[..], j, A);
            assert 0 <= a.Length-j < Vj0;
        }
        ...
        i := i+1;

    }
}

thanks in advance :)

Upvotes: 0

Views: 376

Answers (1)

Mika&#235;l Mayer
Mika&#235;l Mayer

Reputation: 10701

It's great to see you work out a proof! When any Dafny proof fails, I heavily recommend following this guide https://dafny.org/dafny/DafnyRef/DafnyRef#sec-verification-debugging to figure out what is wrong. I followed it for your code, and ended up founding something strange: At the end of your inner loop according to your code, the following should hold: assert Inv(a[..], a.Length, A); So that means your array would be sorted after only 1 inner loop, meaning the outer loop is useless.

I don't know how to prove the code otherwise. I've seen this sort algorithm recently, and it's very likely the proof is not obvious.

Upvotes: 1

Related Questions