Re: SPARK - an idea for high integrity data structures

[Matteo Bordin <matteo.bordin@gmail.com>]

Hi Phil,

you may be interested in having a look at Hi-Lite:

http://www.open-do.org/projects/hi-lite/

and in particular this discussion:

http://lists.forge.open-do.org/pipermail/hi-lite-discuss/2010-June/000129.html

Cheers,

Matteo



On Jul 20, 2:40 pm, Phil Thornley <phil.jpthorn...@gmail.com> wrote:
> 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 onhttp://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