Which simple types have a unique inhabitant?

Gabriel Scherer, Didier Rémy

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)243-255
Number of pages13
JournalACM SIGPLAN Notices
Volume50
Issue number9
DOIs
Publication statusPublished - 1 Sept 2015
Externally publishedYes

Keywords

  • Unique inhabitants
  • canonicity
  • code inference
  • focusing
  • proof search
  • saturation
  • simply-typed lambda-calculus
  • sums

Fingerprint

Dive into the research topics of 'Which simple types have a unique inhabitant?'. Together they form a unique fingerprint.

Cite this