ICFP 2025
Sun 12 - Sat 18 October 2025 Singapore
co-located with ICFP/SPLASH 2025
Tue 14 Oct 2025 14:30 - 14:55 at Orchid Plenary Ballroom - Denotational Semantics Chair(s): Alex Kavvos

The metatheory of dependent types has seen a lot of progress in recent years. In particular, the development of categorical gluing finally lets us work with semantic presentations of type theory (such as categories with families) to establish fundamental properties of type theory such as canonicity and normalisation.

However, proofs by gluing have yet to reach the stage of computer formalisation: formal proofs for the metatheory of dependent types are still stuck in the age of tedious syntactic proofs. The main reason for this is that semantic presentations of type theory are defined using sophisticated indexed inductive types, which are especially prone to "transport hell".

In this paper, we introduce a new technique to work with CwFs in intensional type theory without getting stuck in transport hell. More specifically, we construct an alternative presentation of the initial CwF which encodes the substitutions as metatheoretical functions. This has the effect of strictifying all the equations that are involved in the substitution calculus, which greatly reduces the need for transports.

As an application, we use our strictified initial CwF to give a short and elegant proof of canonicity for a type theory with dependent products and booleans with large elimination. The resulting proof is fully formalised in Agda.

Tue 14 Oct

Displayed time zone: Perth change

13:40 - 15:20
Denotational SemanticsICFP Papers at Orchid Plenary Ballroom
Chair(s): Alex Kavvos University of Bristol
13:40
25m
Talk
Fulls Seldom Differ
ICFP Papers
Mark Koch Quantinuum, Alan Lawrence Quantinuum, Conor McBride University of Strathclyde, Craig Roy Quantinuum
DOI
14:05
25m
Talk
Normalization by Evaluation for Non-cumulativity
ICFP Papers
Shengyi Jiang The University of Hong Kong, Jason Z. S. Hu Amazon, Bruno C. d. S. Oliveira University of Hong Kong
DOI
14:30
25m
Talk
Type Theory in Type Theory using a Strictified Syntax
ICFP Papers
Ambrus Kaposi ELTE Eötvös Loránd University, Budapest, Hungary, Loïc Pujet Stockholm University
DOI Pre-print
14:55
25m
Talk
Type Universes as Kripke Worlds
ICFP Papers
Paulette Koronkevich University of British Columbia, William J. Bowman University of British Columbia
DOI Pre-print