SPARK - an idea for high integrity data structures

[Phil Thornley <phil.jpthornley@gmail.com>]

I have had a hobby project for a while to create SPARK versions of
data structures, supported by partial proofs of correctness.

However, if the proofs are tackled in the most obvious way then the
effort required to show that the relevant data structure invariant is
maintained by each operation grows out of all proportion to the size
of the code being proved, and it would be easier to validate the code
directly than to validate all the proof artefacts (annotations and
rules) that are generated for the proof.

So I have recently tried an alternative approach that shows some
potential for completing the proofs without requiring disproportionate
effort.

The idea is to determine, for each path through an operation that
exports a value of the data structure, the relationship between the
imported value and exported value and to create a single proof rule
that encapsulates that transformation.  If the rule proves the
postcondition VC generated for the path then the code implements the
transformation.

This is clearly a less rigorous approach than proving that the code
maintains all the individual conditions within the invariant, but it
is much more practicable.

As an example of this approach I have completed the proofs for an
ordered list of integers and put this up on http://www.sparksure.com
(I have included a stack and a queue as well, but neither of these
require data structure invariants).

I am very interested in all comments that anybody might have about
this idea - either here on cla or via the email address on the
website.

Phil Thornley