Generating Constrained Test Data using Datatype Generic Programming

Cas van der Rest

The generation of suitable test data is an essential part of property based testing. Obtaining test data is simple enough when there are no additional constraints, however things become more complicated once we require data with a richer structure, for example well-formed programs when testing a compiler. We observe that we can often describe constrained data as an indexed datatype. By generating values of the indexed datatype that describes a set of constrained test data, we simultaneously obtain a way to generate the constrained data itself. To achieve this goal, we consider three increasingly expressive type universes: regular types, indexed containers and indexed descriptions. We show how generators can be derived from codes in these universes, and for regular types and indexed descriptions we show that these derived generators obey a completeness property. We implement the generic generator for indexed descriptions in Haskell, and use this implementation to generate constrained test data, such as well-typed lambda terms.

---

Previous: Peter Mosses | A component-based formal language workbench
Next: Mitra Nasri | Towards an Efficient and Accurate Timing Analysis for Real-Time Cyber-Physical Systems