Definitional Functoriality for Dependent (Sub)Types - Ecole Centrale de Nantes Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Definitional Functoriality for Dependent (Sub)Types

Résumé

Dependently-typed proof assistant rely crucially on a definitional equality, identifying the types and terms that are automatically undistinguishable for the underlying type theory. This paper extends type theory with definitional functor laws, two equations satisfied propositionally by a large class of container-like type con- structors F: Type → Type, equipped with a mapF : (A → B) → F A → F B, such as lists or trees. Promot- ing these equations to definitional ones strengthen the theory, enabling slicker proofs and more automation for functorial type constructors. This extension is then used to justify modularly a structural form of coercive subtyping, propagating subtyping through type formers. We show that the resulting notion of coercive sub- typing, thanks to the extra definitional equations, is equivalent to a natural and implicit form of subsumptive subtyping. The key result of decidability of type-checking in a dependent type system with functor laws for lists has been entirely mechanized in Coq
Fichier principal
Vignette du fichier
main.pdf (367.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04160858 , version 1 (20-07-2023)
hal-04160858 , version 2 (23-10-2023)
hal-04160858 , version 3 (08-04-2024)

Licence

Paternité

Identifiants

  • HAL Id : hal-04160858 , version 1

Citer

Théo Laurent, Meven Lennon-Bertrand, Kenji Maillard. Definitional Functoriality for Dependent (Sub)Types. 2023. ⟨hal-04160858v1⟩
183 Consultations
163 Téléchargements

Partager

Gmail Facebook X LinkedIn More