TY - JOUR
T1 - Fair enumeration combinators
AU - NEW, MAX S.
AU - FETSCHER, BURKE
AU - Findler, Robert
AU - MCCARTHY, JAY
N1 - Publisher Copyright:
Copyright © Cambridge University Press 2017.
PY - 2017/8/30
Y1 - 2017/8/30
N2 - 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 elements into each of its components instead of, say, indexing into one and 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 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.
AB - 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 elements into each of its components instead of, say, indexing into one and 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 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.
UR - http://www.scopus.com/inward/record.url?scp=85030863146&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85030863146&partnerID=8YFLogxK
U2 - 10.1017/S0956796817000107
DO - 10.1017/S0956796817000107
M3 - Article
AN - SCOPUS:85030863146
SN - 0956-7968
VL - 27
JO - Journal of Functional Programming
JF - Journal of Functional Programming
M1 - e19
ER -