I am a Marie Skłodowska-Curie fellow at Inria in the Gallinette team in Nantes. Before, I did my PhD at Saarland University under the supervision of Gert Smolka.

My research centers around analysing, formalising, and machine-checking different aspects of computation in constructive type theory, and especially in the proof assistant Coq. 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, level of expertise, or academic experience!

News

• My paper Parametric Church’s Thesis: Synthetic Computability without Choice got accepted at LFSC ‘22 and won the Rosser Prize. LFCS has free online participation!

Projects

Verified extraction and compilation

I am interested in using the Coq proof assistant as a system to obtain verified executable programs: 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 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) and an introduction to Parametric Church’s Thesis and synthetic computability without choice (LFCS’ 22).

Synthetic undecidability

Decidability and unecidability 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

1. Yannick Forster, 2022. Parametric Church’s Thesis: Synthetic Computability Without Choice, In: S. Artemov and A. Nerode (editors). Logical Foundations of Computer Science, Cham: Springer International Publishing, pp. 70–89.
2. Yannick Forster, Fabian Kunze, Gert Smolka and Maximilian Wuttke, 2021. A Mechanised Proof of the Time Invariance Thesis for the Weak Call-By-Value \(λ\)-Calculus, In: L. Cohen and C. Kaliszyk (editors). 12th International Conference on Interactive Theorem Proving, ITP 2021, June 29 to July 1, 2021, Rome, Italy (Virtual Conference), LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 19:1–19:20.
3. Yannick Forster, Dominik Kirst and Dominik Wehr, 2021. Completeness theorems for first-order logic analysed in constructive type theory (extended version), J. Log. Comput., volume 31, number 1, pp. 112–151.
4. Yannick Forster, 2021. Church’s Thesis and Related Axioms in Coq’s Type Theory, In: C. Baier and J. Goubault-Larrecq (editors). 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference), LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 21:1–21:19. (talk)
5. Matthieu Sozeau, Abhishek Anand, Simon Boulier, Cyril Cohen, Yannick Forster, Fabian Kunze, Gregory Malecha, Nicolas Tabareau and Théo Winterhalter, 2020. The MetaCoq Project, J. Autom. Reason., volume 64, number 5, pp. 947–999.
6. Matthieu Sozeau, Simon Boulier, Yannick Forster, Nicolas Tabareau and Théo Winterhalter, 2020. Coq Coq Correct! verification of type checking and erasure for Coq, in Coq, Proc. ACM Program. Lang., volume 4, number POPL, pp. 8:1–8:28.
7. Yannick Forster, Fabian Kunze and Marc Roth, 2020. The weak call-by-value λ-calculus is reasonable for both time and space, Proc. ACM Program. Lang., volume 4, number POPL, pp. 27:1–27:23.
8. Yannick Forster, Fabian Kunze and Maximilian Wuttke, 2020. Verified programming of Turing machines in Coq, In: J. Blanchette and C. Hritcu (editors). Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2020, New Orleans, LA, USA, January 20-21, 2020, ACM, pp. 114–128.
9. Simon Spies and Yannick Forster, 2020. Undecidability of higher-order unification formalised in Coq, In: J. Blanchette and C. Hritcu (editors). Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2020, New Orleans, LA, USA, January 20-21, 2020, ACM, pp. 143–157.
10. Yannick Forster and Kathrin Stark, 2020. Coq à la carte: a practical approach to modular syntax with binders, In: J. Blanchette and C. Hritcu (editors). Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2020, New Orleans, LA, USA, January 20-21, 2020, ACM, pp. 186–200.
11. Yannick Forster, Dominik Kirst and Dominik Wehr, 2020. Completeness Theorems for First-Order Logic Analysed in Constructive Type Theory, In: S.N. Artëmov and A. Nerode (editors). Logical Foundations of Computer Science - International Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4-7, 2020, Proceedings, Lecture Notes in Computer Science, Springer, pp. 47–74.
12. Dominique Larchey-Wendling and Yannick Forster, 2020. Hilbert’s Tenth Problem in Coq (extended version), CoRR, volume abs/2003.04604.
13. Yannick Forster and Gert Smolka, 2019. Call-by-Value Lambda Calculus as a Model of Computation in Coq, J. Autom. Reason., volume 63, number 2, pp. 393–413.
14. Yannick Forster, Ohad Kammar, Sam Lindley and Matija Pretnar, 2019. On the expressive power of user-defined effects: Effect handlers, monadic reflection, delimited control, J. Funct. Program., volume 29, p. e15.
15. Yannick Forster, Dominik Kirst and Gert Smolka, 2019. On synthetic undecidability in Coq, with an application to the Entscheidungsproblem, In: A. Mahboubi and M.O. Myreen (editors). Proceedings of the 8th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2019, Cascais, Portugal, January 14-15, 2019, ACM, pp. 38–51.
16. Yannick Forster and Dominique Larchey-Wendling, 2019. Certified undecidability of intuitionistic linear logic via binary stack machines and Minsky machines, In: A. Mahboubi and M.O. Myreen (editors). Proceedings of the 8th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2019, Cascais, Portugal, January 14-15, 2019, ACM, pp. 104–117.
17. Yannick Forster, Steven Schäfer, Simon Spies and Kathrin Stark, 2019. Call-by-push-value in Coq: operational, equational, and denotational theory, In: A. Mahboubi and M.O. Myreen (editors). Proceedings of the 8th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2019, Cascais, Portugal, January 14-15, 2019, ACM, pp. 118–131.
18. Yannick Forster and Fabian Kunze, 2019. A Certifying Extraction with Time Bounds from Coq to Call-By-Value Lambda Calculus, In: J. Harrison, J. O’Leary and A. Tolmach (editors). 10th International Conference on Interactive Theorem Proving, ITP 2019, September 9-12, 2019, Portland, OR, USA, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 17:1–17:19.
19. Dominique Larchey-Wendling and Yannick Forster, 2019. Hilbert’s Tenth Problem in Coq, In: H. Geuvers (editor). 4th International Conference on Formal Structures for Computation and Deduction, FSCD 2019, June 24-30, 2019, Dortmund, Germany, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 27:1–27:20.
20. Fabian Kunze, Gert Smolka and Yannick Forster, 2018. Formal Small-Step Verification of a Call-by-Value Lambda Calculus Machine, In: S. Ryu (editor). Programming Languages and Systems - 16th Asian Symposium, APLAS 2018, Wellington, New Zealand, December 2-6, 2018, Proceedings, Lecture Notes in Computer Science, Springer, pp. 264–283.
21. Yannick Forster, Edith Heiter and Gert Smolka, 2018. Verification of PCP-Related Computational Reductions in Coq, In: J. Avigad and A. Mahboubi (editors). Interactive Theorem Proving - 9th International Conference, ITP 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9-12, 2018, Proceedings, Lecture Notes in Computer Science, Springer, pp. 253–269.
22. Yannick Forster, Ohad Kammar, Sam Lindley and Matija Pretnar, 2017. On the expressive power of user-defined effects: effect handlers, monadic reflection, delimited control, Proc. ACM Program. Lang., volume 1, number ICFP, pp. 13:1–13:29.
23. Yannick Forster and Gert Smolka, 2017. Weak Call-by-Value Lambda Calculus as a Model of Computation in Coq, In: M. Ayala-Rincón and C.A. Muñoz (editors). Interactive Theorem Proving - 8th International Conference, ITP 2017, Brası́lia, Brazil, September 26-29, 2017, Proceedings, Lecture Notes in Computer Science, Springer, pp. 189–206.

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.

