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 k44mr23808398yhg.16.1431405734178; Mon, 11 May 2015 21:42:14 -0700 (PDT) X-Received: by 10.140.99.44 with SMTP id p41mr175043qge.3.1431405734134; Mon, 11 May 2015 21:42:14 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!peer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!j5no6766045qga.1!news-out.google.com!t92ni327qga.1!nntp.google.com!j5no6766044qga.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Mon, 11 May 2015 21:42:14 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=87.91.37.131; posting-account=hya6vwoAAADTA0O27Aq3u6Su3lQKpSMz NNTP-Posting-Host: 87.91.37.131 References: <2430252d-52a1-4609-acef-684864e6ca0c@googlegroups.com> <0a718b39-ebd3-4ab5-912e-f1229679dacc@googlegroups.com> <9ee5e186-5aaa-4d07-9490-0f9fdbb5ca18@googlegroups.com> <87tww5296f.fsf@adaheads.sparre-andersen.dk> <871tj9dp5b.fsf@theworld.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <5f0cdb00-27de-4f2d-ae84-8a0a1a199200@googlegroups.com> Subject: Re: {Pre,Post}conditions and side effects From: vincent.diemunsch@gmail.com Injection-Date: Tue, 12 May 2015 04:42:14 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Received-Bytes: 3329 X-Received-Body-CRC: 1034178428 Xref: news.eternal-september.org comp.lang.ada:25829 Date: 2015-05-11T21:42:14-07:00 List-Id: Oops, my message was incomplete :=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 ver= ification > 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 out= =20 > > that, given an array A and two indices i /=3D j in the proper range, th= e new=20 > > array I get from A by swapping A(i) and A(j) (without changing any of t= he=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; 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~); 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