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.3 required=5.0 tests=BAYES_00,INVALID_MSGID, MSGID_RANDY autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,14f7200925acb579 X-Google-Attributes: gid103376,public From: Robert Dewar Subject: Re: No Go To's Forever! Date: 2000/03/29 Message-ID: <8bu48a$3tt$1@nnrp1.deja.com>#1/1 X-Deja-AN: 604076973 References: <8bbsc6$aes$1@nnrp1.deja.com> <8bdbof$t19$1@nnrp1.deja.com> <38E1F6D5.8303903C@dowie-cs.demon.co.uk> <874s9p7jwi.fsf@deneb.cygnus.argh.org> X-Http-Proxy: 1.0 x28.deja.com:80 (Squid/1.1.22) for client 205.232.38.14 Organization: Deja.com - Before you buy. X-Article-Creation-Date: Wed Mar 29 23:39:56 2000 GMT X-MyDeja-Info: XMYDJUIDrobert_dewar Newsgroups: comp.lang.ada X-Http-User-Agent: Mozilla/4.61 [en] (OS/2; I) Date: 2000-03-29T00:00:00+00:00 List-Id: In article <874s9p7jwi.fsf@deneb.cygnus.argh.org>, Florian Weimer wrote: > Martin Dowie writes: > > > one of the reasons I had always been told for avoiding using gotos, was > > that it makes a program unprovable. a) was this true; > > No. I disagree as per previous note > > > and if so, b) is this still true? > > No. I disagree as per previous node >Why should it have changed, BTW? Becauswe proof of correctness techniques have improved! > One of the standard textbooks in computer science uses gotos > quite > heavily, and it contains correctness proofs. Although the proofs are > not "formal", informal proofs are a long way from proof of correctness. For formal proof of correctness you need a formal specification of the language, and that formal specification is definitely made much more complex by the inclusion of a general goto statement. > and neither is the algorithm description, they are more > substantial than the "formal" proofs which I've seen at the > local CS department. I have no idea what substantial means in this respect, but a formal proof of correctness of a program is a rather definite process, involving typically the use of a program to resolve proof obligations (have a look for example at the Praxis tools in this area). > BTW: What does "formal program verification" mean in practice? It means a formal proof of semantic equivalence of a program with a form spec, where the languages are formally defined. > I was told that it must involve quantifiers and other fancy > stuff. Well there is nothing "fancy" about a quantifier. Certainly most proof of correctness techniques make use of predicate algebra and set theory, and other simple basic mathematics. > Is this true, or are rigid, but non-formal proofs considered > sufficient I have no idea what a "rigid" proof might be. Any non-formal proof is suspect. For example, it is infeasible to prove any program written in Ada 95 as such, due to a lack of a formal definition of the semantics of Ada 95. Praxis uses a well defined (i.e. formally defined) subset of the language for its proof arena. > (i.e. proofs whose formalization is easy, but tedious work, > and which would result in proofs nobody could understand). It is not really important if a human can understand a proof, if all proof obligations have been satisfied algorithmicly using a verifier. > After attending some CS > courses, I should probably know it, but our formal program verification > exercises where quite a nightmare (for example, we should prove the > correctness of an implementation without having the specification). Obviously that's not quite right as stated, the concept of total correctness requires a specification of what correct means. On the other hand, you can prove certain properties of a program without a spec, e.g. that it terminates for all inputs, or that it cannot raise an exception etc. > Sent via Deja.com http://www.deja.com/ Before you buy.