Internal Parametricity, without an Interval
Thorsten Altenkirch, Yorgo Chamoun, Ambrus Kaposi, Michael Shulman
摘要
Parametricity is a property of the syntax of type theory implying, e.g., that there is only one function having the type of the polymorphic identity function. Parametricity is usually proven externally, and does not hold internally. Internalising it is difficult because once there is a term witnessing parametricity, it also has to be parametric itself and this results in the appearance of higher dimensional cubes. In previous theories with internal parametricity, either an explicit syntax for higher cubes is present or the theory is extended with a new sort for the interval. In this paper we present a type theory with internal parametricity which is a simple extension of Martin-Löf type theory: there are a few new type formers, term formers and equations. Geometry is not explicit in this syntax, but emergent: the new operations and equations only refer to objects up to dimension 3. We show that this theory is modelled by presheaves over the BCH cube category. Fibrancy conditions are not needed because we use span-based rather than relational parametricity. We define a gluing model for this theory implying that external parametricity and canonicity hold. The theory can be seen as a special case of a new kind of modal type theory, and it is the simplest setting in which the computational properties of higher observational type theory can be demonstrated.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper2
- AdapTT: Functoriality for Dependent Type CastsArthur Adjedj, Meven Lennon-Bertrand, Thibaut Benjamin, Kenji MaillardPOPL 2026 · 被引用 1 次
- Canonicity for Indexed Inductive-Recursive TypesAndrás KovácsPOPL 2026 · 被引用 1 次
它引用的顶会 Paper4
- Multimodal Dependent Type TheoryDaniel Gratzer, G. A. Kavvos, Andreas Nuyts, Lars BirkedalLICS 2020 · 被引用 36 次
- Normalization for Multimodal Type TheoryDaniel GratzerLICS 2022 · 被引用 23 次
- Large and Infinitary Quotient Inductive-Inductive TypesAndrás Kovács, Ambrus KaposiLICS 2020 · 被引用 7 次
- Internal and Observational Parametricity for Cubical AgdaAntoine Van Muylder, Andreas Nuyts, Dominique DevriesePOPL 2024 · 被引用 2 次
相关 Paper
- Parametricity and Semi-Cubical TypesHugo MoeneclaeyLICS 2021
- From Semantics to Syntax: A Type Theory for Comprehension CategoriesNiyousha Najmaei, Niels van der Weide, Benedikt Ahrens, Paige Randall NorthPOPL 2026
- Impredicative Observational EqualityLoïc Pujet, Nicolas TabareauPOPL 2023 · 被引用 14 次
- Eliminating Reversals from Cubical Type TheoriesEvan Cavallo, Christian SattlerLICS 2026
- Bialgebraic Reasoning on Higher-order Program EquivalenceSergey Goncharov, Stefan Milius, Stelios Tsampas, Henning UrbatLICS 2024 · 被引用 4 次
