{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T11:23:37Z","timestamp":1770290617845,"version":"3.49.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T00:00:00Z","timestamp":1661731200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,8,29]]},"abstract":"<jats:p>\n            To date, the most effective approach to compiling strict, higher-order functional languages (such as OCaml, Scheme, and SML) has been to use whole-program techniques to convert the program to a first-order monomorphic representation that can be optimized using traditional compilation techniques. This approach, popularized by MLton, has limitations, however. We are interested in exploring a different approach to compiling such languages, one that preserves the higher-order and polymorphic character of the program throughout optimization. To enable such an approach, we must have effective analyses that both provide precise information about higher-order programs and that scale to larger units of compilation. This paper describes one such analysis for determining the\n            <jats:italic>extent<\/jats:italic>\n            of variable bindings. We classify the extent of variables as either\n            <jats:italic>register<\/jats:italic>\n            (only one binding instance can be live at any time),\n            <jats:italic>stack<\/jats:italic>\n            (the lifetimes of binding instances obey a LIFO order), or\n            <jats:italic>heap<\/jats:italic>\n            (binding lifetimes are arbitrary). These extents naturally connect variables to the machine resources required to represent them. We believe that precise information about binding extents will enable efficient management of environments, which is a key problem in the efficient compilation of higher-order programs.\n          <\/jats:p>\n          <jats:p>At the core of the paper is the 3CPS intermediate representation, which is a factored CPS-based intermediate representation (IR) that statically marks variables to indicate their binding extent. We formally specify the management of this binding structure by means of a small-step operational semantics and define a static analysis that determines the extents of the variables in a program. We evaluate our analysis using a standard suite of SML benchmark programs. Our implementation gets surprisingly high yield and exhibits scalable performance. While this paper uses a CPS-based IR, the algorithm and results are easily transferable to other \u03bb-calculus IRs, such as ANF.<\/jats:p>","DOI":"10.1145\/3547645","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T19:39:26Z","timestamp":1661974766000},"page":"650-678","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Analyzing binding extent in 3CPS"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6922-9706","authenticated-orcid":false,"given":"Benjamin","family":"Quiring","sequence":"first","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5881-298X","authenticated-orcid":false,"given":"John","family":"Reppy","sequence":"additional","affiliation":[{"name":"University of Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8171-386X","authenticated-orcid":false,"given":"Olin","family":"Shivers","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"2007","unstructured":"Alfred V. Aho , Monica S. Lam , Ravi Sethi , and Jeffrey D . Ullman . 2007 . Compilers : Principles, Techniques and Tools (2nd ed.). Pearson, New York City, New York, USA. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2007. Compilers: Principles, Techniques and Tools (2nd ed.). Pearson, New York City, New York, USA."},{"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 . 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 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.1145\/268946.268949"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/800055.802037"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46425-5_4"},{"key":"e_1_2_1_7_1","volume-title":"Hansen","author":"Clinger William D.","year":"2017","unstructured":"William D. Clinger and Lars T . Hansen . 2017 . The Larceny Project . http:\/\/www.larcenists.org William D. Clinger and Lars T. Hansen. 2017. The Larceny Project. http:\/\/www.larcenists.org"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341643"},{"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\/155090.155113"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837631"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001891"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796814000100"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291179"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/12276.13333"},{"key":"e_1_2_1_17_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 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_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/507635.507641"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062380"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.031"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60360-3_44"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143125"},{"key":"e_1_2_1_23_1","volume-title":"33rd Symposium on Implementation and Application of Functional Languages (IFL \u201921)","author":"Quiring Benjamin","year":"2021","unstructured":"Benjamin Quiring , John Reppy , and Olin Shivers . 2021 . 3CPS: The Design of an Environment-Focussed Intermediate Representation . In 33rd Symposium on Implementation and Application of Functional Languages (IFL \u201921) . Association for Computing Machinery, New York, NY, USA. 9 pages. https:\/\/doi.org\/10.1145\/3544885.3544889 10.1145\/3544885.3544889 Benjamin Quiring, John Reppy, and Olin Shivers. 2021. 3CPS: The Design of an Environment-Focussed Intermediate Representation. In 33rd Symposium on Implementation and Application of Functional Languages (IFL \u201921). Association for Computing Machinery, New York, NY, USA. 9 pages. https:\/\/doi.org\/10.1145\/3544885.3544889"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800194.805852"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/315891.315934"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/232627.232635"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345125"},{"key":"e_1_2_1_28_1","unstructured":"Peter Shirley. 2020. Ray Tracing in One Weekend. https:\/\/raytracing.github.io \t\t\t\t  Peter Shirley. 2020. Ray Tracing in One Weekend. https:\/\/raytracing.github.io"},{"key":"e_1_2_1_30_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 . Jeffrey M. Siskind. 1999. Flow-Directed Lightweight Closure Conversion. NEC Research Institute, Princeton, New Jersey."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796898003086"},{"key":"e_1_2_1_32_1","volume-title":"CFA2: Pushdown Flow Analysis for Higher-Order Languages. Ph. D. Dissertation","author":"Vardoulakis Dimitrios","unstructured":"Dimitrios Vardoulakis . 2012. CFA2: Pushdown Flow Analysis for Higher-Order Languages. Ph. D. Dissertation . Northeastern University . Boston, MA, USA. Dimitrios Vardoulakis. 2012. CFA2: Pushdown Flow Analysis for Higher-Order Languages. Ph. D. Dissertation. Northeastern University. Boston, MA, USA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(2:3)2011"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159877"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547645","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3547645","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:43:29Z","timestamp":1750272209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547645"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,29]]},"references-count":33,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2022,8,29]]}},"alternative-id":["10.1145\/3547645"],"URL":"https:\/\/doi.org\/10.1145\/3547645","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,29]]},"assertion":[{"value":"2022-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}