My picture

Yannick Forster

yannick.forster@inria.fr

, office BJ31

ORCID dblp Github Google Scholar

I am a tenured researcher (“chargé de recherche”) at Inria in the Cambium team in Paris.

My research focuses on proof assistants. I am interested in formalisation of models of computation and complexity, code extraction and compilation, meta-programming, type theory, and constructive and synthetic mathematics. Much of my research involves the proof assistant Rocq. See below for a list of projects. I am excited about any potential collaborator for any of these topics, if you are interested in working with me please get in touch no matter your location or experience – including no or little experience!

Before joining Cambium, I was a Marie Skłodowska-Curie fellow at Inria in the Gallinette team in Nantes. And before that, I did my PhD at Saarland University with Gert Smolka.

News

Older news * In October 2025 + [Mathis Bouverot-Dupuis](https://mathisbd.github.io/) is starting his PhD on guarantees for meta-programming, co-supervised by [François Pottier](https://cambium.inria.fr/~fpottier/). + [Timothée Huneau](https://timotheehuneau.github.io/) is starting his PhD on constructive and classical reverse mathematics related to model theory, co-supervised by [Dominik Kirst](https://ps.uni-saarland.de/~kirst/) and [Sam van Gool](https://www.samvangool.net/). + Sara Rousta is starting her Master's thesis on realisability in synthetic computability, co-supervised by [Dominik Kirst](https://ps.uni-saarland.de/~kirst/). + [Jean Caspar](https://jeancaspar.github.io) is starting a 4 months internship on continuity properties for partial functions in constructive mathematics. * I was in the PC of ITP '26. * Together with [Chantal Keller](https://usr.lmf.cnrs.fr/~ckeller/), I am a PC chair of [ITP '25](https://icetcs.github.io/frocos-itp-tableaux25/itp/). * I gave an invited talk at [LFMTP '25](https://lfmtp.github.io/lfmtp-page/workshops/2025/) on obtaining executable programs from dependently typed proof assistants. * I am in the PC of [CICM '25](https://cicm-conference.org/2025/cicm.php). * From April to August, [Simon Dima](https://www.normalesup.org/~sdima/about/) will do an internship with me on extraction of programs from proof assistants, and [Timothée Huneau](https://timotheehuneau.github.io/) on a Rocq proof on the Downward Löwenheim Skolen theorem for arbitrary cardinalities, co-supervised by Dominik Kirst. * In June and July, [Hugo Segoufin-Chollet](https://hsegoufin.github.io/) will do an internship on defining the semantics of a sublanguage of CakeML in Rocq. * I'm very proud of my students who got abstracts accepted at [TYPES '25](https://msp.cis.strath.ac.uk/types2025/accepted.html): + Janis Bailitis on [Löb’s Theorem and Provability Predicates in Rocq](https://msp.cis.strath.ac.uk/types2025/abstracts/TYPES2025_paper17.pdf) (joint work with Dominik Kirst), + Mathis Bouverot-Dupuis on [Code Generation via Meta-programming in Dependently Typed Proof Assistants (Experience Report)](https://msp.cis.strath.ac.uk/types2025/abstracts/TYPES2025_paper2.pdf), and + Yee-Jian Tan on [Towards Formalising the Guard Checker of Rocq](https://msp.cis.strath.ac.uk/types2025/abstracts/TYPES2025_paper15.pdf). * I am an invited speaker at [CSL '25](https://csl2025.github.io/) in Amsterdam in February. * I am an invited speaker at the [Simons Institute for the Theory of Computing and SLMath Joint Workshop: AI for Mathematics and Theoretical Computer Science](https://simons.berkeley.edu/workshops/simons-institute-theory-computing-slmath-joint-workshop-ai-mathematics-theoretical) in Berkeley in April * I was in the PC of [PLDI '25](https://pldi25.sigplan.org/). * The [5-th busy beaver number is 47,176,870](https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237). I reviewed the Coq proof and can confirm that it proves what it claims to prove. This [Quanta Magazine article](https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/) has the full story, and this [Le Monde article](https://www.lemonde.fr/sciences/article/2024/07/17/mathematiques-le-defi-du-castor-affaire-resolu_6251337_1650684.html) has a shorter story in French. * From September to November, I will be teaching the [course on proof assistants](https://mpri-prfa.github.io) in the Parisian Master of Research in Computer Science (MPRI) together with [Théo Winterhalter](https://theowinterhalter.github.io/). * [Thomas Lamiaux](https://thomas-lamiaux.github.io) started his PhD in September in Nantes, and will work with Nicolas Tabareau, Matthieu Sozeau, and me on Coq's guard condition. * [Mathis Bouverot-Dupuis](https://mathisbd.github.io/) will do a 5 months long internship with me, working on meta-programming in proof assistants based on dependent type theory. * From May to August, I had two interns working on the MetaCoq project: [Yee-Jian Tan](https://www.yeejian.dev), working on a reimplementation and specification of Coq's guard condition, and Weituo Dai, working on scope guarantees for meta-programs. * I am workshop co-chair of [ICFP '24](https://icfp24.sigplan.org) together with [Chandra Nandi](https://cnandi.com/). * I gave an invited talk on [Synthetic Computability without Choice](downloads/talk-pls24.pdf) at the Panhellenic Logic Symposium in Thessaloniki, reporting on joint work with Dominik Kirst, Gert Smolka, Felix Jahn, Niklas Mück, and Haoyi Zeng. * Our paper [Separating Markov's Principles](https://inria.hal.science/hal-04584831), joint work with Liron Cohen, Dominik Kirst, Bruno da Rocha Paiva, and Vincent Rahli, got accepted at [LICS '24](https://lics.siglog.org/lics24/accepted.php). * Our paper [Verified Extraction from Coq to OCaml](https://hal.science/hal-04329663), joint work with Matthieu Sozeau and Nicolas Tabareau, got accepted at [PLDI '24](https://pldi24.sigplan.org/) and was chosen as a distinguished paper! * I will attend TYPES '24. Lots of interesting talks in [session 4](https://easychair.org/smart-program/TYPES2024/2024-06-10.html#talk:253953)! * Our paper *The Kleene-Post and Post’s Theorem in the Calculus of Inductive Constructions* with Dominik Kirst and Niklas Mück was accepted at [CSL '24](https://csl2024.github.io/Home/#accepted%20papers) [(pre-print)](https://www.ps.uni-saarland.de/~kirst/downloads/paper-csl24.pdf). * We ran a [tutorial on MetaCoq](https://popl24.sigplan.org/details/POPL-2024-tutorialfest/8/MetaCoq-Tutorial) at POPL, on Sunday, January 14th, with [Meven Lennon-Bertrand](https://www.meven.ac), [Matthieu Sozeau](https://sozeau.gitlabpages.inria.fr/www/), and [Théo Winterhalter](https://theowinterhalter.github.io/). * As of December 1st, I joined the [Cambium team](http://cambium.inria.fr/) at Inria Paris on a permanent position. * From September to November I taught the [course on proof assistants](https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-7-2) in the Parisian Master of Research in Computer Science (MPRI) together with [Théo Winterhalter](https://theowinterhalter.github.io/). * Our paper [Oracle Computability and Turing Reducibility in the Calculus of Inductive Constructions](https://arxiv.org/abs/2307.15543) with Dominik Kirst and Niklas Mück was accepted at [APLAS '23](https://conf.researchr.org/home/aplas-2023). * New pre-print on [hal](https://hal.science/EC-NANTES/hal-04077552v1): *Correct and Complete Type Checking and Certified Erasure for Coq, in Coq*, with Matthieu Sozeau, Meven Lennon-Bertrand, Jakob Botsch Nielsen, Nicolas Tabareau, and Théo Winterhalter. * I gave 3 lectures on Coq, MetaCoq, and (verified) extraction at the [Proof and Computation 2023](https://www.mathematik.uni-muenchen.de/~schwicht/pc23.php) autumn school in Herrsching near Munich in September. Slides for [lecture 1 on Coq](https://docs.google.com/presentation/d/e/2PACX-1vRYiD3-WmKIthTkKrbrPzvyJOxiJWwfkCvfZ1U6uKTYEaFmxAO1SlucoIk7BybEK3bz_KqDCowi5way/pub), [lecture 2 on MetaCoq](https://docs.google.com/presentation/d/e/2PACX-1vRKDPKnz6YT5qVR8GsqZ5pD0R5ZvbXrg3oGKCzNo7eGiKeAITUm4cRQpyoq0-mbGIeiz5jqq3xWMBSi/pub), [lecture 3 on verified extraction](https://docs.google.com/presentation/d/e/2PACX-1vR7GdStSsogyQ_-Jg5x-kpqxdbkAedlOCemY_fe0M04In01MWLy6g6LwnMevIOA0C7wQEIaLUWqcfCY/pub). * I will attend [ICFP 2023](https://icfp23.sigplan.org/) in Seattle where I served as workshop co-chair with [Arthur Azevedo de Amorim](http://arthuraa.net/). * I gave a talk on [Synthetic Computability in Constructive Type Theory](files/talk-mfps23.pdf) in the special session on proof assistants at [CALCO & MFPS 2023](https://coalg.org/calco-mfps-2023/mfps/) in Bloomington, Indiana. * I was an invited speaker at [TYPES 2023](https://types2023.webs.upv.es) in Valencia and gave a talk about [verified extraction from Coq to OCaml](https://docs.google.com/presentation/d/e/2PACX-1vT8g651LbcmxeP7_GRrFFvJmfFKJY6IoDuxyK2ZDLWt7ccjJxGyF3TN-PZybYMjQkMcrkL5odOYzGc1/pub). * At TYPES, I also gave a talk on [*Markov’s Principles in Constructive Type Theory*](files/markovs-principles-types23.pdf), joint work with Dominik Kirst, Bruno da Rocha Paiva, and Vincent Rahli. * Our paper *A Computational Cantor-Bernstein and Myhill's Isomorphism Theorem in Constructive Type Theory* with Felix Jahn and [Gert Smolka](https://www.ps.uni-saarland.de/~smolka/) was accepted at [CPP 2023](https://popl23.sigplan.org/home/CPP-2023). Pre-print on [hal](https://hal.inria.fr/view/index/docid/3891390). * Our paper *Constructive and Synthetic Reducibility Degrees: Post's Problem for Many-one and Truth-table Reducibility in Coq* with Felix Jahn was accepted at [CSL 2023](https://csl2023.mimuw.edu.pl/). Pre-print on [hal](https://hal.inria.fr/hal-03901942v1). * The [TYPES conference](https://types22.inria.fr) in Nantes has lots of interesting talks! I was involved in several: - On Tuesday, Tiago Cogumbreiro will present our work [*Towards a Mechanized Theory of Computation for Education*](https://types22.inria.fr/files/2022/06/TYPES_2022_paper_50.pdf). - Immediately afterwards, Felix Jahn will talk about our joint work with Gert Smolka, [*Myhill Isomorphism Theorem and a Computational Cantor-Bernstein Theorem in Constructive Type Theory*](https://types22.inria.fr/files/2022/06/TYPES_2022_paper_53.pdf). - Then I'll give a talk on [*Synthetic Turing Reducibility in CIC*](https://types22.inria.fr/files/2022/06/TYPES_2022_paper_64.pdf), joint work with Dominik Kirst. - On Wednesday, I'll be talking about [*Aspects of a machine-checked intermediate language for extraction from Coq, in MetaCoq*](https://types22.inria.fr/files/2022/06/TYPES_2022_paper_67.pdf), joint work with Matthieu Sozeau. - And on Thursday, Dominik Kirst will talk about our [*Synthetic Versions of the Kleene-Post and Post’s Theorem*](https://types22.inria.fr/files/2022/06/TYPES_2022_paper_65.pdf), joint work with Niklas Mück. * Our paper [Synthetic Kolmogorov Complexity in Coq](#forster:hal-03596267) with Fabian Kunze and Nils Lauermann got accepted at ITP '22! * Two new pre-prints out! With Felix Jahn and Gert Smolka: [A Constructive and Synthetic Theory of Reducibility: Myhill’s Isomorphism Theorem and Post’s Problem for Many-one and Truth-table Reducibility in Coq](#forster:hal-03580081). With Fabian Kunze and Nils Lauermann: [Synthetic Kolmogorov Complexity in Coq](#forster:hal-03596267). * My paper [Parametric Church's Thesis: Synthetic Computability without Choice](#10.1007/978-3-030-93100-1_6) got accepted at [LFSC '22](https://lfcs.ws.gc.cuny.edu/) and won the Rosser Prize. LFCS has free online participation!

Current Students

Projects

Verified extraction and compilation

I am interested in using the Coq proof assistant as a system to obtain verified executable programs: I co-developed verified extraction from Coq to OCaml (PLDI ’24); I am involved in the MetaCoq project, a formalisation and implementation of Coq in Coq, where I verified type and proof erasure (POPL ’20); and I am a team member in the CertiCoq project, a verified compiler from Coq to C.

Synthetic computability

Synthetic computability was pioneered by Richman, Bridges, and Bauer in different flavours of constructive logic. In synthetic computability theory, the fact that all definable functions in constructive logic are computable is made explicit via axioms. Thereby, formalisations can focus on the mathematical essence of results and on rigorous simplification of proofs rather than on encoding programs in model of computation.

Since synthetic computability in most presentations assumes the axiom of countable choice the theory becomes anti-classical, i.e. the law of excluded middle is disprovable. When choosing constructive type theory as implemented by the Coq proof assistant as foundation for synthetic computability, classical logic via the law of excluded middle can be consistently assumed.

We gave a general discussion of the axiom CT (Church’s Thesis) in relation to other axioms for Coq’s type theory (CSL ’21) an introduction to Parametric Church’s Thesis and synthetic computability without choice (LFCS 22), a definition of Kolmogorov complexity (ITP ‘22’), a solution for Post’s problem for many-one and truth-table reducibility (CSL ’23), a definition of oracle computability and Turing reductions (APLAS ‘23’), and a proof of Post’s hierarchy theorem (CSL ‘24’).

Synthetic undecidability

Decidability and undecidability proofs are the subarea of computability theory with the most influence on general theoretical computer science. Both kinds of proofs are often intricate and their details are error-prone: Several later retracted results have been published at renowned venues. Synthetic undecidability offers a method to verify the undecidability in a proof assistant such that no doubt remains, without ever dealing with models of computation. This is because all functions definable in Coq’s type theory are by definition computable, and thus undecidability of a problem can be proved by a reduction from Turing machine halting to the problem in question. A prime result is our synthetic undecidability proof of Hilbert’s tenth problem (FSCD ’19). I co-maintain the Coq Library of Undecidability Proofs, a collaborative project containing machine-checked undecidability proofs.

Formalising models of computation

We have given several machine-checked equivalence proofs between different models of computation such as Turing machines, register machines, the lambda-calculus or partial recursive functions. As part of this work we have proved that the weak call-by-value λ-calculus is reasonable for both time and space (POPL ’20) and provided a machine-checked version of the result for time (ITP ’21).

Publications

Pre-prints
  1. Thomas Lamiaux, Yannick Forster, Matthieu Sozeau, Nicolas Tabareau. Nested Inductive Types – Justified and Usable Nested Inductive Types in Lean and Rocq, PLDI 2026..
  2. Mathis Bouverot-Dupuis, Yannick Forster. Code Generation via Meta-programming in Dependently Typed Proof Assistants, ESOP 2026.
  3. Haoyi Zeng, Yannick Forster, Dominik Kirst, Takako Nemoto. Post's Problem in Constructive Mathematics, pre-print.

Conferences
  1. Martin Baillon, Yannick Forster, Assia Mahboubi, Pierre-Marie Pédrot, Matthieu Piquerez. A Zoo of Continuity Properties in Constructive Type Theory, FSCD 2025.
  2. Liron Cohen, Yannick Forster, Dominik Kirst, Bruno da Rocha Paiva, and Vincent Rahli. Separating Markov's Principles, LICS 2024.
  3. Yannick Forster, Matthieu Sozeau, and Nicolas Tabareau. Verified Extraction from Coq to OCaml, PLDI 2024.
  4. Yannick Forster, Dominik Kirst, and Niklas Mück. The Kleene-Post and Post’s Theorem in the Calculus of Inductive Constructions, CSL 2024.
  5. Yannick Forster, Dominik Kirst, and Niklas Mück. Oracle Computability and Turing Reducibility in the Calculus of Inductive Constructions, APLAS 2023.
  6. Yannick Forster, Felix Jahn, and Gert Smolka. A Computational Cantor-Bernstein and Myhill’s Isomorphism Theorem in Constructive Type Theory, CPP 2023.
  7. Yannick Forster and Felix Jahn. Constructive and Synthetic Reducibility Degrees: Post’s Problem for Many-One and Truth-Table Reducibility in Coq, CSL 2023.
  8. Yannick Forster, Fabian Kunze, and Nils Lauermann. Synthetic Kolmogorov Complexity in Coq, ITP 2022.
  9. Yannick Forster, 2022. Parametric Church’s Thesis: Synthetic Computability Without Choice, LFCS 2022.
  10. Yannick Forster, Fabian Kunze, Gert Smolka, and Maxi Wuttke. A Mechanised Proof of the Time Invariance Thesis for the Weak Call-By-Value λ-Calculus, ITP 2021.
  11. Yannick Forster. Church’s Thesis and Related Axioms in Coq’s Type Theory, CSL 2021. (talk)
  12. Matthieu Sozeau, Simon Boulier, Yannick Forster, Nicolas Tabareau, and Théo Winterhalter. Coq Coq Correct! verification of type checking and erasure for Coq, in Coq, POPL 2020.
  13. Yannick Forster, Fabian Kunze, and Marc Roth. The weak call-by-value λ-calculus is reasonable for both time and space, POPL 2020.
  14. Yannick Forster, Fabian Kunze, and Maxi Wuttke. Verified programming of Turing machines in Coq, CPP 2020.
  15. Simon Spies and Yannick Forster. Undecidability of higher-order unification formalised in Coq, CPP 2020.
  16. Yannick Forster and Kathrin Stark. Coq à la carte: a practical approach to modular syntax with binders, CPP 2020.
  17. Yannick Forster, Dominik Kirst, and Dominik Wehr. Completeness Theorems for First-Order Logic Analysed in Constructive Type Theory, LFCS 2020.
  18. Yannick Forster and Fabian Kunze. A Certifying Extraction with Time Bounds from Coq to Call-By-Value Lambda Calculus, ITP 2019.
  19. Dominique Larchey-Wendling and Yannick Forster. Hilbert’s Tenth Problem in Coq, FSCD 2019.
  20. Yannick Forster, Dominik Kirst, and Gert Smolka. On synthetic undecidability in Coq, with an application to the Entscheidungsproblem, CPP 2019.
  21. Yannick Forster and Dominique Larchey-Wendling. Certified undecidability of intuitionistic linear logic via binary stack machines and Minsky machines, CPP 2019.
  22. Yannick Forster, Steven Schäfer, Simon Spies, and Kathrin Stark. Call-by-push-value in Coq: operational, equational, and denotational theory, CPP 2019.
  23. Fabian Kunze, Gert Smolka, and Yannick Forster. Formal Small-Step Verification of a Call-by-Value Lambda Calculus Machine, APLAS 2018.
  24. Yannick Forster, Edith Heiter, and Gert Smolka. Verification of PCP-Related Computational Reductions in Coq, ITP 2018.
  25. Yannick Forster, Ohad Kammar, Sam Lindley, and Matija Pretnar. On the expressive power of user-defined effects: effect handlers, monadic reflection, delimited control, ICFP 2017.
  26. Yannick Forster and Gert Smolka. Weak Call-by-Value Lambda Calculus as a Model of Computation in Coq, ITP 2017.

Journals
  1. Matthieu Sozeau, Yannick Forster, Meven Lennon-Bertrand, Jakob Botsch Nielsen, Nicolas Tabareau, and Théo Winterhalter. Correct and Complete Type Checking and Certified Erasure for Coq, in Coq, Journal of the ACM.
  2. Yannick Forster, Dominik Kirst, and Dominik Wehr. Completeness theorems for first-order logic analysed in constructive type theory (extended version), J. Log. Comput. , volume 31, number 1, pp. 112–151.
  3. Matthieu Sozeau, Abhishek Anand, Simon Boulier, Cyril Cohen, Yannick Forster, Fabian Kunze, Gregory Malecha, Nicolas Tabareau, and Théo Winterhalter. The MetaCoq Project, J. Autom. Reason., volume 64, number 5, pp. 947–999.
  4. Dominique Larchey-Wendling and Yannick Forster. Hilbert’s Tenth Problem in Coq (extended version), LMCS, Volume 18, Issue 1.
  5. Yannick Forster and Gert Smolka. Call-by-Value Lambda Calculus as a Model of Computation in Coq, J. Autom. Reason., volume 63, number 2, pp. 393–413.
  6. Yannick Forster, Ohad Kammar, Sam Lindley, and Matija Pretnar. On the expressive power of user-defined effects: Effect handlers, monadic reflection, delimited control, J. Funct. Program., volume 29, p. e15.

Extended Workshop Abstracts

Theses

Computability in Constructive Type Theory
PhD thesis, Saarland University, 2021.

On the expressive power of effect handlers and monadic reflection (pdf)
Master’s Thesis, Robinson College, University of Cambridge, 2016.

A Formal and Constructive Theory of Computation (pdf)
Bachelor’s Thesis, Programming Systems Lab, Saarland University, 2014.

Talks

Talks since December 2021, for older talks see my old website.

Teaching

Supervised students

Lectures

Short CV

Click here for a full but only occasionally updated CV.

Website based on this basic page template developed by Théo Winterhalter and me.