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.
next prev parent 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