Garbage-Collection Safety for Region-Based Type-Polymorphic Programs
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Garbage-Collection Safety for Region-Based Type-Polymorphic Programs. / Elsman, Martin.
In: Proceedings of the ACM on Programming Languages, Vol. 7, No. PLDI, 115, 2023.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Garbage-Collection Safety for Region-Based Type-Polymorphic Programs
AU - Elsman, Martin
N1 - Publisher Copyright: © 2023 Owner/Author.
PY - 2023
Y1 - 2023
N2 - Region inference offers a mechanism to reduce (and sometimes entirely remove) the need for reference-Tracing garbage collection by inferring where to insert allocation and deallocation instructions in a program at compile time. When the mechanism is combined with techniques for reference-Tracing garbage collection, which is helpful in general to support programs with very dynamic memory behaviours, it turns out that region-inference is complementary to adding generations to a reference-Tracing collector. However, region-inference and the associated region-representation analyses that make such a memory management strategy perform well in practice are complex, both from a theoretical point-of-view and from an implementation point-of-view. In this paper, we demonstrate a soundness problem with existing theoretical developments, which have to do with ensuring that, even for higher-order polymorphic programs, no dangling-pointers appear during a reference-Tracing collection. This problem has materialised as a practical soundness problem in a real implementation based on region inference. As a solution, we present a modified, yet simple, region type-system that captures garbage-collection effects, even for polymorphic higher-order code, and outline how region inference and region-representation analyses are adapted to the new type system. The new type system allows for associating simpler region type-schemes with functions, compared to original work, makes it possible to combine region-based memory management with partly tag-free reference-Tracing (and generational) garbage-collection, and repairs previously derived work that is based on the erroneous published results.
AB - Region inference offers a mechanism to reduce (and sometimes entirely remove) the need for reference-Tracing garbage collection by inferring where to insert allocation and deallocation instructions in a program at compile time. When the mechanism is combined with techniques for reference-Tracing garbage collection, which is helpful in general to support programs with very dynamic memory behaviours, it turns out that region-inference is complementary to adding generations to a reference-Tracing collector. However, region-inference and the associated region-representation analyses that make such a memory management strategy perform well in practice are complex, both from a theoretical point-of-view and from an implementation point-of-view. In this paper, we demonstrate a soundness problem with existing theoretical developments, which have to do with ensuring that, even for higher-order polymorphic programs, no dangling-pointers appear during a reference-Tracing collection. This problem has materialised as a practical soundness problem in a real implementation based on region inference. As a solution, we present a modified, yet simple, region type-system that captures garbage-collection effects, even for polymorphic higher-order code, and outline how region inference and region-representation analyses are adapted to the new type system. The new type system allows for associating simpler region type-schemes with functions, compared to original work, makes it possible to combine region-based memory management with partly tag-free reference-Tracing (and generational) garbage-collection, and repairs previously derived work that is based on the erroneous published results.
KW - garbage-collection
KW - region-inference
KW - Standard ML
U2 - 10.1145/3591229
DO - 10.1145/3591229
M3 - Journal article
AN - SCOPUS:85162005921
VL - 7
JO - Proceedings of the ACM on Programming Languages
JF - Proceedings of the ACM on Programming Languages
SN - 2475-1421
IS - PLDI
M1 - 115
ER -
ID: 358550468