Internal and Observational Parametricity for Cubical Agda
Antoine Van Muylder, Andreas Nuyts, Dominique Devriese
Abstract
Two approaches exist to incorporate parametricity into proof assistants based on dependent type theory. On the one hand, parametricity translations conveniently compute parametricity statements and their proofs solely based on individual well-typed polymorphic programs. But they do not offer internal parametricity: formal proofs that any polymorphic program of a certain type satisfies its parametricity statement. On the other hand, internally parametric type theories augment plain type theory with additional primitives out of which internal parametricity can be derived. But those type theories lack mature proof assistant implementations and deriving parametricity in them involves low-level intractable proofs. In this paper, we contribute Agda --bridges: the first practical internally parametric proof assistant. We provide the first mechanized proofs of crucial theorems for internal parametricity, like the relativity theorem. We identify a high-level sufficient condition for proving internal parametricity which we call the structure relatedness principle (SRP) by analogy with the structure identity principle (SIP) of HoTT/UF. We state and prove a general parametricity theorem for types that satisfy the SRP. Our parametricity theorem lets us obtain one-liner proofs of standard internal free theorems. We observe that the SRP is harder to prove than the SIP and provide in Agda --bridges a shallowly embedded type theory to compose types that satisfy the SRP. This type theory is an observational type theory of logical relations and our parametricity theorem ought to be one of its inference rules.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on4
- Observational equality: now for goodLoïc Pujet, Nicolas TabareauPOPL 2022 · 26 citations
- Internalizing representation independence with univalenceCarlo Angiuli, Evan Cavallo, Anders Mörtberg, Max ZeunerPOPL 2021 · 18 citations
- A Higher Structure Identity PrincipleBenedikt Ahrens, Paige Randall North, Michael Shulman, Dimitris TsementzisLICS 2020 · 6 citations
- Internal Parametricity, without an IntervalThorsten Altenkirch, Yorgo Chamoun, Ambrus Kaposi, Michael ShulmanPOPL 2024 · 4 citations
Related papers
- BiSikkel: A Multimode Logical Framework in AgdaJoris Ceulemans, Andreas Nuyts, Dominique DevriesePOPL 2025
- Impredicative Observational EqualityLoïc Pujet, Nicolas TabareauPOPL 2023 · 14 citations
- All Your Base Are Belong to Us: Sort Polymorphism for Proof AssistantsJosselin Poiret, Gaëtan Gilbert, Kenji Maillard, Pierre-Marie Pédrot et al.POPL 2025 · 6 citations
- Normalisation for First-Class Universe LevelsNils Anders Danielsson, Naïm Camille Favier, Ondrej KubánekPOPL 2026 · 1 citation
- Definitional Proof Irrelevance Made AccessibleThiago Felicissimo, Yann Leray, Loïc Pujet, Nicolas Tabareau et al.LICS 2026
