Lune

POPL2024Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Internalizing representation independence with univalence cites A Higher Structure Identity Principle
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Internal Parametricity, without an IntervalThorsten Altenkirch, Yorgo Chamoun, Ambrus Kaposi, Michael ShulmanPOPL 2024 · 4 citations

Builds on4

  1. Observational equality: now for goodLoïc Pujet, Nicolas TabareauPOPL 2022 · 26 citations
  2. Internalizing representation independence with univalenceCarlo Angiuli, Evan Cavallo, Anders Mörtberg, Max ZeunerPOPL 2021 · 18 citations
  3. A Higher Structure Identity PrincipleBenedikt Ahrens, Paige Randall North, Michael Shulman, Dimitris TsementzisLICS 2020 · 6 citations
  4. Internal Parametricity, without an IntervalThorsten Altenkirch, Yorgo Chamoun, Ambrus Kaposi, Michael ShulmanPOPL 2024 · 4 citations

Related papers

  1. BiSikkel: A Multimode Logical Framework in AgdaJoris Ceulemans, Andreas Nuyts, Dominique DevriesePOPL 2025
  2. Impredicative Observational EqualityLoïc Pujet, Nicolas TabareauPOPL 2023 · 14 citations
  3. 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
  4. Normalisation for First-Class Universe LevelsNils Anders Danielsson, Naïm Camille Favier, Ondrej KubánekPOPL 2026 · 1 citation
  5. Definitional Proof Irrelevance Made AccessibleThiago Felicissimo, Yann Leray, Loïc Pujet, Nicolas Tabareau et al.LICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines