Certification de programmes avec des effets calculatoires

Mots clé :

• état
• exceptions
• preuves de programmes
• sémantique equationnelle
• logique décorée
• certification de programmes
• Coq

Dans cette thèse, nous visons à formaliser les effets calculatoires. En effet, les langages de programmation les plus utilisés impliquent différentes sortes d'effets de bord: changement d'état, exceptions, entrées / sorties, non-déterminisme, etc. Ils peuvent apporter facilité et flexibilité dans le processus de codage. Cependant, le problème est de prendre en compte les effets lorsque l'on veut prouver des propriétés de programmes. La principale difficulté dans ce genre de preuve de programmes est le décalage entre la syntaxe des opérations avec effets de bord et leur interprétation. Typiquement, un fragment de programme avec des arguments de type X qui retourne une valeur de type Y n'est pas interprété comme une fonction de X vers Y, à cause des effets. L'approche algébrique la plus connue pour ce problème permet une interprétation des programmes, y compris ceux comportant des effets, en utilisant des monades : l'interprétation est une fonction de X vers T(Y) où T est une monade. Cette approche a été étendue aux théories de Lawvere et aux "gestionnaires algébriques" (algebraic handlers). Une autre approche, appelée logique décorée, fournit une sémantique équationnelle pour ces programmes.

Nous spécialisons l'approche de la logique décorée pour les effets liés à l'état de la mémoire et à la gestion des exceptions en définissant la logique décorée pour les états (L_st) et la logique décorée pour les exceptions (L_exc), respectivement. Elles nous permettent de prouver des propriétés de programmes impliquant de tels effets. Ensuite, nous formalisons ces logiques en Coq et certifions les preuves associées. Ces logiques sont construites de manière à être correctes. En outre, nous introduisons une notion de complétude syntaxique relative d'une théorie dans une logique donnée par rapport à une sous-logique. Nous montrons que la théorie décorée pour les états globaux ainsi que deux théories décorées pour les exceptions sont relativement complets relativement à leur sous-logique pure. Non seulement nous pouvons utiliser le système développé pour prouver des programmes comportant des effets, mais également nous utilisons cette formalisation pour certifier les résultats de complétude obtenus.

Directeurs:

• Mr Jean Guillaume Dumas (Professeur - Université Joseph Fourier )
• Mme Dominique Duval (Professeure - Université Joseph Fourier )

Raporteurs:

• Mme Catherine Dubois (Professeur - ENSIIE )
• Mr Olivier Laurent (Directeur de Recherche - CNRS )
• Mr Alan Schmitt (Directeur de Recherche - INRIA )

Examinateurs:

• Mr Andrej Bauer (Professeur - Université de Ljubljana )
• Mr Jean François Monin (Professeur - Université Joseph Fourier )
• Mr Damien Pous (Chercheur - CNRS )