{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T11:52:27Z","timestamp":1774007547714,"version":"3.50.1"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T00:00:00Z","timestamp":1570665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100005801","name":"Facebook","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005801","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016682","name":"VMware","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016682","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1553471, 1564207, 1918483"],"award-info":[{"award-number":["1553471, 1564207, 1918483"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0018050"],"award-info":[{"award-number":["DE-SC0018050"]}],"id":[{"id":"10.13039\/100000015","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":[[2019,10,10]]},"abstract":"<jats:p>It is well known that a staged interpreter is a compiler: specializing an interpreter to a given program produces an equivalent executable that runs faster. This connection is known as the first Futamura projection. It is even more widely known that an abstract interpreter is a program analyzer: tweaking an interpreter to run on abstract domains produces a sound static analysis. What happens when we combine these two ideas, and apply specialization to an abstract interpreter?<\/jats:p>\n          <jats:p>In this paper, we present a unifying framework that naturally extends the first Futamura projection from concrete interpreters to abstract interpreters. Our approach derives a sound staged abstract interpreter based on a generic interpreter with type-level binding-time abstractions and monadic abstractions. By using different instantiations of these abstractions, the generic interpreter can flexibly behave in one of four modes: as an unstaged concrete interpreter, a staged concrete interpreter, an unstaged abstract interpreter, or a staged abstract interpreter. As an example of abstraction without regret, the overhead of these abstraction layers is eliminated in the generated code after staging. We show that staging abstract interpreters is practical and useful to optimize static analysis, all while requiring less engineering effort and without compromising soundness. We conduct three case studies, including a comparison with Boucher and Feeley\u2019s abstract compilation, applications to various control-flow analyses, and a demonstration for modular analysis. We also empirically evaluate the effect of staging on the execution time. The experiment shows an order of magnitude speedup with staging for control-flow analyses.<\/jats:p>","DOI":"10.1145\/3360552","type":"journal-article","created":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T14:53:33Z","timestamp":1570805613000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Staged abstract interpreters: fast and modular whole-program analysis via meta-programming"],"prefix":"10.1145","volume":"3","author":[{"given":"Guannan","family":"Wei","sequence":"first","affiliation":[{"name":"Purdue University, USA"}]},{"given":"Yuxuan","family":"Chen","sequence":"additional","affiliation":[{"name":"Purdue University, USA"}]},{"given":"Tiark","family":"Rompf","sequence":"additional","affiliation":[{"name":"Purdue University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,10,10]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048105"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/888251.888254"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2426890.2426917"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158140"},{"key":"e_1_2_2_5_1","volume-title":"Partial evaluation for constraint-based program analyses. BRICS Report Series 6, 45","author":"Amtoft Torben","year":"1999","unstructured":"Torben Amtoft . 1999. Partial evaluation for constraint-based program analyses. BRICS Report Series 6, 45 ( 1999 ). Torben Amtoft. 1999. Partial evaluation for constraint-based program analyses. BRICS Report Series 6, 45 (1999)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088515.3088522"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/291891.291898"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628153"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1565824.1565827"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61053-7_62"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39815-8_4"},{"key":"e_1_2_2_12_1","volume-title":"Multi-stage Programming with Functors and Monads: Eliminating Abstraction Overhead from Generic Code","author":"Carette Jacques","unstructured":"Jacques Carette and Oleg Kiselyov . 2005. Multi-stage Programming with Functors and Monads: Eliminating Abstraction Overhead from Generic Code . In Generative Programming and Component Engineering, Robert Gl\u00fcck and Michael Lowry (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 256\u2013274. Jacques Carette and Oleg Kiselyov. 2005. Multi-stage Programming with Functors and Monads: Eliminating Abstraction Overhead from Generic Code. In Generative Programming and Component Engineering, Robert Gl\u00fcck and Michael Lowry (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 256\u2013274."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007205"},{"key":"e_1_2_2_14_1","volume-title":"Functional Programming in Scala","author":"Chiusano Paul","unstructured":"Paul Chiusano and Rnar Bjarnason . 2014. Functional Programming in Scala ( 1 st ed.). Manning Publications Co. , Greenwich, CT, USA . Paul Chiusano and Rnar Bjarnason. 2014. Functional Programming in Scala (1st ed.). Manning Publications Co., Greenwich, CT, USA.","edition":"1"},{"key":"e_1_2_2_15_1","volume-title":"The Calculational Design of a Generic Abstract Interpreter","author":"Cousot P.","unstructured":"P. Cousot . 1999. The Calculational Design of a Generic Abstract Interpreter . In Calculational System Design, M. Broy and R. Steinbr\u00fcggen (Eds.). NATO ASI Series F. IOS Press , Amsterdam . P. Cousot. 1999. The Calculational Design of a Generic Abstract Interpreter. In Calculational System Design, M. Broy and R. Steinbr\u00fcggen (Eds.). NATO ASI Series F. IOS Press, Amsterdam."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_2_17_1","volume-title":"Conference Record of the Sixth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press","author":"Cousot P.","unstructured":"P. Cousot and R. Cousot . 1979. Systematic design of program analysis frameworks . In Conference Record of the Sixth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press , New York, NY, San Antonio, Texas, 269\u2013282. P. Cousot and R. Cousot. 1979. Systematic design of program analysis frameworks. In Conference Record of the Sixth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, New York, NY, San Antonio, Texas, 269\u2013282."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45937-5_13"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290355"},{"key":"e_1_2_2_20_1","volume-title":"BRICS PhD School","author":"Damian Daniel","unstructured":"Daniel Damian . 1999. Partial evaluation for program analysis. Progress report , BRICS PhD School , University of Aarhus (1999) . Daniel Damian. 1999. Partial evaluation for program analysis. Progress report, BRICS PhD School, University of Aarhus (1999)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110256"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814308"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951934"},{"key":"e_1_2_2_25_1","volume-title":"Flare: Optimizing Apache Spark with Native Compilation for Scale-Up Architectures and Medium-Size Data. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018","author":"Essertel Gr\u00e9gory M.","year":"2018","unstructured":"Gr\u00e9gory M. Essertel , Ruby Y. Tahboub , James M. Decker , Kevin J. Brown , Kunle Olukotun , and Tiark Rompf . 2018 . Flare: Optimizing Apache Spark with Native Compilation for Scale-Up Architectures and Medium-Size Data. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018 , Carlsbad, CA, USA , October 8-10, 2018., Andrea C. Arpaci-Dusseau and Geoff Voelker (Eds.). USENIX Association, 799\u2013815. https:\/\/www.usenix.org\/conference\/osdi18\/ presentation\/essertel Gr\u00e9gory M. Essertel, Ruby Y. Tahboub, James M. Decker, Kevin J. Brown, Kunle Olukotun, and Tiark Rompf. 2018. Flare: Optimizing Apache Spark with Native Compilation for Scale-Up Architectures and Medium-Size Data. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018, Carlsbad, CA, USA, October 8-10, 2018., Andrea C. Arpaci-Dusseau and Geoff Voelker (Eds.). USENIX Association, 799\u2013815. https:\/\/www.usenix.org\/conference\/osdi18\/ presentation\/essertel"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41654"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155113"},{"key":"e_1_2_2_28_1","first-page":"45","article-title":"Partial evaluation of ccomputation process-an approach to a compiler-compiler. Systems, Compurters","volume":"25","author":"Futamura Yoshihiko","year":"1971","unstructured":"Yoshihiko Futamura . 1971 . Partial evaluation of ccomputation process-an approach to a compiler-compiler. Systems, Compurters , Controls 25 (1971), 45 \u2013 50 . Yoshihiko Futamura. 1971. Partial evaluation of ccomputation process-an approach to a compiler-compiler. Systems, Compurters, Controls 25 (1971), 45\u201350.","journal-title":"Controls"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010095604496"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676987"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951936"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837631"},{"key":"e_1_2_2_33_1","unstructured":"Github Inc. 2019. Semantic Analyzer. https:\/\/github.com\/github\/semantic .  Github Inc. 2019. Semantic Analyzer. https:\/\/github.com\/github\/semantic ."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375616"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2011.5764696"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863553"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796812000238"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500604"},{"key":"e_1_2_2_39_1","volume-title":"What not to do when writing an interpreter for specialisation","author":"Jones Neil D.","unstructured":"Neil D. Jones . 1996. What not to do when writing an interpreter for specialisation . In Partial Evaluation, Olivier Danvy, Robert Gl\u00fcck, and Peter Thiemann (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 216\u2013237. Neil D. Jones. 1996. What not to do when writing an interpreter for specialisation. In Partial Evaluation, Olivier Danvy, Robert Gl\u00fcck, and Peter Thiemann (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 216\u2013237."},{"key":"e_1_2_2_40_1","volume-title":"Partial evaluation and automatic program generation","author":"Jones Neil D.","unstructured":"Neil D. Jones , Carsten K. Gomard , and Peter Sestoft . 1993. Partial evaluation and automatic program generation . Prentice Hall . Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. 1993. Partial evaluation and automatic program generation. Prentice Hall."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660241"},{"key":"e_1_2_2_42_1","volume-title":"Souffl\u00e9: On Synthesis of Program Analyzers","author":"Jordan Herbert","year":"2016","unstructured":"Herbert Jordan , Bernhard Scholz , and Pavle Suboti\u0107 . 2016 . Souffl\u00e9: On Synthesis of Program Analyzers . In Computer Aided Verification, Swarat Chaudhuri and Azadeh Farzan (Eds.). Springer International Publishing , Cham , 422\u2013430. Herbert Jordan, Bernhard Scholz, and Pavle Suboti\u0107. 2016. Souffl\u00e9: On Synthesis of Program Analyzers. In Computer Aided Verification, Swarat Chaudhuri and Azadeh Farzan (Eds.). Springer International Publishing, Cham, 422\u2013430."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236767"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07151-0_6"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000038"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009880"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199528"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814275"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187671.2187672"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159803.1159807"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90091-1"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90006-X"},{"key":"e_1_2_2_54_1","volume-title":"Two-level Functional Languages","author":"Nielson Flemming","unstructured":"Flemming Nielson and Hanne Riis Nielson . 1992. Two-level Functional Languages . Cambridge University Press , New York, NY, USA . Flemming Nielson and Hanne Riis Nielson. 1992. Two-level Functional Languages. Cambridge University Press, New York, NY, USA."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3136040.3136060"},{"key":"e_1_2_2_56_1","unstructured":"Erik Osheim. 2019. Kind Projector. https:\/\/github.com\/non\/kind-projector .  Erik Osheim. 2019. Kind Projector. https:\/\/github.com\/non\/kind-projector ."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159888"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30936-1_17"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784760"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868294.1868314"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594316"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.129.7"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2491979"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/331960.331975"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/636517.636528"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.54007"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/115865.115884"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158143"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009885"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000014"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2584665"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517208.2517220"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/258993.259019"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196893"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SNAPL.2017.18"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411243"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(2:3)2011"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/143165.143169"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236800"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110273"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360552","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360552","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360552","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:58Z","timestamp":1750202578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360552"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,10]]},"references-count":79,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2019,10,10]]}},"alternative-id":["10.1145\/3360552"],"URL":"https:\/\/doi.org\/10.1145\/3360552","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,10]]},"assertion":[{"value":"2019-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}