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.182.219.225 with SMTP id pr1mr21612268obc.23.1431380988948;
        Mon, 11 May 2015 14:49:48 -0700 (PDT)
X-Received: by 10.140.33.100 with SMTP id i91mr150621qgi.41.1431380988812;
 Mon, 11 May 2015 14:49:48 -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!news.glorb.com!m20no10407463iga.0!news-out.google.com!t92ni321qga.1!nntp.google.com!z60no6732203qgd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Mon, 11 May 2015 14:49:48 -0700 (PDT)
In-Reply-To: <alpine.DEB.2.11.1505111113020.12062@debian>
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>
 <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>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c6a5c672-9e37-4d2b-b313-1f2139fffc66@googlegroups.com>
Subject: Re: {Pre,Post}conditions and side effects
From: vincent.diemunsch@gmail.com
Injection-Date: Mon, 11 May 2015 21:49:48 +0000
Content-Type: text/plain; charset=ISO-8859-1
Xref: news.eternal-september.org comp.lang.ada:25815
Date: 2015-05-11T14:49:48-07:00
List-Id: <comp.lang.ada>

Hello Stefan,

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 verification
condition extracted from the code is correct. 

>.................... Recently, when trying to write 
> a sorting procedure in SPARK, the prover has been unable to figure out 
> that, given an array A and two indices i /= j in the proper range, the new 
> array I get from A by swapping A(i) and A(j) (without changing any of the 
> values A(k) for k not in {i,j}), is a permutation of A. I haven't yet 
> solved the problem.

It was easy in Spark 2005 :

--# function Perm (A, B : Array_Type) return Boolean;
--# assume Perm ( T~ [ I => T~(J); J => T~(I) ],  T~);

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.).

Maybe you can also do that using "Ghost functions" in Spark 2014.

Regards,

Vincent