Extensionality of Ghost Dependent Types for Free - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Preprints, Working Papers, ... Year : 2023

Extensionality of Ghost Dependent Types for Free

Abstract

We introduce ghost type theory (GTT) a dependent type theory extended with a new universe for ghost data that can safely be erased when running a program but which is not proof irrelevant like with a universe of (strict) propositions. Instead, ghost data carry information that can be used in proofs or to discard impossible cases in relevant computations. Casts can be used to replace ghost values by others that are propositionally equal, but crucially these casts can safely be ignored for conversion. We give a syntactical model of GTT using a program translation akin to the parametricity translation and thus show consistency of the theory. We further extend GTT to support equality reflection and show that we can eliminate its use without the need for the usual extra axioms of function extensionality and uniqueness of identity proofs. In particular we validate the intuition that indices of inductive types such as the length index of vectors do not matter for computation and can safely be considered modulo theory.
Fichier principal
Vignette du fichier
ghost-tt-popl24.pdf (601.21 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Licence : CC BY - Attribution

Dates and versions

hal-04163836 , version 1 (17-07-2023)
hal-04163836 , version 2 (29-02-2024)

Licence

Attribution

Identifiers

  • HAL Id : hal-04163836 , version 1

Cite

Théo Winterhalter. Extensionality of Ghost Dependent Types for Free. 2023. ⟨hal-04163836v1⟩
120 View
150 Download

Share

Gmail Facebook X LinkedIn More