Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!uakari.primate.wisc.edu!ames!henry.jpl.nasa.gov!elroy.jpl.nasa.gov!hacgate!ashtate!atsun!dwiggins From: dwiggins@atsun.a-t.com (Don Dwiggins) Newsgroups: comp.sw.components Subject: Re: Problem requiring GC -- try again. Message-ID: Date: 28 Sep 89 18:26:33 GMT References: <911@scaup.cl.cam.ac.uk> <8310@goofy.megatest.UUCP> <923@scaup.cl.cam.ac.uk> Sender: dwiggins@ashtate Organization: Ashton-Tate, Inc. Lines: 26 OK, here's another shot at a problem that seems to call for GC; let's see what y'all can make of it. One of the elements of the Prolog language is the "atom" (read "name" or "symbol"). In the language model, atoms aren't created or destroyed, they just *are* (like the integers, for instance). To support this model, the Prolog interpreter must allocate a block in "atom space" whenever a mention of a new atom is required (either read in or needed as the result of a string-to-atom conversion). Problem: when to delete blocks in atom space? The Prolog user is no help, having no concept of "atom deletion". Reference counting is one possibility, but it has one serious defect. During backtracking, which is a common Prolog operation, potentially large chunks of stack space are "cut away"; to have to wade through that space finding pointers and decrementing counts would be a major performance hit. IMHO, a good asynchronous garbage collector working in the background would be the best solution. Historical note: at the time I was last involved in implementations of Prolog (several years ago), atom space was generally not "cleaned up" at all; when it filled up, the system had to abort. -- Don Dwiggins "Solvitur Ambulando" Ashton-Tate, Inc. dwiggins@ashtate.uucp