Formal verification in Coq of program properties involving the global state effect


Séminaire Modèles et Algorithmes Déterministes: CASYS

5/12/2013 - 09:45 Mr Burak EKICI Salle 2 - Tour IRMA

The syntax of an imperative language does not mention the state explicitly, while its denotational semantics (interpretations) has to mention it. This talk addresses to present a Coq framework for verifying the properties of the programs with state manipulation. These properties are expressed in a proof system which is close to the syntax, as in effect systems, in the sense that the state does not appear explicitly in the type of expressions which manipulate it. Rather, the state appears via decorations (annotations) added to terms and to equations. In this system, proofs of programs thus present two aspects: properties can be verified up to effects or the effects can be taken into account. The design of our Coq library consequently reflects these two aspects: our framework is centered around the construction of two inductive and dependent types, one for terms up to effects and one for the manipulation of decorations.