Teaching

Supervised students

Niklas Mück, 2021, Bachelor's thesis, co-advised with Dominik Kirst
The Arithmetical Hierarchy and Post’s Theorem in Coq

Roberto Álvarez, 2021, Master's thesis
Mechanized undecidability of subtyping in System F

Felix Jahn, 2020, Bachelor's thesis
Synthetic One-One, Many-One, and Truth-Table Reducibility in Coq

Marcel Ullrich, 2020, Bachelor's thesis
Generating induction principles for nested inductive types in MetaCoq

Dominik Wehr, 2019, Bachelor's thesis, co-advised with Dominik Kirst
A Constructive Analysis of First-Order Completeness Theorems in Coq

Simon Spies, 2019, Bachelor's thesis
Formalising the Undecidability of Higher-Order Unification

Maximilian Wuttke, 2018, Bachelor's thesis
Verified Programming Of Turing Machines In Coq

Edith Heiter, 2017, Bachelor's thesis, co-advised with Gert Smolka
Undecidability of the Post Correspondence Problem in Coq

Lectures

Short CV

• since 2021: Postdoctoral Marie Skłodowska-Curie Fellow in the Gallinette team at Inria Nantes
• 2021: PhD student in the group of Gert Smolka at Saarland University
• 2016: MPhil in advanced computer science at the University of Cambridge
• 2015: B. Sc. in computer science at Saarland University

Click here for a full but only occasionally updated CV.