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=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=unavailable autolearn_force=no version=3.4.4
X-Received: by 10.236.105.196 with SMTP id k44mr26918245yhg.16.1431442426535;
 Tue, 12 May 2015 07:53:46 -0700 (PDT)
X-Received: by 10.140.34.182 with SMTP id l51mr213896qgl.8.1431442426488; Tue,
 12 May 2015 07:53:46 -0700 (PDT)
Path: 
 border1.nntp.dca1.giganews.com!nntp.giganews.com!z60no6852518qgd.0!news-out.google.com!t92ni337qga.1!nntp.google.com!z60no6852517qgd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Tue, 12 May 2015 07:53:46 -0700 (PDT)
In-Reply-To: <5f0cdb00-27de-4f2d-ae84-8a0a1a199200@googlegroups.com>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com;
 posting-host=143.117.250.151;
 posting-account=Jzt5lQoAAAB4PhTgRLOPGuTLd_K1LY-C
NNTP-Posting-Host: 143.117.250.151
References: <2430252d-52a1-4609-acef-684864e6ca0c@googlegroups.com>
 <AnYlw.957256$Rp.242412@fx23.iad>
 <0a718b39-ebd3-4ab5-912e-f1229679dacc@googlegroups.com>
 <wccoaqucn51.fsf@shell01.TheWorld.com>
 <9ee5e186-5aaa-4d07-9490-0f9fdbb5ca18@googlegroups.com>
 <alpine.CYG.2.11.1412231747100.4196@WIL414CHAPIN.vtc.vsc.edu>
 <wccegrpq2om.fsf@shell01.TheWorld.com>
 <87tww5296f.fsf@adaheads.sparre-andersen.dk>
 <871tj9dp5b.fsf@theworld.com>
 <ce4af31e-d491-479f-a5b3-0b3eedea2a68@googlegroups.com>
 <midvq5$2u3$1@loke.gir.dk> <alpine.DEB.2.11.1505071103310.14859@debian>
 <migc9a$jp8$1@loke.gir.dk> <alpine.DEB.2.11.1505072052570.16448@debian>
 <mijen0$1hj$1@loke.gir.dk> <alpine.DEB.2.11.1505111113020.12062@debian>
 <c6a5c672-9e37-4d2b-b313-1f2139fffc66@googlegroups.com>
 <5f0cdb00-27de-4f2d-ae84-8a0a1a199200@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <709f632c-7e94-4b89-b392-f1ff444ad2e3@googlegroups.com>
Subject: Re: {Pre,Post}conditions and side effects
From: johnscpg@googlemail.com
Injection-Date: Tue, 12 May 2015 14:53:46 +0000
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Xref: number.nntp.giganews.com comp.lang.ada:193150
Date: 2015-05-12T07:53:46-07:00
List-Id: <comp.lang.ada>

On Tuesday, May 12, 2015 at 5:42:14 AM UTC+1, vincent....@gmail.com wrote:
> Oops, my message was incomplete :=20
>=20
> Le lundi 11 mai 2015 23:49:50 UTC+2, vincent....@gmail.com a =E9crit=A0:
> > Hello Stefan,
> >=20
> > The correct way of proving is to use SYMBOLIC COMPUTATION : you assume
> > basic facts on proof function and then let the solver infer that your v=
erification
> > condition extracted from the code is correct.=20
> >=20
> > >.................... Recently, when trying to write=20
> > > a sorting procedure in SPARK, the prover has been unable to figure ou=
t=20
> > > that, given an array A and two indices i /=3D j in the proper range, =
the new=20
> > > array I get from A by swapping A(i) and A(j) (without changing any of=
 the=20
> > > values A(k) for k not in {i,j}), is a permutation of A. I haven't yet=
=20
> > > solved the problem.
> >=20
> > It was easy in Spark 2005 :
> >=20
> > --# function Perm (A, B : Array_Type) return Boolean;
>=20
> procedure Swap (T : in out Array_Type; I,J : Index_Type)
> --# derives T from T, I, J;
> --# post T(I) =3D T~(J) and T(J) =3D T~(I) and Perm (T, T~);
>=20
> Then in the body of Swap :
> > --# assume Perm ( T~ [ I =3D> T~(J); J =3D> T~(I) ],  T~);
> >=20
> > Then you can prove that A is a permutation of B by
> > proving that A results from a sequence of permutations
> > of two elements, starting with B. It is the case in all sorting
> > algorithm that I know (QuickSort, HeapSort, etc.).
> >=20
> > Maybe you can also do that using "Ghost functions" in Spark 2014.
> >=20
> > Regards,
> >=20
> > Vincent

Claire Dross has a post on this .. sounds relevant but
I'm not sure!

http://www.spark-2014.org/entries/detail/manual-proof-in-spark-2014

J.