Thesis Topic Details

Topic ID:
Combining garbage collection and region allocation in typed functional languages
Ben Lippmeier
Research Area:
Compiler, Programming Languages, Formal Methods
Associated Staff
Gabriele Keller
Topic Details
R & D
Group Suitable:
Experience with Haskell, and working knowledge of programming language semantics and type theory
Using Garbage Collection (GC) to manage memory (de)allocation frees the programmer from worrying about this themselves. It also eliminates a large class of programming errors, as there is no risk of an object being freed while it is still being used by the program. The downsides of GC are that it becomes difficult to reason about the space usage of a program, simple stop-the-world collectors can suffer from high pause-times, and global collection is difficult to implement in parallel shared memory machines.

An alternate approach is to use region based memory management, as in MLKit [1]. In a region based system, memory is allocated and freed in a stack-like manner. Region allocation has the advantage that most free space is reclaimed more quickly than with GC, similar heap objects are kept close together which improves cache usage, and the running program does not need to be stopped to reclaim space. The downside of region allocation is that if the lifetime of an object does not follow the syntactic tree structure of the program, then region deallocation will not reclaim it soon enough, causing a space leak.

The goal of this project is to investigate how garbage collection and region based memory management might be combined in the same system, particularly in the context of DDC [2]. DDC is a compiler for Disciple, an experimental dialect of the functional language Haskell. Disciple extends the Haskell type system with region and effect information. We would seek to leverage the Disciple type system to decide when it is profitable (and safe) to use region based memory management over garbage collection.

In the initial stages of this project you will need to read existing research papers, particularly from the MLKit team, to determine what can reasonably be attempted in the available time. The direction you would take from there would depend on the outcome of this reading, and your own interests. Possibilities include extending the Disciple language to support combined memory management, adding a garbage collector and/or region allocator to the DDC runtime system, or undertake semantics work to clarity the existing approaches.

DDC itself is written in Haskell, so any development work will be done in Haskell and/or the DDC core language. Any mechanised semantics work would preferably be done in Coq.

This project requires a working knowledge of programming language semantics and basic type theory. Good results in COMP3161 or similar would count here. If not sure then ask the project supervisor.
Past Student Reports
No Reports Available. Contact the supervisor for more information.

Check out all available reports in the CSE Thesis Report Library.

NOTE: only current CSE students can login to view and select reports to download.