Théo Winterhalter, doctorant au sein de l’équipe Gallinette, soutiendra sa thèse intitulée « Formalisation et Méta-Théorie de la Théorie des Types » / « Formalisation and Meta-Theory of Type Theory »

vendredi 18 septembre 2020 à 14h.

Jury :
– Directeur thèse : Nicolas Tabareau
– Co-encadrant : Mathieu Sozeau
– Rapporteurs : Andrej Bauer (U Ljubljana), Herman Geuvers (Raboud University, Nijmegen)
– Autres membres : Assia Mahboubi, Bas Spitters (Aarhus University), Andreas Abel (Goteborg University), Hugo Herbelin (U Paris Diderot), Gilles Dowek (ENS Paris Saclay)

Résumé : Dans cette thèse, je parle de la méta-théorie de la théorie des types et de la façon de la formaliser dans un assistant de preuve.
Je me concentre d’abord sur une traduction conservative de la théorie des types extensionnelle vers la théorie des types intensionnelle ou faible, entièrement écrite en Coq. La première traduction consiste en une suppression de la règle de reflection de l’égalité, tandis que la deuxième traduction produit quelque chose de plus fort : la théorie des types faibles est une théorie des types sans notion de conversion. Le résultat de conservativité implique que la conversion n’augmente pas la puissance logique de la théorie des
types.
Ensuite, je montre ma contribution au projet MetaCoq de formalisation et de spécification de Coq au sein de Coq. En particulier, j’ai travaillé sur l’implantation d’un vérificateur de type pour Coq, en Coq. Ce vérificateur de type est prouvé correct vis à vis de la spécification et peut être extrait en code OCaml et exécuté indépendamment du vérificateur de type du noyau de Coq. Pour que cela fonctionne, nous devons nous appuyer sur la métathéorie de Coq que nous développons, en partie, dans le projet MetaCoq. Cependant, en raison des théorèmes d’incomplétude de Gödel, nous ne pouvons pas prouver la cohérence de Coq dans Coq, ce qui signifie que certaines propriétés — principalement la forte normalisation — doivent être supposées, c’est-à-dire prises comme axiomes.

Mots-clés : théorie des types, formalisation, traduction de programme, vérification de type

********

Abstract: In this thesis, I talk about the metatheoryof type theory and about how to formalise it in a proof assistant.
I first focus on a conservative translation between extensional type theory and either intensional or weak type theory, entierely written in Coq. The first translation consists in a removal of the reflection of equalityr rule, whereas the second translation produces something stronger: weak type theory is a type theory with no notion of conversion. The conservativity result implies that conversion doesn’t increase the logical power of type theories.
Then, I show my work for the Meta- Coq project of formalising and specifying Coq within Coq. In particular I worked on writing a type-checker for Coq, in Coq. This type checker is proven sound with respect to the specification and can be extracted to OCaml code and run independently of Coq’s kernel type-checker. For this to work we have to rely on the meta-theory of Coq which we develop, in part, in the MetaCoq project. However, because of Gödel’s incompleteness theorems, we cannot prove consistency of Coq within Coq, and this means that some properties— mainly strong normalisation—have to be assumed, i.e. taken as axioms.

Keywords: type theory, extensionality, program translation, type checking

Ambroise Lafont, doctorant au sein de l’équipe Gallinette, soutiendra sa thèse intitulée « Signatures et modèles pour la syntaxe et la sémantique opérationnelle en présence de liaison de variables » / « Signatures and models for syntax and operational semantics in the presence of variable binding »

lundi 2 décembre 2019 à 14h, dans la salle 3 du bâtiment 11 sur le site de la FST.

Jury :

• Directeur thèse : Nicolas Tabareau
• Co encadrant : Tom Hirschowitz (CR CNRS LAMA)
• Rapporteurs : Peter Lefanu Lumsdaine, U Stocklom), Marcelo Fiore (U Cambridge)
• Autres membres : Benedikt Ahrens (U Birmingham), Thomas Ehrhard (U Paris Diderot), Delia Kesner (U Paris Diderot)

Résumé : Cette thèse traite de la spécification et la construction de la syntaxe et sémantique opérationnelle d’un langage de programmation. Nous travaillons avec une notion générale de “signature” pour spécifier des objets d’une catégorie donnée comme des objets initiaux dans une catégorie appropriée de modèles. Cette caractérisation, dans l’esprit de la sémantique initiale, donne une justification du principe de récursion.  Les langages avec liaisons, telles que le lambda calcul pur, sont des monades sur la catégorie des ensembles spécifiées par les signatures algébriques classiques. Les premières extensions de syntaxes avec des équations que nous considérons sont des “quotients” de ces signatures algébriques. Ils  permettent, par exemple, de spécifier une opération commutative binaire. Cependant, certaines équations, comme l’associativité, semblent hors d’atteinte. Ceci motive la notion de 2-signature qui complète la définition précédente avec la donnée d’un ensemble d’équations. Nous identifions la classe des “2- signatures algébriques” pour lesquelles l’existence de la syntaxe associée est garantie. Finalement, nous abordons la spécification de la sémantique opérationnelle d’un langage de programmation tel que le lambda calcul avec -réduction. Nous introduisons à cette fin la notion de monade de réduction et leur signatures, puis les généralisons pour aboutir à la notion de monade opérationnelle.

