What are the practical examples of reference cycles?

Question

Garbage collectors have functionality to deal with reference cycles. As far, as I understand, this is necessary for all languages with GC.

But I do not understand, why there can not be created language avoiding reference cycles, using some weak references, if necessary.

What are the real life examples of unavoidable reference cycles, arising in programming?

Answer 1

You can not create a programming language avoiding reference cycles, as it would be the responsibility of the application programmer, not to create the cycles. You could only create a language which requires the programmer to always take that responsibility.

It’s the fundamental design of the data structures which may allow cycles or not. E.g. in Java, a List is a list of references, therefore, there is no problem in storing a List in itself, directly or indirectly. But to name a more straight-forward example, with a doubly linked list, each node has a pointer to its next node and its previous node. This is already enough to form reference cycles:

 ┌──────┐             ┌──────┐             ┌──────┐             ┌──────┐             
 │      │ -next-----> │      │ -next-----> │      │ -next-----> │      │
 │ Node │             │ Node │             │ Node │             │ Node │
 │      │ <-previous- │      │ <-previous- │      │ <-previous- │      │
 └──────┘             └──────┘             └──────┘             └──────┘

This is already forming multiple loops, short loops between two adjacent nodes via their previous and next references, but also indirectly between the other nodes.

To cut these loops via weak references, the designer of the Node class would have to decide whether to make the next or previous reference weak. Either of them would destroy one of the fundamental functionality:

• If you have a reference to the first node, you can reach and traverse all nodes via a chain of next references
• If you have a reference to the last node, you can reach and traverse all nodes via a chain of previous references
• In fact, having a reference to any of the chained nodes is sufficient to reach all nodes
• If all nodes are unreachable, all nodes can get garbage collected

If you declare one of the two references weak, you can not assume that a reference to one node keeps all nodes alive anymore. If next was weak you were required to always keep a reference to the last node to prevent sudden removal of next nodes. If previous was weak, you had to keep a reference to the first node all the time.

So requiring the developer to always cut loops via weak references would cause fundamental restrictions to the way, the software has to be designed. As another example, consider a component to which you register a listener will modify the component when an event happened (or another component having a reference to the former), therefore forming a cyclic loop. Making the listener reference weak would imply that it could suddenly disappear without a cause.

---

That said, even the weak references themselves are a feature that is naturally provided by garbage collectors doing graph traversal, as only those can cheaply act when discovering their existence. A reference counting system can easily free an object when it discovers that the last/only existing strong reference has been removed, but it would need additional bookkeeping of all existing weak references to clear them when the object has been freed.

This is the point, where reference counting simply makes no sense anymore. It wouldn’t be simple to implement anymore (which is the only advantage), while being inefficient at the same time, as when traversing an object graph, like iterating over the linked list, you permanently have to update reference counters (in a thread safe way if your language supports multi-threading), whereas a traversing garbage collector only has to do something when it has to check for reclaimable memory. And it only has to traverse alive objects, thus the longer it can get away with doing nothing, the less work it will have on the next cycle.

Answer 2

One of the core data structures in programming is graphs, which are just interconnected groups of nodes. Cycles are completely permissible in graphs. Since nodes can be coded as objects on a heap, cycles are necessary.

On a less abstract note, graphs have many practical uses. Basically, they represent networks of things: networks of friends on Facebook, networks of cities on maps, networks of computers on the Internet, etc.