[gclist] Garbage collection FAQ.

[Gregory Morrisett]

Actually, Goldberg wasn't the first to suggest that ML could
be garbage collected in a tag-free manner.  Appel's work
predates this.  Goldberg showed something much more interesting --
that you could not reconstruct the types of all reachable objects
(without auxiliary information maintained at run time).  However,
and this is the fascinating part, these objects were guaranteed
to be "semantic" garbage -- i.e., even though the objects were
reachable, they would never be accessed.  

This fundamental property of unification (it actually has nothing
to do with polymorphism, but rather type inference) was first
suggested by (you guessed it) Henry Baker.  

Ironically, Goldberg's proposed algorithm does not work for
Standard ML, only because of the presence of a single non-parametric
operator, namely polymorphic equality.

Other tag-free collectors for polymorphic languages include
Aditya & Cairo's type reconstructor for Id, and Tolmach's
tag-free collection for ML, as well as my own tag-free implementation
in the TIL/ML compiler (see the up coming PLDI for more information).

-Greg Morrisett
 jgm@cs.cornell.edu