Academic literature on the topic 'Proof system interoperability'

Dedukti est un cadre logique résultant de la combinaison du typage dépendant et de la réécriture. Il permet d'encoder de nombreux systèmes logiques au moyen de plongements superficiels qui préservent la notion de réduction. Ces traductions de systèmes logiques dans un format commun sont une première étape nécessaire à l'échange de preuves entre ces systèmes. Cet objectif d'interopérabilité des systèmes de preuve est la motivation principale de cette thèse. Pour y parvenir, nous nous inspirons du monde des langages de programmation et plus particulièrement des langages orientés-objet parce qu'ils mettent en œuvre des mécanismes avancés d'encapsulation, de modularité et de définitions par défaut. Pour cette raison, nous commençons par une traduction superficielle d'un calcul orienté-objet en Dedukti. L'aspect le plus intéressant de cette traduction est le traitement du sous-typage. Malheureusement, ce calcul orienté-objet ne semble pas adapté à l'incorporation de traits logiques. Afin de continuer, nous devons restreindre les mécanismes orientés-objet à des mécanismes statiques, plus faciles à combiner avec la logique et apparemment suffisant pour notre objectif d'interopérabilité. Une telle combinaison de mécanismes orientés-objet et de logique est présente dans l'environnement FoCaLiZe donc nous proposons un encodage superficiel de FoCaLiZe dans Dedukti. Les difficultés principales proviennent de l'intégration de Zenon, le prouveur automatique de théorèmes sur lequel FoCaLiZe repose, et de la traduction du langage d'implantation fonctionnel de FoCaLiZe qui présente deux constructions qui n'ont pas de correspondance simple en Dedukti : le filtrage de motif local et la récursivité. Nous démontrons finalement comment notre encodage de FoCaLiZe dans Dedukti peut servir en pratique à l'interopérabilité entre des systèmes de preuve à l'aide de FoCaLiZe, Zenon et Dedukti. Pour éviter de trop renforcer la théorie dans laquelle la preuve finale est obtenue, nous proposons d'utiliser Dedukti en tant que méta-langage pour éliminer des axiomes superflus<br>Dedukti is a Logical Framework resulting from the combination ofdependent typing and rewriting. It can be used to encode many logical systems using shallow embeddings preserving their notion of reduction. These translations of logical systems in a common format are a necessary first step for exchanging proofs between systems. This objective of interoperability of proof systems is the main motivation of this thesis.To achieve it, we take inspiration from the world of programming languages and more specifically from object-oriented languages because they feature advanced mechanisms for encapsulation, modularity, and default definitions. For this reason we start by a shallow translation of an object calculus to Dedukti. The most interesting point in this translation is the treatment of subtyping. Unfortunately, it seems very hard to incorporate logic in this object calculus. To proceed, object-oriented mechanisms should be restricted to static ones which seem enough for interoperability. Such a combination of static object-oriented mechanisms and logic is already present in the FoCaLiZe environment so we propose a shallow embedding of FoCaLiZe in Dedukti. The main difficulties arise from the integration of FoCaLiZe automatic theorem prover Zenon and from the translation of FoCaLiZe functional implementation language featuring two constructs which have no simple counterparts in Dedukti: local pattern matching and recursion. We then demonstrate how this embedding of FoCaLiZe to Dedukti can be used in practice for achieving interoperability of proof systems through FoCaLiZe, Zenon, and Dedukti. In order to avoid strengthening to much the theory in which the final proof is expressed, we use Dedukti as a meta-language for eliminating unnecessary axioms

