Skip to content

bsall/thesis-dev

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

13 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Programmation impérative par raffinements avec l'assistant de preuve Coq

Ce développement nécessite Coq 8.9.1. Le projet peut être compilé avec la commande : make -f CoqMakefile. L'installation de Proof General et company coq est recommandée. Le développement comporte deux parties, une partie théorique et quelques exemples.

Théorie

Dans Statement.v on trouve la syntaxe d'un langage impératif classique. Le fichier HoareWp.v contient une logique de Hoare et une définition du raffinement de programmes à partir de cette logique. On définit aussi une sémantique prédicative du langage dans Predicative.v, et l'équivalence (modulo raffinement) entre cette sémantique et la logique de Hoare est établie dans HoareWp_Predicative.v. Pour faciliter les raisonnements, on s'appuie sur un calcul de la plus faible pré-spécification défini dans Wpr.v. Enfin, on trouvera CbC.v une formalisation d'un ensemble de règles de développement permettant d'obtenir des résultats corrects par construction. La correction et la complétude de ces règles est également établie dans ce même fichier.

Exemples

Le dossier examples contient des illustrations de preuve de programmes avec la sémantique prédicative directement, avec le calcul de la plus faible pré-spécification, et avec les règles de la correction par construction. En particulier, on trouvera dans Sqrt.v le développement par raffinements d'un algorithme de calcul de la racine carrée d'un entier.

Description

La théorie formalisée par ce développement Coq est décrite dans ce manuscrit. Le tableau ci-dessous fait correspondre les définitions et résultats principaux avec leur nom dans les fichiers .v.

Définitions Nom Fichier
Définition 8 lfp LeastFixpoint.v
Lemme 1 f_lfp LeastFixpoint.v
Lemme 2 lfp_fix LeastFixpoint.v
Définition 9 tcl TransitiveClosure.v
Lemme 3 tcl_trans TransitiveClosure.v
Lemme 4 tcl_fix TransitiveClosure.v
Syntaxe (Figure 4.1) Statement Statement.v
Sémantique prédicative (Figure 4.2) pred Predicative.v
Définition 13 (Composition démoniaque) fn DemonicComposition.v
Définition 13 (Composition angélique) fn AngelicComposition.v
Lemme 5 right_monotonic DemonicComposition.v
Lemme 6 (1) while_fix Predicative.v
Lemme 6 (2) while_ind Predicative.v
Lemme 7 ex_while_ind Predicative.v
Théorème 1 while_well_founded Predicative.v
Définition 14 refines Predicative.v
Lemme 8 (1) refines_reflexive Predicative.v
Lemme 8 (3) refines_trans Predicative.v
Lemme 9 (1) If_monotonic_refines Predicative.v
Lemme 9 (2) Seq_monotonic_refines Predicative.v
Lemme 9 (3) While_monotonic_refines Predicative.v
Définition 15 et Figure 4.3 ValidHoareTriple ValidHoareTriple.v
Lemme 10 hoare_pred HoareWp_Predicative.v
Définition 16 refines ValidHoareTriple.v
Lemme 11 triple_ext_triple HoareWp_Predicative.v
Théorème 2 extended_definition_iff_simple_definition HoareWp_Predicative.v
Théorème 3 hoare_refines_iff_pred_refines HoareWp_Predicative.v
Sémantique prédicative (Figure 5.1) pred ImprovedPredicative.v
Lemme 12 pred_opt_pred_seq ImprovedPredicative.v
Theorem 4 pred_old_pred ImprovedPredicative.v
Définition 19 wpr_spec Wpr.v
Définition 20 wpr Wpr.v
Lemme 14 (1) wpr_while_construct, wpr_while_destruct Wpr.v
Lemme 14 (2) wpr_while_ind Wpr.v
Lemme 15 wpr_pred Wpr.v
Théorème 5 wpr_refines Wpr.v
Lemme 16 wfd_while_iff_if Predicative.v
Théorème 6 while_rule_sound_and_complete Predicative.v
Langage de développement (Figure 6.2) Dev CbC.v
Définition 21 dsem CbC.v
Définition 23 CbC CbC.v
Théorème 7 wpr_wpr' CbC.v
Théorème 8 soundness CbC.v
Théorème 9 completeness CbC.v

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published