25
$\begingroup$

When using reference counting for garbage collection, memory leaks can occur when cyclic structures are created (an object which contains a pointer to itself, or a pointer to an object with a pointer to the first one, or so on). One way to solve this would be disallowing this in the first place.

It would be best not to enforce this at runtime, since any bug not caught by the compiler (or in an interpreter before the code runs) could make it to production if it's not noticed.

Is there a way to enforce no cyclic data structures at compile time?

$\endgroup$
10
  • 3
    $\begingroup$ I wouldn't be surprised if this is equivalent to the halting problem ... $\endgroup$
    – Glorfindel
    May 16, 2023 at 18:45
  • 3
    $\begingroup$ Rust's borrow checker goes pretty far. There are intentional backdoors left in, such as RefCell, that can violate these expectations. But I feel like, if you remove some of the more complex RefCell and Rc types from Rust, you would get a completely acyclic language. I'll have to think about it some more. $\endgroup$ May 16, 2023 at 18:51
  • 1
    $\begingroup$ Such structures are useful, though. $\endgroup$ May 17, 2023 at 0:42
  • 1
    $\begingroup$ @KarlKnechtel That's true. One solution would be having a built-in type for certain common cyclic data structures, which could be hardcoded to safely work with reference counting (such as doubly linked lists) $\endgroup$ May 17, 2023 at 1:47
  • 1
    $\begingroup$ @UnrelatedString Yup. It's the Enterprise Rules Engine Law: any compiler restriction can be defeated, at the cost of losing all of the performance and safety features of a compiler. $\endgroup$ May 17, 2023 at 2:00

5 Answers 5

24
$\begingroup$

Yes, it can be. There are three simple ways:

  • Ban recursive type definitions, so e.g. a Foo can't have a field of type Foo, or a field of type Bar if Bar has a field of type Foo; and this also must apply to generics, so e.g. Foo cannot implement the interface List<Foo> or List<Bar>. This can be achieved e.g. by forbidding all forward references of type names, and requiring types to be declared in the order they are used.
  • Ban mutation and lazy initialisation of objects. If objects can only hold references to objects which already exist at instantiation time, then a reference cycle is impossible, because it would imply the object was created before itself. (This must apply not just to traditional "objects", but anything that might hold a reference while also being referenced, including closures, or local variables in languages which allow direct references to those.)
  • Ban everything. All programs fail at compile time.

The last one is a joke, obviously, but it gets the point across ─ it is possible for a compile-time check to disallow whatever you want, as long as you don't mind disallowing more than just that thing. The real question is how much more you have to disallow. How much baby do you have to throw out with the bathwater?

Probably the other two options also throw out too much baby for your liking, but they are relatively simple. If you want less collateral damage, then the language will need to be more complicated. Some other options, in increasing order of complexity and expressiveness:

  • Allow recursive type definitions, but fields which could allow for reference cycles must be read-only and not lazily initialised.
  • Use runtime checks, but enforce the use of these checks in the type system. For example, if Foo is your recursive type then make it generic in a "depth" parameter, so that Foo<N> can only hold references to Foo<M> when M < N, and the assignment foo1.child = foo2; is a type error if it isn't guarded by the appropriate check.
  • Require the programmer to write a proof that M < N, and check the proof at compile-time. Allow the depth parameter to take values from an arbitrary ordered set.

Note that even proof-checking doesn't work for all possible programs ─ not everything true is provable. But it's generally acceptable for compiled languages to reject programs which are correct but not provably correct.

$\endgroup$
2
  • 4
    $\begingroup$ If you choose the 2nd option, and your language has closures, then you have to make sure to also ban mutation of closures by mutating their local variables, which is basically equivalent to mutating objects. For example this Python code doesn't appear to directly mutate any objects, but still produces a self-referential closure object. $\endgroup$
    – pxeger
    May 16, 2023 at 22:08
  • $\begingroup$ @pxeger Good point ─ there are more "objects" to consider than just what we normally think of by that word. $\endgroup$
    – kaya3
    May 16, 2023 at 22:16
10
$\begingroup$

Yes, we do this in Roc. There's no way to express a cyclic data structure in Roc, and we rely on this invariant for our memory management design: we use automatic reference counting with no cycle detection.

There isn't a dedicated error message for cyclic data or anything; in Roc, all assignments are (effectively) const and all data structures are semantically immutable, so there is no way to express a cyclic data structure!

$\endgroup$
1
  • 5
    $\begingroup$ How does that work with functions? If you can have recursive functions, return function from functions and pass functions as function arguments, then you can construct mutually recursive function objects (closures). Does Roc rule out one of these? $\endgroup$ May 21, 2023 at 20:52
6
$\begingroup$

Yes...

... at least, if you add some stronger limiting conditions on what the language can do.

One way to prevent cyclic data structures is to make all values immutable. This works because cycles are created by code like this:

let a = new Cell()
let b = new Cell()
a.next = b
b.next = a

If values cannot be mutated after they are created, it is impossible to set both a.next = b and b.next = a. The most you could do would be

let a = new Cell()
let b = new Cell(next = a)
let c = a.copy(next = b)

but you still don't have a cycle in this case, since it's a copy of a that points to b, not a itself.

This may not be the answer you're looking for, since it limits the capabilities of the language in significant ways (for example, preventing data structures like doubly linked lists). However, it is possible to design a usable programming language that works this way. My languages tinylisp and tinylisp 2 are examples. (Caveat: they are both toy languages, and the current implementations are neither compiled nor explicitly garbage-collected; but such an implementation would be possible.)

$\endgroup$
2
  • $\begingroup$ I believe I got around this in Java with some convoluted static variables that were final and initialized to an instance of the other class. $\endgroup$
    – CPlus
    May 16, 2023 at 20:26
  • $\begingroup$ Cycles are also created by recursive definitions of functions. $\endgroup$ May 21, 2023 at 20:53
6
$\begingroup$

Many people have noted you can remove mutability, which gets rid of cycles. However, it’s not all mutability which causes cycle, just aliased mutability.

For instance, in safe rust you can’t form cycles because to close the reference loop you would have to send a mutation through the loop, which would prevent it being read and therefore a reference to it being formed.

$\endgroup$
1
  • $\begingroup$ This is a good point ─ Rust's ownership semantics imply that a value cannot indirectly own itself, so recursive types which own their children necessarily cannot be cyclic. $\endgroup$
    – kaya3
    May 16, 2023 at 23:31
3
$\begingroup$

Mercury did this for many years, because it had no way to express binding a free variable after it was already in a structure. The result of this is that the only data structures you could build were bottom-up. We did this because we hadn't implemented that part of the mode checker yet, and we got quite far without it.

(Technical aside: See Charlie Lidbury's answer; what Mercury's mode checker specifically couldn't handle yet was aliasing of free variables.)

"Sound" dialects of Prolog also have no cyclic data structures, but it is enforced at run-time via the occurs check. The ISO standard states that this behaviour is optional for normal unification, but also provides a sound variant unify_with_occurs_check/2, as well as acyclic_term/1 which does exactly what you think it does.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .