Computer systems are nowadays entangled with every aspect of our life. Whereas a few decades ago a ``computer bug'' might have been just a little annoyance, it can be life-threatening today. It is therefore of vital importance to develop a systematic methodology for producing ``bug-free'' software. The task is easier for declarative programming languages than for imperative ones. In particular, functional languages come with a rich tool set helping establishing the correctness of programs. This is mainly due to the successful application of mathematical logic, based on the proofs-as-programs principle (also known as Curry-Howard correspondence) stating that writing a program is basically the same thing as proving a theorem, and the computation of the program is the same a normalizing the proof. This is the basis of all functional programming languages.

The normalization process and its complexity depend on the chosen representation of the proof or program. The standard setting here is the correspondence between terms on the lambda-calculus on one side and proofs in intuitionistic logic on the other side. And in this setting, intuitionistic combinatorial proofs offer a completely new perspective, as they (i) incorporate a form of sharing that is not present in the lambda-calculus, and (ii) form a representation of proofs that it independent from the syntax of proof systems.

In this project we plan to explore the potential of combinatorial proofs in two directions: first, in the theory of functional programming languages, through their normalization behaviour, and second, in the verification of imperative programs, through their representation of proofs in the logic of bunched implications.

Partout team, Inria Saclay - Ile-de-France

Responsible: Lutz Straßburger

Mathematical foundations group, University of Bath

Responsible: Willem Heijltjes

PPLV group, University College London

Responsible: David Pym

Responsible: Lutz Straßburger

Mathematical foundations group, University of Bath

Responsible: Willem Heijltjes

PPLV group, University College London

Responsible: David Pym

- PhD defense of Giti Omidvar, Inria Saclay, France, 11 December 2023
- PhD defense of Marianela Morales, Inria Saclay, France, 8 December 2023
- Workshop on New Ideas in Effects, Types, and Sharing (NIETS), University of Bath, UK, 14-16 June 2022
- Structure vs Invariants in Proofs (StrIP) Kick-off Workshop, University of Birmingham, UK, 7-10 June 2022

(Due to the Covid19 crisis, all meetings planned for 2020 and 2021 have been cancelled.)

Giti Omidvar and Lutz
Straßburger

**Combinatorial Flows as Bicolored Atomic Flows**

Pdf September 2022

Presented at WoLLIC 2022

Willem Heijltjes and Dominic Hughes and Lutz Straßburger

**Normalization without syntax**

Pdf August 2022

In proceedings of FSCD 2022

Pdf September 2022

Presented at WoLLIC 2022

Willem Heijltjes and Dominic Hughes and Lutz Straßburger

Pdf August 2022

In proceedings of FSCD 2022

Last update: December 13, 2023 Lutz Straßburger