comp.lang.ada
 help / color / mirror / Atom feed
From: Robert Dewar <robert_dewar@my-deja.com>
Subject: Re: No Go To's Forever!
Date: 2000/03/29
Date: 2000-03-29T00:00:00+00:00	[thread overview]
Message-ID: <8bu48a$3tt$1@nnrp1.deja.com> (raw)
In-Reply-To: 874s9p7jwi.fsf@deneb.cygnus.argh.org

In article <874s9p7jwi.fsf@deneb.cygnus.argh.org>,
  Florian Weimer <fw-usenet@deneb.cygnus.argh.org> wrote:
> Martin Dowie <martin@dowie-cs.demon.co.uk> 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.




  reply	other threads:[~2000-03-29  0:00 UTC|newest]

Thread overview: 105+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2000-03-21  0:00 No Go To's Forever! Bill Dale
2000-03-21  0:00 ` David Starner
2000-03-21  0:00   ` Bill Dale
2000-03-22  0:00     ` Robert Dewar
2000-03-22  0:00   ` Robert Dewar
2000-03-22  0:00     ` Paul Graham
2000-03-22  0:00       ` Robert Dewar
2000-03-22  0:00         ` Brian Rogoff
2000-03-22  0:00           ` Ted Dennison
2000-03-22  0:00             ` Michael P. Walsh
2000-03-23  0:00           ` Robert Dewar
2000-03-22  0:00         ` Michael P. Walsh
2000-03-22  0:00           ` Charles Hixson
2000-04-06  0:00             ` Wes Groleau
2000-04-07  0:00               ` Charles Hixson
2000-03-22  0:00         ` Paul Graham
2000-03-23  0:00           ` Robert Dewar
2000-03-23  0:00             ` Ted Dennison
2000-03-23  0:00               ` Paul Graham
2000-03-23  0:00                 ` Robert Dewar
2000-03-23  0:00               ` Robert Dewar
2000-03-23  0:00               ` Larry Kilgallen
2000-03-22  0:00     ` Robert A Duff
2000-03-22  0:00     ` Roger Barnett
2000-03-22  0:00       ` Charles Hixson
2000-03-22  0:00   ` Robert Dewar
2000-03-21  0:00 ` Charles Hixson
2000-03-21  0:00   ` Gautier
2000-03-21  0:00   ` Robert Dewar
2000-03-21  0:00     ` Michael P. Walsh
2000-03-21  0:00       ` Andrew Berg
2000-03-22  0:00         ` Wes Groleau
2000-03-22  0:00           ` No Go To's Forever! (I'm sorry I spoke...) dis90072
2000-03-23  0:00             ` tmoran
2000-03-23  0:00               ` Larry Kilgallen
2000-03-22  0:00     ` No Go To's Forever! Ken Garlington
2000-03-22  0:00       ` Marin D. Condic
2000-03-22  0:00         ` Roger Barnett
2000-03-22  0:00           ` Larry Kilgallen
2000-03-23  0:00             ` Robert Dewar
2000-03-23  0:00         ` Keith Thompson
2000-03-24  0:00           ` Marin D. Condic
2000-03-24  0:00           ` Ted Dennison
2000-03-27  0:00             ` Keith Thompson
2000-03-28  0:00               ` Come From Forever! (was: No Go To's Forever!) Ted Dennison
2000-03-29  0:00                 ` Keith Thompson
2000-03-25  0:00           ` No Go To's Forever! Richard D Riehle
2000-03-22  0:00   ` Tim Gahnström
2000-03-21  0:00     ` David Starner
2000-03-22  0:00     ` Robert Dewar
2000-03-22  0:00       ` Ken Garlington
2000-03-21  0:00         ` Keith Thompson
2000-03-22  0:00         ` Robert Dewar
2000-03-22  0:00         ` Robert Dewar
2000-03-23  0:00           ` Ken Garlington
2000-03-23  0:00       ` Tim Gahnstr�m
2000-03-22  0:00     ` tmoran
2000-03-22  0:00       ` Robert Dewar
2000-03-22  0:00         ` tmoran
2000-03-23  0:00           ` Robert Dewar
2000-03-23  0:00             ` tmoran
2000-03-23  0:00               ` Robert Dewar
2000-03-23  0:00                 ` tmoran
2000-03-24  0:00                   ` Robert Dewar
2000-03-24  0:00                     ` Robert Dewar
2000-04-16  0:00                     ` Kenneth Almquist
2000-04-17  0:00                       ` Robert Dewar
2000-04-17  0:00                       ` Robert Dewar
2000-04-18  0:00                         ` Dale Stanbrough
2000-04-18  0:00                           ` Robert Dewar
2000-04-18  0:00                           ` David Starner
2000-03-23  0:00                 ` Jeff Carter
2000-03-24  0:00                   ` Robert Dewar
2000-03-29  0:00                 ` Martin Dowie
2000-03-29  0:00                   ` Robert Dewar
2000-03-29  0:00                   ` Florian Weimer
2000-03-29  0:00                     ` Robert Dewar [this message]
2000-03-30  0:00                       ` Robert A Duff
2000-04-01  0:00                         ` Robert Dewar
2000-04-01  0:00                           ` Robert A Duff
2000-04-02  0:00                             ` Robert Dewar
2000-04-21  0:00                       ` Florian Weimer
2000-04-21  0:00                         ` Robert Dewar
2000-03-29  0:00                   ` Robert Dewar
2000-03-24  0:00         ` tmoran
2000-03-22  0:00 ` Pascal Obry
2000-03-22  0:00 ` Marin D. Condic
2000-03-22  0:00   ` Robert Dewar
2000-03-22  0:00   ` Robert Dewar
2000-03-22  0:00   ` Robert Dewar
2000-03-22  0:00     ` Jon S Anthony
2000-03-22  0:00       ` Roger Barnett
2000-03-23  0:00         ` Robert Dewar
2000-03-23  0:00           ` Roger Barnett
2000-03-24  0:00             ` Robert Dewar
2000-03-23  0:00       ` Robert Dewar
2000-03-22  0:00         ` Jon S Anthony
2000-03-23  0:00   ` Chris Morgan
2000-03-22  0:00 ` Richard D Riehle
2000-03-23  0:00   ` Jeff Carter
2000-03-23  0:00     ` Robert Dewar
2000-03-23  0:00     ` Michael P. Walsh
2000-03-23  0:00       ` Brian Rogoff
     [not found] ` <01bf9436$9c054880$2c5101be@bthomas4663>
2000-03-23  0:00   ` Ken Garlington
2000-03-23  0:00   ` Robert Dewar
replies disabled

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox