[gclist] ancient history (was: Are there any studies or reports about the analysis of cyclic structures?)

[Nick Barnes]

At 2005-06-16 12:24:39+0000, "David F. Bacon" writes:
> > I feel I should point out that the first garbage collector was
> > mark-sweep tracing, not reference counting [McCarthy 1960, section
> > 4c].
> 
> reference counting was published by collins in the same year, in the
> december cacm (http://portal.acm.org/citation.cfm?id=367501) --
> although the lack of cycle collection wasn't pointed out until
> somewhat later (citation, anyone?).  so the invention of the two
> algorithms was roughly contemporaneous, although it is highly likely
> that tracing came first since collins cites mccarthy's work (he
> calls it "elegant but inefficient"!).  how early they were in use
> (as opposed to when they were published) would be an interesting
> tidbit.

In MIT AI Memo 8, March 1959, there were still the erasure functions,
eralis and erase.  Then in the RLE Quarterly Progress Report in April
1959, McCarthy apparently describes garbage collection, which was
implemented in the summer of that year by Russell and Edwards.

This is all according to Herb Stoyan's work on the development of
Lisp: <http://www8.informatik.uni-erlangen.de/html/lisp/mcc91.html>

I don't have good copies of *any* of the relevant documents from the
era.  In the early 90s I contacted Stoyan and he told me that he only
had the low-resolution GIFs of the memos.  I believe I also asked
McCarthy at the time.  If anyone on this list does have digital copies
of any of the MIT AI memos, or of the RLE QPR, please let me know.

Memo 4, from October 1958, also describes, and apparently invents, the
use of a stack ("the public push-down list") for recursive function
calls.

Nick Barnes
Ravenbrook Limited