Introduction Substitution Preservation Progres Conclusion

Stage M2-MPRI : Micro-F* en F*

Simon Forest

Ecole Normale Superieure

sous la supervision de Catalin Hritcu, INRIA Paris

8 Septembre 2015

1 / 36

Introduction Substitution Preservation Progres Conclusion

F*

I un langage de programmation fonctionnelle, similaire a OCaml

I un systeme de verification automatique, comme Why3

I un assistant de preuve, comme Coq

2 / 36

Introduction Substitution Preservation Progres Conclusion

Fonctionnalites

I fragment logique au niveau des typesI typage etendu par des types de computation : Γ ` e : M t wp

I M effet : pure ou avec des effets de bordI wp transformeur de predicat

I verification semi-automatisee grace a un SMT-solveur

I preuve de terminaison grace a des metriques lexicographiques

3 / 36

Introduction Substitution Preservation Progres Conclusion

Problematique

I F* est un langage de verification

I . . . mais peu verifie lui-meme : quelques preuves papiers de sametatheorie

I F* est trop complexe pour que l’on puisse faire confiance aune preuve papier

I POPLMark : chaque metatheorie de langage devrait etreaccompagnee d’une preuve mechanisee

I peu de preuves effectuees avec F*, et presence de bugs

I opportunite de trouver des patterns de preuve efficaces

Probleme : peut-on donner une preuve de correction d’un fragmentsignificatif de F*, avec F* ?

4 / 36

Introduction Substitution Preservation Progres Conclusion

Micro-F*

I un sous-langage de F*, qui peut etre vu comme unlambda-calcul

I une syntaxe comprenant expressions, types, kinds

I un systeme de type avec 7 jugements : typage, sous-typage,sous-computation, kinding, sous-kinding, bonne formation dekind, validite

5 / 36

Introduction Substitution Preservation Progres Conclusion

effets M =:: PURE | ALLconstantes d’expression ec =:: () | n | h | l | select | update

| fixpure | fixomega . . .expressions e =:: x | ec | e e |λx:t.e

valeurs v =:: () | n | h | l |λx:t.e | . . .constantes de type tc =:: unit | int | heap | location | false | and

| forallexpr | foralltype k | prec

types t =:: a | tc | t e | t t | x:t→c |λx:t . t |λa:k. t

kinds k =:: Type | x:t → k | a:k → k

types de computation c =:: M t t

Figure : Syntaxe de micro-F?

6 / 36

Introduction Substitution Preservation Progres Conclusion

(T-Var)

x : t ∈ ΓΓ ` x : Tot t

(T-Const)

Γ ` ec : Tot (tec)

(T-Abs)

Γ ` t : Type Γ, x :t ` e : M t wp

Γ ` λx :t. e : Tot (x :t → M t wp)

(T-App1)

x ∈ FV (t ′) Γ ` e1 : M (x : t → M t ′ wp) wp1 Γ ` e2 : Tot t

Γ ` e1 e2 : M (t ′[e2/x ]) (bindM wp1 λ .wp[e2/x ])

Figure : Quelques regles de typage de micro-F*

7 / 36

Introduction Substitution Preservation Progres Conclusion

Contributions

I Preuve avancee de correction de micro-F* :I Preservation : Γ ` e : c et e→ e’ impliquent Γ ` e’ : cI Progres : Γ ` e : c et e pas valeur impliquent e→ e’I ces proprietes impliquent une propriete importante : partial

correctnessI decouverte de bugs et d’ameliorations possibles dans la

specification et dans la preuve papier

I Une preuve avec F* :I un exemple de preuve longue (6500 lignes)I utilisation de patterns de preuve efficaces et reutilisablesI decouverte de bugs importants dans l’outil

8 / 36

Introduction Substitution Preservation Progres Conclusion

Remarques :

I representation des variables avec les indices DeBruijn

I simplification 1 : Γ ` e : M t wp→ Γ ` e : t

I simplification 2 : uniquement les variables d’expression

9 / 36

Introduction Substitution Preservation Progres Conclusion

Substitution syntactique

Comment definir la substitution ?

I substitution parallele

I variables d’expression et de type en meme temps

I definitions mutuellement recursives, une pour chaque type determe (esubst, tsubst, ksubst. . . )

I pour chaque fonction de substitution, deux parametres :I un “sub” s : paire de deux fonctions qui definissent ce qui est

substitueI un term m a substituer

I on note m[s] la substitution de m par s.Exemple : esubst s e = e[s]

10 / 36

Introduction Substitution Preservation Progres Conclusion

Terminaison

I terminaison : a priori induction sur le terme substitue doncmetrique simple

I mais probleme pour les lambdas : (λt.e)[s] =λt[s].e[s’]

I transformation s→ s’ : utilise la substitution

I substitution sur s lui-meme, qui n’est pas un sous-terme :probleme de terminaison !

11 / 36

Introduction Substitution Preservation Progres Conclusion

Solution

I s → s’ utilise un sub simple appele renommage de la formes(n) = m

I definition par etapes de m[s] :I si m est une variableI si s est un renommageI definition generale

I mais complexification des preuves . . .

I Avec F* : utilisation d’une metrique lexicographique quireflete ces etapes pour une definition en un bloc :

%[is var m; is renaming s; m]

I compatible avec la definition mutellement recursive

12 / 36

Introduction Substitution Preservation Progres Conclusion

Lemmes intermediaires

Sur le chemin de la preuve de preservation :

I lemme de substitution : si Γ ` e’ : t’, alorsΓ, t’ ` e : t→ Γ ` e[e’/0] : t

I lemme d’affaiblissement : Γ ` e : t→ Γ, t ` e : t

I lemme de supertypage : si Γ ` t1 <: t2 alorsΓ, t2 ` e : t→ Γ, t1 ` e : t

