{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T03:28:27Z","timestamp":1783740507032,"version":"3.55.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2132318, 2122950, 2029457, 1936731, 1918027, 1924435, 1723352"],"award-info":[{"award-number":["2132318, 2122950, 2029457, 1936731, 1918027, 1924435, 1723352"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["042741-394324, FA8750?16?2?0032"],"award-info":[{"award-number":["042741-394324, FA8750?16?2?0032"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"publisher","award":["1723352"],"award-info":[{"award-number":["1723352"]}],"id":[{"id":"10.13039\/100002418","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":[[2023,1,9]]},"abstract":"<jats:p>The development of constraint solvers simplified automated reasoning about programs and shifted the engineering burden to implementing symbolic compilation tools that translate programs into efficiently solvable constraints. We describe Grisette, a reusable symbolic evaluation framework for implementing domain-specific symbolic compilers. Grisette evaluates all execution paths and merges their states into a normal form that avoids making guards mutually exclusive. This ordered-guards representation reduces the constraint size 5-fold and the solving time more than 2-fold. Grisette is designed entirely as a library, which sidesteps the complications of lifting the host language into the symbolic domain. Grisette is purely functional, enabling memoization of symbolic compilation as well as monadic integration with host libraries. Grisette is statically typed, which allows catching programming errors at compile time rather than delaying their detection to the constraint solver. We implemented Grisette in Haskell and evaluated it on benchmarks that stress both the symbolic evaluation and constraint solving.<\/jats:p>","DOI":"10.1145\/3571209","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T21:58:14Z","timestamp":1673474294000},"page":"455-487","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Grisette: Symbolic Compilation as a Functional Programming Library"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2757-7603","authenticated-orcid":false,"given":"Sirui","family":"Lu","sequence":"first","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6639-1647","authenticated-orcid":false,"given":"Rastislav","family":"Bod\u00edk","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30936-1_14"},{"key":"e_1_2_1_2_1","volume-title":"Instruction sets should be free: The case for risc-v. EECS Department","author":"Asanovi\u0107 Krste","year":"2014","unstructured":"Krste Asanovi\u0107 and David A Patterson . 2014. Instruction sets should be free: The case for risc-v. EECS Department , University of California , Berkeley, Tech . Rep. UCB\/EECS- 2014 -146. Krste Asanovi\u0107 and David A Patterson. 2014. Instruction sets should be free: The case for risc-v. EECS Department, University of California, Berkeley, Tech. Rep. UCB\/EECS-2014-146."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568293"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3182657"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30569-9_3"},{"key":"e_1_2_1_6_1","unstructured":"R\u00e9gis William Blanc Etienne Kneuss Viktor Kuncak and Philippe Suter. 2013. On Verification by Translation to Recursive Functions. \t\t\t\t  R\u00e9gis William Blanc Etienne Kneuss Viktor Kuncak and Philippe Suter. 2013. On Verification by Translation to Recursive Functions."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872406"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276519"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800027.808445"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00768-2_16"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201908)","author":"Cadar Cristian","year":"2008","unstructured":"Cristian Cadar , Daniel Dunbar , and Dawson Engler . 2008 . KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs . In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201908) . USENIX Association, USA. 209\u2013224. Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201908). USENIX Association, USA. 209\u2013224."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455518.1455522"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158150"},{"key":"e_1_2_1_14_1","volume-title":"Cosette: An Automated Prover for SQL.. In CIDR.","author":"Chu Shumo","year":"2017","unstructured":"Shumo Chu , Chenglong Wang , Konstantin Weitz , and Alvin Cheung . 2017 . Cosette: An Automated Prover for SQL.. In CIDR. Shumo Chu, Chenglong Wang, Konstantin Weitz, and Alvin Cheung. 2017. Cosette: An Automated Prover for SQL.. In CIDR."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24730-2_15"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/91556.91622"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110256"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(72)90034-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1995376.1995394"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146238.1146251"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287653"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110271"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190226"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065036"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314618"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331545.3342590"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04694-0_6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100090050043"},{"key":"e_1_2_1_29_1","unstructured":"Joe Hermaszewski. 2021. vector-sized. https:\/\/hackage.haskell.org\/package\/vector-sized \t\t\t\t  Joe Hermaszewski. 2021. vector-sized. https:\/\/hackage.haskell.org\/package\/vector-sized"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_2_1_31_1","unstructured":"James Cornelius. King. 1969. A program verifier.. Ph. D. Dissertation. lccn:76127837 \t\t\t\t  James Cornelius. King. 1969. A program verifier.. Ph. D. Dissertation. lccn:76127837"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800027.808444"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360252"},{"key":"e_1_2_1_34_1","unstructured":"Oleg Kiselyov. 2013. Efficient Set Monad. https:\/\/web.archive.org\/web\/20201112030922\/http:\/\/okmij.org\/ftp\/Haskell\/set-monad.html archived 2020-11-12 \t\t\t\t  Oleg Kiselyov. 2013. Efficient Set Monad. https:\/\/web.archive.org\/web\/20201112030922\/http:\/\/okmij.org\/ftp\/Haskell\/set-monad.html archived 2020-11-12"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503778.2503791"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103675"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254088"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17511-4_20"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12002-2_26"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2884781.2884807"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3358502.3361269"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2393596.2393667"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359641"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498709"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Richard L Rudell. 1986. Multiple-valued logic minimization for PLA synthesis. CALIFORNIA UNIV BERKELEY ELECTRONICS RESEARCH LAB. \t\t\t\t  Richard L Rudell. 1986. Multiple-valued logic minimization for PLA synthesis. CALIFORNIA UNIV BERKELEY ELECTRONICS RESEARCH LAB.","DOI":"10.21236\/ADA606736"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500602"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491447"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786805.2786830"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409734"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/581690.581691"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2008.ECP.23"},{"key":"e_1_2_1_54_1","unstructured":"Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph. D. Dissertation. USA. isbn:9781109097450 AAI3353225 \t\t\t\t  Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph. D. Dissertation. USA. isbn:9781109097450 AAI3353225"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_1_56_1","unstructured":"Don Stewart and Duncan Coutts. 2021. bytestring. https:\/\/hackage.haskell.org\/package\/bytestring \t\t\t\t  Don Stewart and Duncan Coutts. 2021. bytestring. https:\/\/hackage.haskell.org\/package\/bytestring"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90018-D"},{"key":"e_1_2_1_58_1","unstructured":"Emina Torlak. 2016. unsound behavior? https:\/\/web.archive.org\/web\/20201122222820\/https:\/\/github.com\/emina\/rosette\/issues\/36 archived 2020-11-22 \t\t\t\t  Emina Torlak. 2016. unsound behavior? https:\/\/web.archive.org\/web\/20201122222820\/https:\/\/github.com\/emina\/rosette\/issues\/36 archived 2020-11-22"},{"key":"e_1_2_1_59_1","unstructured":"Emina Torlak. 2021. Use early return in rosette? https:\/\/web.archive.org\/web\/20220223043310\/https:\/\/github.com\/emina\/rosette\/issues\/201 archived 2022-02-22 \t\t\t\t  Emina Torlak. 2021. Use early return in rosette? https:\/\/web.archive.org\/web\/20220223043310\/https:\/\/github.com\/emina\/rosette\/issues\/201 archived 2022-02-22"},{"key":"e_1_2_1_60_1","unstructured":"Emina Torlak. 2022. Debugging Rosette Guide. https:\/\/web.archive.org\/web\/20220520032819\/https:\/\/docs.racket-lang.org\/rosette-guide\/ch_error-tracing.html##%28part._sec~3aerrors-in-rosette%29 archived 2022-05-20 \t\t\t\t  Emina Torlak. 2022. Debugging Rosette Guide. https:\/\/web.archive.org\/web\/20220520032819\/https:\/\/docs.racket-lang.org\/rosette-guide\/ch_error-tracing.html##%28part._sec~3aerrors-in-rosette%29 archived 2022-05-20"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509578.2509586"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594340"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_45"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660208"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428232"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304027"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1093"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19797-5_15"},{"key":"e_1_2_1_69_1","unstructured":"Nicolas Wu Tom Schrijvers Rob Rix and Patrick Thomson. 2022. fused-effects. https:\/\/hackage.haskell.org\/package\/fused-effects \t\t\t\t  Nicolas Wu Tom Schrijvers Rob Rix and Patrick Thomson. 2022. fused-effects. https:\/\/hackage.haskell.org\/package\/fused-effects"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040334"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:21Z","timestamp":1750183701000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":70,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2023,1,9]]}},"alternative-id":["10.1145\/3571209"],"URL":"https:\/\/doi.org\/10.1145\/3571209","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,9]]},"assertion":[{"value":"2023-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}