{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:13:35Z","timestamp":1775873615485,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1521523"],"award-info":[{"award-number":["1521523"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>Random data generators can be thought of as parsers of streams of randomness. This perspective on generators for random data structures is established folklore in the programming languages community, but it has never been formalized, nor have its consequences been deeply explored.<\/jats:p>\n          <jats:p>We build on the idea of freer monads to develop free generators, which unify parsing and generation using a common structure that makes the relationship between the two concepts precise. Free generators lead naturally to a proof that a monadic generator can be factored into a parser plus a distribution over choice sequences. Free generators also support a notion of derivative, analogous to the familiar Brzozowski derivatives of formal languages, allowing analysis tools to \"preview\" the effect of a particular generator choice. This gives rise to a novel algorithm for generating data structures satisfying user-specified preconditions.<\/jats:p>","DOI":"10.1145\/3563291","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T20:23:35Z","timestamp":1667247815000},"page":"89-113","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Parsing randomness"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9631-1169","authenticated-orcid":false,"given":"Harrison","family":"Goldstein","sequence":"first","affiliation":[{"name":"University of Pennsylvania, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7839-1636","authenticated-orcid":false,"given":"Benjamin C.","family":"Pierce","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796815000143"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351266"},{"key":"e_1_2_2_4_1","volume-title":"Automated Black Box Generation of Structured Inputs for Use in Software Testing","author":"Dewey Kyle Thomas","unstructured":"Kyle Thomas Dewey . 2017. Automated Black Box Generation of Structured Inputs for Use in Software Testing . University of California , Santa Barbara . Kyle Thomas Dewey. 2017. Automated Black Box Generation of Structured Inputs for Use in Software Testing. University of California, Santa Barbara."},{"key":"e_1_2_2_5_1","volume-title":"OCaml Workshop.","author":"Dolan Stephen","year":"2017","unstructured":"Stephen Dolan and Mindy Preston . 2017 . Testing with crowbar . In OCaml Workshop. Stephen Dolan and Mindy Preston. 2017. Testing with crowbar. In OCaml Workshop."},{"key":"e_1_2_2_6_1","unstructured":"Tony Garnock-Jones Mahdi Eslamimehr and Alessandro Warth. 2018. Recognising and generating terms using derivatives of parsing expression grammars. arXiv preprint arXiv:1801.10490. \t\t\t\t  Tony Garnock-Jones Mahdi Eslamimehr and Alessandro Warth. 2018. Recognising and generating terms using derivatives of parsing expression grammars. arXiv preprint arXiv:1801.10490."},{"key":"e_1_2_2_7_1","volume-title":"Categorical aspects of topology and analysis","author":"Giry Michele","unstructured":"Michele Giry . 1982. A categorical approach to probability theory . In Categorical aspects of topology and analysis . Springer , 68\u201385. Michele Giry. 1982. A categorical approach to probability theory. In Categorical aspects of topology and analysis. Springer, 68\u201385."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2017.8115618"},{"key":"e_1_2_2_9_1","unstructured":"Harrison Goldstein. 2021. Ungenerators. In ICFP Student Research Competition. https:\/\/harrisongoldste.in\/papers\/icfpsrc21.pdf \t\t\t\t  Harrison Goldstein. 2021. Ungenerators. In ICFP Student Research Competition. https:\/\/harrisongoldste.in\/papers\/icfpsrc21.pdf"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7086231"},{"key":"e_1_2_2_11_1","volume-title":"International Symposium on Practical Aspects of Declarative Languages. 1\u201332","author":"Hughes John","year":"2007","unstructured":"John Hughes . 2007 . QuickCheck testing for fun and profit . In International Symposium on Practical Aspects of Declarative Languages. 1\u201332 . https:\/\/dl.acm.org\/doi\/10.1007\/978-3-540-69611-7_1 John Hughes. 2007. QuickCheck testing for fun and profit. In International Symposium on Practical Aspects of Declarative Languages. 1\u201332. https:\/\/dl.acm.org\/doi\/10.1007\/978-3-540-69611-7_1"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2887747.2804319"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009868"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the ACM on Programming Languages, 2, POPL","author":"Lampropoulos Leonidas","year":"2017","unstructured":"Leonidas Lampropoulos , Zoe Paraskevopoulou , and Benjamin C Pierce . 2017 . Generating good generators for inductive relations . Proceedings of the ACM on Programming Languages, 2, POPL (2017), 1\u201330. https:\/\/dl.acm.org\/doi\/10.1145\/3158133 Leonidas Lampropoulos, Zoe Paraskevopoulou, and Benjamin C Pierce. 2017. Generating good generators for inductive relations. Proceedings of the ACM on Programming Languages, 2, POPL (2017), 1\u201330. https:\/\/dl.acm.org\/doi\/10.1145\/3158133"},{"key":"e_1_2_2_15_1","volume-title":"Parsec: Direct style monadic parser combinators for the real world.","author":"Leijen Daan","year":"2001","unstructured":"Daan Leijen and Erik Meijer . 2001 . Parsec: Direct style monadic parser combinators for the real world. Daan Leijen and Erik Meijer. 2001. Parsec: Direct style monadic parser combinators for the real world."},{"key":"e_1_2_2_16_1","unstructured":"Vladimir I Levenshtein. 1966. Binary codes capable of correcting deletions insertions and reversals. In Soviet physics doklady. 10 707\u2013710. \t\t\t\t  Vladimir I Levenshtein. 1966. Binary codes capable of correcting deletions insertions and reversals. In Soviet physics doklady. 10 707\u2013710."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092703.3092711"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.21105\/joss.01891"},{"key":"e_1_2_2_19_1","volume-title":"Notions of computation and monads. Information and computation, 93, 1","author":"Moggi Eugenio","year":"1991","unstructured":"Eugenio Moggi . 1991. Notions of computation and monads. Information and computation, 93, 1 ( 1991 ), 55\u201392. Eugenio Moggi. 1991. Notions of computation and monads. Information and computation, 93, 1 (1991), 55\u201392."},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of ITAT.","author":"Pet\u0159\u00ed\u010dek Tom\u00e1\u0161","year":"2009","unstructured":"Tom\u00e1\u0161 Pet\u0159\u00ed\u010dek . 2009 . Encoding monadic computations in C# using iterators . Proceedings of ITAT. Tom\u00e1\u0161 Pet\u0159\u00ed\u010dek. 2009. Encoding monadic computations in C# using iterators. Proceedings of ITAT."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380399"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993532"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563291","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563291","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:10Z","timestamp":1750178290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563291"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":22,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563291"],"URL":"https:\/\/doi.org\/10.1145\/3563291","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2022-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}