{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T08:58:41Z","timestamp":1790413121100,"version":"4.1.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T00:00:00Z","timestamp":1786924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,8,17]]},"abstract":"<jats:p>Property-based testing (PBT) is a powerful technique for software verification that relies on random input generators and \u201cshrinking\u201d processes to find and minimize counterexamples to executable specifications called properties. While optimizing these generators is crucial for testing efficiency, formally justifying such optimizations is currently difficult because existing languages lack a compositional semantics that is coarse-grained enough for high-level reasoning.<\/jats:p>\n                  <jats:p>In this paper, we first provide a formal account of the syntax and semantics of Hedgehog, a popular PBT framework. We demonstrate that Hedgehog\u2019s distribution semantics \u2013 which models how users typically reason about generators \u2013 is non-compositional. Furthermore, we prove that any sound and complete compositional semantics for Hedgehog must necessarily be equivalent to its sampling semantics, which is too fine-grained to justify common program optimizations.<\/jats:p>\n                  <jats:p>\n                    To resolve this dilemma, we introduce Hedgehog\n                    <jats:sup>\u2191<\/jats:sup>\n                    , a restricted version of the language based on the arrow calculus, and prove that Hedgehog\n                    <jats:sup>\u2191<\/jats:sup>\n                    possesses a compositional distribution semantics. We evaluate Hedgehog\n                    <jats:sup>\u2191<\/jats:sup>\n                    through a Haskell implementation and show that it remains expressive enough to capture generators of practical interest, while providing the formal foundation needed for compositional generator equivalence proofs.\n                  <\/jats:p>","DOI":"10.1145\/3828695","type":"journal-article","created":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T20:23:46Z","timestamp":1786998226000},"page":"663-691","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Compositional Generator Equivalence"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-3926-149X","authenticated-orcid":false,"given":"Anthony","family":"Vandikas","sequence":"first","affiliation":[{"name":"University of Toronto, Department of Computer Science, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9460-084X","authenticated-orcid":false,"given":"Kiarash","family":"Sotoudeh","sequence":"additional","affiliation":[{"name":"University of Toronto, Department of Computer Science, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6301-3517","authenticated-orcid":false,"given":"Marsha","family":"Chechik","sequence":"additional","affiliation":[{"name":"University of Toronto, Department of Computer Science, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,17]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198537625.003.0001"},{"key":"e_1_3_1_3_1","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho Alfred V.","year":"2006","unstructured":"Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., USA.","edition":"2"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_31"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05089-3_30"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351266"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1631687.1596574"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_14"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45231-5_8"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3609026.3609733"},{"key":"e_1_3_1_11_1","unstructured":"Emil Eriksson. 2024. RapidCheck. github.com\/emil-e\/rapidcheck."},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","unstructured":"Claudia Faggian and Simona Ronchi della Rocca. 2019. Lambda Calculus and Probabilistic Computation. In 2019 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). IEEE 1\u201313. doi:10.1109\/lics.2019.8785699","DOI":"10.1109\/lics.2019.8785699"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","unstructured":"Andrew Farmer Andy Gill Ed Komp and Neil Sculthorpe. 2012. The HERMIT in the machine: a plugin for the interactive transformation of GHC core language programs. In Proceedings of the 2012 Haskell Symposium (Copenhagen Denmark) (Haskell \u201912). Association for Computing Machinery New York NY USA 1\u201312. doi:10.1145\/2364506.2364508","DOI":"10.1145\/2364506.2364508"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034574.2034777"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3607842"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","unstructured":"Chris Heunen Ohad Kammar Sam Staton and Hongseok Yang. 2017. A Convenient Category for Higher-Order Probability Theory. In 2017 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS). IEEE 1\u201312. doi:10.1109\/lics.2017.8005137","DOI":"10.1109\/lics.2017.8005137"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(99)00023-4"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","unstructured":"John Hughes. 2004. Programming with arrows. In Proceedings of the 5th International Conference on Advanced Functional Programming (Tartu Estonia) (AFP\u201904). Springer-Verlag Berlin Heidelberg 73\u2013129. doi:10.1007\/11546382_2","DOI":"10.1007\/11546382_2"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","unstructured":"Robert Krook Nicholas Smallbone Bo Joel Svensson and Koen Claessen. 2024. QuickerCheck: Implementing and Evaluating a Parallel Run-Time for QuickCheck. In Proceedings of the 35th Symposium on Implementation and Application of Functional Languages (Braga Portugal) (IFL \u201923). Association for Computing Machinery New York NY USA Article 9 12 pages. doi:10.1145\/3652561.3652570","DOI":"10.1145\/3652561.3652570"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/S095679680999027X"},{"key":"e_1_3_1_21_1","unstructured":"Jason Lyngle. 2019. Proptest. https:\/\/altsysrq.github.io\/proptest-book\/print.html#differences-between-quickcheck-and-proptest"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.21105\/joss.01891"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796807006326"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2004.04.019"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/507669.507664"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677999.3678275"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3798263"},{"key":"e_1_3_1_30_1","unstructured":"Jacob Stanley. 2024. Hedgehog. https:\/\/www.hackage.haskell.org\/package\/hedgehog."},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"e_1_3_1_32_1","unstructured":"Fraser Tweedale. 2020. Migrating from QuickCheck to Hedgehog: mixed results. https:\/\/frasertweedale.github.io\/blog-fp\/posts\/2020-03-31-quickcheck-hedgehog.html#shrinking-performance"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290349"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.5281\/ZENODO.21018867"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","unstructured":"Anthony Vandikas Kiarash Sotoudeh and Marsha Chechik. 2026b. Compositional Generator Equivalence (Extended Version). doi:10.48550\/ARXIV.2606.22616","DOI":"10.48550\/ARXIV.2606.22616"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/s0960129505005074"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3828695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T08:10:03Z","timestamp":1790410203000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3828695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,17]]},"references-count":35,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2026,8,17]]}},"alternative-id":["10.1145\/3828695"],"URL":"https:\/\/doi.org\/10.1145\/3828695","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,17]]},"assertion":[{"value":"2026-02-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}