Supervision : Julia LAWALL

Co-supervision : DAGAND Pierre-Evariste

Effectful programs and their proofs in type theory : application to certified compilation and certified packet processing

One way to reason about our programs is to write them directly into a proof assistant. Using the Curry-Howard correspondence, programs and proofs are then one. In order not to undermine the logical consistency of the proof assistant, the system is forced to restrict the programs to have no side effects. However, side effects are ubiquitous and essential in programming. Different techniques such as monads or algebraic effects have emerged to model them, thus offering a way to write imperative programs in purely functional languages. It is therefore quite natural that the results of decades of research invested in reasoning about imperative programs try to be adapted to reasoning about programs with effects. In this thesis, we are first interested in the use of separation logic to reason about programs with effects implemented in a proof assistant. We study an approach to describe the behaviour of effects using a predicate transformer. We focus first on freshness, then on packet processing and zero-copy. To study our approach, we rely on two concrete examples which are the SimplExpr module of CompCert and the decoder library Nom. Finally, in order to compile the packet parsers produced to C, we propose a refinement method removing the continuations introduced by the use of a free monad and performing some optimizations.

2021-2022 Publications

• 2022
  • P. Nigron : “Programmes avec effets et leurs preuves dans la théorie des types : application à la compilation certifiée et aux traitements de paquets certifiés”, thesis, phd defence 11/17/2022, supervision Lawall, Julia, co-supervision : Dagand, Pierre-Evariste (2022)
• 2021
  • P. Nigron, P.‑E. Dagand : “Reaching for the Star: Tale of a Monad in Coq”, Leibniz International Proceedings in Informatics, vol. 193, Leibniz International Proceedings in Informatics (LIPIcs), Rome, Italy, pp. 29:1-29:19, (Schloss Dagstuhl) (2021)