An important property of the Newell Shaw-Simon scheme for computer storage of lists is that data having multiple occurrences need not be stored at more than one place in the computer. That is, lists may be “overlapped.” Unfortunately, overlapping poses a problem for subsequent erasure. Given a list that is no longer needed, it is desired to erase just those parts that do not overlap other lists. In LISP, McCarthy employs an elegant but inefficient solution to the problem. The present paper describes a general method which enables efficient erasure. The method employs interspersed reference counts to describe the extent of the overlapping.
Metadata: Crossref. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
Maybe not how you were brought up, and people argue... But Watson & Watson, back in '87, described ref counting as "An efficient garbage collection scheme for parallel computer architectures".
Even the dragon book refers to ref counting as a form of garbage collection.
Line 2 of Ref counting's Wikipedia page refers to garbage collection.
People have argued since the invention in 1960, but... Ref counting is one form of GC. [0] It might not be a tracing GC, but it is GC.
[0] https://dl.acm.org/doi/10.1145/367487.367501
There is another page <https://github.com/naver/lispe/wiki/2.5--LispE-vs.-Python:-A...> on implementation details that I don't get either.
In particular, the hash table apparently cannot have collisions, as "variables are necessarily unique". Sure, but there are only 64 buckets for 65,536 names, so it is further necessary for all variable names to be unique modulo 64, which can't be guaranteed. One option (which I believe CPython uses, more or less, by numbering locals and arguments) is to use De Bruijn indexes [0], but I'm not sure how to make it work with a tree-walking interpreter.
I'm also not sure how it is possible to come up with a reference-counting algorithm that…
Read the full comment
performs "recursive increments", as an assignment X := Y only ever adds one incoming reference to Y from X. The example suggests the reference counts are the number of ways each value is transitively reachable, which is unnecessary and no one does that; Collin's original paper on reference counting [1] describes it as "a tally of the number of arrows pointing to [an object]" which is not transitive.
[0] https://en.wikipedia.org/wiki/De_Bruijn_index
[1] https://dl.acm.org/doi/10.1145/367487.367501
I believe this is the first paper to describe reference counting:
George E. Collins. A method for overlapping and erasure of lists. Commun. ACM 3, 12 (Dec. 1960), 655–657. https://doi.org/10.1145/367487.367501
Abstract If future net-zero emissions energy systems rely heavily on solar and wind resources, spatial and temporal mismatches between resource availability and electricity demand may challenge system reliability.