Copenhagen Programming Language Seminar


Garbage Collection Safety for Region-based Memory Management

Martin Elsman
Royal Veterinary and Agricultural University, Denmark and IT University of Copenhagen, Denmark

Thursday, October 3rd, 15:15-16:00
IT-C, Glentevej 67, room 2.03


In previous work, Hallenberg et al. [1] have integrated region-based memory management with a Cheney-style copying garbage collection algorithm. In this talk, we prove the safety of the integration, which relies on a refinement of the region typing rules that forbid dangling pointers during evaluation.

To accommodate the triggering of garbage collection at any step in the evaluation process, we base our type-safety result for the region-based system on a small-step contextual semantics and show that whenever a well-typed expression reduces to another expression, possibly by deallocating a region, then no dangling pointers are introduced. Because there are no dangling pointers in the initial heap, no dangling pointers appears during evaluation.

The memory discipline, which combines garbage collection and region-based memory management, is implemented for Standard ML in the ML Kit compiler. Although in principle the refinement of the region typing rules lead to less flexibility and can cause worse memory behaviour than when dangling pointers are permitted, experiments show that for a range of benchmark programs, the refinement has little effect on the overall memory behaviour.

[1] Niels Hallenberg, Martin Elsman, and Mads Tofte. Combining Region Inference and Garbage Collection. In ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI'02). Berlin, Germany. June 2002.

Scientific host: Peter Sestoft. Administrative host: Camilla Jørgensen. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, IT-C and KVL.
To receive information about COPLAS talks by email, send a message to prog-lang-request@mail.it-c.dk with the word 'subscribe' as subject or in the body.

For more information about COPLAS, see http://www.coplas.org