Fri 21 Jan 2022 15:55 - 16:20 at Salon III - Type Theory Chair(s): Kuen-Bang Hou (Favonia)

Building on the recent extension of dependent type theory with a universe of definitionally proof-irrelevant types, we introduce TTobs , a new type theory based on the setoidal interpretation of dependent type theory. TTobs equips every type with an identity relation that satisfies function extensionality, propositional extensionality, and definitional uniqueness of identity proofs (UIP). Compared to other existing proposals to enrich dependent type theory with these principles, our theory features a notion of reduction that is normalizing and provides an algorithmic canonicity result, which we formally prove in Agda using the logical relation framework of Abel et al. Our paper thoroughly develops the meta-theoretical properties of TTobs , such as the decidability of the conversion and of the type checking, as well as consistency. We also explain how to extend our theory with quotient types, and we introduce a setoidal version of Swan’s Id types that turn it into a proper extension of MLTT with inductive equality.

Fri 21 Jan

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

15:05 - 16:20
Type TheoryPOPL at Salon III
Chair(s): Kuen-Bang Hou (Favonia) University of Minnesota
15:05
25m
Research paper
A Cost-Aware Logical FrameworkInPerson
POPL
Yue Niu Carnegie Mellon University, Jonathan Sterling Aarhus University, Harrison Grodin Carnegie Mellon University, Robert Harper Carnegie Mellon University
DOI Media Attached
15:30
25m
Research paper
Formal Metatheory of Second-Order Abstract SyntaxDistinguished PaperRemote
POPL
Marcelo Fiore University of Cambridge, Dmitrij Szamozvancev University of Cambridge
DOI Media Attached
15:55
25m
Research paper
Observational Equality: Now for GoodDistinguished PaperRemote
POPL
DOI Media Attached