Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-19T00:44:24.015Z Has data issue: false hasContentIssue false
  • English
  • Français

Generating constrained random data with uniform distribution

Part of: JFP Research Articles

Published online by Cambridge University Press:  13 July 2015

KOEN CLAESSEN ,
JONAS DUREGÅRD  and
MICHAŁ H. PAŁKA
KOEN CLAESSEN
Affiliation:
Department of Computer Science and Engineering, Chalmers University of Technology, Gothenburg, Sweden (e-mail: koen@chalmers.se, jonas.duregard@chalmers.se, michal.palka@chalmers.se)
JONAS DUREGÅRD
Affiliation:
Department of Computer Science and Engineering, Chalmers University of Technology, Gothenburg, Sweden (e-mail: koen@chalmers.se, jonas.duregard@chalmers.se, michal.palka@chalmers.se)
MICHAŁ H. PAŁKA
Affiliation:
Department of Computer Science and Engineering, Chalmers University of Technology, Gothenburg, Sweden (e-mail: koen@chalmers.se, jonas.duregard@chalmers.se, michal.palka@chalmers.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present a technique for automatically deriving test data generators from a given executable predicate representing the set of values we are interested in generating. The distribution of these generators is uniform over values of a given size. To make the generation efficient, we rely on laziness of the predicate, allowing us to prune the space of values quickly. In contrast, implementing test data generators by hand is labour intensive and error prone. Moreover, handwritten generators often have an unpredictable distribution of values, risking that some values are arbitrarily underrepresented. We also present a variation of the technique that has better performance, but where the distribution is skewed in a limited, albeit predictable way. Experimental evaluation of the techniques shows that the automatically derived generators are much easier to define than handwritten ones, and their performance, while lower, is adequate for some realistic applications.

Type
Articles
Information
Journal of Functional Programming , Volume 25 , 2015 , e8
Copyright
Copyright © Cambridge University Press 2015 

References

Arts, T., Hughes, J., Johansson, J. & Wiger, Ulf. (2006) Testing telecoms software with Quviq QuickCheck. In Proceedings of the Workshop on Erlang (Erlang 2006). New York, NY, USA: ACM, pp. 2–10.CrossRefGoogle Scholar
Boyapati, C., Khurshid, S. & Marinov, D. (2002) Korat: Automated testing based on Java predicates. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 2002). New York, NY, USA: ACM, pp. 123–133.CrossRefGoogle Scholar
Christiansen, J. & Fischer, S. (2008) EasyCheck: Test data for free. In Proceedings of the International Conference on Functional and Logic Programming (FLOPS 2008). LNCS, vol. 4989. Berlin, Heidelberg: Springer, pp. 22–336.CrossRefGoogle Scholar
Claessen, K., Duregård, J. & Pałka, M. H. (2014) Generating constrained random data with uniform distribution. In Proceedings of the International Conference on Functional and Logic Programming (FLOPS 2014), Codish, M. & Sumii, E. (eds), LNCS, vol. 8475, Springer International Publishing, pp. 18–34.CrossRefGoogle Scholar
Claessen, K. & Hughes, J. (2000) QuickCheck: A lightweight tool for random testing of Haskell programs. In Proceedings of the International Conference on Functional Programming (ICFP 2000). New York, NY, USA: ACM, pp. 268–279.CrossRefGoogle Scholar
Duregård, J., Jansson, P. & Wang, M. (2012) Feat: Functional enumeration of algebraic types. In Proceedings of the Haskell Symposium (Haskell 2012). ACM, pp. 61–72.CrossRefGoogle Scholar
Feldt, R. & Poulding, S. (2013) Finding test data with specific properties via metaheuristic search. In Proceedings of the International Symposium on Software Reliability Engineering (ISSRE 2013). IEEE, pp. 350–359.CrossRefGoogle Scholar
Fischer, S., Kiselyov, O. & Shan, C.-C. (2011) Purely functional lazy nondeterministic programming. J. Funct. Program. 21 (4–5), 413–465.CrossRefGoogle Scholar
Flajolet, P., Éric, F. & Pivoteau, C. (2007) Boltzmann sampling of unlabelled structures. In Proceedings of the Workshop on Analytic Algorithmic and Combinatorics. SIAM Press, pp. 201–211.CrossRefGoogle Scholar
Flajolet, P., Zimmermann, P. & Cutsem, B. V. (1994) A calculus for the random generation of labelled combinatorial structures. Theor. Comput. Sci. 132 (1–2), 1–35.CrossRefGoogle Scholar
Grygiel, K. & Lescanne, P. (2013) Counting and generating lambda terms. J. Funct. Program. 23 (9), 594–628.CrossRefGoogle Scholar
Knuth, D. E. (2006) The Art of Computer Programming, volume 4, fascicle 4: Generating All Trees–History of Combinatorial Generation (Art of Computer Programming). Addison-Wesley Professional.Google Scholar
Lindblad, F. (2008) Property directed generation of first-order test data. In Trends in Functional Programming (TFP 2007). Intellect, pp. 105–123.Google Scholar
Pałka, M. H. (2012) Testing an Optimising Compiler by Generating Random Lambda Terms. Licentiate thesis, Chalmers University of Technology, Gothenburg, Sweden.CrossRefGoogle Scholar
Pałka, M. H., Claessen, K., Russo, A. & Hughes, J. (2011) Testing an optimising compiler by generating random lambda terms. Proceedings of the International Workshop on Automation of Software Test (AST 2011). ACM, pp. 91–97.CrossRefGoogle Scholar
Reich, J. S, Naylor, M. & Runciman, C. (2012) Lazy generation of canonical test programs. In Implementation and Application of Functional Languages (IFL 2012). LNCS, vol. 7257, Springer, pp. 69–84.CrossRefGoogle Scholar
Runciman, C., Naylor, M. & Lindblad, F. (2008) Smallcheck and Lazy Smallcheck: Automatic exhaustive testing for small values. In Proceedings of the Haskell Symposium (Haskell 2008). New York, NY, USA: ACM, pp. 37–48.CrossRefGoogle Scholar
Yakushev, A. R. & Jeuring, J. (2009) Enumerating well-typed terms generically. In Proceedings of International Workshop of Approaches and Applications of Inductive Programming (AAIP 2009). LNCS, vol. 5812. Springer, pp. 93–116.Google Scholar
Yorgey, B. A. (2010) Species and functors and types, oh my! In Proceedings of the Haskell Symposium (Haskell 2010). New York, NY, USA: ACM, pp. 147–158.Google Scholar
Yorgey, B. A. (2014) Combinatorial Species and Labelled Structures. Ph.D. thesis, University of Pennsylvania.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.