{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:05:48Z","timestamp":1784199948222,"version":"3.55.0"},"reference-count":46,"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":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["212537 and 221253"],"award-info":[{"award-number":["212537 and 221253"]}],"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>\n                    We define\n                    <jats:italic toggle=\"yes\">webs<\/jats:italic>\n                    to be the collections of producers and consumers (\n                    <jats:italic toggle=\"yes\">e.g<\/jats:italic>\n                    ., functions and calls) in a program that are constrained: in higher-order languages, multiple functions can flow to the same call, all of which must agree on an interface (e.g., calling convention). We argue that webs are fundamentally the\n                    <jats:italic toggle=\"yes\">unit of transformation<\/jats:italic>\n                    : a change to one member requires changes across the entire web. We introduce a web-centric intermediate language that exposes webs as annotations, and describe web-based (that is, flow-directed) transformations guided by these annotations. As they affect all members of a web, these transformations are interprocedural, operating over entire modules. Through the lens of webs we reframe and generalize a collection of transformations from the literature, including dead-parameter elimination, uncurrying, and defunctionalization, as well as describe novel transformations. We contrast this approach with rewriting strategies that rely on inlining and cascading rewrites.\n                  <\/jats:p>\n                  <jats:p>\n                    Webs are an over-approximation of the semantic function-call relationship produced by control-flow analyses (CFA). This information is inherently independent from the transformations; more precise analyses permit more transformations. A limitation of precise analyses is that the transformations may not maintain well-typedness, as the type system is a less-precise static analysis. Our solution is a simple and lightweight typed-based analysis that causes the flow-directed transformations to preserve well-typedness, making flow-directed, type-preserving transformations easily accessible in many compilers. This analysis builds on unification, distinguishing types that\n                    <jats:italic toggle=\"yes\">look<\/jats:italic>\n                    the same from types that have to\n                    <jats:italic toggle=\"yes\">be<\/jats:italic>\n                    the same. Our experiments show that while our analysis is theoretically less precise, in practice its precision is similar to CFAs.\n                  <\/jats:p>","DOI":"10.1145\/3729280","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"748-772","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Webs and Flow-Directed Well-Typedness Preserving Program Transformations"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6922-9706","authenticated-orcid":false,"given":"Benjamin","family":"Quiring","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9201-6864","authenticated-orcid":false,"given":"David","family":"Van Horn","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5881-298X","authenticated-orcid":false,"given":"John","family":"Reppy","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8171-386X","authenticated-orcid":false,"given":"Olin","family":"Shivers","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"GHC Team. 2024. GHC user guide: Controlling inlining via optimisation flags. https:\/\/downloads.haskell.org\/ghc\/9.10-latest\/docs\/users_guide\/hints.html#controlling-inlining-via-optimisation-flags Accessed: 2024-11-14."},{"key":"e_1_3_2_3_2","unstructured":"Michael D. Adams. 2011. Flow-sensitive control-flow analysis in linear-log time. Ph.D. Dissertation. USA. Advisor(s) Dybvig R. Kent. AAI3488016."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","unstructured":"Connor Adsit and Matthew Fluet. 2014. An Efficient Type- and Control-Flow Analysis for System F. In Proceedings of the 26nd 2014 International Symposium on Implementation and Application of Functional Languages (IFL \u203214) (Boston MA USA). Association for Computing Machinery New York NY USA Article 3 14 pages. https:\/\/doi.org\/10.1145\/2746325.2746327 10.1145\/2746325.2746327","DOI":"10.1145\/2746325.2746327"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Andrew W. Appel. 1992. Compiling with Continuations. Cambridge University Press USA.","DOI":"10.1017\/CBO9780511609619"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129502003845"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/258949.258953"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","unstructured":"Nick Benton Andrew Kennedy Sam Lindley and Claudio Russo. 2005. Shrinking Reductions in SML.NET. In Implementation and Application of Functional Languages Clemens Grelck Frank Huch Greg J. Michaelson and Phil Trinder (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 142\u2013159.","DOI":"10.1007\/11431664_9"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Lars Bergstrom and John Reppy. 2009. Arity Raising in Manticore. In 21st International Symposia on Implementation and Application of Functional Languages (IFL 2009) (Lecture Notes in Computer Science Vol. 6041). Springer-Verlag New York NY 90\u2013106.","DOI":"10.1007\/978-3-642-16478-1_6"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591260"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","unstructured":"Henry Cejtin Suresh Jagannathan and Stephen Weeks. 2000. Flow-Directed Closure Conversion for Typed Languages. In Programming Languages and Systems Gert Smolka (Ed.). Springer Berlin Heidelberg Berlin Heidelberg 56\u201371.","DOI":"10.1007\/3-540-46425-5_4"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","unstructured":"Maheen Riaz Contractor and Matthew Fluet. 2021. Type- and Control-Flow Directed Defunctionalization. In Proceedings of the 32nd Symposium on Implementation and Application of Functional Languages (IFL \u203220) (Canterbury United Kingdom). Association for Computing Machinery New York NY USA 79\u201392. https:\/\/doi.org\/10.1145\/3462172.3462193 10.1145\/3462172.3462193","DOI":"10.1145\/3462172.3462193"},{"key":"e_1_3_2_13_2","unstructured":"Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2009. Introduction to Algorithms Third Edition (3rd ed.). The MIT Press."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","unstructured":"Greg DeFouw David Grove and Craig Chambers. 1998. Fast interprocedural class analysis. In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL \u203298) (San Diego California USA). Association for Computing Machinery New York NY USA 222\u2013236. https:\/\/doi.org\/10.1145\/268946.268965 10.1145\/268946.268965","DOI":"10.1145\/268946.268965"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/507669.507640"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","unstructured":"Martin Elsman. 1999. Static interpretation of modules. In Proceedings of the Fourth ACM SIGPLAN International Conference on Functional Programming (ICFP \u203299) (Paris France). Association for Computing Machinery New York NY USA 208\u2013219. https:\/\/doi.org\/10.1145\/317636.317800 10.1145\/317636.317800","DOI":"10.1145\/317636.317800"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632919"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007175"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","unstructured":"Thomas Gilray Steven Lyde Michael D. Adams Matthew Might and David Van Horn. 2016. Pushdown control-flow analysis for free. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL \u203216) (St. Petersburg FL USA). Association for Computing Machinery New York NY USA 691\u2013704. https:\/\/doi.org\/10.1145\/2837614.2837631 10.1145\/2837614.2837631","DOI":"10.1145\/2837614.2837631"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Alex Gyori Shuvendu K. Lahiri and Nimrod Partush. 2017. Refining interprocedural change-impact analysis using equivalence relations. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2017) (Santa Barbara CA USA). Association for Computing Machinery New York NY USA 318\u2013328. https:\/\/doi.org\/10.1145\/3092703.3092719 10.1145\/3092703.3092719","DOI":"10.1145\/3092703.3092719"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","unstructured":"Nevin Heintze and David McAllester. 1997. Linear-time subtransitive control flow analysis. In Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (PLDI \u203297) (Las Vegas Nevada USA). Association for Computing Machinery New York NY USA 261\u2013272. https:\/\/doi.org\/10.1145\/258915.258939 10.1145\/258915.258939","DOI":"10.1145\/258915.258939"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","unstructured":"Celeste Hollenbeck Michael F. P. O\u2032Boyle and Michel Steuwer. 2022. Investigating magic numbers: improving the inlining heuristic in the Glasgow Haskell Compiler. In Proceedings of the 15th ACM SIGPLAN International Haskell Symposium (Haskell 2022) (Ljubljana Slovenia). Association for Computing Machinery New York NY USA 81\u201394. https:\/\/doi.org\/10.1145\/3546189.3549918 10.1145\/3546189.3549918","DOI":"10.1145\/3546189.3549918"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Bruce M. Kapron Valerie King and Ben Mountjoy. 2013. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 1131\u20131142. https:\/\/doi.org\/10.1137\/1.9781611973105.81 10.1137\/1.9781611973105.81","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_24_2","unstructured":"Fredrik Kjolstad Danny Dig Gabriel Acevedo and Marc Snir. 2010. Refactoring for Immutability. https:\/\/api.semanticscholar.org\/CorpusID:11471932"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3473579"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","unstructured":"Yasuhiko Minamide Greg Morrisett and Robert Harper. 1996. Typed closure conversion. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL \u203296) (St. Petersburg Beach Florida USA). Association for Computing Machinery New York NY USA 271\u2013283. https:\/\/doi.org\/10.1145\/237721.237791 10.1145\/237721.237791","DOI":"10.1145\/237721.237791"},{"key":"e_1_3_2_27_2","unstructured":"S. Muchnick. 1997. Advanced Compiler Design Implementation. Morgan Kaufmann Publishers San Francisco CA USA."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/210184.210187"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3473591"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796802004331"},{"key":"e_1_3_2_31_2","unstructured":"Simon PeytonJones Andrew Tolmach and Tony Hoare. 2001. Playing by the Rules: Rewriting as a practical optimisation technique in GHC. Haskell 2001 (04 2001)."},{"key":"e_1_3_2_32_2","unstructured":"Matthew Pickering. 2023. Interface Files with Core Definitions. https:\/\/well-typed.com\/blog\/2023\/02\/interface-files-with-core\/ Accessed: 2024-11-14."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3547645"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","unstructured":"Benjamin Quiring John Reppy Olin Shivers Skye Soss Byron Zhong J. Carr and Lingxiao Zheng. 2025. Artifact for \"Webs and Flow-directed Well-Typedness Preserving Program Transformations\". doi:10.5281\/zenodo.15050194 10.5281\/zenodo.15050194","DOI":"10.5281\/zenodo.15050194"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3674650"},{"key":"e_1_3_2_36_2","first-page":"363","article-title":"Definitional Interpreters for Higher-Order Programming Languages","author":"Reynolds John C.","year":"1972","unstructured":"John C. Reynolds. 1972. Definitional Interpreters for Higher-Order Programming Languages. Higher-Order and Symbolic Computation(1972), 363\u2013397. https:\/\/api.semanticscholar.org\/CorpusID:163294","journal-title":"Higher-Order and Symbolic Computation"},{"key":"e_1_3_2_37_2","unstructured":"Bratin Saha Nevin Heintze and Dino Oliva. 1998. Subtransitive CFA using types (oct 1998)."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796814000045"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","unstructured":"Manuel Serrano. 1995. Control Flow Analysis: A Functional Languages Compilation Paradigm. In Proceedings of the 1995 ACM Symposium on Applied Computing (SAC \u203295) (Nashville Tennessee USA). ACM New York NY USA 118\u2013122. https:\/\/doi.org\/10.1145\/315891.315934 10.1145\/315891.315934","DOI":"10.1145\/315891.315934"},{"key":"e_1_3_2_40_2","unstructured":"Olin Shivers. 1991. Control-Flow Analysis of Higher-Order Languages or Taming Lambda. Ph.D. Dissertation. School of Computer Science Carnegie Mellon University Pittsburgh Pennsylvania. Technical Report CMU-CS-91-145."},{"key":"e_1_3_2_41_2","unstructured":"Olin Shivers. 1991. Useless-variable elimination. In Proceedings of the Workshop on Static Analysis of Equational Functional and Logic Programs (JTASPEFL\u203291) (Bigre Vol. 74) Michel Billaud Pierre Cast\u00e9ran Marc-Michel Corsini Kandina Musumbu and Antoine Rauzy (Eds.). Atelier Irisa IRISA Campus de Beaulieu Laboratoire Bordelais de Recherche en Informatique 197\u2013201."},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","unstructured":"Olin Shivers and Mitchell Wand. 2005. Bottom-Up \u03b2-Reduction: Uplinks and ?-DAGs. In Programming Languages and Systems Mooly Sagiv (Ed.). Springer Berlin Heidelberg Berlin Heidelberg 217\u2013232.","DOI":"10.1007\/978-3-540-31987-0_16"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/239912.239915"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","unstructured":"Benno Stein Bor-Yuh Evan Chang and Manu Sridharan. 2021. Demanded Abstract Interpretation. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021) (Virtual Canada). Association for Computing Machinery New York NY USA 282\u2013295. https:\/\/doi.org\/10.1145\/3453483.3454044 10.1145\/3453483.3454044","DOI":"10.1145\/3453483.3454044"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/989393.989449"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1961204.1961205"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","unstructured":"Frank Tip Adam Kiezun and Dirk B\u00e4umer. 2003. Refactoring for generalization using type constraints. In Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programing Systems Languages and Applications (OOPSLA \u203203) (Anaheim California USA). Association for Computing Machinery New York NY USA 13\u201326. https:\/\/doi.org\/10.1145\/949305.949308 10.1145\/949305.949308","DOI":"10.1145\/949305.949308"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729280","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:06:35Z","timestamp":1784196395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":46,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729280"],"URL":"https:\/\/doi.org\/10.1145\/3729280","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"}}]}}