Ponton's site

Yay, another parser in Haskell! That was a Haskell week, but I’m glad I had an opportunity to recall this beautiful full-of-math language.

This program reads an annotated program — a program with assertions. Assertions are just logic formulas. We use them to describe the program state between instructions, ie. variable x is equal to variable y squared. But assertions cannot be random, they must be derived from Hoare’s logic axioms and rules (which base on the formal semantic of the language). How do we know if there is an derivation of a program?

Here verification condicitions come. They are logic formulas too, but generated from annotated program. If all of them are true, then the program is derivable. More information here: http://www.macs.hw.ac.uk/~air/hic-hisd/ and http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html. The whole point is about formal verification of programs. Nowadays compiler can tell only whether given program has a syntax or type error. It doesn’t know anything about how this program should work and can’t say something like: “This program certainly does not multiply matrices.”. Assertions are some way to tell the programmer’s intentions to the compiler: “This is my piece of code and it should multiply two matrices”, and thus, by generating verification conditions and using automated theorem proving it could say: “It does.”.

So after a boring digression… this program reads an annotated program in a simple imperative language and generates verification conditions. That’s all.

All files are here: http://srednikpe.org/src/vc/