3 ms·
I think, the first mark‑and‑sweep collector was published in McCarthy's 1960 Communications of the ACM paper "Recursive Functions of Symbolic Expressions and Th
by Rochus 1y ago
I think, the first mark‑and‑sweep collector was published in McCarthy's 1960 Communications of the ACM paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". It's resonable to assume, that they already had it when Steve Russell implemented the first Lisp evaluator, but we don't know exactly when it was added.
- kragen 1y agoNo, that paper doesn't describe the garbage collector. I do think it is true that before it was published Slug Russell had implemented the GC, but I think it's correct that we don't have listings from that early. Edit: yes, yes it does describe the garbage collector.
- andsoitis 1y agoThe concept of automatic memory management dates back to the 1950s. However, John McCarthy, the creator of Lisp, introduced the first widely recognized garbage collection mechanism around 1959/1960.
- kragen 1y agoIf so, he didn't write about it in that paper, and I don't think he introduced it at all; I think Slug Russell did. Correction: as Rochus pointed out, he certainly did write about it in that paper, giving a complete description.
- Rochus 1y agoIsn't the "Free-Storage List" in section 4c, starting on page 26, a mark & sweep collector? They didn't use the term then, but I think it describes one. I'm not aware of any earlier publication.
- kragen 1y agoThe paper only has 12 pages, but there is a section 4c with that title starting on page 192 of https://dl.acm.org/doi/pdf/10.1145/367177.367199 https://dl.acm.org/doi/pdf/10.1145/367177.367199, and you are correct that it describes a mark-and-sweep collector. I was mistaken, and I appreciate the correction.
- Rochus 1y agoOk, I see. Just downloaded the first hit from Google, which has 34 pages and is nicely printed: https://www-formal.stanford.edu/jmc/recursive.pdf https://www-formal.stanford.edu/jmc/recursive.pdf.