Garbage-Collection Safety for Region-Based Type-Polymorphic Programs

Research output: Contribution to journalJournal articleResearchpeer-review

Documents

  • Fulltext

    Final published version, 319 KB, PDF document

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.

Original languageEnglish
Article number115
JournalProceedings of the ACM on Programming Languages
Volume7
Issue numberPLDI
DOIs
Publication statusPublished - 2023

Bibliographical note

Publisher Copyright:
© 2023 Owner/Author.

    Research areas

  • garbage-collection, region-inference, Standard ML

ID: 358550468