12.3.12 Activation Records for Lisp-like Languages
Lisp is a programming language whose primary data struture is a list. Druing execution, lists can grow and shrink in size and thus are implemented using a heap data structure.
Although we refer explicitly to Lisp here, we could equally well be discussing Snobol, a string-oriented language, or any other language that requires data to be created and destroyed during program execution.
In Lisp-like languages, a new element may be added to an existing list structure at any point, requiring storage to be allocated. A heap pointer, say, Hp, is set to point to the next free element on the heap. As storage is allocated, this pointer is continually updated. Calls to operating system routines manage this allotment.
Certainly, if storage is continually allocated and not recovered, the system may soon find itself out of space. There are two ways of recovering space:explicitly and garbage collection, a general technique used in operation system. We will discuss these two as they relate to Lisp.
Explicit Return of Stroage
Consider the list 
in Figure 4, where each element contains two fields: the information
field and a field containing a pointer to the next element of the list. The element
, itself, points to (contains the address of) the first element in the list.
In LISP, an operator called (for historical reasons) cdr, given a pointer to one element in a list, returns a pointer to the next element on the list.
The question is whether or not cdr should cause the pointer to be returned to the
heap.
If is the only pointer and cdr doesn't return it to the heap, then it becomes
"garbage" (a technical term whose meaning should be clear!).
However, if cdr does return it and other pointers (shown as "?" in the picture
above) do exist, then they become dangling references; they no longer point to
because it no longer exists.
Unfortunately, it is difficult to know, although some creative (and time consuming!) bookkeeping could keep track. The alternative is to allow garbage to be created and periodically to "clean up"- a method called garbage collection.
Garbage Collection
When the garbage collection method is used, garbage is allowed to be created. Thus, there is no dangling reference problem.
When the heap becomes exhausted (empty), a garbage collection mechanism is invoked to identify and recover the garbage. The following describes a garbage collection algorithm. It presumes that each element in the system has an extra bit called a "garbage collection bit" initially set to "on" for all elements.
Algorithm
Garbage Collection
Step 1. Mark "active" elements, that is, follow all active pointers, turning "off" of the garbage collection bits for these active elements.
Step 2. Collect garbage elements, that is, perform a simple sequential scan to find elements with garbage bit on and return them to the heap.