Deciding unique inhabitants with sums (work in progress)

Abstract : Our ongoing work focuses on types that have a unique inhabitant—modulo program equivalence. If we were able to detect when such types appear in a program, we could perform program inference to releave the programmer from the obligation to write the less-interesting parts of the program. Unicity of inhabitant is a strong form of principality: inference cannot make a "wrong" guess as there is only one choice. To decide uniqueness, we must be able to enumerate the distinct terms at a given type. As a first step, we consider the simply-typed lambda-calculus with arrows, product and sums. We are looking for a term enumeration process that is complete, i.e., it does not miss any computational behavior, and canonical, i.e., it has no duplicates. We propose an approach based on saturation, with encouraging results, although termination is still a conjecture.
Type de document :
Communication dans un congrès
TYPES, May 2014, Paris, France. 2014, 〈http://www.pps.univ-paris-diderot.fr/types2014/〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01094127
Contributeur : Scherer Gabriel <>
Soumis le : jeudi 18 décembre 2014 - 09:08:10
Dernière modification le : mercredi 14 décembre 2016 - 01:07:26
Document(s) archivé(s) le : samedi 15 avril 2017 - 07:56:14

Fichiers

scherer-types14-extended-abstr...
Fichiers produits par l'(les) auteur(s)

Résumé du travail soumis à la relecture

Identifiants

  • HAL Id : hal-01094127, version 1

Collections

Citation

Gabriel Scherer, Didier Rémy. Deciding unique inhabitants with sums (work in progress). TYPES, May 2014, Paris, France. 2014, 〈http://www.pps.univ-paris-diderot.fr/types2014/〉. 〈hal-01094127〉

Partager

Métriques

Consultations de
la notice

88

Téléchargements du document

77