Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |
Download paper Adobe portable document format (pdf)
Copyright noticeThis material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
We show how to formalise a constraint-based data flow analysis in the specification language of the Coq proof assistant. This involves defining a dependent type of lattices together with a library of lattice functors for modular construction of complex abstract domains. Constraints are expressed in an intermediate representation that allows for both efficient constraint resolution and correctness proof of the analysis with respect to an operational semantics. The proof of existence of a correct, minimal solution to the constraints is constructive which means that the extraction mechanism of Coqprovides a provably correct data flow analyser in ocaml. The library of lattices together with the intermediate representation of constraints are defined in an analysis-independent fashion that provides a basis for a generic framework for proving and extracting static analysers in Coq.
Vlad Rusu
Vlad.Rusu@irisa.fr
@InProceedings{rusu04c,
Author = {Cachera, D. and Jensen, T. and Pichardie, D. and Rusu, V.},
Title = {Extracting a data flow analyser in constructive logic},
BookTitle = {European Symposium on Programming,ESOP'04. Volume 2986 of LNCS},
Pages = {385--400},
Publisher = {Springer-Verlag},
Month = {February},
Year = {2004}
}
Get EndNote Reference (.ref)