Fair enumeration combinators

MAX S. NEW*, BURKE FETSCHER, Robert Findler, JAY MCCARTHY

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Enumerations represented as bijections between the natural numbers and elements of some given type have recently garnered interest in property-based testing because of their efficiency and flexibility. There are, however, many ways of defining these bijections, some of which are better than others. This paper offers a new property of enumeration combinators called fairness that identifies enumeration combinators that are better suited to property-based testing. Intuitively, the result of a fair combinator indexes into its argument enumerations equally when constructing its result. For example, extracting the nth element from our enumeration of three-tuples indexes about (Formula presented.) elements into each of its components instead of, say, indexing (Formula presented.) into one and (Formula presented.) into the other two, as you would if a three-tuple were built out of nested pairs. Similarly, extracting the nth element from our enumeration of a three-way union returns an element that is (Formula presented.) into one of the argument enumerators. The paper presents a semantics of enumeration combinators, a theory of fairness, proofs establishing fairness of our new combinators and that some combinations of fair combinators are not fair. We also report on an evaluation of fairness for the purpose of finding bugs in programming-language models. We show that fair enumeration combinators have complementary strengths to an existing, well-tuned ad hoc random generator (better on short time scales and worse on long time scales) and that using unfair combinators is worse across the board.

Original languageEnglish (US)
JournalJournal of Functional Programming
DOIs
StateAccepted/In press - Aug 30 2017

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Fair enumeration combinators'. Together they form a unique fingerprint.

Cite this