Extracting a Data Flow Analyser in Constructive Logic

David Cachera 1 Thomas Jensen 1 David Pichardie 1 Vlad Rusu 2
1 Lande - Logiciel : ANalyse et DEveloppement
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
2 DART - Contributions of the Data parallelism to real time
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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 Coq provides 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.
Type de document :
Communication dans un congrès
ESOP, 2004, Barcelona, Spain. 2004
Liste complète des métadonnées

https://hal.inria.fr/inria-00564633
Contributeur : Mister Dart <>
Soumis le : mercredi 9 février 2011 - 14:51:37
Dernière modification le : vendredi 16 novembre 2018 - 01:23:51
Document(s) archivé(s) le : mardi 10 mai 2011 - 02:58:41

Fichier

extractDataFlow-ESOP-nospringe...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00564633, version 1

Citation

David Cachera, Thomas Jensen, David Pichardie, Vlad Rusu. Extracting a Data Flow Analyser in Constructive Logic. ESOP, 2004, Barcelona, Spain. 2004. 〈inria-00564633〉

Partager

Métriques

Consultations de la notice

667

Téléchargements de fichiers

157