CS Paper Radar

Type classifiers

Martin E. Bidlingmaier

cs.LO math.CT ·submitted 2026-10-30 16:00 UTC · v1

Abstract

We extend dependent type theory by type classifiers and construct an interpretation in the category of contextual categories with families. Type classifiers extend contexts by type variables, complementing the usual context extensions by term variables of specified types. This allows statements with arbitrary type parameters to be formulated without assuming a universe. We show that substituting isomorphic types induces isomorphisms between the resulting types even in extensional type theory, giving an analogue of the invariance supplied by the univalence axiom in homotopy type theory. Omitting function types from the theory, so that all type formers are covariant, extends this naturality to arbitrary, possibly noninvertible maps.

Comment
7 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A General Construction of Strict Models in HoTT

cs.LO cs.PLmath.CT ·2026-10-20 ·Niyousha Najmaei, Niels van der Weide
similarity 0.62
Abstract

Homotopy type theory (HoTT) provides a natural setting for studying the metatheory of type theory, as it comes with additional extensionality principles compared to ordinary Martin-Löf type theory. In particular, it is especially suitable for developing semantics of type theory, where one distinguishes two kinds of models: strict models, which give us sound interpretations, and pseudomodels. Pseudomodels are useful as they occur prevalently and can be turned into strict models by constructions called strictifications. However, the commonly used strictifications do not translate well to HoTT, as they require assumptions that are generally not satisfied by concrete examples of models. We show how to carry out the universe model construction, due to Voevodsky, in HoTT. Under this construction, every pseudomodel together with a universe type closed under enough type formers gives rise to a strict model. We also show how to interpret type formers in the resulting model assuming that the universe is closed under them. Finally, we demonstrate that this construction generalises existing instances of strict set models in the literature, and we apply it to more examples, yielding presheaf models and assembly models of type theory in HoTT. Our results are formalised in Rocq using the UniMath library.

0.27

On Left Adjoints Preserving Colimits in Homotopy Type Theory

cs.LO math.CT ·2026-08-28 ·Perry Hart
code/data similarity 0.60
Abstract · Agda code: https://github.com/PHart3/colimits-agda/tree/lapc-lmcs

We examine how the standard proof that left adjoints preserve colimits behaves in the setting of wild categories, a natural setting for synthetic homotopy theory inside homotopy type theory. We show that the proof may fail for adjunctions between wild categories and even produce a wild left adjoint that fails to preserve colimits. Our core contribution, however, is a sufficient condition on the left adjoint for the proof to go through. The condition, which we call 2-coherence, expresses that the naturality structure of the hom-isomorphism commutes with composition of morphisms. We present two useful examples of this condition in action. First, we use it, along with a new version of a known trick for homogeneous types, to show that the suspension functor, as well as a generalization thereof, preserves graph-indexed colimits. Second, we show that every modality, viewed as a functor on coslices of a type universe, is 2-coherent as a left adjoint to the forgetful functor from the subcategory of modal types, thereby proving this subcategory is cocomplete. We have formalized our main results in Agda.

0.38

Hippogriff: a semantic approach to uniting core and modules

cs.PL cs.LO ·2026-08-20 ·Owen Lynch, Sam Staton
similarity 0.59
Abstract · 36 pages, including supplemental appendix

In this paper we introduce Hippogriff, a language with a module system that unifies syntax between the core level and the module level. Hippogriff's type theory is dependent, with modularity features enabled via a universe of small types, but Hippogriff still supports general recursion without making typechecking nonterminating. This paper contains two halves. In the first half, we describe Hippogriff and its implementation. In the second half, we build categorical semantics for our use of dependent types that justify the use of general recursion at the value level. Specifically, we use an extension of the second-order generalized algebraic theory framework to include a synthetic phase distinction, and this allows us to make a mathematical connection between dependent type theories and split-context type theories (like System F). Included as supplements are a Haskell implementation of Hippogriff and an appendix describing the full type theory of Hippogriff using a second-order generalized algebraic theory with phase distinction.

0.20

Univalent Non-Associative Categorical Structures

cs.LO cs.PLmath.CT ·2026-10-15 ·Beatrice Szilvasy
similarity 0.58
Abstract

We study category-like structures in which composition is not associative, especially Munch-Maccagnoni's duploids, in univalent foundations. Included is a definition of what a univalent duploid is: one where isomorphisms of a suitable kind render the objects indistinguishable to the type theory. We show that the existing construction of a duploid from an adjunction is not univalent as a "single-sorted" duploid, and provide a novel construction which is. This work is formalized in the UniMath library for the Rocq proof assistant.

0.27

Unit: a type checker for dependent type theory

