Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a "fuss-free" generalized algebraic presentation for polymorphic cumulative universes in dependent type theory, simplifying the complex landscape of coherent universe coercions. The authors prove the equivalence of their formulation through a normalization theorem and provide evidence of its utility via a bidirectional elaboration algorithm and a concrete implementation in Haskell. Additionally, they extend this framework to include a judgemental notion of datatype description, enabling the derivation of previous concepts of cumulative inductive types.
Simplifying the handling of polymorphic cumulative universes could revolutionize how dependent type theory is applied in practical programming languages.
Universes are central to dependent type theory, and they are notoriously difficult to handle in a way that is both correct and usable. We propose a new"fuss-free"generalised algebraic presentation for polymorphic cumulative universes that dispenses with the intricate theory of coherent universe coercions in favour of a simpler formulation, which we prove equivalent by means of a normalisation theorem for the former. Evidence for the utility of the fuss-free formulation is provided in the form of (1) an abstract specification of its bidirectional elaboration algorithm, and (2) a concrete implementation in Haskell. We also describe and implement an extension of the fuss-free universe hierarchy with a judgemental notion of datatype description from which prior notions of cumulative inductive type may be derived.