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
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.