PhD Position F/M Algebraic structures in dependent types theory

Télécharger l'offre au format PDF
Le descriptif de l’offre ci-dessous est en Anglais

Type de contrat : CDD

Niveau de diplôme exigé : Bac + 5 ou équivalent

Fonction : Doctorant

A propos du centre ou de la direction fonctionnelle

The Inria Rennes - Bretagne Atlantique Centre is one of Inria's eight centres and has more than thirty research teams. The Inria Center is a major and recognized player in the field of digital sciences. It is at the heart of a rich R&D and innovation ecosystem: highly innovative PMEs, large industrial groups, competitiveness clusters, research and higher education players, laboratories of excellence, technological research institute, etc.

Contexte et atouts du poste

The PhD thesis witll be co-supervised by Assia Mahboubi (GALLINETTE) and Cyril Cohen (STAMP/CASH). It takes place in the frame of the FRESCO ERC project, conducted by Assia Mahboubi.

Mission confiée

The goal of this project consists in advancing the support for abstract algebra in proof assistants based on dependent type theory, such as Coq/Rocq, Agda or Lean. The main objective is to devise principled approaches to relate the different formal representations of a given structure, typically involving different variants of inductive types, with the relevant corresponding category. This study should enable automating the generation of the expected corresponding data and properties, improving this way the robustness and maintainability of libraries of formalized mathematics. Typical examples of expected applications include the generation of abstract syntax trees, of hierarchies of morphisms, of the construction of (co)limits, etc. By lack of relevant support, all these items are currently treated in a manual and ad hoc manner in state corpora of formalized mathematics, such as Coq/Rocq's Mathematical Components library or Lean's Mathlib ibrary.

Hierarchies of abstract mathematical structures are the cornerstone of modern libraries of formalized mathematics [2,4]. In type theory, mathematical structures are usually represented as telescopes, i.e., as dependent tuples (also called dependent records), which pack a carrier type with a signature and an equational theory. These telescopes provide an internal representation of interfaces for domains equipped with an algebraic structure, and hierarchies describe the existing inheritance and sharing relations between these abstractions.
Modern techniques for representing algebraic structures and for inferring instances thereof are used extensively in large corpora of formalized mathematics, so as to share notations and properties [2,4], or to provide representation independence principles [1]. Studying and exploiting the functorial structure of (co)datatype constructors [3] as well as syntactic relational models of type theory [5,6] have resulted in useful concrete tools, e.g., for automating proof transfer or for generating useful elimination schemes. But no such support exist as of today to turn basic category theory into effective automation for formalized abstract algebra, resulting in excessively bureaucratic formal developments. The main objective of the present project is thus to investigate this question.


[1] Carlo Angiuli, Evan Cavallo, Anders Mörtberg,Max Zeuner. Internalizing representation independence with univalence. Proc. ACM Program. Lang. 5(POPL): 1-30 (2021)

[2] Anne Baanen. “Use and Abuse of Instance Parameters in the Lean Mathematical Library”. Proc: ITP 2022: 4:1-4:20.

[3] Basil Fürer, Andreas Lochbihler, Joshua Schneider, Dmitriy Traytel. Quotients of Bounded Natural Functors. Log. Methods Comput. Sci. 18(1) (2022).

[4] Assia Mahboubi and Enrico Tassi. Mathematical Components. Zenodo, Jan. 2021.

[5] Nicolas Tabareau, Éric Tanter, and Matthieu Sozeau. “The Marriage of Univalence and Parametricity”. J. ACM 68.1 (2021), 5:1–5:44.

[6] Enrico Tassi. “Deriving Proved Equality Tests in Coq-Elpi: Stronger Induction Principles for Containers in Coq”. Proc. ITP 2019: 29:1-29:18

Principales activités

The PhD student will contribute to the development of fundamental type theoretic and categorical methods, and will investigate their implementation in the Coq/Rocq proof assistant.

Compétences

Working language : English or French.

We particularly welcome applications from underrepresented groups in mathematics and computer science.

Avantages

  • Subsidized meals
  • Partial reimbursement of public transport costs

Rémunération

monthly gross salary amounting to 2100 euros