research-article

Deriving compositional random generators

Authors:

Agustín Mista,

Alejandro RussoAuthors Info & Claims

IFL '19: Proceedings of the 31st Symposium on Implementation and Application of Functional Languages

Article No.: 11, Pages 1 - 12

https://doi.org/10.1145/3412932.3412943

Published: 15 July 2021 Publication History

Abstract

Generating good random values described by algebraic data types is often quite intricate. State-of-the-art tools for synthesizing random generators serve the valuable purpose of helping with this task, while providing different levels of invariants imposed over the generated values. However, they are often not built for composability nor extensibility, a useful feature when the shape of our random data needs to be adapted while testing different properties or sub-systems.

In this work, we develop an extensible framework for deriving compositional generators, which can be easily combined in different ways in order to fit developers' demands using a simple type-level description language. Our framework relies on familiar ideas from the à la Carte technique for writing composable interpreters in Haskell. In particular, we adapt this technique with the machinery required in the scope of random generation, showing how concepts like generation frequency or terminal constructions can also be expressed in the same type-level fashion. We provide an implementation of our ideas, and evaluate its performance using real-world examples.

References

[1]

T. Arts, J. Hughes, U. Norell, and H. Svensson. 2015. Testing AUTOSAR software with QuickCheck. In In Proc. of IEEE International Conference on Software Testing, Verification and Validation, ICST Workshops.

[2]

K. Claessen and J. Hughes. 2000. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In Proc. of the ACM SIGPLAN International Conference on Functional Programming (ICFP).

[3]

Koen Claessen and John Hughes. 2002. Testing Monadic Code with QuickCheck. SIGPLAN Not. 37, 12 (2002), 47--59.

Digital Library

[4]

