[Haskell-cafe] Haskell Weekly News: Issue 85 - September 13, 2008

Robin Green greenrd at greenrd.org
Mon Sep 15 13:43:01 EDT 2008


On Mon, 15 Sep 2008 13:05:11 -0300
"Rafael C. de Almeida" <almeidaraf at gmail.com> wrote:
> I do not know. I'm not experienced on the field and I was under the
> impression you'd write your code then get a pen and a paper and try to
> prove some property of it.

In fairness, that's how it's often done in universities (where
correctness doesn't really matter to most people - no offense
intended). But once you start using software to write formal proofs, it
is quite easy in principle to get a computer to check your proof for
you. Many academics do not use formal proof tools because (a) they are
not aware of them, or (b) they see them as too hard to learn, or (c)
they see them as too time-consuming to use, or (d) they don't see the
point. Hopefully this situation will gradually change.

> Someone mentioned coq, I read a bit about it, but it looked really
> foreign to me. The idea is to somehow prove somethings based only on
> the specification and, after that, you write your code, based on your
> proof?

No. There are 3 main ways of using Coq:

1. Code extraction. You write your code in Coq itself, prove that it
meets your specification, and then use the Extraction commands to
convert the Coq code into Haskell (throwing away all the proof bits,
which aren't relevant at runtime).

2. Verification condition generation (VCGen) - you write your code in
some "ordinary" language, say Haskell, and annotate it with
specifications. Then you run a VCGen tool over it and it tries to prove
the trivial things, and spits out the rest as "verification conditions"
in the language of Coq, ready to be proved in Coq.

3. A combination of both of the above approaches - you write your code
in Coq, ignoring the proof at first, and then verification conditions
(called "obligations" in Coq) are generated. This is experimental. The
commands that begin with "Program" in Coq are used for this.

None of these involve writing the same code twice in different
languages.

-- 
Robin


More information about the Haskell-Cafe mailing list