{"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":1775873615455,"version":"3.50.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2020,8,2]],"date-time":"2020-08-02T00:00:00Z","timestamp":1596326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S028129\/1"],"award-info":[{"award-number":["EP\/S028129\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,8,2]]},"abstract":"<jats:p>Parser combinators are a middle ground between the fine control of hand-rolled parsers and the high-level almost grammar-like appearance of parsers created via parser generators. They also promote a cleaner, compositional design for parsers. Historically, however, they cannot match the performance of their counterparts.<\/jats:p>\n          <jats:p>This paper describes how to compile parser combinators into parsers of hand-written quality. This is done by leveraging the static information present in the grammar by representing it as a tree. However, in order to exploit this information, it will be necessary to drop support for monadic computation since this generates dynamic structure. Selective functors can help recover lost functionality in the absence of monads, and the parser tree can be partially evaluated with staging. This is implemented in a library called Parsley.<\/jats:p>","DOI":"10.1145\/3409002","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T13:48:02Z","timestamp":1596462482000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Staged selective parser combinators"],"prefix":"10.1145","volume":"4","author":[{"given":"Jamie","family":"Willis","sequence":"first","affiliation":[{"name":"Imperial College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4161-985X","authenticated-orcid":false,"given":"Nicolas","family":"Wu","sequence":"additional","affiliation":[{"name":"Imperial College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Pickering","sequence":"additional","affiliation":[{"name":"University of Bristol, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775050.2633369"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908128"},{"key":"e_1_2_2_3_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"2006"},{"key":"e_1_2_2_4_1","volume-title":"Compiling with Continuations","author":"Appel Andrew W."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017472.1017485"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_24"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/236114.236119"},{"key":"e_1_2_2_9_1","volume-title":"Trends in Functional Programming, Ricardo Pe\u00f1a and Rex Page (Eds.)","author":"Delbianco Germ\u00e1n Andr\u00e9s"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796812000226"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/982962.964011"},{"key":"e_1_2_2_13_1","volume-title":"Domain Specific Languages","author":"Fowler Martin","edition":"1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034574.2034777"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628138"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596638.1596653"},{"key":"e_1_2_2_17_1","unstructured":"Andy Gill and Simon Marlow. 1995. Happy: the parser generator for Haskell.  Andy Gill and Simon Marlow. 1995. Happy: the parser generator for Haskell."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360553"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","volume-title":"Mathematics of Program Construction","author":"Hinze Ralf","DOI":"10.1007\/978-3-319-19797-5"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2502488.2502496"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500578"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/242224.242477"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000411"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660241"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291179"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236780"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314625"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/773473.178246"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/331963.331977"},{"key":"e_1_2_2_33_1","volume-title":"Parsec: Direct Style Monadic Parser Combinators For The Real World. Technical Report. Microsoft.","author":"Leijen Daan","year":"2001"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2692915.2628144"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062380"},{"key":"e_1_2_2_37_1","unstructured":"Conor McBride. 2011. Functional pearl: Kleisli arrows of outrageous fortune. Journal of Functional Programming (accepted for publication) ( 2011 ).  Conor McBride. 2011. Functional pearl: Kleisli arrows of outrageous fortune. Journal of Functional Programming (accepted for publication) ( 2011 )."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796807006326"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13346-1_15"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341694"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004178"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1942788.1868314"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/636517.636528"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03153-3_6"},{"key":"e_1_2_2_45_1","volume-title":"Error-Correcting Combinator Parsers. In Advanced Functional Programming, Second International School-Tutorial Text","author":"Doaitse Swierstra S."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/258994.259019"},{"key":"e_1_2_2_47_1","unstructured":"Tarmo Uustalu and Varmo Vene. 1999. Primitive (Co)Recursion and Course-of-Value (Co)Iteration Categorically. Informatica 10 ( 1999 ) 5-26.  Tarmo Uustalu and Varmo Vene. 1999. Primitive (Co)Recursion and Course-of-Value (Co)Iteration Categorically. Informatica 10 ( 1999 ) 5-26."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411286.1411296"},{"key":"e_1_2_2_49_1","volume-title":"Mathematics of Program Construction, Philippe Audebaud and Christine Paulin-Mohring (Eds.)","author":"Voigtl\u00e4nder Janis"},{"key":"e_1_2_2_50_1","doi-asserted-by":"crossref","volume-title":"How to replace failure by a list of successes a method for exception handling, backtracking, and pattern matching in lazy functional languages","author":"Wadler Philip","DOI":"10.1007\/3-540-15975-4_33"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241653.3241656"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2633357.2633358"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110273"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294032.3294078"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409002","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:59Z","timestamp":1750193279000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,2]]},"references-count":50,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2020,8,2]]}},"alternative-id":["10.1145\/3409002"],"URL":"https:\/\/doi.org\/10.1145\/3409002","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,2]]},"assertion":[{"value":"2020-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}