Garbage Collection

Lisp implementations have the advantage that all objects are accessible through some path originating in the symbol tables and the whole accessible structure is an intrinsic part of Lisp. Thus, much of the extra data structure for doing garbage collection in Lisp exists for free and is more cogent than C++ as a starting point for garbage collection algorithms. Since Lpp does not have this structure available under C++ and since there are many reasonably good C++ garbage collection algorithms available, Lpp does not commit to any of these in principle nor provides any kind of automatic garbage collection.

Lpp does provide a facility for doing manual garbage collection much the same way delete works in standard C++. But it makes the garbage collection of complex Lpp data structures easier. All Lpp garbage collection functions only serve to deallocate the storage of some data and then just return nil.

gc object

Function

gc garbage collects the Lpp object object.

Here is a trivial example:

     let a = L(1);
     let b = L(2);
     let c = plus(a, b);  // assume c is needed from here on
     gc(a); gc(b);        // and a and b are not
     

In general, for predefined Lpp object types the object and all of its components are collected except for some exceptions listed in the next paragraph. For user defined Lpp objects gc calls delete of the specific subtype class for object.

Since Lpp symbols have global import gc will do nothing if object is a Symbol. Usually you do not want to remove symbols. However in cases where you absolutely must the proper way to remove symbols and have them collected is to use unintern which removes the symbol from the system and garbage collects all of the associated parts, See Creating Symbols. If gc is called on a cons it collects the cons object only and not its car or cdr.

For garbage collecting cons structures gcList should be used for garbage collecting top level lists and gcTree for collecting tree structures. In these functions a leaf argument says what to do with the leaf nodes of a list or a tree. Leaf nodes are a car or cdr of a cons that is something other than a list (nil or another cons). However the main difference between gcList and gcTree is that with gcList the car of every cons in the top level list is also treated as a leaf node for the listed meanings below of the leaf argument. Note that because of this using gcList with a special user collection function as the leaf argument the user can effectively create his own special version of gcTree. This also implies that if the programmer wants to use gcTree on a top level list that has a cons in some of its cars he should use gcTree instead or else supply his own leaf function argument to collect such cars or otherwise take care of them.

The leaf argument can be one of three things with the following implied meanings:

     nil => Do not garbage collect leaf nodes
     t => Apply gc() to leaf nodes
     Function f => Apply Function f to leaf nodes
     

gcList will handle all lists including circular and dotted lists. gcTree will handle all trees except trees that have circular or multiple references. However it will break with an explanation error message if it detects either circular or multiple references for most trees. The only cases where it doesn't detect is where there are circular or multiple reference paths where there are no leaves in the path. For example

     let self = list(True);
     rplaca(self, self);
     

Clearly this simple tree has a circularity with no leaf nodes in the circular path. This would fail with gcTree. But this is not usual and is probably not even useful. In such unusual trees the programmer must either create his own collection function or else store a non-cons in such a problematical cons slot and then call gcTree.

gcList list leaf

Function

gcList will garbage collect the list list and leaf nodes depending on the leaf argument as described above. For this purpose the cars of each cons in the list will always be treated as leaf nodes even if they contain other cons objects.

Here are some examples.

     let list1 = list(L("one"), L("two"), L("three"));
     let list2 = copyList(list1);
     
     // leaf argument is nil, so list1 is grabage collected
     // but Strings "one", "two", "three" are left alone.
     gcList(list1, Nil);
     
     // leaf argument is t, so list2 is grabage collected
     // and so are Strings "one", "two", "three"
     gcList(list2, True);
     
     list1 = list(myObject1, myObject2);
     
     // leaf argument is the Function myCollector
     // so list1 is garbage collected while the function myCollector
     // is applied to the leaf node objects myObject1, myObject2
     gcList(list1, L(myCollector));
     

gcTree tree leaf

Function

gcTree will garbage collect the tree tree and leaf nodes depending on the leaf argument as described above. The tree argument can be a cons or a non-cons Lpp object. If it is a non-cons object then the leaf argument is applied to the object.

If there are circular or multiple references in the tree in paths that have one of more leaves then gcTree will break with an error message stating such. For any trees with circular or multiple references the programmer can either store a non-cons in the offending cons slots and then call gcTree or write a gc function specialized for such a data structure and call gcList passing the specialized function as the leaf argument.

Here are some examples using association lists which are in effect small trees:

     let alist1 = list(cons(L("one"), L(1)),
                       cons(L("two"), L(2)),
                       cons(L("three"), L(3)));
     let alist2 = copyAlist(list1);
     
     // leaf argument is nil, so alist1 is grabage collected
     // but Strings "one", "two", "three" are left alone
     // and numbers 1, 2 and 3 are left alone.
     gcTree(alist1, Nil);
     
     // leaf argument is t, so alist2 is grabage collected
     // and so are Strings "one", "two", "three"
     // and numbers 1, 2 and 3.
     gcTree(alist2, True);
     
     alist1 = list(cons(L(1), myObject1),
                   cons(L(2), myObject2));
     
     // leaf argument is the Function myCollector
     // so alist1 is garbage collected while the function myCollector
     // is applied to the leaf node objects 1, 2, myObject1, myObject2
     gcTree(alist1, L(myCollector));
     
     
     It is easy to garbage collect raw cons objects and their parts.
     For example assume the variable var contains a cons,
     then
     
          gcTree(cdr(var));  // Collects just the whole cdr tree of var
          gc(var);  // Collects just the cons var and not the car or cdr
          
     
     There are many combinations of ways to collect cons structures
     and their parts.  But the following function fulfills a common case

     



gcConsElement cons
          
Function



     
     Given a cons in the cons argument gcConsElement will
     garbage collect the whole car tree of cons using
     gcTree and then garbage collect the cons itself.  It is
     useful for completely collecting ordinary list elements that are
     represented by cons structures and is used by some Lpp functions that
     optionally perform a garbage collection on destructive list
     operations, such as nremove, See Modifying Sequences.