Thu 27 Aug 2026 13:30 - 13:48 at IP126 Auditorium - Dependent Types and Proof Chair(s): Sam Westrick

In the meta-theoretic study of dependent type theory, confluence techniques are powerful tools for establishing the properties required when proving correctness of implementations. Unfortunately, such techniques have historically mostly been studied for type theories with untyped conversion, which are harder to relate to semantics. In this work, we show how to scale confluence techniques to rich dependent type theories with typed conversion. To do this, we prove a confluence theorem for a theory featuring not only function types (without eta) and universes, but also some inductive types (Nat and sums), dependent pairs (without eta), definitional proof irrelevance and a lift type (with eta), allowing to simulate a weak form of explicit cumulativity (as done in Agda). We then show how to extend our framework with a proof-irrelevant equality in two ways, either with an observational equality or with an eliminator with a non-linear computation rule (as done in Lean), illustrating the extensibility of our approach. With confluence in hand, we then fulfil our promise of showing correctness of conversion and type checking algorithms. Moreover, while our specification for the type theory is fully annotated, which eases the connection with semantics, we prove correctness of algorithms that operate on usual non-annotated terms, an important optimization for real-life implementations. Finally, our results have been fully formalized in Rocq and can serve as a basis for future type theory formalizations.

Thu 27 Aug

Displayed time zone: Eastern Time (US & Canada) change

13:30 - 15:00
Dependent Types and ProofICFP Papers at IP126 Auditorium
Chair(s): Sam Westrick New York University
13:30
18m
Talk
Confluence Techniques for Dependent Type Theory with Typed ConversionRemote
ICFP Papers
DOI Pre-print
13:48
18m
Talk
An Equational and Graphical Fixed-Point Calculus (Functional Pearl)Remote
ICFP Papers
Gustavo de Mendonça Freire Universidade Federal do Rio de Janeiro, Hugo Musso Gualandi Universidade Federal do Rio de Janeiro, Hugo Nobrega Universidade Federal do Rio de Janeiro, Joao Paixao Universidade Federal do Rio de Janeiro
DOI
14:06
18m
Talk
Citrus: Algebraic Reasoning About Superconductor Electronics
ICFP Papers
Harlan Kringen , Ben Hardekopf University of California at Santa Barbara, Timothy Sherwood University of California at Santa Barbara
DOI
14:24
18m
Talk
Compositional Neural-Cyber-Physical System Verification in the Interactive Theorem Prover of Your Choice
ICFP Papers
Matthew L. Daggitt University of Western Australia, Ekaterina Komendantskaya University of Southampton, Alessandro Bruni IT University of Copenhagen, Samuel Teuber KIT, Alistair Sirman University of Southampton, Grant Passmore Imandra Inc., Josh Smart University of Southampton
DOI
14:42
18m
Talk
Completeness of Iris-Based Program Logics
ICFP Papers
Johannes Hostert ETH Zurich, Zichen Zhang New York University, Puming Liu NYU Shanghai, Simon Oddershede Gregersen CISPA Helmholtz Center for Information Security, Ralf Jung ETH Zurich, Joseph Tassarotti New York University
DOI Pre-print