Il existe aujourd'hui une large famille de systèmes de preuve baséesur différentes logiques: Le calcul des constructions inductives, lalogique d'ordre supérieur, la théorie des ensembles, etc... Undésavantage majeur de cette diversité est, que les théorèmes sontprouvés de nombreuses fois. Une possibilité pour résoudre ce problèmeest de rendre les systèmes de preuve interoperables. Dans cette thèse,nous avons attaqué le problème d'interopérabilité entre systèmes depreuve aussi bien sur le plan théorique que le plan pratique enutilisant le cadre logique Dedukti.Notre voyage commence avec l'exploration des systèmes de typescumulatifs (CTS), une famille de systèmes de type qui étend celle dessystèmes de types pures avec une relation de sous-typage. Les CTSfournissent aujourd'hui une squelette commun a beaucoup de logiquesutilisés aujourd'hui. Les logiques derrières les systèmes Coq,HOL-Light, Lean, Matita ou bien PVS peuvent toutes être vues comme desextensions des CTS avec des fonctionnalités différentes (typesinductifs, irrelevance de la preuve, sous-typage propositionnel,...). Nous définissons une nouvelle notion de traduction entreCTS. Entre autre, nous expliquons un nouvel algorithme (correct maisincomplet) pour déterminer si une preuve écrite dans un CTS peut-êtretraduire dans un autre CTS. Cet algorithme peut aussi être vu commeune extension de l'algorithme de Coq qui permet de vérifier qu'unensemble de contraintes sur les univers est cohérent. Finalement, nousproposons un nouvel encodage des CTS dans Dedukti et nous prouvonsque cet encodage est correct. Ces résultats montrent que Dedukti estun cadre logique approprié sur le plan théorique pour étudierl'interopérabilité entre systèmes de preuve.Nous poursuivons notre voyage avec une étude de cas: le petit théorèmede Fermat prouvé en Matita. Nous montrons comment nous avons putraduire cette preuve vers différents systèmes à travers le cadrelogique Dedukti. Cette traduction se repose principalement sur deuxoutils que nous avons créees :- Dkmeta qui permet d'utiliser la réécriture comme un langage à partentière pour écrire des traductions de preuves. Un avantage de cetoutil est qu'il ré-utilise la syntaxe de Dedukti.- Universo, un outil qui permet d'implémenter l'algorithme mentionnéprécédemment qui permet de traduire une preuve d'un CTS (en Dedukti)vers un autre.Cette procédure semi-automatique permet de traduire la preuve du petitthéorème de Fermat dans une logique assez faible mais expressive quel'on appelle STTforall. STTforall est une version constructive de lathéorie des types simples avec du polymorphisme prénexe. La simplicitéde cette logique permet d'exporter des preuves de STTforall vers denombreux systèmes de preuve. Cette étude de cas montre que Deduktiest tout aussi efficace en tant qu'outil pour faire del'interopérabilité sur le plan pratique.Les outils que nous avons développés dans cette thèse ne sont passpécifiques à cette traduction et peuvent être réutilisés pourd'autres systèmes de preuve dont un encodage en Dedukti est connu(comme Coq ou bien Agda).Finalement, nous concluons ce voyage avec l'exportation du petitthéorème de Fermat vers cinq systèmes de preuve différents: Coq, Lean,Matita, OpenTheory (membre de la famille des systèmes de preuve basésur la logique d'ordre supérieure) et PVS. Cette traduction estdisponible via un site web appelé Logipedia.Logipedia n'a pas été créé seulement pour cette traduction mais avecl'objectif de contenir beaucoup plus de preuves que l'on pourraitpartager entre plusieurs systèmes de preuves. Cela rendrait Logipediaalors une encyclopédie de preuves formelles en ligne<br>There is today a large family of proof systems based upon variouslogics: The Calculus of Inductive Constructions, Higher-Order logic orSet theory, etc. The diversity of proof systems has the negativeconsequence that theorems are formalized many times. One way toovercome this issue would be to make proof systems interoperable. Inthis thesis, we have tackled the interoperability problem for proofsystems both on the theoretical and the practical side using theDedukti logical framework.We begin our journey by looking at Cumulative Type Systems (CTS), afamily of type systems which extends that of Pure Type Systemswith a subtyping relation. CTS provides a common skeleton to manylogics used today. The logic behind Coq, HOL-Light, Lean, Matita orPVS can be seen as an extension of CTS with various features(inductive types, proof irrelevance, predicate subtyping, …). Wedefine a new notion of embedding between CTS. We also provide a soundbut incomplete algorithm to decide whether a proof in one CTS can betranslated into another CTS. This algorithm can also be seen as anextension of Coq's algorithm to check that the floating universeconstraints are consistent. Then, we propose a new embedding of CTSinto Dedukti and give a soundness proof of this embedding. Theseresults show that Dedukti is suitable for studying interoperability onthe theoretical side.We continue our journey on a case of study: The proof of Fermat'slittle theorem written in Matita. We show how we were able totranslate this proof to various proof systems through Dedukti. Thistranslation mainly relies on two tools created for this purpose:— Dkmeta, a tool which proposes to use rewriting as a way to writeproofs transformation programs. One advantage of this tool is that itreuses the syntax of Dedukti itself.— Universo, a tool which implements the aforementioned algorithm whichallows to translate a proof in one CTS (written in Dedukti) toanother.This semi-automatic translation allows to translate the proof ofFermat's little theorem into a weak but expressive logic calledSTTforall. STTforall is a constructive version of Simple Type Theorywith prenex polymorphism. As a consequence, a proof in STTforall canbe exported easily to many proof systems. This case of study showsthat Dedukti is also suitable for interoperability on the practicalside.The tools used for these transformations could be reused also forproofs coming from other proof systems for which an encoding inDedukti is known (such as Coq or Agda).The journey ends with the exportation of the proof of Fermat's littletheorem encoded in STTforall towards 5 different proof systems: Coq,Lean, Matita, OpenTheory (a member of the HOL-family proof systems)and PVS. We have implemented a user interface for that via a websitecalled Logipedia.Logipedia was designed with the goal of containing many more proofs thatcould be shared between proof systems and as such is intended to be anencyclopedia of formal proofs

Les théories des types dépendants sont des systèmes formels qui peuvent être utilisés à la fois comme langages de programmation et pour la formalisation des mathématiques, et constituent la base de plusieurs assistants de preuve tels que Coq et Agda. Afin d'unifier leur étude, les Logical Frameworks (LFs) fournissent un méta-langage unifié permettant de définir ces théories, dans lequel diverses notions universelles sont intégrées par défaut et où des méta-théorèmes génériques peuvent être prouvés. Cette thèse se concentre sur les LFs conçus pour être implémentés, avec pour objectif de fournir des type-checkers génériques. Notre principale contribution est un nouveau LF permettant de représenter les théories des types avec leurs syntaxes non annotées habituelles. La clé pour permettre de supprimer des annotations sans compromettre la décidabilité du typage est l'intégration du typage bidirectionnel, une discipline dans laquelle le jugement de typage est décomposé en modes d'inférence et de checking. Si le typage bidirectionnel est déjà bien étudié dans la littérature, l'une des contributions centrales de notre travail est sa formulation dans un LF, ce qui donne un traitement générique pour toutes les théories définissables dans notre système. Notre proposition a été implémentée dans le type-checker générique BiTTs, permettant son utilisation avec diverses théories.En plus de notre contribution principale, nous proposons des avancés dans l'étude de Dedukti, un LF appartenant à la même famille que le système que nous proposons. Tout d'abord, nous revisitons le problème de la correction des encodages dans Dedukti en proposant une méthodologie qui permet de démontrer plus facilement la conservativité. De plus, nous montrons comment Dedukti peut être utilisé en pratique comme outil de traduction de preuves, en proposant une transformation pour partager des preuves avec des systèmes prédicatifs. Cette transformation a permis la traduction de preuves de Matita vers Agda, aboutissant aux toutes premières preuves en Agda du Petit Théorème de Fermat et du Postulat de Bertrand<br>Dependent type theories are formal systems that can be used both as programming languages and for the formalization of mathematics, and constitute the foundation of popular proof assistants such as Coq and Agda. In order to unify their study, Logical Frameworks (LFs) provide a unified meta-language for defining such theories in which various universal notions are built in by default and metatheorems can be proven in a theory-independent way. This thesis focuses on LFs designed with implementation in mind, with the goal of providing generic type-checkers. Our main contribution is a new such LF which allows for representing type theories with their usual non-annotated syntaxes. The key to allowing the removal of annotations without jeopardizing decidability of typing is the integration of bidirectional typing, a discipline in which the typing judgment is decomposed into inference and checking modes. While bidirectional typing has been well known in the literature for quite some time, one of the central contributions of our work is that, by formulating it in an LF, we give it a generic treatment for all theories fitting our framework. Our proposal has been implemented in the generic type-checker BiTTs, allowing it to be used in practice with various theories. In addition to our main contribution, we also advance the study of Dedukti, a sibling LF of our proposed framework. First, we revisit the problem of showing that theories are correctly represented in Dedukti by proposing a methodology for encodings which allows for showing their conservativity easily. Furthermore, we demonstrate how Dedukti can be used in practice as a tool for translating proofs by proposing a transformation for sharing proofs with predicative systems. This transformation has allowed for the translation of proofs from Matita to Agda, yielding the first-ever Agda proofs of Fermat's Little Theorem and Bertrand's Postulate

Les vérificateurs et assistants de preuve sont utilisés pour formaliser des théorèmes mathématiques et la vérification logicielle, notamment de systèmes critiques tels que des sytèmes médicaux, industriels ou de transport. La diversité des systèmes de preuves soulève la question de leur interopérabilité : comment revérifier ou réutiliser des preuves d'un système dans un autre ? Des cadres logiques tels que le lambdaPi-calcul modulo théorie procurent un formalisme commun dans lequel peuvent être exprimées divers systèmes logiques et théories mathématiques. Des outils de transformation de preuves au sein du lambdaPi-calcul modulo théorie permettent alors de traduire des preuves d'un système logique à l'autre.De manière analogue aux cadres logiques, des théories combinant plusieurs théories fournissent un langage commun entre ces théories. L'enjeu principal de ce manuscrit est l'étude de la définition et des propriétés de ces théories, spécifiquement dans le cadre des théories calculatoires, c'est-à-dire dont la définition repose sur la réécriture. Plus précisément, les combinaisons de théories calculatoires seront étudiées dans deux contextes : les logiques œcuméniques, c'est-à-dire des logiques combinant logiques intuitionnistes et classiques, et les théories des systèmes de types purs modulo réécriture, qui sont utilisées dans le lambdaPi-calcul modulo pour exprimer les systèmes logiques de divers assistants de preuve.Dans un premier temps, on s'intéresse au cas particulier des logiques œcuméniques. Une nouvelle logique œcuménique NE est définie et étudiée. Ces principales propriétés sont que sa définition, bien que guidée par, ne repose pas sur les traductions par doubles négations et qu'elle permet la définition de théories œcuméniques calculatoires, par exemple la définition d'une théorie des types simples œcuménique.Dans un second temps, les théories des systèmes de types purs modulo théorie, dont un exemple est le cadre logique du lambdaPi-calcul modulo théorie, sont étudiées. Notamment, des outils permettant de prouver le bon typage de théories calculatoires de manière modulaire sont exhibés, que ce soit pour l'extension ou la restriction (appelée fragmentation) des théories. Finalement, il est établi qu'étant donné une preuve dans une théorie combinant de multiples fragments, il est possible d'établir à quel fragment cette preuve appartient à partir des constantes qu'elle contient, sans indication explicite des règles de réécriture utilisées. Ce résultat est crucial pour justifier l'utilisation de telles théories pour l'interopérabilité des systèmes de preuves.Enfin, en s'appuyant sur la définition deec et sur les résultats de modularité précédents, on s'intéresse à une théorie calculatoire du lambdaPi-calcul nommée théorie U et combinant logiques du premier ordre et d'ordre supérieur minimales, intuitionnistes, classiques et œcuméniques, avec ou sans polymorphisme prénexe ou sous-typage par prédicats, et le calcul des constructions. Les propriétés de correction, conservativité, cohérence, normalisation, et décidabilité de la vérification de type sont notamment établies pour les fragments des logiques œcuméniques du premier order et d'ordre supérieur sont établies<br>Proof checkers and proof assistants are used to formalize mathematical theorems and verify software, notably critical systems such as medical, industrial and transport systems. The diversity of proof systems raises the question of their interoperability: how can proofs be rechecked and reused across systems? Logical frameworks such as the lambdaPi-calculus modulo theory provide a common formalism in which various logical systems and mathematical theories can be expressed. The proof transformation tools within the lambdaPi-calculus modulo theory allow proofs to be translated from one logical system another.In a similar way to logical frameworks, theories combining several theories provide a common language between theories. The main focus of this manuscript is the study of the definition and properties of these theories, specifically in the context of computational theories, that is whose definition relies on rewriting. More specifically, combinations of computational theories will be studied in two contexts: ecumenical logics, i.e. logics that combine intuitionistic and classical logics, and theories of pure type systems modulo rewriting, which are used in the lambdaPi-calculus modulo theory to express logical systems of various proof assistants.First, we look at the special case of ecumenical logics, i.e. logics that combine intuitionistic and classical logics. A new ecumenical logic called NE is defined and studied. Its main properties are that its definition, though guided by, does not rely on double negations, and that it allows the definition of computational ecumenical theories, such as an ecumenical simple type theory.In a second time, the computational theories of pure type systems, an example of which is the logical framework of the lambdaPi-calculus modulo theory, are studied. In particular, we give tools to establish the well typedness of computational theories in a modular way, whether for extension or restriction (called fragmentation) of theories. Finally, we prove that for a given proof in a theory combining multiple fragments, it is possible to establish to which fragment this proof belongs from the constants it contains, without explicit indications of the rewriting rules used. This result is crucial in justifying the use of such theories for the interoperability of proof systems.Finally, based on the definition of NE and the previous modularity results, we focus on a computational theory of lambdaPi-calculus called theory U, combining first- and higher-order logics, minimal, intuitionistic, classical and ecumenical logics, prenex polymorphism and predicate subtyping, and the calculus of constructions. Properties of soundness, conservativity, consistency, normalization, and decidability of type-checking are established for the first- and higher-order logical fragments of theory U