POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Mechanizing a type theory and its meta-theory in a proof assistant establishes a high degree of trust in its correctness. However, this is also an intricate and time-consuming endeavour, since such mechanizations often exploit the specific structure of the type theory considered. This results in a patch-work of developments for a range of type theories that are similar, but still largely incompatible.

One way of uniformly describing a large family of calculi is to embrace pure type systems (PTSs) as a type-theoretic framework for characterizing type systems generically. This is achieved by abstracting over sorts and sort relations using a PTS signature. In this paper, we expand on this idea and introduce the PTS* framework for studying extensions of PTSs in a principled, generic way, by associating each extension to a new relation in the PTS* signature. We demonstrate this design by considering extensions with recursion over natural numbers and covariant sort subtyping.

We leverage PTS* to develop a unifying, generic framework, called McPTS, for formalizing meta-theoretic results of PTS* in Rocq. We prove basic properties like presupposition for all PTS* and establish stronger results by constraining the PTS* signatures with appropriate properties. First, we prove normalization for predicative PTS* signatures. Next, we design and prove correct an algorithmic type checking judgment for predicative and functional PTS* signatures. Finally, we implement the type checking algorithm for predicative, functional, and decidable PTS* signatures. By instantiating our development with the corresponding PTS* signature, we directly obtain normalization proofs for several important languages, including a version of MiniML, the logical framework LF, and several variants of Martin-Löf type theory, as well as the corresponding verified type checking implementations.