{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T03:59:57Z","timestamp":1790740797046,"version":"4.1.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["270449797"],"award-info":[{"award-number":["270449797"]}],"id":[{"id":"10.13039\/501100001659","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":[[2018,7,30]]},"abstract":"<jats:p>\n            Abstract interpretation is a technique for developing static analyses. Yet, proving abstract interpreters sound is challenging for interesting analyses, because of the high\n            <jats:italic>proof complexity<\/jats:italic>\n            and\n            <jats:italic>proof effort<\/jats:italic>\n            . To reduce complexity and effort, we propose a framework for abstract interpreters that makes their soundness proof compositional. Key to our approach is to capture the similarities between concrete and abstract interpreters in a single shared interpreter, parameterized over an arrow-based interface. In our framework, a soundness proof is reduced to proving reusable soundness lemmas over the concrete and abstract instances of this interface; the soundness of the overall interpreters follows from a generic theorem.\n          <\/jats:p>\n          <jats:p>\n            To further reduce proof effort, we explore the relationship between soundness and parametricity. Parametricity not only provides us with useful guidelines for how to design non-leaky interfaces for shared interpreters, but also provides us soundness of shared pure functions as\n            <jats:italic>free theorems<\/jats:italic>\n            . We implemented our framework in Haskell and developed a\n            <jats:italic>k<\/jats:italic>\n            -CFA analysis for PCF and a tree-shape analysis for Stratego. We were able to prove both analyses sound compositionally with manageable complexity and effort, compared to a conventional soundness proof.\n          <\/jats:p>","DOI":"10.1145\/3236767","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Compositional soundness proofs of abstract interpreters"],"prefix":"10.1145","volume":"2","author":[{"given":"Sven","family":"Keidel","sequence":"first","affiliation":[{"name":"Delft University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Casper Bach","family":"Poulsen","sequence":"additional","affiliation":[{"name":"Delft University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Erdweg","sequence":"additional","affiliation":[{"name":"Delft University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"26th International Workshop\/21st Annual Conference of the EACSL, CSL 2012","author":"Atkey Robert","year":"2012","unstructured":"Robert Atkey . 2012 . Relational Parametricity for Higher Kinds. In Computer Science Logic (CSL\u201912) - 26th International Workshop\/21st Annual Conference of the EACSL, CSL 2012 , September 3-6, 2012, Fontainebleau, France. 46\u201361. Robert Atkey. 2012. Relational Parametricity for Higher Kinds. In Computer Science Logic (CSL\u201912) - 26th International Workshop\/21st Annual Conference of the EACSL, CSL 2012, September 3-6, 2012, Fontainebleau, France. 46\u201361."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190221"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the Domain-Specific Aspect Languages Workshop.","author":"Bagge Anya Helene","year":"2006","unstructured":"Anya Helene Bagge and Karl Trygve Kalleberg . 2006 . DSAL= library+ notation: Program transformation for domain-specific aspect languages . In Proceedings of the Domain-Specific Aspect Languages Workshop. Anya Helene Bagge and Karl Trygve Kalleberg. 2006. DSAL= library+ notation: Program transformation for domain-specific aspect languages. In Proceedings of the Domain-Specific Aspect Languages Workshop."},{"key":"e_1_2_2_4_1","first-page":"1","article-title":"Program Transformation with Scoped Dynamic Rewrite Rules","volume":"69","author":"Bravenboer Martin","year":"2006","unstructured":"Martin Bravenboer , Arthur van Dam , Karina Olmos , and Eelco Visser . 2006 . Program Transformation with Scoped Dynamic Rewrite Rules . Fundam. Inform. 69 , 1 - 2 (2006), 123\u2013178. Martin Bravenboer, Arthur van Dam, Karina Olmos, and Eelco Visser. 2006. Program Transformation with Scoped Dynamic Rewrite Rules. Fundam. Inform. 69, 1-2 (2006), 123\u2013178.","journal-title":"Fundam. Inform."},{"key":"e_1_2_2_5_1","volume-title":"COLOG-88, Per Martin-L\u00f6f and Grigori Mints (Eds.). LNCS","author":"Coquand Thierry","unstructured":"Thierry Coquand and Christine Paulin-Mohring . 1990. Inductively defined types . In COLOG-88, Per Martin-L\u00f6f and Grigori Mints (Eds.). LNCS , Vol. 417 . Springer , 50\u201366. Thierry Coquand and Christine Paulin-Mohring. 1990. Inductively defined types. In COLOG-88, Per Martin-L\u00f6f and Grigori Mints (Eds.). LNCS, Vol. 417. Springer, 50\u201366."},{"key":"e_1_2_2_6_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_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/567752.567778"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/2.4.511"},{"key":"e_1_2_2_9_1","volume-title":"11th Asian Computing Science Conference","author":"Cousot Patrick","year":"2006","unstructured":"Patrick Cousot , Radhia Cousot , J\u00e9r\u00f4me Feret , Laurent Mauborgne , Antoine Min\u00e9 , David Monniaux , and Xavier Rival . 2006 . Combination of Abstractions in the ASTR\u00c9E Static Analyzer. In Advances in Computer Science - ASIAN 2006. Secure Software and Related Issues , 11th Asian Computing Science Conference , Tokyo, Japan , December 6-8, 2006, Revised Selected Papers. 272\u2013300. Patrick Cousot, Radhia Cousot, J\u00e9r\u00f4me Feret, Laurent Mauborgne, Antoine Min\u00e9, David Monniaux, and Xavier Rival. 2006. Combination of Abstractions in the ASTR\u00c9E Static Analyzer. In Advances in Computer Science - ASIAN 2006. Secure Software and Related Issues, 11th Asian Computing Science Conference, Tokyo, Japan, December 6-8, 2006, Revised Selected Papers. 272\u2013300."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110256"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814308"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2427048.2427050"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80427-4"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1988783.1988787"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048099"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2015.12.011"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/227699.227700"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2036918.2036927"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863553"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(99)00023-4"},{"key":"e_1_2_2_22_1","volume-title":"Abstract interpretation: a semantics-based tool for program analysis. Handbook of logic in computer science 4","author":"Jones N","year":"1994","unstructured":"N Jones and Flemming Nielson . 1994. Abstract interpretation: a semantics-based tool for program analysis. Handbook of logic in computer science 4 ( 1994 ), 527\u2013636. N Jones and Flemming Nielson. 1994. Abstract interpretation: a semantics-based tool for program analysis. Handbook of logic in computer science 4 (1994), 527\u2013636."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3141517.3141855"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199528"},{"key":"e_1_2_2_25_1","volume-title":"Categories for the Working Mathematician","author":"Lane Saunders Mac","unstructured":"Saunders Mac Lane . 1978. Categories for the Working Mathematician . Springer New York . Saunders Mac Lane. 1978. Categories for the Working Mathematician. Springer New York."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187671.2187672"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_2_2_28_1","volume-title":"Hanne Riis Nielson, and Chris Hankin","author":"Nielson Flemming","year":"1999","unstructured":"Flemming Nielson , Hanne Riis Nielson, and Chris Hankin . 1999 . Principles of program analysis. Springer . Flemming Nielson, Hanne Riis Nielson, and Chris Hankin. 1999. Principles of program analysis. Springer."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/507635.507664"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"e_1_2_2_31_1","volume-title":"Lambda-definability in the full type hierarchy. To HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism","author":"Plotkin Gordon D","year":"1980","unstructured":"Gordon D Plotkin . 1980. Lambda-definability in the full type hierarchy. To HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism ( 1980 ), 363\u2013373. Gordon D Plotkin. 1980. Lambda-definability in the full type hierarchy. To HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism (1980), 363\u2013373."},{"key":"e_1_2_2_32_1","volume-title":"Abstraction and Parametric Polymorphism. In IFIP Congress. 513\u2013523","author":"Reynolds John C.","year":"1983","unstructured":"John C. Reynolds . 1983 . Types , Abstraction and Parametric Polymorphism. In IFIP Congress. 513\u2013523 . John C. Reynolds. 1983. Types, Abstraction and Parametric Polymorphism. In IFIP Congress. 513\u2013523."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010027404223"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2491979"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814189.2817270"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88643-3_7"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/289423.289425"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99404"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/647698.734146"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236767","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236767","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:28Z","timestamp":1750282888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236767"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":38,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236767"],"URL":"https:\/\/doi.org\/10.1145\/3236767","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}