{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:43:21Z","timestamp":1780994601802,"version":"3.54.1"},"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 (\n            <jats:italic toggle=\"yes\">e.g.<\/jats:italic>\n            , 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_2_2_1_1","unstructured":"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_2_2_2_1","unstructured":"Michael D. Adams. 2011. Flow-sensitive control-flow analysis in linear-log time. Ph. D. Dissertation. USA. isbn:9781267077776 AAI3488016"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746325.2746327"},{"key":"e_1_2_2_4_1","volume-title":"Compiling with Continuations","author":"Appel Andrew W.","unstructured":"Andrew W. Appel. 1992. Compiling with Continuations. Cambridge University Press, USA. isbn:9780511609619"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129502003845"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/258949.258953"},{"key":"e_1_2_2_7_1","volume-title":"Implementation and Application of Functional Languages, Clemens Grelck, Frank Huch, Greg J","author":"Benton Nick","year":"2038","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. isbn:978-3-540-32038-8"},{"key":"e_1_2_2_8_1","volume-title":"21st International Symposia on Implementation and Application of Functional Languages (IFL 2009)","volume":"106","author":"Bergstrom Lars","year":"2009","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."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591260"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46425-5_4"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3462172.3462193"},{"key":"e_1_2_2_12_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2033","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. isbn:0262033844","edition":"3"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268965"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","unstructured":"Allyn Dimock Ian Westmacott Robert Muller Franklyn Turbak and J. B. Wells. 2001. Functioning without closure: type-safe customized function representations for standard ML. SIGPLAN Not. 36 10 (2001) oct 14\u201325. issn:0362-1340 https:\/\/doi.org\/10.1145\/507669.507640 10.1145\/507669.507640","DOI":"10.1145\/507669.507640"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/317636.317800"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632919"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007175"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837631"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092703.3092719"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/258915.258939"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3546189.3549918"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_2_2_23_1","unstructured":"Fredrik Kjolstad Danny Dig Gabriel Acevedo and Marc Snir. 2010. Refactoring for Immutability. https:\/\/api.semanticscholar.org\/CorpusID:11471932"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3473579"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237791"},{"key":"e_1_2_2_26_1","volume-title":"Advanced Compiler Design Implementation","author":"Muchnick S.","unstructured":"S. Muchnick. 1997. Advanced Compiler Design Implementation. Morgan Kaufmann Publishers, San Francisco, CA, USA. isbn:9781558603202 lccn:97013063"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/210184.210187"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3473591"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796802004331"},{"key":"e_1_2_2_30_1","first-page":"04","article-title":"Playing by the Rules: Rewriting as a practical optimisation technique in GHC","volume":"2001","author":"Jones Simon Peyton","year":"2001","unstructured":"Simon Peyton Jones, Andrew Tolmach, and Tony Hoare. 2001. Playing by the Rules: Rewriting as a practical optimisation technique in GHC. Haskell 2001, 04.","journal-title":"Haskell"},{"key":"e_1_2_2_31_1","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_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547645"},{"key":"e_1_2_2_33_1","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\". https:\/\/doi.org\/10.5281\/zenodo.15050194 10.5281\/zenodo.15050194","DOI":"10.5281\/zenodo.15050194"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3674650"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010027404223"},{"key":"e_1_2_2_36_1","unstructured":"Bratin Saha Nevin Heintze and Dino Oliva. 1998. Subtransitive CFA using types. oct isbn:Technical report YALEU\/DCS\/TR-1166"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796814000045"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/315891.315934"},{"key":"e_1_2_2_39_1","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_2_2_40_1","volume-title":"Proceedings of the Workshop on Static Analysis of Equational, Functional and Logic Programs (JTASPEFL\u201991)","volume":"201","author":"Shivers Olin","year":"1991","unstructured":"Olin Shivers. 1991. Useless-variable elimination. In Proceedings of the Workshop on Static Analysis of Equational, Functional and Logic Programs (JTASPEFL\u201991), Michel Billaud, Pierre Cast\u00e9ran, Marc-Michel Corsini, Kandina Musumbu, and Antoine Rauzy (Eds.) (Bigre, Vol. 74). Atelier Irisa, IRISA Campus de Beaulieu, Laboratoire Bordelais de Recherche en Informatique. 197\u2013201."},{"key":"e_1_2_2_41_1","volume-title":"Bottom-Up \u03b2 -Reduction: Uplinks and \u03bb -DAGs","author":"Shivers Olin","year":"1987","unstructured":"Olin Shivers and Mitchell Wand. 2005. Bottom-Up \u03b2 -Reduction: Uplinks and \u03bb -DAGs. In Programming Languages and Systems, Mooly Sagiv (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 217\u2013232. isbn:978-3-540-31987-0"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/239912.239915"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454044"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/989393.989449"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961204.1961205"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","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":[[2025,7,16]],"date-time":"2025-07-16T06:06:32Z","timestamp":1752645992000},"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"}}]}}