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.7 required=5.0 tests=BAYES_00,FREEMAIL_FROM, FREEMAIL_REPLYTO,REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,8bc4790fae14ac33 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit X-Received: by 10.180.75.137 with SMTP id c9mr3491637wiw.0.1366448568679; Sat, 20 Apr 2013 02:02:48 -0700 (PDT) Path: p18ni2407wiv.0!nntp.google.com!proxad.net!feeder1-2.proxad.net!usenet-fr.net!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!feeds.phibee-telecom.net!zen.net.uk!dedekind.zen.co.uk!reader02.nrc01.news.zen.net.uk.POSTED!not-for-mail From: Phil Thornley Newsgroups: comp.lang.ada Subject: Re: SPARK - divide algorithm issue Date: Sat, 20 Apr 2013 10:02:18 +0100 Message-ID: References: <957ef6e4-23d8-499f-ba19-20d32e82a7df@googlegroups.com> Reply-To: phil.jpthornley@gmail.com MIME-Version: 1.0 User-Agent: MicroPlanet-Gravity/3.0.4 Organization: Zen Internet NNTP-Posting-Host: f2a9a4dc.news.zen.co.uk X-Trace: DXC=;c5fPe@5Wk17SeeF=2_\U2]G;bfYi23h4=dR0\ckLKG0WeZ<[7LZNR6DO2GOE2lFC26JNOYoB;SJ>1>5DlN708X1Y=V>2D^>]Q2 X-Complaints-To: abuse@zen.co.uk Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Date: 2013-04-20T10:02:18+01:00 List-Id: In article <957ef6e4-23d8-499f-ba19-20d32e82a7df@googlegroups.com>, see.my.homepage@gmail.com says... > > Playing further with implementing division in SPARK, but this time an example from John Barnes book is causing problems: > > procedure Divide (M, N : in Integer; Q, R : out Integer); > --# derives Q, R from M, N; > --# pre M >= 0 and N > 0; > --# post (M = Q * N + R) and (R < N) and R >= 0; > > procedure Divide (M, N : in Integer; Q, R : out Integer) is > begin > Q := 0; > R := M; > loop > --# assert M = Q * N + R and R >= 0; > exit when R < N; > Q := Q + 1; -- here > R := R - N; > end loop; > end Divide; > > In this example SPARK cannot prove that the marked line (Q := Q + 1) is safe with respect to Integer'Last. What is most frustrating is that this is a book example, where it is claimed to verify OK. You should not expect too much of the SPARK Simplifier - there are many proveable VCs that it fails to prove and this is one of them: procedure_divide_5. H1: q * n + r <= 2147483647 . H2: n <= 2147483647 . H3: q * n + r >= 0 . H4: n > 0 . H5: r <= 2147483647 . H6: n <= r . H7: q >= - 2147483648 . H8: q <= 2147483647 . H9: integer__size >= 0 . -> C1: q <= 2147483646 . This can be proved by contradiction: if q >= 2147483647 then there is a contradiction with H1, H4 and H6 (remembering that n is integer). Victor/Alt-Ergo does prove this VC: ,divide,procedure,,,5,,true,0.016,,, No matter how good the proof tools are, there will probably always be some proveable VCs that they fail to prove in practicable time - so it's up to the analyst to distinguish these from unproveable ones. If you are using worked examples to help with understanding SPARK proof, you may find the proof tutorials at: http://www.sparksure.com helpful. (But these are now somewhat out-of-date with respect to the recent versions of SPARK, and particularly with respect to the change in the way return annotations are handled in the 2012 GPL version.) Cheers, Phil