Fundamentals of garbage collection (2023)

Kindof unrelated to the article, but I was recently wondering if it would be possible to detect and deny pointer cycles in a language in an efficient way, so that you could then use simple reference counting instead of full-blown garbage collection.

It probably wouldn't be usable for a general-purpose programming language, but for a special-purpose scripting language I could see it making the language implementation easier.

One solution is to forbid recursive data types - e.g., require every struct type to only reference types that have already been defined. I can't think of any languages that do this.

Another solution is to make things immutable (like Erlang), or "as-if" immutable (like Koka), which guarantees that data can only point to things that have already been defined, preventing cycles.* Erlang uses this to simplify generational collection - because old data can't point to young data, it doesn't need a card table or anything like that.

I think it's perfectly possible to have a general purpose language without cycles: you can just use integer indices into an array instead of pointers if you want cyclic data structures. This is common in Rust, when people want to avoid the overhead of reference counting, but don't want to use unsafe code.

* A hidden assumption here is that the language is eagerly evaluated. There are languages like Haskell that have immutability and cyclic data structures.

Even with cyclic relationships between types, immutability makes cycles within instances difficult (without laziness anyway). A syntax tree would be a good example.