CSE 341 -- Garbage Collection

Scheme, like Smalltalk and Java, uses garbage collection to manage storage.

When an expression such as (cons 'fred ()) is evaluated, the cons function allocates a new cons cell (bit of storage) from the heap. There is no explicit deallocation procedure; rather, when the cons cell is no longer accessible it can be garbage collected.

Scheme implementations typically keep a free list of unused cons cells. Except for not being directly accessible to the user, this is just an ordinary list, sprinkled through memory. The cons function just grabs the first cell at the head of the free list, and then sets the free list pointer to the next available cell.

There are lots of variations on garbage collectors. One of the simplest is mark-and-sweep. When free storage is exhausted, first the system marks all the cells that can be reached by following pointers. (The pointers will be from the global symbol table or any local variables on the stack.) Then the system sweeps through memory. Every unmarked cell is no longer accessible and can be added to the free list.

Some variations:

There are lots of other versions. In all cases the system has to be careful to distinguish pointers from other kinds of data (such as characters and numbers).

In reference counting the systems keeps track of how many references there are to an object. When the count drops to zero the storage is reclaimed. This is naturally incremental, but doesn't reclaim circular structures.