Elaborating inductive definitions

Pierre-Evariste Dagand 1 Conor Mcbride 1
1 Mathematically Structured Programming Group
Mathematically Structured Programming Group
Abstract : We present an elaboration of inductive de nitions down to a universe of datatypes. The universe of datatypes is an internal presentation of strictly positive types within type theory. By elaborating an inductive de nition { a syntactic artefact { to its code { its semantics { we obtain an internalised account of inductives inside the type theory itself: we claim that reasoning about inductive de nitions could be carried in the type theory, not in the meta-theory as it is usually the case. Besides, we give a formal speci cation of that elaboration process. It is therefore amenable to formal reasoning too. We prove the soundness of our translation and hint at its completeness with respect to Coq's Inductive de nitions. The practical bene ts of this approach are numerous. For the type theorist, this is a small step toward bootstrapping, i.e. implementing the inductive fragment in the type theory itself. For the programmer, this means better support for generic programming: we shall present a lightweight deriving mechanism, entirely de nable by the programmer and therefore not requiring any extension to the type theory.
Type de document :
Communication dans un congrès
Damien Pous and Christine Tasson. JFLA - Journées francophones des langages applicatifs, Feb 2013, Aussois, France. 2013
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00778975
Contributeur : Ist Inria Saclay <>
Soumis le : lundi 21 janvier 2013 - 15:48:36
Dernière modification le : lundi 13 octobre 2014 - 15:43:25
Document(s) archivé(s) le : samedi 1 avril 2017 - 07:52:16

Fichier

jfla2013-03.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00778975, version 1

Collections

Citation

Pierre-Evariste Dagand, Conor Mcbride. Elaborating inductive definitions. Damien Pous and Christine Tasson. JFLA - Journées francophones des langages applicatifs, Feb 2013, Aussois, France. 2013. 〈hal-00778975〉

Partager

Métriques

Consultations de la notice

95

Téléchargements de fichiers

69