{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T05:46:50Z","timestamp":1784180810281,"version":"3.55.0"},"reference-count":48,"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>The recently introduced _Perceus_ algorithm can automatically insert  \nreference count instructions such that the resulting (cycle-free) program is  \n_garbage free_: objects are freed at the very moment they can no longer be  \nreferenced. An important extension is reuse analysis. This optimization pairs  \nobjects of known size with fresh allocations of the same size and tries to  \nreuse the object in-place at runtime if it happens to be unique. Unfortunately,  \ncurrent implementations of reuse analysis are fragile with respect to small  \nprogram transformations, or can cause an arbitrary increase in the peak heap  \nusage. We present a novel _drop-guided_ reuse algorithm that is simpler and  \nmore robust than previous approaches. Moreover, we generalize the linear  \nresource calculus to precisely characterize garbage-free and frame-limited  \nevaluations. On each function call, a frame-limited evaluation may hold on to  \nmemory longer if the size is bounded by a constant factor. Using this framework  \nwe show that our drop-guided reuse _is_ frame-limited and find that an  \nimplementation of our new reuse approach in Koka can provide significant  \nspeedups.<\/jats:p>","DOI":"10.1145\/3547634","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T19:39:26Z","timestamp":1661974766000},"page":"357-380","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Reference counting with frame limited reuse"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3538-9688","authenticated-orcid":false,"given":"Anton","family":"Lorenzen","sequence":"first","affiliation":[{"name":"University of Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1027-5430","authenticated-orcid":false,"given":"Daan","family":"Leijen","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609619"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070109"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/359636.359713"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158093"},{"key":"e_1_2_1_5_1","unstructured":"Hans Boehm. 2000. GC bench. https:\/\/hboehm.info\/gc\/gc_bench \t\t\t\t  Hans Boehm. 2000. GC bench. https:\/\/hboehm.info\/gc\/gc_bench"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2021.9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001660"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243176.3243195"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/367487.367501"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/325694.325716"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85373-2_12"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158611"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40648-0_12"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155113"},{"key":"e_1_2_1_15_1","volume-title":"Silicon Graphics, and Hewlett\u2013Packard Company","author":"Foundation Free Software","year":"1994","unstructured":"Free Software Foundation , Silicon Graphics, and Hewlett\u2013Packard Company . 1994 . Internal red-black tree implemention for \u00dftl::map\". https:\/\/github.com\/gcc-mirror\/gcc\/tree\/master\/libstdc++-v3\/src\/c++98\/tree.cc Free Software Foundation, Silicon Graphics, and Hewlett\u2013Packard Company. 1994. Internal red-black tree implemention for \u00dftl::map\". https:\/\/github.com\/gcc-mirror\/gcc\/tree\/master\/libstdc++-v3\/src\/c++98\/tree.cc"},{"key":"e_1_2_1_16_1","unstructured":"Matt Gallagher. 2016. Reference Counted Releases in Swift. Dec. https:\/\/www.cocoawithlove.com\/blog\/resources-releases-reentrancy.html Blog post. \t\t\t\t  Matt Gallagher. 2016. Reference Counted Releases in Swift. Dec. https:\/\/www.cocoawithlove.com\/blog\/resources-releases-reentrancy.html Blog post."},{"key":"e_1_2_1_17_1","unstructured":"The Computer Language Benchmark Game. 2021. binarytrees. Nov. https:\/\/benchmarksgame-team.pages.debian.net\/benchmarksgame\/performance\/binarytrees.html \t\t\t\t  The Computer Language Benchmark Game. 2021. binarytrees. Nov. https:\/\/benchmarksgame-team.pages.debian.net\/benchmarksgame\/performance\/binarytrees.html"},{"key":"e_1_2_1_18_1","volume-title":"Implicit Memory Management for SAC. In 6th International Workshop on Implementation and Application of Functional Languages (IFL\u201904)","author":"Grelck Clemens","year":"2004","unstructured":"Clemens Grelck and Kai Trojahner . 2004 . Implicit Memory Management for SAC. In 6th International Workshop on Implementation and Application of Functional Languages (IFL\u201904) . Clemens Grelck and Kai Trojahner. 2004. Implicit Memory Management for SAC. In 6th International Workshop on Implementation and Application of Functional Languages (IFL\u201904)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/318593.318660"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796897002864"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.153.8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009872"},{"key":"e_1_2_1_24_1","unstructured":"Daan Leijen. 2021. The Koka Language. https:\/\/koka-lang.github.io \t\t\t\t  Daan Leijen. 2021. The Koka Language. https:\/\/koka-lang.github.io"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34175-6_13"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Anton Lorenzen and Daan Leijen. 2021. Reference Counting with Frame Limited Reuse (extended version). Microsoft Research. \t\t\t\t  Anton Lorenzen and Daan Leijen. 2021. Reference Counting with Frame Limited Reuse (extended version). Microsoft Research.","DOI":"10.1145\/3547634"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.6946310"},{"key":"e_1_2_1_28_1","unstructured":"Conor McBride. 2001. The Derivative of a Regular Type is its Type of One-Hole Contexts. http:\/\/strictlypositive.org\/diff.pdf (Extended Abstract). \t\t\t\t  Conor McBride. 2001. The Derivative of a Regular Type is its Type of One-Hole Contexts. http:\/\/strictlypositive.org\/diff.pdf (Extended Abstract)."},{"key":"e_1_2_1_29_1","first-page":"1","article-title":"SISAL: streams and iteration in a single-assignment language. Language reference manual","volume":"1","author":"McGraw J.","year":"1983","unstructured":"J. McGraw , S. Skedzielewski , S. Allan , D. Grit , R. Oldehoeft , J. Glauert , I. Dobes , and P. Hohensee . 1983 . SISAL: streams and iteration in a single-assignment language. Language reference manual , Version 1. 1 . Lawrence Livermore National Lab., CA, USA. J. McGraw, S. Skedzielewski, S. Allan, D. Grit, R. Oldehoeft, J. Glauert, I. Dobes, and P. Hohensee. 1983. SISAL: streams and iteration in a single-assignment language. Language reference manual, Version 1. 1. Lawrence Livermore National Lab., CA, USA.","journal-title":"Version"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80286-5"},{"key":"e_1_2_1_31_1","unstructured":"Yaron Minsky Anil Madhavapeddy and Jason Hickey. 2012. Real World OCaml: Functional programming for the masses. isbn:978-1449323912 https:\/\/dev.realworldocaml.org \t\t\t\t  Yaron Minsky Anil Madhavapeddy and Jason Hickey. 2012. Real World OCaml: Functional programming for the masses. isbn:978-1449323912 https:\/\/dev.realworldocaml.org"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79876-5_37"},{"key":"e_1_2_1_33_1","volume-title":"Purely Functional Data Structures","author":"Okasaki Chris","unstructured":"Chris Okasaki . 1999. Purely Functional Data Structures . Colombia University . isbn:9780521663502 Chris Okasaki. 1999. Purely Functional Data Structures. Colombia University. isbn:9780521663502"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003494"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341687"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023064908962"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00590-9_7"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454032"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796802004458"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/363534.363554"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408995"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00054-7"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3412932.3412935"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133841.3133843"},{"key":"e_1_2_1_45_1","unstructured":"Phillip Wadler. 1990. Linear Types can Change the World!. In Programming Concepts and Methods. \t\t\t\t  Phillip Wadler. 1990. Linear Types can Change the World!. In Programming Concepts and Methods."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1093"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3473576"},{"key":"e_1_2_1_48_1","unstructured":"Danil Yarantsev. 2020. ORC - Nim\u2019s cycle collector. Oct. https:\/\/nim-lang.org\/blog\/2020\/10\/15\/introduction-to-arc-orc-in-nim.html \t\t\t\t  Danil Yarantsev. 2020. ORC - Nim\u2019s cycle collector. Oct. https:\/\/nim-lang.org\/blog\/2020\/10\/15\/introduction-to-arc-orc-in-nim.html"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547634","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3547634","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\/3547634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,29]]},"references-count":48,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2022,8,29]]}},"alternative-id":["10.1145\/3547634"],"URL":"https:\/\/doi.org\/10.1145\/3547634","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"}}]}}