From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD,
	FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,6941f5cd4f1d4739
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII
Path: 
 g2news1.google.com!postnews.google.com!y13g2000yqa.googlegroups.com!not-for-mail
From: Matteo Bordin <matteo.bordin@gmail.com>
Newsgroups: comp.lang.ada
Subject: Re: SPARK - an idea for high integrity data structures
Date: Tue, 20 Jul 2010 07:33:02 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: 
 <1a490b86-e9cf-46c4-8f2e-3d633b51fa50@y13g2000yqa.googlegroups.com>
References: 
 <9ac8feb3-5b79-41b1-a124-df211039c1bc@c10g2000yqi.googlegroups.com>
NNTP-Posting-Host: 212.99.106.125
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1279636382 5097 127.0.0.1 (20 Jul 2010 14:33:02
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Tue, 20 Jul 2010 14:33:02 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: y13g2000yqa.googlegroups.com; posting-host=212.99.106.125;
	posting-account=0fK-ZgoAAACswzEJSZ3LA9AZ4FnRU7mX
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.2.6)
	Gecko/20100625 Firefox/3.6.6 (.NET CLR 3.5.30729),gzip(gfe)
Xref: g2news1.google.com comp.lang.ada:12482
Date: 2010-07-20T07:33:02-07:00
List-Id: <comp.lang.ada>

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.h=
tml

Cheers,

Matteo



On Jul 20, 2:40=A0pm, 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. =A0If 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