Upload
timothee-peyre
View
104
Download
0
Embed Size (px)
Citation preview
JFLA’06
28 janvier [email protected]://cedric.cnam.fr/~delahaye/
Pauillac
http://focal.inria.fr/
Tutoriel Focal(première partie)
David Delahaye
Équipe FocalFocal
228 janvier 2006
JFLA’06 Pauillac
Introduction
• Méthodes formelles pour la certification de programmes:
1. Vérification (automates, RdPs, …)
2. Preuve (logique, Mathématiques, …)
• Atelier FocalFocal (anciennement FocFoc):
– Outil de spécification et d’aide à la preuve
– Orienté objets (héritage, paramétrisation, …)
– Orienté spécifications algébriques (support, implantation, …)
– Preuve automatisée (ZenonZenon) et vérifiée (CoqCoq)
328 janvier 2006
JFLA’06 Pauillac
L’équipe FocalFocal
FocalFocal
LIP6LIP6
T. HardinR. RiobooM. Jaume
LIP6LIP6
T. HardinR. RiobooM. Jaume
INRIAINRIA
D. DoligezP. Weis
INRIAINRIA
D. DoligezP. Weis
Cédric, CPRCédric, CPR
C. DuboisV. Donzeau-GougeO. PonsD. DelahayeX. UrbainP. Courtieu
Cédric, CPRCédric, CPR
C. DuboisV. Donzeau-GougeO. PonsD. DelahayeX. UrbainP. Courtieu
J. BlondR. BonichonC. MorissetI. NoyerS. BoulméS. FechterV. Prevosto
J. BlondR. BonichonC. MorissetI. NoyerS. BoulméS. FechterV. Prevosto
J.-F. ÉtienneM. CarlierJ.-F. ÉtienneM. Carlier
428 janvier 2006
JFLA’06 Pauillac
Un peu d’histoire
• Groupe BiPBiP (T. Hardin, V. Donzeau-Gouge, J. R. Abrial): Interactions entre les communautés CoqCoq et BB
• Projet FocFoc (T. Hardin, R. Rioboo, S. Boulmé):
– Bibliothèque certifiée de calcul formel (failles d’AxiomAxiom)
– Structures avec héritage, représentation et paramétrisation
• Conception d’un compilateur (D. Doligez, V. Prevosto):– Codes OcamlOcaml (exécution), CoqCoq (certification)– Code FocDocFocDoc (documentation)
528 janvier 2006
JFLA’06 Pauillac
Un peu d’histoire (suite)
• Développement d’une bibliothèque de calcul formel (R. Rioboo):
Polynômes distribués, clôture réelle, …
• Sémantique opérationnelle (T. Hardin, C. Dubois, S. Fechter):
Meilleure compréhension du compilateur
• Prouveur automatique ZenonZenon (D. Doligez, D. Delahaye):
– Premier ordre avec égalité (classique), méthode des tableaux
– Traduction en CoqCoq des preuves générées
628 janvier 2006
JFLA’06 Pauillac
Spécifications FocalFocal: espèces
EspEspèceèce
species nom (pars) inherits esps (pars) = corps end
ParamétrisationParamétrisation
HéritageHéritage
Représentation: rep; ou rep = type;
Signatures: sig nom in type;
Définitions: let nom (args) = corps;
Propriétés: property nom : prop;
Théorèmes: theorem nom : prop proof : preuve;
Référencée par self Référencée par self
728 janvier 2006
JFLA’06 Pauillac
Spécifications FocalFocal: collections
CollectionCollection
collection nom implements esps (pars) = corps end
EncapsulationEncapsulation
ImplantationImplantation
Tout doit être défini et démontré:
rep; rep = type;
sig nom in type;
let nom (args) = corps;
property nom : prop;
theorem nom : prop proof : preuve;
828 janvier 2006
JFLA’06 Pauillac
Le compilateur de FocalFocal
CompilateurCompilateur
Spécification FocalFocal
FocDocFocDoc OcamlOcaml CoqCoq
XMLXML LaTeXLaTeX
ZenonZenon
928 janvier 2006
JFLA’06 Pauillac
Un exemple: les ensembles finis
(** fo_set.foc *)
(** @title A library for finite sets
@author D. Delahaye *)
species set (typ is setoid) inherits setoid =
(* Declarations *)
sig empty in self;
sig add in typ → self → self;
sig rem in typ → self → self;
sig union in self → self → self;
sig inter in self → self → self;
…
species setoid inherits basic_object =
sig equal in self → self → bool;
sig element in self;
let different (x, y) = #not_b (!equal (x, y));
property equal_reflexive : …;
property equal_symmetric : …;
property equal_transitive : …;
end
Racine de la hiérarchie:
species basic_object =
rep;
let print (x in self) = ...;
let parse (x in string) in self = ...;
end
1028 janvier 2006
JFLA’06 Pauillac
Ensembles (suite)
(* Definitions *)
let is_empty (e) = !equal (e, !empty);
let mem (e, a) = !different (a, !rem (e, a));
(* Set axioms *)
property ext : all a b in self, (!mem (e, a) ↔ !mem (e, b)) ↔ !equal (a, b);
letprop mem_union (e, a, b) = !mem (e, a) or !mem (e, b);
property pair : all a b in self, all e in typ, !mem (e, !union (a, b)) ↔ !mem_union (e, a, b);
(* We do not need axioms of reunion
and powerset due to ... *)
...
1128 janvier 2006
JFLA’06 Pauillac
Ensembles (fin) et compilation
property rem_empty : all e in typ, !equal (!rem (e, !empty), !empty);
theorem mem_empty : all e in typ, not (!mem (e, !empty))
proof : by !rem_empty, !equal_symmetric def !different, !mem;
end
Compilation:
$:> focc -I … fset.foc
$:> ls fset.*
fset.fo fset.foc fset.ml fset.mli fset.zv
$:> zvtov -zenon … fset.zv
Pourquoi?
not (!mem (e, !empty)) different, mem (défs.)
not (#not_b (!equal (!empty, !rem (e, !empty)))) rem_empty, equal_symmetric (props.)
1228 janvier 2006
JFLA’06 Pauillac
Finitude (modularité)
species finite =
rep;
sig card in self → int;
sig is_finite in self → bool;
property finite : all a in self, !is_finite (a);
end
Cette espèce représente une propriété
possibilité de modulariser le développement!
Comment utiliser cette propriété? …
Solution alternative:
species finite inherits basic_object =
sig card in self → int;
sig is_finite in self → bool;
property finite : all a in self, !is_finite (a);
end
1328 janvier 2006
JFLA’06 Pauillac
Ensembles finis
species finite_set (typ is setoid) inherits set (typ), finite =
(** Choice operator *)
sig choose in self → typ;
property choose_ne : all a in self, not (!is_empty (a)) → !mem (!choose (a), a);
theorem choice : all a in self, not (!is_empty (a)) → ex e in typ, !mem (e, a)
proof : by !choose_ne;
(* Definitions *)
let rec is_finite (a) = if !is_empty (a) then #True
else let e = !choose (a) in !is_finite (!rem (e, a));
…
1428 janvier 2006
JFLA’06 Pauillac
Ensembles finis (suite)
let rec union (a, b) = if !is_empty (a) then b
else let e = !choose (a) in !union (!rem (e, a), !add (e, b));
let inter (a, b) =
let ab = !restrict (a, b) in
let ba = !restrict (b, a) in
!restrict (!restrict (!union (a, b), ab), ba);
(* Theorems *)
theorem union_empty : all a in self, !equal (!union (!empty, a), a)
proof : by !equal_reflexive def !is_empty, !union;
…
end
1528 janvier 2006
JFLA’06 Pauillac
Ensembles finis (espèce complète)
Implantation avec des listes:
species fset_list (typ is setoid) inherits finite_set (typ) =
rep = list (typ);
let empty = #Nil;
let card (e) = #length (e);
let add (e, a) = if !mem (e, a) then a else #Cons (e, a);
proof of rem_empty = …;
…
end
La propriété rem_empty provient de set:
property rem_empty : all e in typ, !equal (!rem (e, !empty), !empty);
1628 janvier 2006
JFLA’06 Pauillac
Ensembles finis d’entiers (collection)
collection int_fset implements fset_list (foc_small_integers) = end
La collection int_fset représente du code exécutable.
foc_small_integers est une collection (prédéfinie):
elle doit au moins implanter l’espèce setoid (paramètre de fset_list)
On peut donner à fset_list toute collection implantant setoid.
Attention, cependant:
le paramètre ne peut pas être une espèce; c’est uniquement une collection!
1728 janvier 2006
JFLA’06 Pauillac
Utiliser les collections
let a = foc_small_integers!parse ("1");;
…
let l1 = int_fset!add (#a, int_fset!add (#b, int_fset!empty));;
let l2 = int_fset!add (#b, int_fset!add (#c, int_fset!add (#d, int_fset!empty)));;
#print_string (int_fset!print (int_fset!union (#l1, #l2)));;
#print_string (int_fset!print (int_fset!inter (#l1, #l2)));;
#print_string (foc_small_integers!print (#hd (#l1)));;
Exécution:
$:> fset
1 2 3 4
2
→ la représentation est abstraite!
1828 janvier 2006
JFLA’06 Pauillac
Une autre implantation
species efset_list (typ is setoid) inherits finite_set (typ) =
rep = int × list (typ);
let empty = #crp (0, #Nil);
let card (e) = #first (e);
let mem (e, a) = #mem (e, #scnd (a));
proof of mem_empty = …;
…
end
collection int_efset implements efset_list (foc_small_integers) = end
La méthode mem est redéfinie.
La preuve de mem_empty faite dans set:
theorem mem_empty : all e in typ, not (!mem (e, !empty))proof : by !rem_empty, !equal_symmetric def !different, !mem;
doit être refaite!
1928 janvier 2006
JFLA’06 Pauillac
Hiérarchie de la spécification
Espèce
Collection
Héritage
Paramétrisation
Implantation
Espèce
Collection
Héritage
Paramétrisation
Implantation
setoisetoidd
sesett
finite_sfinite_setet
finitfinitee
fset_lifset_listst
efset_liefset_listst
int_fseint_fsett
fsifsi
int_efseint_efsett
2028 janvier 2006
JFLA’06 Pauillac
Extension de la spécification
• On souhaite étendre notre spécification:
Ensembles finis (totalement) ordonnés
• En ne changeant rien à la spécification existante
En ne dupliquant pas de code
• Est-ce possible?
Oui: héritage avec raffinement du paramètre
Technique issue de la programmation objets
2128 janvier 2006
JFLA’06 Pauillac
Ordre total
Espèce de la bibliothèque standard:
species ordered_set inherits partial_order =
let equal (x, y) = #and_b (!leq (x, y), !leq (y, x));
let lt (x, y) = #not_b (!leq (y, x));
property total_order : all x y in self, !leq (x, y) or !leq (y, x);
proof of lt_is_not_leq =
by !total_order def !lt, !different, !equal;
...
end
species partial_order inherits pre_order =
property leq_antisymmetric : all x y in self,
!leq (x, y) → !leq (y, x) → !equal (x, y);
end
species pre_order inherits setoid =
sig leq in self → self → bool;
let lt (x, y) = #and_b (!leq (x, y),
#not_b (!equal (x, y)));
let geq (x, y) = !leq (y, x);
let gt (x, y) = !lt (y, x);
theorem lt_is_not_leq : all x y in self,
(!lt (x, y) → !leq (x, y) and !different (x, y))
and (!leq (x, y) → !lt (x, y) or !equal (x, y))
proof : def !lt, !different;
end
2228 janvier 2006
JFLA’06 Pauillac
Ensembles finis ordonnés
species finite_ordered_set (typ is ordered_set) inherits finite_set (typ) =
(* Definitions *)
let is_single (a) = !is_empty (!rem (!choose (a), a));
let min_e (e, f) = if typ!leq (e, f) then e else f;
let max_e (e, f) = if typ!leq (e, f) then f else e;
let rec min (a) =
if !is_empty (a) then #foc_error ("min: set is empty")
else
let e = !choose (a) in
if !is_single (a) then e else !min_e (e, !min (!rem (e, a)));
…
2328 janvier 2006
JFLA’06 Pauillac
Ensembles finis ordonnés (suite)
let rec max (a) =
if !is_empty (a) then #foc_error ("max: set is empty")
else
let e = !choose (a) in
if !is_single (a) then e else !max_e (e, !max (!rem (e, a)));
(* Properties:
must be careful to partiality *)
property minp : all a in self, all e in typ, !mem (e, a) → typ!leq (!min (a), e);
property maxp : all a in self, all e in typ, !mem (e, a) → typ!leq (e, !max (a));
…
end
2428 janvier 2006
JFLA’06 Pauillac
Implantation: 2 possibilités
species foset_list (typ is ordered_set) inherits finite_ordered_set (typ) =
rep = list (typ);
…
end
ou mieux:
species foset_list (typ is ordered_set) inherits finite_ordered_set (typ), fset_list (typ) =
…
end
2528 janvier 2006
JFLA’06 Pauillac
Ensembles finis ordonnés d’entiers
species oints inherits ordered_set, integers_int =
let leq = #int_leq;
proof of leq_reflexive = ...;
proof of leq_antisymmetric = ...;
proof of leq_transitive = ...;
proof of lt_is_not_leq = ...;
proof of total_order = ...;
end
collection ints implements oints = end
collection int_foset implements foset_list (ints) = end
2628 janvier 2006
JFLA’06 Pauillac
Nouvelle hiérarchiesetoisetoi
dd
sesett
finite_sfinite_setet
finitfinitee
fset_lifset_listst
int_fseint_fsett
fsifsi
finite_ordered_setfinite_ordered_set
intsints
ordered_setordered_set
foset_listfoset_list
int_fosetint_foset
2728 janvier 2006
JFLA’06 Pauillac
Documentation: FocDocFocDoc
• Le compilateur peut produire un fichier FocDocFocDoc Fichier XMLXML décrivant l’interface des espèces
• Validité: DTDDTD ou XSDXSD fournies
• Production de documents HTMLHTML (MathMLMathML) ou LaTeXLaTeX XSLXSL stylesheets (pré-processeur XSLXSL requis)
• Gestion de base de données Focal Requêtes XqueryXquery (SQLSQL adapté à XMLXML)
Documentation de notre exemple:
$:> focc -I … -focdoc -dtd focdoc.dtd fo_set.foc
$:> xsltproc -o fo_set.xhtml focdoc2html.xsl fo_set.focdoc
$:> xsltproc -o fo_set.xml mmlctop2_0.xsl fo_set.xhtml
fo_set.focdoc
fo_set.xml
2828 janvier 2006
JFLA’06 Pauillac
Applications FocalFocal
• Bibliothèque de calcul formel (R. Rioboo, LIP6LIP6):
Actuelle bibliothèque standard de FocalFocal
• Projet EDEMOIEDEMOI de l’ACI Sécurité Informatique
(V. Donzeau-Gouge, C. Dubois, D. Delahaye, J. F. Étienne, CNAMCNAM):
Réglementation de la sûreté dans les aéroports
• Politiques de sécurité (M. Jaume, C. Morisset, LIP6LIP6; J. Blond, BertinBertin):
Bell et Lapadula, Muraille de Chine, ...Voir l’exposé lundi!
2928 janvier 2006
JFLA’06 Pauillac
Application: le projet EDEMOIEDEMOI
• V. Donzeau-Gouge, C. Dubois, D. Delahaye, J.-F. Étienne:
Réglementation de la sûreté dans les aéroports formalisée en Focal
• Modélisation:
– Héritage, paramétrisation
– Sortie vers UMLUML
• Certification:
– Cohérence de la spécification
– ZenonZenon se révèle très approprié!
Annexe 17Annexe 17(ICAO)
Doc 30Doc 30(ECAC)
Posez-lui des questions!
3028 janvier 2006
JFLA’06 Pauillac
Pour finir…
• Distribution disponible sur le site du projet FocalFocal:
http://focal.inria.fr/
• Quelques travaux en cours ou futurs:
– Tests (C. Dubois, M. Carlier)
– Invariants de représentation, réécriture, déduction modulo, ...
• Demain, C. Morisset pour la deuxième partie du tutoriel
ou comment il est difficile de louer des DVDDVDs sans FocalFocal...