GC in Ada

[macrakis@HARVARD.HARVARD.EDU (Stavros Macrakis)]

`Garbage collection' (GC) has been used in more than one sense in
this discussion.  Several contributors equate GC with `storage
reclamation'.  This is misleading.  The essence of GC is finding free
space by determining what access objects remain in use.

GC is a particular type of automatic storage reclamation -- reference
counting, e.g., is another.  And explicit deallocation or deallocation
of stack frames at scope exit time is simply not automatic storage
reclamation.  Neither is deallocating an entire collection at the exit
of the scope declaring the type.  All of these are useful techniques,
but they are not GC.  GC has different advantages and disadvantages
than each of these other methods.

It is not possible to write a garbage collector within Ada (unless, of
course, you have hooks into the implementation).  It is not even
possible to define a private type which reclaims its own space within
Ada.  The essential problem is that there is no way of determining the
``immediately accessible nodes'' in Knuth's ("Art") terminology, i.e.
the variables containing access values.  It would be possible to
define a limited type that used GC or ref counting if there were a
finalization operation (see Schwarz&Melliar-Smith, ``The Finalization
Operation for Abstract Types'' ICSE/5, p273).

For a discussion of issues relating to GC implementation in an
Ada-like environment, see Susan Owicki, ``Making the World Safe for
GC'' in POPL/8, p77.

The term `Garbage collection' has had a precise meaning for over
twenty years.  Here are some citations:

J.McCarthy et al, "Lisp 1.5 Programmer's Manual" (2nd ed, 1965) p105:
   garbage collector: The routine in LISP which identifies all active
   list structure by tracing it from fixed base cells and marking it,
   and then collects all unneeded cells (garbage) into a free-storage
   list so that these words can be used again.

Knuth, "Art" (1st ed, 1968), sec 2.5B p438:
   ...a policy of simply doing nothing until space runs out, then
   searching for all the areas currently in use and fashioning a
   new AVAIL list.

Aho&Ullman, "Principles of Compiler Design" (1st ed, 1977) p44:
   A garbage collection scans all records, determining which are in
   use, and making an <available space list> of those which may be
   reused.

Note that "garbage collection" has been used in many systems other than
Lisp with the same meaning: Snobol, ECL, MIT Teco (!), ....

	-s


ICSE = Intl. Conf. on Software Engineering
POPL = Principles of Programming Languages (Conf.)