L. E. Day and G. Hutton. 2014. Compilation À La Carte. In Proceedings of the 25th Symposium on Implementation and Application of Functional Languages (IFL '13).

[5]

Benjamin Delaware, Bruno C d S Oliveira, and Tom Schrijvers. 2013. Meta-theory à la carte. In ACM SIGPLAN Notices, Vol. 48. ACM, 207--218.

[6]

J. Duregård, P. Jansson, and M. Wang. 2012. Feat: Functional enumeration of algebraic types. In Proc. of the ACM SIGPLAN Int. Symp. on Haskell.

[7]

Richard A Eisenberg, Stephanie Weirich, and Hamidhasan G Ahmed. 2016. Visible type application. In European Symposium on Programming. Springer, 229--254.

Digital Library

[8]

G. Grieco, M. Ceresa, and P. Buiras. 2016. QuickFuzz: An automatic random fuzzer for common file formats. In Proc. of the ACM SIGPLAN International Symposium on Haskell.

[9]

G. Grieco, M. Ceresa, A. Mista, and P. Buiras. 2017. QuickFuzz testing for fun and profit. Journal of Systems and Software 134 (2017).

[10]

J. Hughes, C. Pierce B, T. Arts, and U. Norell. 2016. Mysteries of DropBox: Property-Based Testing of a Distributed Synchronization Service. In Proc. of the Int. Conf. on Software Testing, Verification and Validation.

[11]

J. Hughes, U. Norell, N. Smallbone, and T. Arts. 2016. Find more bugs with QuickCheck!. In The IEEE/ACM International Workshop on Automation of Software Test (AST).

[12]

H. Kiriyama, H. Aotani, and H. Masuhara. 2016. A Lightweight Optimization Technique for Data Types a La Carte. In Companion Proceedings of the 15th Int. Conference on Modularity (MODULARITY 2016). ACM, New York, NY, USA.

Digital Library

[13]

Casey Klein and Robert Bruce Findler. 2009. Randomized testing in PLT Redex. In ACM SIGPLAN Workshop on Scheme and Functional Programming.

[14]

L. Lampropoulos, D. Gallois-Wong, C. Hritcu, J. Hughes, B. C. Pierce, and L. Xia. 2017. Beginner's luck: a language for property-based generators. In Proc. of the ACM SIGPLAN Symposium on Principles of Programming Languages, POPL.

[15]

C. McBride and R. Paterson. 2008. Applicative Programming with Effects. Journal of Functional Programming 18, 1 (Jan. 2008).

Digital Library

[16]

J. Midtgaard, M. N. Justesen, P. Kasting, F. Nielson, and H. R. Nielson. 2017. Effect-driven QuickChecking of compilers. In Proceedings of the ACM on Programming Languages, Volume 1 ICFP (2017).

[17]

Agustín Mista and Alejandro Russo. 2019. Generating Random Structurally Rich Algebraic Data Type Values. In Proceedings of the 14th International Workshop on Automation of Software Test.

Digital Library

[18]

Agustín Mista, Alejandro Russo, and John Hughes. 2018. Branching processes for QuickCheck generators. In Proc. of the ACM SIGPLAN Int. Symp. on Haskell.

Digital Library

[19]

Chris Okasaki. 1999. Red-black trees in a functional setting. Journal of functional programming 9, 4 (1999), 471--477.

Digital Library

[20]

Bryan O'Sullivan. 2014. Criterion: a Haskell microbenchmarking library. http://www.serpentine.com/criterion/

[21]

Anders Persson, Emil Axelsson, and Josef Svenningsson. 2011. Generic monadic constructs for embedded languages. In International Symposium on Implementation and Application of Functional Languages. Springer, 85--99.

[22]

Colin Runciman, Matthew Naylor, and Fredrik Lindblad. 2008. Smallcheck and lazy smallcheck: automatic exhaustive testing for small values. In Acm sigplan notices, Vol. 44. ACM, 37--48.

[23]

T. Schrijvers, M. Sulzmann, S. P. Jones, and M. Chakravarty. 2007. Towards open type functions for Haskell. In Proceedings of the 19th International Symposium on Implemantation and Application of Functional Languages.

[24]

Wouter Swierstra. 2008. Data Types à La Carte. J. Funct. Program. 18, 4 (July 2008), 423--436.

Digital Library

[25]

Philip Wadler. 1998. The expression problem. https://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt

[26]

P. Wadler and S. Blott. 1989. How to Make Ad-hoc Polymorphism Less Ad Hoc. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '89). 60--76.

[27]

Nicolas Wu, Tom Schrijvers, and Ralf Hinze. 2014. Effect handlers in scope. (2014).

Cited By

Shi JKeles AGoldstein HPierce BLampropoulos L(2023)Etna: An Evaluation Platform for Property-Based Testing (Experience Report)Proceedings of the ACM on Programming Languages10.1145/36078607:ICFP(878-894)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607860

Index Terms

Deriving compositional random generators
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Empirical software validation
  2. Software notations and tools
    1. Software maintenance tools

Recommendations

Splittable pseudorandom number generators using cryptographic hashing
Haskell '13: Proceedings of the 2013 ACM SIGPLAN symposium on Haskell

We propose a new splittable pseudorandom number generator (PRNG) based on a cryptographic hash function. Splittable PRNGs, in contrast to linear PRNGs, allow the creation of two (seemingly) independent generators from a given random number generator. ...
Splittable pseudorandom number generators using cryptographic hashing
Haskell '13

We propose a new splittable pseudorandom number generator (PRNG) based on a cryptographic hash function. Splittable PRNGs, in contrast to linear PRNGs, allow the creation of two (seemingly) independent generators from a given random number generator. ...
Bit-Wise Behavior of Random Number Generators

In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

IFL '19: Proceedings of the 31st Symposium on Implementation and Application of Functional Languages

September 2019

177 pages

ISBN:9781450375627

DOI:10.1145/3412932

Editors:
Jurriën Stutterheim
Standard Chartered Bank, Singapore
,
Wei Ngan Chin
National University of Singapore

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Swedish Foundation for Strategic Research
Swedish research agency Vetenskapsrådet
e Swedish Foundation for Strategic Research

Conference

IFL '19

IFL '19: Implementation and Application of Functional Languages

September 25 - 27, 2019

Singapore, Singapore

Acceptance Rates

Overall Acceptance Rate 19 of 36 submissions, 53%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
30
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shi JKeles AGoldstein HPierce BLampropoulos L(2023)Etna: An Evaluation Platform for Property-Based Testing (Experience Report)Proceedings of the ACM on Programming Languages10.1145/36078607:ICFP(878-894)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607860

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents