Thu 19 Jan 2023 15:35 - 16:00 at Avenue34 - Type Theory Chair(s): Brigitte Pientka

We present a novel formulation of universe polymorphism in dependent type theory in terms of monads on the category of strict partial orders, and a novel algebraic structure, <em>displacement algebras,</em> on top of which one can implement a generalized form of McBride’s “crude but effective stratification” scheme for lightweight universe polymorphism. We give some examples of exotic but consistent universe hierarchies, and prove that every universe hierarchy in our sense can be embedded in a displacement algebra and hence implemented via our generalization of McBride’s scheme. Many of our technical results are mechanized in Agda, and we have an OCaml library for universe levels based on displacement algebras, for use in proof assistant implementations.

Thu 19 Jan

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

15:10 - 16:25
Type TheoryPOPL at Avenue34
Chair(s): Brigitte Pientka McGill University
15:10
25m
Talk
Admissible Types-to-PERs Relativization in Higher-Order LogicDistinguished Paper
POPL
Andrei Popescu University of Sheffield, Dmitriy Traytel University of Copenhagen
DOI
15:35
25m
Talk
An Order-Theoretic Analysis of Universe Polymorphism
POPL
Kuen-Bang Hou (Favonia) University of Minnesota, Carlo Angiuli Carnegie Mellon University, Reed Mullanix University of Minnesota
DOI
16:00
25m
Talk
Impredicative Observational Equality
POPL
DOI