A Compacting Garbage Collector for Unidirectional Heaps

. A unidirectional heap is a heap where all pointers go in one direction, e.g. from newer to older objects. For a strict functional language, such as Erlang, the heap may be arranged so that it is unidirectional. We here present a compacting garbage collection algorithm which utilizes the fact that a heap is unidirectional. Only one memory space is used in our algorithm. In fact, no extra memory is used at all, not even any reserved bits within the cells. The algorithm is quite easy to extend to a variant of generational garbage collection. 1 Introduction The Erlang functional programming language [5] is typically implemented using a copying garbage collection algorithm. In [4] a completely new method was suggested utilizing the fact that objects on the heap may be allocated so that each object only points to earlier allocated ones. In order to be able to deallocate data in the middle of the heap, without disturbing the order of objects, all objects were linked, each with a `...