Mot-clés : monades, syntaxe, sémantique, signature

*******

Abstract: This thesis deals with the specification and construction of syntax and operational semantics of a programming language. We work with a general notion of “signature” for specifying objects of a given category as initial objects in a suitable category of models. This characterization, in the spirit of Initial Semantics, gives a justification of the recursion principle. Languages with variable binding, such as the pure lambda calculus, are monads on the category of sets specified through the classical algebraic signatures. The first extensions to syntaxes with equations that we consider are “quotients” of these algebraic signatures. They allow, for example, to specify a binary commutative operation. But some equations, such as associativity, seem to remain out of reach. We thus introduce the notion of 2-signature, consisting in two parts: a specification of operations through a usual signature as before, and a set of equations among them. We identify the class of “algebraic 2-signatures” for which the existence of the associated syntax is guaranteed. Finally, we takle the specificiation of the operational semantics of a programming language such as lambda calculus with – reduction. To this end, we introduce the notion of reduction monad and their signatures, then we generalize them to get the notion of operational them to get the notion of operational monad.

Keywords: monads, syntax, semantic, signature

Gaëtan Gilbert, doctorant au sein de l’équipe Gallinette, soutiendra sa thèse intitulée « Une théorie des types avec insignifiance des preuves définitionnelle » / « A type theory with definitional proof-irrelevance »

vendredi 20 décembre 2019 à 10h, dans l’amphi Besse de l’IMT-A.

Jury :
Directeur thèse : TABAREAU Nicolas
Co encadrant : SOZEAU Matthieu (CR Inria)
Rapporteurs : ABEL Andreas (Chalmers Techniska Hogskola AB), SPITTERS Bas (Aarhus University)
Autres membres : MAHBOUBI Assia, BERTOT Yves (DR Inria Antipolis), SMOLKA Gert (Saarland University)

Résumé : L’égalité définitionnelle, aussi appelée conversion, pour une théorie des types avec une vérification de type décidable est l’outil le plus simple pour prouver que deux
objets sont les mêmes, laissant le système décider en utilisant uniquement le calcul. Par conséquent, plus il y a de choses égales par conversion, plus il est simple d’utiliser un
langage basé sur la théorie des types. L’insignifiance des preuves, indiquant que deux preuves quelconques de la même proposition sont égales, est une manière possible
d’étendre la conversion afin de rendre une théorie des types plus puissante. Cependant, ce nouveau pouvoir a un prix si nous l’intégrons naïvement, soit en rendant la vérification
de type indécidable, soit en réalisant de nouveaux axiomes—tels que l’unicité des preuves d’identité (UIP)—qui sont incompatibles avec d’autres extensions, comme l’univalence.
Dans cette thèse, nous proposons un moyen général d’étendre une théorie des types avec l’insignifiance des preuves, de manière à ce que la vérification du type soit décidable
et est compatible avec l’univalence. Nous fournissons un nouveau critère pour décider si une proposition peut être éliminée sur un type (en corrigeant et en améliorant la règle
d’élimination des singletons de Coq) en utilisant des techniques provenant de développements récents du filtrage dépendant sans UIP. Nous fournissons aussi une preuve de
la décidabilité du typage à base de relations logiques. Cette extension de la théorie des types a été implementée dans les assistants de preuve Coq et Agda.

Mot-clés : Assistant de preuve, Coq, insignifiance des preuves, univers, UIP

********

Abstract: Definitional equality, a.k.a conversion, for a type theory with a decidable type checking is the simplest tool to prove that two objects are the same, letting the system decide just using computation. Therefore, the more things are equal by conversion, the simpler it is to use a language based on type theory. Proof-irrelevance, stating that any two proofs of the same proposition are equal, is a possible way to extend conversion to make a type theory more powerful. However, this new power comes at a price if we integrate it naively, either by making type checking undecidable or by realizing new axioms—such as uniqueness of identity proofs (UIP)—that are incompatible with other extensions, such as univalence. In this thesis, we propose a general way to extend a type theory with definitional proof irrelevance, in a way that keeps type checking decidable and is compatible 
with univalence. We provide a new criterion to decide whether a proposition can be eliminated over a type (correcting and improving the so-called singleton elimination of Coq) byusing techniques coming from recent development on dependent pattern matching without UIP. We show the decidability of type checking using logical relations. This extension of type theory has been implemented both in Coq and Agda.

Keywords: Proof assistant, Coq, proof-irrelevance, universes, UIP