{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:43:15Z","timestamp":1780994595339,"version":"3.54.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2212537, 2212538"],"award-info":[{"award-number":["2212537, 2212538"]}],"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,8,5]]},"abstract":"<jats:p>\n            The representation of functions in higher-order languages includes both the function\u2019s code and an\n            <jats:italic toggle=\"yes\">environment<\/jats:italic>\n            structure that captures the bindings of the function\u2019s free variables. This paper explores caller-provided environments, where instead of\n            <jats:italic toggle=\"yes\">packaging<\/jats:italic>\n            the entirety of a function\u2019s environment in its closure, a function can be\n            <jats:italic toggle=\"yes\">provided<\/jats:italic>\n            with a portion of its environment by its caller. In higher-order languages, it is difficult to determine where functions are called, let alone what pieces of the function\u2019s environment are available to be provided by the caller, thus we need a higher-order control-flow analysis to enable caller-provided environments.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we present a new abstract-interpretation-based analysis that discovers which pieces of a function\u2019s environment are always shared between its definition and its callers. In such cases, the caller can provide the environment to the callee. Our analysis has been formalized in the Rocq proof assistant. We evaluate our analysis on a collection of programs demonstrating that it is both scalable and provides significantly better information over the common syntactic approach and better information than\n            <jats:italic toggle=\"yes\">lightweight closure conversion<\/jats:italic>\n            . In fact, it yields the theoretical upper-bound for many programs.\n          <\/jats:p>\n          <jats:p>For caller-provided environments, deciding how to transform the program based on these revealed facts is also non-trivial and has the potential to incur extra runtime cost over standard strategies. We discuss how to make these decisions in a way that avoids the extra costs and how to transform a program accordingly. We also propose other uses of the analysis results beyond enabling caller-provided environments. We evaluate our transformation using an instrumented interpreter, showing that our approach is effective in reducing dynamic allocations for environments.<\/jats:p>","DOI":"10.1145\/3747516","type":"journal-article","created":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T16:56:02Z","timestamp":1754412962000},"page":"341-370","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Environment-Sharing Analysis and Caller-Provided Environments for Higher-Order Languages"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-7254-9607","authenticated-orcid":false,"given":"J. A.","family":"Carr","sequence":"first","affiliation":[{"name":"University of Chicago, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6922-9706","authenticated-orcid":false,"given":"Benjamin","family":"Quiring","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park, 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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9182-0084","authenticated-orcid":false,"given":"Skye","family":"Soss","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8671-3547","authenticated-orcid":false,"given":"Byron","family":"Zhong","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,8,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"3CPS. 2025. Artifact for \u201cEnvironment-Sharing Analysis and Caller-Provided Environments for Higher-Order Languages\u201d. https:\/\/doi.org\/10.5281\/zenodo.15708994 10.5281\/zenodo.15708994","DOI":"10.5281\/zenodo.15708994"},{"key":"e_1_2_1_2_1","volume-title":"Compiling with Continuations","author":"Appel Andrew W.","unstructured":"Andrew W. Appel. 1992. Compiling with Continuations. Cambridge University Press, Cambridge, England, UK."},{"key":"e_1_2_1_3_1","volume-title":"Jim","author":"Appel Andrew W.","year":"1988","unstructured":"Andrew W. Appel and Trevor T.Y. Jim. 1988. Optimizing Closure Environment Representations. Department of Computer Science, Princeton University. https:\/\/www.cs.princeton.edu\/research\/techreps\/TR-168-88"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01807505"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628153"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591260"},{"key":"e_1_2_1_7_1","unstructured":"Luca Cardelli. 1983. The Functional Abstract Machine. AT&T Bell Laboratories. Available at http:\/\/lucacardelli.name\/Papers\/FAM.pdf"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46425-5_4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500001535"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110256"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386232"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/507635.507640"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2364527.2364576"},{"key":"e_1_2_1_15_1","unstructured":"2021. JSON in Elm. Accessed: 2024-07-11"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41582-1_8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3473601"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796818000138"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837631"},{"key":"e_1_2_1_20_1","unstructured":"Sebastian Graf and Simon Peyton Jones. 2019. Selective Lambda Lifting. arxiv:1910.11717. arxiv:1910.11717"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001891"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468111"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268973"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502880"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661103.2661106"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/13310.13333"},{"key":"e_1_2_1_27_1","volume-title":"ORBIT: An Optimizing Compiler for Scheme. Ph. D. Dissertation. Computer Science Department","author":"Kranz David A.","year":"1988","unstructured":"David A. Kranz. 1988. ORBIT: An Optimizing Compiler for Scheme. Ph. D. Dissertation. Computer Science Department, Yale University. New Haven, Connecticut. Research Report 632"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/6.4.308"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11319-2_20"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-93900-9_22"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.031"},{"key":"e_1_2_1_32_1","volume-title":"Advanced Compiler Design and Implementation. Morgan Kaufmann","author":"Muchnick Steven","unstructured":"Steven Muchnick. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA, USA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(90)90017-J"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-006-8611-7"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544885.3544889"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547645"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3674650"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3729280"},{"key":"e_1_2_1_39_1","volume-title":"Implementation: The Translation and Use of Algol 60 Programs on a Computer","author":"Randell B.","year":"1964","unstructured":"B. Randell and L. J. Russell. 1964. Algol 60 Implementation: The Translation and Use of Algol 60 Programs on a Computer. Academic Press, London and New York."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/315891.315934"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345125"},{"key":"e_1_2_1_42_1","unstructured":"Peter Shirley. 2020. Ray Tracing in One Weekend. https:\/\/raytracing.github.io"},{"key":"e_1_2_1_43_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_1_44_1","volume-title":"Flow-Directed Lightweight Closure Conversion","author":"Siskind Jeffrey M.","unstructured":"Jeffrey M. Siskind. 1999. Flow-Directed Lightweight Closure Conversion. NEC Research Institute, Princeton, New Jersey."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/239912.239915"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796898003086"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2017.07.007"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863553"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(2:3)2011"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236800"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3747516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T16:57:06Z","timestamp":1754413026000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3747516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,5]]},"references-count":50,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2025,8,5]]}},"alternative-id":["10.1145\/3747516"],"URL":"https:\/\/doi.org\/10.1145\/3747516","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,5]]},"assertion":[{"value":"2025-02-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}