This is certainly a false claim then. What you're describing is a precise garbage collector, but there also exist conservative garbage collectors which will fail to reclaim objects even when no cycle exists so long as any integer interpretation of currently allocated memory shares the same integer interpretation of an object's memory address.
GNU Java, and the Mono implementation of .NET both use the Boehm conservative garbage collector and they are most certainly still considered garbage collected systems:
The issue with cycles is that it can easily lead to significant memory leaks if a large subgraph gets caught in a cycle. A definition of GC that excludes this capability does not have the contract of “You only have to worry about reachability from roots”.
Computer science is absolutely a formal science in every sense of the word.
>If Boehm GCs really leak as much as you claim then nobody would use them.
I mean if anything this argument applies more to your characterization that reference counting easily leads to memory exhaustion due to cycles than it does to conservative garbage collectors. If RC based garbage collectors leaked as much as your post implies then nobody would use them. And yet Swift, a language that is almost exclusively used with large graphs(that's how most UIs are represented in memory) and that exhibits all kinds of non-deterministic shared ownership uses RC based garbage collection. Objects involved in UI code are shared in wildly unpredictable ways with no clear hierarchy among layouts, event handlers, observables, IO systems, etc...
>A definition of GC that excludes this capability does not have the contract of “You only have to worry about reachability from roots”.
Exactly, because that's not part of the contract for a GC. That's part of the contract for a tracing garbage collector:
https://en.wikipedia.org/wiki/Tracing_garbage_collection
When your definitions don't fit reality then it's time to adjust your definitions, not reality.
It is sufficient in a functional language that lacks haskell's lazy capacity to "tie the knot". Erlang's data structures, for example, are fully immutable, and it is not possible to create a cyclic data structure. Since there cannot be a cyclic data structure, reference counting would be sufficient to manage its memory automatically.
It would still suck since it has to constantly write to all objects being referenced, but it would work.
In an ideal world and in a program running with a not-huge # of objects you could keep the entire basket of reference counts in L1 cache, separate from the objects. Then decrements would be potentially cheap. A bit utopian though.
Reference counting is not GC in the modern sense unless it also includes a cycle collector. So Swift is not GC’d (RC only) yet Python is GC’d (RC+CC).