Garbage collection

Garbage collection is an essential part of any Lisp interpreter or compiler. It allows Lisp to manipulate lists and more complex data structures without requiring the programmer to be concerned about the allocation and deallocation of the memory they need.

During the normal running of a Lisp program, objects are left that are no longer accessible by anything else in the environment. These objects are essentially wasted memory, and are called garbage. The garbage collector runs intermittently to gather up these inaccessible blocks of memory, and restore them for use by the program.

Mark and sweep

The type of garbage collector used in uLisp is called mark and sweep. It runs in two stages:

First, markobject() marks all the objects that are still accessible. After marking each object it recursively follows the car and cdr of each cons object to mark all the objects it points to.

void markobject (object *obj) {
  if (obj == NULL) return;
  object* arg = car(obj);
  if (marked(obj)) return;

  int type = obj->type;
  if (type != SYMBOL && type != NUMBER) { // cons
An object is marked by setting the top bit of its car cell, using the C macro mark(x):
#define mark(x)            (car(x) = (object *)(((unsigned int)(car(x))) | 0x8000))

The top bit will usually be zero, because uLisp has a maximum RAM size of 32 Kbytes, so the highest possible address is 0x7FFF.

Then sweep() builds a new freelist out of the unmarked objects, and unmarks the marked objects:

void sweep () {
  freelist = NULL;
  freespace = 0;
  for (int i=0; i<workspacesize; i++) {
    object *obj = &workspace[i];
    if (!marked(obj)) {
      car(obj) = NULL;
      cdr(obj) = freelist;
      freelist = obj;
    } else unmark(obj);

The macro unmark(x) clears the mark bit:

#define unmark(x)          (car(x) = (object *)(((unsigned int)(car(x))) & 0x7FFF))

and the macro marked(x) returns TRUE if the object is marked:

#define marked(x)          ((((unsigned int)(car(x))) & 0x8000) != 0)

Finally, the actual garbage collection is performed by gc(), which calls markobject() and sweep():

void gc (object *form, object *env) {
  markobject(bra); markobject(ket); markobject(quo);
  markobject(tee); markobject(dot);

This first marks the following objects:

  • The language symbols, open and closing bracket, quote, t, and dot.
  • The global environment GlobalEnv containing an association list of all the globally-defined variables and functions.
  • The garbage-collection stack, GCStack, used to push temporary structures that need to be protected from garbage collection during evaluation.
  • The form and local environment passed to gc as arguments.

It then calls sweep() to free the unmarked objects.

Invoking garbage collection

The garbage collector is invoked each time eval() is called if the amount of free space is less than 10 objects, by the statement:

  if (freespace < 10) gc(form, env);