Re: Historical Implementations to Garbage Collectors

On 2014-05-04, Robin Vowels <robin51@dodo.com.au> wrote:
>: <lpsantil@gmail.com> wrote:
>> I'm interested in studying historical implementations of garbage
>> collection in early programming languages (BASIC, Lisp, etc). I'm
>> especially interested in language/runtime interface descriptions.
>> Does anybody have references they can share?
>
> McKeeman, Horning, and Wortman's XPL compiler used garbage
> collection for strings on S/360. Collection was automatic
> and invisible to the user.
>
> No tags were needed.


Why would there be tags; strings don't point to other strings. There are no
arcs or cycles in the graph. You never have to solve the problem "has the
garbage collector already visited this string", since you can use a handles to
keep track of strings---hence there is no need to walk the graph of non-string
objects in order to find strings; just the array or list of string handles,
where no two handles reference the same string.


String-only garbage collection is relatively trivial and uninteresting.
The general idea behind compacting allocation is usually: sort the strings in
by address and blit them to one end of the string arena.
If compaction isn't the chosen approach, then the sorted list of strings can
instead be used used to identify the free space between the strings and put them into a free
list for new string allocations.

Return to the comp.compilers page.
Search the comp.compilers archives again.