Ban lãnh đạo nghiên cứu : Julia LAWALL

Đồng hướng dẫn : 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.

Bài báo khoa học 2021-2022