Towards region-based memory management for Mercury programs

Logic programming systems build the terms on the heap. Then automatic memory management for the heap relies on backtracking and runtime garbage collection to reclaim space on the heap. While efficient implementations of garbage collectors for logic programming languages can reuse more than 90 % of the heap space, they introduce performance overhead to the execution of a program. To remedy this shortcoming there has been a lot of research on compile-time memory management techniques, which derive the memory behaviour of a program when compiling and enhance the program with instructions to reuse memory. This static method generally follows two approaches: region-based memory management (RBMM) and compile-time garbage collection (CTGC). The basic idea of RBMM is to divide the heap memory into different regions. The dynamically created terms and their subterms have to be distributed over the regions in such a way that at a certain point in the execution of the program all terms in a region are dead and the region can be removed. RBMM has long been a topic of intensive research for functional programming languages [8, 1, 4] an