How the GC works

Before showing how to define a new Scheme type, it is important to understand how the GC works. First a certain number of cells are created1. When the interpreter needs a new cell, in the cons primitive for instance, it will take an unused cell in the pool of pre-allocated cells. If no more cell is available in this area, the GC is called. Its works is divided in two phases. First phase consists to mark all the cells which are currently in use. Finding the cells which are in used is done by marking recursively all the object which are accessible from

Marking phase is recursive; that means that if a variable denotes a list, all the elements of this list have to be marked , to avoid that the GC frees some of them. Of course, the recursive call for marking the component of a cell depends on the cell's type. This first phase is called the marking phase.

The second phase of the GC is called the sweeping phase. It is relatively simple: each allocated cells whose mark bit is unset is placed in the list of free cells, since nobody points anymore on it.

If no cells can be obtained when the sweeping phase terminates, the pool of pre-allocated cells will be extended by a new bank of cells.