Problemes :

I Induction sur tous les jugements (typage, kinding,sous-typage etc. . . ) a chaque preuve : beaucoup d’efforts

I Lemmes tres peu flexibles, qui ne s’adaptent pas aux casparticuliers

13 / 36

Introduction Substitution Preservation Progres Conclusion

Solution : generalisation de la substitution

substitution de termes ⇒ substitution de jugementsarbres de syntaxe ⇒ arbres de derivation

variable libres ⇒ regles T-Var (et K-Var)

sub s ⇒ fleche de substitution hs : (Γ1)s−→ (Γ2)

x → s(x) ⇒ x:t ∈ Γ1 → Γ2 ` s(x) : t[s]

renommage s(x) = y ⇒ renommage hs(x) = (T-Var)

Theoreme (Lemme fort de substitution)

Soit (Γ1)s−→ (Γ2) une fleche de substitution.

Si Γ1 ` e : t alors Γ2 ` e[s] : t[s].

14 / 36

Introduction Substitution Preservation Progres Conclusion

Contributions

I ecriture de ce lemme, avec metrique de terminaison

I affaiblissement, substitution, supertypage : ces lemmess’obtiennent comme instances simples avec la bonne fleche→ simplification de la preuve

I une seule induction sur tous les jugements au lieu deplusieurs (economie d’au moins 1000 lignes de preuve)

I une specification corrigee et amelioree

I 1 mois et demi de travail, 600 lignes de code, 11 fonctionsmutuellement recursives

15 / 36

Introduction Substitution Preservation Progres Conclusion

Preservation

I Preuve de preservation par induction syntactique e → e ′

I On aimerait raisonner de facon syntactique sur les typagesI Exemple : a partir de Γ ` e1 e2 : t, on aimerait pouvoir

deconstruire :I Γ ` e1 : t’ → tI Γ ` e2 : t’

I N’est pas vrai car presence de regles non syntactiques :

(T-Sub)Γ ` e : M ′ t ′ wp′ Γ ` M ′ t ′ wp′ <: M t wp

Γ ` e : M t wp

(T-Ret)Γ ` e : Tot t

Γ ` e : PURE t (return t e)

16 / 36

Introduction Substitution Preservation Progres Conclusion

Lemmes d’inversion

I l’induction syntaxique necessite des lemmes d’inversionI Exemple : a partir de Γ ` e1 e2 : t, on veut :

I Γ ` e1 : t1 → t2

I Γ ` e2 : t1

I Γ ` t2 <: t

I maisI un lemme par construction syntaxiqueI lemmes tres difficiles a ecrire, peu flexibles, avec des types

compliques

17 / 36

Introduction Substitution Preservation Progres Conclusion

Contributions

I Amelioration 1 : induction sur le typage Γ ` e : t au lieu dee→ e’

I besoins moindres en lemmes d’inversionI mais il en reste quelques-uns assez compliques

I Amelioration 2 : lemme general d’inversionI Principe : toute derivation a la forme

(regle non syntactique)*.regle syntactiqueI renvoie de la chaıne non syntactique ainsi que l’arbre associe a

la regle syntactiqueI flexibilite : suffisante pour gerer tous les besoins d’inversion !

I Une preuve considerablement simplifiee

18 / 36

Introduction Substitution Preservation Progres Conclusion

Progres

I Preuve relativement simple pour la plupart des cas

I . . . mais quantite de travail importante pour les constantes

I chaque constante est un cas independant

I Exemple : update h l n→ h[n/l]

Si Γ ` update eh el en : t, il faut :I Γ ` eh : heap, Γ ` el : location, Γ ` en : intI puis eh= h, el= l, en= nI pour conclure : update h l n→ h[n/l]

en sachant : update : heap → location → int →heap

I Probleme : comment relier les types des arguments au type deupdate ? Comment rester generique dans ce traitement ?

19 / 36

Introduction Substitution Preservation Progres Conclusion

Contributions

I Conception d’une methode generique de traitement desconstantes

I derouler les regles d’applications successives en utilisant lelemme d’inversion pour gerer les regles non syntactiques

I enrouler a nouveau les regles d’applications en reutilisant lesinformations retournees par le lemme d’inversion

I Reutilisation de cette methode a plusieurs endroits du code(et pas seulement pour la preuve de progres)

I Preuve simplifiee par le traitement unifie des constantes

20 / 36

Introduction Substitution Preservation Progres Conclusion

Γ ` update e1 e2 e3 : t3

Γ ` update e1 e2 : tn → t3 Γ ` e3 : tn

Γ ` update e1 e2 : t2

Γ ` update e1 : tl → t2 Γ ` e2 : tl

Γ ` update e1 : t1

Γ ` update : th → t1 Γ ` e1 : th

Γ ` update : heap location int heap

Figure : Cas de update

21 / 36

Introduction Substitution Preservation Progres Conclusion

Γ ` update e1 e2 e3 : t3

Γ ` update e1 e2 : tn → t3 Γ ` e3 : tn

Γ ` update e1 e2 : t2

Γ ` update e1 : tl → t2 Γ ` e2 : tl

Γ ` update e1 : t1

Γ ` update : th → t1 Γ ` e1 : th

Γ ` update : heap location int heap

Figure : Cas de update

22 / 36

Introduction Substitution Preservation Progres Conclusion

Conclusion

I Preuve avancee de la correction

I Simplification de la preuve papier

I Patterns de preuve efficaces et reutilisables grace a F*

I Plus grosse preuve faite avec F* (6500 lignes)

I Decouverte de limitations du SMT-solveur

I Dans le futur : ajout de tactiques, afin de finir la preuve

I Article soumis a POPL16

23 / 36