Type Theory in Type Theory using a Strictified Syntax
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 OctDisplayed time zone: Perth change
13:40 - 15:20 | Denotational SemanticsICFP Papers at Orchid Plenary Ballroom Chair(s): Alex Kavvos University of Bristol | ||
13:40 25mTalk | Fulls Seldom Differ ICFP Papers Mark Koch Quantinuum, Alan Lawrence Quantinuum, Conor McBride University of Strathclyde, Craig Roy Quantinuum DOI | ||
14:05 25mTalk | 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 25mTalk | Type Theory in Type Theory using a Strictified Syntax ICFP Papers DOI Pre-print | ||
14:55 25mTalk | Type Universes as Kripke Worlds ICFP Papers Paulette Koronkevich University of British Columbia, William J. Bowman University of British Columbia DOI Pre-print | ||