{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T01:30:29Z","timestamp":1785202229227,"version":"3.55.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Center For Advancing Translational Sciences of the National Institutes of Health","award":["OT2TR003435"],"award-info":[{"award-number":["OT2TR003435"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2348408,2303983,2315884"],"award-info":[{"award-number":["CCF-2348408,2303983,2315884"]}],"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":[[2025,6,10]]},"abstract":"<jats:p>We transport multi-stage programming from functional to relational programming, with novel constructs to give programmers control over staging and non-determinism. We stage interpreters written as relations, in which the programs under interpretation can contain holes representing unknown expressions or values. By compiling the known parts without interpretive overhead and deferring interpretation to run time only for the unknown parts, we compound the benefits of staging (e.g., turning interpreters into compilers) and relational interpretation (e.g., turning functions into relations and synthesizing from sketches). We extend miniKanren with staging constructs and apply the resulting multi-stage language to relational interpreters for subsets of Racket and miniKanren as well as a relational recognizer for context-free grammars. We demonstrate significant performance gains across multiple synthesis problems, systematically comparing unstaged and staged computation, as well as indicatively comparing with an existing hand-tuned relational interpreter.<\/jats:p>","DOI":"10.1145\/3729314","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1591-1615","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-stage Relational Programming"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9958-6281","authenticated-orcid":false,"given":"Michael","family":"Ballantyne","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7266-7422","authenticated-orcid":false,"given":"Rafaello","family":"Sanna","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5405-2936","authenticated-orcid":false,"given":"Jason","family":"Hemann","sequence":"additional","affiliation":[{"name":"Seton Hall University, South Orange, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4730-5293","authenticated-orcid":false,"given":"William E.","family":"Byrd","sequence":"additional","affiliation":[{"name":"University of Alabama at Birmingham, Birmingham, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0830-7248","authenticated-orcid":false,"given":"Nada","family":"Amin","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054101000448"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","unstructured":"Sergei Abramov and Robert Gl\u00fcck. 2002. Principles of inverse computation and the universal resolving algorithm. In The essence of computation. Lecture notes in computer science Vol. 2566. 269\u2013295. doi:10.1007\/3-540-36377-7_13","DOI":"10.1007\/3-540-36377-7_13"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3674627"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","unstructured":"Michael Ballantyne Rafaello Sanna Jason Hemann William E. Byrd and Nada Amin. 2025. Multi-Stage Relational Programming Artifact. doi:10.5281\/zenodo.15233194","DOI":"10.5281\/zenodo.15233194"},{"key":"e_1_3_2_6_1","unstructured":"Alan Bawden. 1999. Quasiquotation in Lisp. In Proc. Workshop on Partial Evaluation and Semantics-Based Program Manipulation. 4\u201312. https:\/\/www.brics.dk\/NS\/99\/1\/BRICS-NS-99-1.pdf"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","unstructured":"Maurice Bruynooghe Michael Leuschel and Konstantinos Sagonas. 1998. A polyvariant binding-time analysis for off-line partial deduction. In Proc. European Symposium on Programming. 27\u201341. doi:10.1007\/BFb0053561","DOI":"10.1007\/BFb0053561"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_2_9_1","unstructured":"Francisco Bueno Manuel Hermenegildo Pedro L\u00f3pez and Germ\u00e1n Puebla. 1996. The Ciao Preprocessor. Technical Report CLIP 1\/06. The Computational logic Languages Implementation and Parallelism (CLIP) Lab at IMDEA Software Institute. https:\/\/ciao-lang.org\/legacy\/files\/ciao\/ciao-1.15\/13954560f564e08056ce53d86ebffad604b000dd\/CiaoDE-1.15-1653-g1395456_ciaopp.pdf"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110252"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","unstructured":"William E. Byrd Eric Holk and Daniel P. Friedman. 2012. miniKanren live and untagged: Quine generation via relational interpreters (programming pearl). In Proc. Workshop on Scheme and Functional Programming. 8\u201329. doi:10.1145\/2661103.2661105","DOI":"10.1145\/2661103.2661105"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","unstructured":"Cristiano Calcagno Walid Taha Liwen Huang and Xavier Leroy. 2003. Implementing multi-stage languages using ASTs gensym and reflection. In Proc. Generative Programming and Component Engineering. 57\u201376. doi:10.1007\/978-3-540-39815-8_4","DOI":"10.1007\/978-3-540-39815-8_4"},{"key":"e_1_3_2_13_1","unstructured":"Artem Chirkov Gregory Rosenblatt Matthew Might and Lisa Zhang. 2020. A relational interpreter for synthesizing JavaScript. In Proc. miniKanren and Relational Programming Workshop. 123\u2013155. http:\/\/hdl.handle.net\/2047\/D20413639"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","unstructured":"Stephen-John Craig John P. Gallagher Michael Leuschel and Kim S. Henriksen. 2005. Fully automatic binding-time analysis for Prolog. In Proc. Symposium on Logic-Based Program Synthesis and Transformation. 53\u201368. doi:10.1007\/11506676_4","DOI":"10.1007\/11506676_4"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","unstructured":"Zachary DeVito James Hegarty Alex Aiken Pat Hanrahan and Jan Vitek. 2013. Terra: a multi-stage language for highperformance computing. In Proc. Programming Language Design and Implementation. 105\u2013116. doi:10.1145\/2491956.2462166","DOI":"10.1145\/2491956.2462166"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/5801.001.0001"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3267158"},{"key":"e_1_3_2_18_1","unstructured":"John Gallagher. 1986. Transforming logic programs by specialising interpreters. In Proc. European Conference on Artificial Intelligence. 313\u2013326."},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","unstructured":"Yuichiro Hanada and Atsushi Igarashi. 2014. On cross-stage persistence in multi-stage programming. In Proc. Functional and Logic Programming. 103\u2013118. doi:10.1007\/978-3-319-07151-0_7","DOI":"10.1007\/978-3-319-07151-0_7"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185679"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","unstructured":"Jason Hemann Daniel P. Friedman William E. Byrd and Matthew Might. 2016. A small embedding of logic programming with a simple complete search. In Proc. Symposium on Dynamic Languages. 96\u2013107. doi:10.1145\/2989225.2989230","DOI":"10.1145\/2989225.2989230"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","unstructured":"Jun Inoue and Walid Taha. 2016. Reasoning about multi-stage programs. Journal of Functional Programming 26 Article e22 (2016). doi:10.1017\/S0956796816000253","DOI":"10.1017\/S0956796816000253"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","unstructured":"Ulrik J\u00f8rring and William L. Scherlis. 1986. Compilers and staging transformations. In Proc. Principles of Programming Languages. 86\u201396. doi:10.1145\/512644.512652","DOI":"10.1145\/512644.512652"},{"key":"e_1_3_2_24_1","unstructured":"Ramana Joshi and William E. Byrd. 2021. metaKanren: Towards a metacircular relational interpreter. In Proc. miniKanren and Relational Programming Workshop. 47\u201373. http:\/\/hdl.handle.net\/1807\/110263"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434311"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","unstructured":"Oleg Kiselyov. 2014. The design and implementation of BER MetaOCaml. In Proc. Functional and Logic Programming. 86\u2013102. doi:10.1007\/978-3-319-07151-0_6","DOI":"10.1007\/978-3-319-07151-0_6"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","unstructured":"Oleg Kiselyov William E. Byrd Daniel P. Friedman and Chung-chieh Shan. 2008. Pure declarative and constructive arithmetic relations (declarative pearl). In Proc. Functional and Logic Programming. 64\u201380. doi:10.1007\/978-3-540-789697_7","DOI":"10.1007\/978-3-540-789697_7"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","unstructured":"Oleg Kiselyov Chung-chieh Shan Daniel P. Friedman and Amr Sabry. 2005. Backtracking interleaving and terminating monad transformers (functional pearl). In Proc. International Conference on Functional Programming. 192\u2013203. doi:10.1145\/1086365.1086390","DOI":"10.1145\/1086365.1086390"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","unstructured":"Dmitry Kosarev and Dmitry Boulytchev. 2016. Typed embedding of a relational language in OCaml. Proc. Workshop on ML. doi:10.48550\/arXiv.1805.11006","DOI":"10.48550\/arXiv.1805.11006"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","unstructured":"Michael Leuschel Stephen J. Craig Maurice Bruynooghe and Wim Vanhoof. 2004a. Specialising interpreters using offline partial deduction. In Program Development in Computational Logic. Lecture notes in computer science Vol. 3049. 340\u2013375. doi:10.1007\/978-3-540-25951-0_11","DOI":"10.1007\/978-3-540-25951-0_11"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001662"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3354584"},{"key":"e_1_3_2_33_1","unstructured":"Petr Lozov Ekaterina Verbitskaia and Dmitry Boulytchev. 2019. Relational interpreters for search problems. In Proc. miniKanren and Relational Programming Workshop. 43\u201357. http:\/\/nrs.harvard.edu\/urn-3:HUL.InstRepos:41307116"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","unstructured":"Petr Lozov Andrei Vyatkin and Dmitry Boulytchev. 2018. Typed relational conversion. In Proc. Trends in Functional Programming. 39\u201358. doi:10.1007\/978-3-319-89719-6_3","DOI":"10.1007\/978-3-319-89719-6_3"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352098"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","unstructured":"Matthew Might David Darais and Daniel Spiewak. 2011. Parsing with derivatives: A functional pearl. In Proc. International Conference on Functional Programming. 189\u2013195. doi:10.1145\/2034773.2034801","DOI":"10.1145\/2034773.2034801"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","unstructured":"Peter-Michael Osera and Steve Zdancewic. 2015. Type-and-example-directed program synthesis. In Proc. Programming Language Design and Implementation. 619\u2013630. doi:10.1145\/2737924.2738007","DOI":"10.1145\/2737924.2738007"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","unstructured":"Oleksandr Polozov and Sumit Gulwani. 2015. FlashMeta: a framework for inductive program synthesis. In Proc. ObjectOriented Programming Systems Languages and Applications. 107\u2013126. doi:10.1145\/2814270.2814310","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","unstructured":"Tiark Rompf and Martin Odersky. 2010. Lightweight modular staging: A pragmatic approach to runtime code generation and compiled DSLs. In Proc. Generative Programming and Component Engineering. 127\u2013136. doi:10.1145\/1868294.1868314","DOI":"10.1145\/1868294.1868314"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2184319.2184345"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","unstructured":"Dmitry Rozplokhas Andrey Vyatkin and Dmitry Boulytchev. 2020. Certified semantics for relational programming. In Proc. Asian Symposium on Programming Languages and Systems. 167\u2013185. doi:10.1007\/978-3-030-64437-6_9","DOI":"10.1007\/978-3-030-64437-6_9"},{"key":"e_1_3_2_42_1","unstructured":"Armando Solar-Lezama. 2008. Program Synthesis by Sketching. Ph. D. Dissertation. USA. Advisor(s) Bodik Rastislav."},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","unstructured":"Armando Solar-Lezama. 2009. The sketching approach to program synthesis. In Proc. Asian Symposium on Programming Languages and Systems. 4\u201313. doi:10.1007\/978-3-642-10672-9_3","DOI":"10.1007\/978-3-642-10672-9_3"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(96)00068-4"},{"key":"e_1_3_2_45_1","volume-title":"The Art of Prolog (2nd Ed.): Advanced Programming Techniques","author":"Sterling Leon","year":"1994","unstructured":"Leon Sterling and Ehud Shapiro. 1994. The Art of Prolog (2nd Ed.): Advanced Programming Techniques. MIT Press, Cambridge, MA, USA."},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139194129"},{"key":"e_1_3_2_47_1","unstructured":"Walid Taha. 1999. Multi-Stage Programming: Its Theory and Applications. Ph. D. Dissertation. Advisor(s) Tim Sheard."},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00053-0"},{"key":"e_1_3_2_49_1","unstructured":"Ekaterina Verbitskaia Danil Berezun and Dmitry Boulytchev. 2020. An empirical study of partial deduction for miniKanren. In Proc. miniKanren and Relational Programming Workshop. 13\u201321. http:\/\/hdl.handle.net\/2047\/D20413639"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729314","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:09:11Z","timestamp":1784196551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":48,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729314"],"URL":"https:\/\/doi.org\/10.1145\/3729314","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}