cs.LO ·2026-10-25 ·Thierry Coquand
theory similarity 0.58
Abstract

We present Unit, a type checker for dependent type theory with a module system in the tradition of Automath and a uniform treatment of definitions. There is no unification, no instance search, no tactics and no unfolding heuristic, so the work of checking can be observed and compared with the informal proof. With Unit we have checked a model of univalent type theory, synthetic algebraic geometry, and synthetic Stone duality with its cohomology, and results in commutative algebra, like finite free resolutions and Zariski Main Theorem. These developments show that a small, uniform system supports substantial mathematics, and give concrete reasons to reconsider the complexity routinely accepted in proof assistants.

0.32

Compiling Environment Classifiers to Contextual Modal Types

cs.PL ·2026-10-19 ·Tianyu Chen, Darshal Shetty, Jeremy G. Siek, Chao-Hong Chen, Weixi Ma +2 more
theory similarity 0.58
Abstract · 45 pages, 26 figures

Type systems for metaprogramming take one of two approaches to safeguarding the scopes of variables in generated code. They either use Environment Classifiers (EC) to identify scopes by name (Taha and Nielsen, 2003), or they use Contextual Modal Type Theory (CMTT) to match scopes by structure (Nanevski, Pfenning, and Pientka, 2008). In this paper, we connect these two approaches by compiling a calculus with polymorphic environment classifiers, subtyping, and mutable references to a CMTT-based calculus with polymorphic contexts, mutable references, and first-class substitutions. The key idea is to map each environment classifier to a context. We prove that the compilation preserves types and that compilation preserves the behavior of metaprograms. Both proofs are mechanized in Agda. The compilation shows that CMTT is at least as expressive as environment classifiers. We conjecture that the converse compilation is difficult, because environment classifiers impose a stricter regime on the metaprogram.

0.25

Typed Knowledge over Constructive Institutions

cs.LO cs.AIcs.DB ·2026-11-05 ·Hans-Martin Will
publishedtheory similarity 0.56
Abstract

Type theories designed for mathematics or program verification need only that a proposition holds; proof irrelevance in conversion erases, at the kernel level, how a claim was established. A persistent knowledge store, by contrast, must retain that record: who established a claim, by which derivation or external tool, and under which assumptions. This volume presents the theory of Eigenius---a store of typed knowledge over constructive institutions---and develops its metatheory from that requirement. The kernel theory is a dependent type theory with cumulative universes, an impredicative universe of propositions, inductive families, and an intensional identity type. Proof irrelevance is an axiom with an explicit witness rather than a conversion rule, so proofs of a proposition are provably equal yet remain distinct terms. Definitional equality is joinability under an orthogonal rewriting system---confluent, injective on type formers, and decidable by a type-free test---while a separate subsumption judgment covers universe cumulativity, codomain-covariant function types, and declared class inclusions. We prove consistency via a set-theoretic model; develop a justification logic over the kernel's propositions to track evidence and support; organize environments as an institution so that store extensions are signature morphisms and external verdicts enter via comorphisms; formulate a typed knowledge-graph theory with records, classes, and refinements; and prove the correctness of conversion, normalization by evaluation, and bidirectional type checking relative to termination. A Lean 4 formalization accompanies the volume.

0.45

A Theory of a Two-Dimensional Typed Lambda Calculus

cs.LO ·2026-09-16 ·Daniel O. Martínez-Rivillas, Arthur F. Ramos, Ruy J. G. B. de Queiroz
similarity 0.55
Abstract

We present a typed two-dimensional $λ$-calculus whose equality evidence is \emph{computational}: a path between two terms is an explicit finite sequence of one-step conversions (the $β$- and $η$-contractions, the congruences, and the structural rules), and every property of paths is proved \emph{by recursion over that sequence}, with any step as a base case --- in deliberate contrast with Martin-Löf type theory, where identity is generated by reflexivity alone and all properties go through the non-computational $J$-eliminator. The higher structure is imported from the $2β$- and $2η$-conversions of the theory of an arbitrary higher $λ$-model: we obtain 2-dimensional coherence laws, computable naturality of homotopies (via inductive homotopies and their explicit evaluations), a 2-dimensional path type with transport, and a parity invariant that proves the system consistent and \emph{really intensional}: the $β$- and $η$-contractions are provably distinct evidence, while in the native syntax of Idris (core MLTT) they are identified by definitional equality. Commutative diagrams accompany the main constructions, and the theory is fully formalized in Idris 2. A parallel Lean formalization is published in the Palomar registry \cite{palomar2026lean}. A philosophical reading closes the paper: constructivism in the BHK sense, proof-relevant intensionality, and the boundary between syntax and semantics, drawn relative to MLTT and HoTT.}

0.34