{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:14:56Z","timestamp":1775873696550,"version":"3.50.1"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>\n            Metaprograms are programs that manipulate (generate, analyze and evaluate) other programs. These tasks are greatly facilitated by quasiquotation, a technique to construct and deconstruct program fragments using quoted code templates expressed in the syntax of the manipulated language. We argue that two main flavors of quasiquotes have existed so far: Lisp-style quasiquotes, which can both construct and deconstruct programs but may produce code that contains type mismatches and unbound variables; and MetaML-style quasiquotes, which rely on static typing to prevent these errors, but can only construct programs. In this paper, we show how to combine the advantages of both flavors into a unified framework: we allow the construction, deconstruction and evaluation of program fragments while ensuring that generated programs are well-typed and well-scoped, a combination unseen in previous work. We formalize our approach as \u03bb\n            <jats:sup>{}<\/jats:sup>\n            , a multi-stage calculus with code pattern matching and rewriting, and prove its type safety. We also present its realization in Squid, a metaprogramming framework for Scala, leveraging Scala\u2019s expressive type system. To demonstrate the usefulness of our approach, we introduce\n            <jats:italic>speculative rewrite rules<\/jats:italic>\n            , a novel code transformation technique that makes decisive use of these capabilities, and we outline how it simplifies the design of some crucial query compiler optimizations.\n          <\/jats:p>","DOI":"10.1145\/3158101","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Unifying analytic and statically-typed quasiquotes"],"prefix":"10.1145","volume":"2","author":[{"given":"Lionel","family":"Parreaux","sequence":"first","affiliation":[{"name":"EPFL, Switzerland"}]},{"given":"Antoine","family":"Voizard","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]},{"given":"Amir","family":"Shaikhha","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}]},{"given":"Christoph E.","family":"Koch","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"H. Abelson R. K. Dybvig C. T. Haynes G. J. Rozas N. I. Adams IV D. P. Friedman E. Kohlbecker G. L. Steele Jr. D. H. Bartley R. Halstead D. Oxley G. J. Sussman G. Brooks C. Hanson K. M. Pitman and M. Wand. 1991. Revised4 Report on the Algorithmic Language Scheme. SIGPLAN Lisp Pointers IV 3 (July 1991) 1\u201355.  H. Abelson R. K. Dybvig C. T. Haynes G. J. Rozas N. I. Adams IV D. P. Friedman E. Kohlbecker G. L. Steele Jr. D. H. Bartley R. Halstead D. Oxley G. J. Sussman G. Brooks C. Hanson K. M. Pitman and M. Wand. 1991. Revised4 Report on the Algorithmic Language Scheme. SIGPLAN Lisp Pointers IV 3 (July 1991) 1\u201355.","DOI":"10.1145\/382130.382133"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687592"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30936-1_14"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MEMCOD.2010.5558637"},{"key":"e_1_2_2_6_1","volume-title":"Quasiquotation in Lisp. In ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM). ACM, 4\u201312","author":"Alan"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007205"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/358769.358784"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-011-9225-2"},{"key":"e_1_2_2_11_1","volume-title":"7th Biennial Conference on Innovative Data Systems Research (CIDR).","author":"Crotty Andrew"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30175-2_12"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/91556.91622"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1996.561317"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382785"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/507635.507646"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489837.2489842"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1890028.1890029"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2008.09.007"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/242224.242477"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSR.1998.685738"},{"key":"e_1_2_2_22_1","volume-title":"Partial evaluation and automatic program generation","author":"Jones Neil D"},{"key":"e_1_2_2_23_1","volume-title":"2001 Haskell Workshop. ACM SIGPLAN.","author":"Peyton Jones Simon L.","year":"2001"},{"key":"e_1_2_2_24_1","volume-title":"Yin-Yang: Concealing the Deep Embedding of DSLs (GPCE","author":"Jovanovic Vojin","year":"2014"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2543728.2543740"},{"key":"e_1_2_2_26_1","unstructured":"Manos Karpathiotakis Ioannis Alagiannis Thomas Heinis Miguel Branco and Anastasia Ailamaki. 2015. Just-in-time data virtualization: Lightweight data management with ViDa. In CIDR.  Manos Karpathiotakis Ioannis Alagiannis Thomas Heinis Miguel Branco and Anastasia Ailamaki. 2015. Just-in-time data virtualization: Lightweight data management with ViDa. In CIDR."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111060"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07151-0_6"},{"key":"e_1_2_2_29_1","unstructured":"Oleg Kiselyov. 2017. MetaOCaml \u2013 an OCaml dialect for multi-stage programming. https:\/\/web.archive.org\/web\/ 20170725111517\/http:\/\/okmij.org\/ftp\/ML\/MetaOCaml.html  Oleg Kiselyov. 2017. MetaOCaml \u2013 an OCaml dialect for multi-stage programming. https:\/\/web.archive.org\/web\/ 20170725111517\/http:\/\/okmij.org\/ftp\/ML\/MetaOCaml.html"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-47958-3_15"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732951.2732959"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_2_33_1","first-page":"70","article-title":"Abstraction Without Regret in Database Systems Building: a Manifesto","volume":"37","author":"Koch Christoph","year":"2014","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/319838.319859"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447892"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2011.68"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291201.1291211"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017472.1017477"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0037113"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732984"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847538.2847541"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/581478.581498"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1017\/S095679680500568X"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1352582.1352591"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517208.2517228"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869489"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3136040.3136043"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3136000.3136005"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.54010"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.11.039"},{"key":"e_1_2_2_53_1","unstructured":"WV Quine. 1940. Mathematical Logic. (1940).  WV Quine. 1940. Mathematical Logic. (1940)."},{"key":"e_1_2_2_54_1","unstructured":"Morten Rhiger. 2005. First-class open and closed code fragments. In IN PROCEEDINGS OF THE SIXTH SYMPOSIUM ON TRENDS IN FUNCTIONAL PROGRAMMING.  Morten Rhiger. 2005. First-class open and closed code fragments. In IN PROCEEDINGS OF THE SIXTH SYMPOSIUM ON TRENDS IN FUNCTIONAL PROGRAMMING."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661103.2661109"},{"key":"e_1_2_2_56_1","volume-title":"ESOP","author":"Rhiger Morten","year":"2012"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2998392.2998399"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784760"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868294.1868314"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915244"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/331960.331975"},{"key":"e_1_2_2_63_1","unstructured":"Tim Sheard James Hook and Nathan Linger. 2005. GADTs+ extensible kinds= dependent programming.  Tim Sheard James Hook and Nathan Linger. 2005. GADTs+ extensible kinds= dependent programming."},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/581690.581691"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/944705.944729"},{"key":"e_1_2_2_66_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB \u201905)","author":"Stonebraker Mike","year":"2005"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159884"},{"key":"e_1_2_2_68_1","volume-title":"Domain-Specific Program Generation: International Seminar","author":"Taha Walid","year":"2003"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/640128.604134"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/258993.259019"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00053-0"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814271"},{"key":"e_1_2_2_73_1","first-page":"12","article-title":"Processing Declarative Queries Through Generating Imperative Code in Managed Runtimes","volume":"37","author":"Viglas Stratis","year":"2014","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45821-2_19"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604150"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158101","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":73,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158101"],"URL":"https:\/\/doi.org\/10.1145\/3158101","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}