Which simple types have a unique inhabitant? - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Which simple types have a unique inhabitant?

Résumé

We study the question of whether a given type has a unique inhabitant modulo program equivalence. In the setting of simply-typed lambda-calculus with sums, equipped with the strong βη-equivalence, we show that uniqueness is decidable. We present a saturating focused logic that introduces irreducible cuts on positive types "as soon as possible". Backward search in this logic gives an effective algorithm that returns either zero, one or two distinct inhabitants for any given type. Preliminary application studies show that such a feature can be useful in strongly-typed programs, inferring the code of highly-polymorphic library functions, or "glue code" inside more complex terms.
Fichier principal
Vignette du fichier
unique_stlc_sums.pdf (404.52 Ko) Télécharger le fichier
unique-stlc-sums-implem.zip (25.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Autre
Origine : Fichiers produits par l'(les) auteur(s)
Commentaire : Implémentation
Loading...

Dates et versions

hal-01235596 , version 1 (30-11-2015)

Identifiants

  • HAL Id : hal-01235596 , version 1

Citer

Gabriel Scherer, Didier Rémy. Which simple types have a unique inhabitant?. The 20th ACM SIGPLAN International Conference on Functional Programming (ICFP 2015), Aug 2015, Vancouver, Canada. ⟨hal-01235596⟩

Collections

INRIA INRIA2
84 Consultations
148 Téléchargements

Partager

Gmail Facebook X LinkedIn More