<p>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.</p>
<p>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.</p>
<p>Is there a way to enforce no cyclic data structures at compile time?</p>

<garbage-collection><data-structures><compiler-checks><compilers>
Can "no cyclic data structures" be enforced at compile time?
CC BY-SA 4.0
2023-05-16T18:45:18.357Z
I wouldn't be surprised if this is equivalent to the halting problem ...
Glorfindel
CC BY-SA 4.0
2023-05-16T18:46:44.563Z
@Glorfindel Well, many existing languages do have turing-complete type systems. Not sure if this would be that sort of situation (where you'd have to go way out of your way to actually take advantage of that) or if a busy beaver type thing could feasibly come up during compilation of normal code for detecting cyclic data structures.
rydwolf
CC BY-SA 4.0
2023-05-16T18:50:24.640Z
This is more than just checking types, unless you encode closures’ capture lists in their types.
Bbrk24
CC BY-SA 4.0
2023-05-16T18:51:55.663Z
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.
Silvio Mayolo
CC BY-SA 4.0
2023-05-16T18:52:01.753Z
@Bbrk24 I suppose that'd be possible right?
rydwolf
CC BY-SA 4.0
2023-05-17T00:42:01.783Z
Such structures are useful, though.
Karl Knechtel
CC BY-SA 4.0
2023-05-17T01:47:03.607Z
@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)
rydwolf
CC BY-SA 4.0
2023-05-17T01:56:08.960Z
Another way to emulate cyclic data structures is to create an extra layer of indirection in user code: everything that can participate in a cycle lives in a flat data structure, and contains keys into that data structure. I'd imagine it comes with a performance hit, but depending on the structure it might still optimize well.
Unrelated String
CC BY-SA 4.0
2023-05-17T02:00:19.543Z
@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.
rydwolf
CC BY-SA 4.0
2023-05-17T02:21:31.717Z
Note that this will make closures a bit tough to work with. You could either ban mutation involving closures or make each closure a separate type (like Rust does). Both are unappealing :(
user
<p>Yes, we do this in <a href="https://roc-lang.org" rel="noreferrer">Roc</a>. 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.</p>
<p>There isn't a dedicated error message for cyclic data or anything; in Roc, all assignments are (effectively) <code>const</code> and all data structures are semantically immutable, so there is no way to express a cyclic data structure!</p>

CC BY-SA 4.0
2023-05-16T19:41:54.900Z
2023-05-16T19:41:54.900Z
rtfeldman
CC BY-SA 4.0
2023-05-21T20:52:50.390Z
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?
Gilles 'SO- stop being evil'
<p>Yes, it can be. There are three simple ways:</p>
<ul>
<li>Ban recursive type definitions, so e.g. a <code>Foo</code> can't have a field of type <code>Foo</code>, or a field of type <code>Bar</code> if <code>Bar</code> has a field of type <code>Foo</code>; and this also must apply to generics, so e.g. <code>Foo</code> cannot implement the interface <code>List&lt;Foo&gt;</code> or <code>List&lt;Bar&gt;</code>. 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.</li>
<li>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 &quot;objects&quot;, but anything that might hold a reference while also being referenced, including closures, or local variables in languages which allow direct references to those.)</li>
<li>Ban everything. All programs fail at compile time.</li>
</ul>
<p>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?</p>
<p>Probably the other two options also throw out too much baby for your liking, but they <em>are</em> 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:</p>
<ul>
<li>Allow recursive type definitions, but fields which could allow for reference cycles must be read-only and not lazily initialised.</li>
<li>Use runtime checks, but enforce the use of these checks in the type system. For example, if <code>Foo</code> is your recursive type then make it generic in a &quot;depth&quot; parameter, so that <code>Foo&lt;N&gt;</code> can only hold references to <code>Foo&lt;M&gt;</code> when M &lt; N, and the assignment <code>foo1.child = foo2;</code> is a type error if it isn't guarded by the appropriate check.</li>
<li>Require the programmer to write a proof that M &lt; N, and check the proof at compile-time. Allow the depth parameter to take values from an arbitrary ordered set.</li>
</ul>
<p>Note that even proof-checking doesn't work for <em>all</em> 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.</p>

CC BY-SA 4.0
2023-05-16T19:21:15.427Z
2023-05-16T22:19:27.693Z
2023-05-16T22:19:27.693Z
kaya3
CC BY-SA 4.0
2023-05-16T22:08:22.410Z
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](https://ato.pxeger.com/run?1=PU85DsJADOz3FZYoCBI0qRASX-APIcwmC4sXbbw53kKTBp5Dz28wBJhuPJ6x53q_DFIHHsdbErtaPx8HWCp9aFJEttgYUvS0pV1gfMhbd8yIWZ9_9Tc4sA9l4an_j_pcfRONkBR58hljdf4_YWxmF2amAR1pckMNvF1FWESwuMIvCS2Y9MtU1eSEzq6qRddwJu9OoA7zFupXJUkhOFDBA4X9EaVMrb7lfiVf) doesn't appear to directly mutate any objects, but still produces a self-referential closure object.
pxeger
CC BY-SA 4.0
2023-05-16T22:16:51.377Z
@pxeger Good point ─ there are more "objects" to consider than just what we normally think of by that word.
kaya3
<h1>Yes...</h1>
<p>... at least, if you add some stronger limiting conditions on what the language can do.</p>
<p>One way to prevent cyclic data structures is to make all values immutable. This works because cycles are created by code like this:</p>
<pre><code>let a = new Cell()
let b = new Cell()
a.next = b
b.next = a
</code></pre>
<p>If values cannot be mutated after they are created, it is impossible to set both <code>a.next = b</code> and <code>b.next = a</code>. The most you could do would be</p>
<pre><code>let a = new Cell()
let b = new Cell(next = a)
let c = a.copy(next = b)
</code></pre>
<p>but you still don't have a cycle in this case, since it's a copy of <code>a</code> that points to <code>b</code>, not <code>a</code> itself.</p>
<p>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 <a href="https://github.com/dloscutoff/Esolangs/tree/master/tinylisp" rel="noreferrer">tinylisp</a> and <a href="https://github.com/dloscutoff/tinylisp2" rel="noreferrer">tinylisp 2</a> 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.)</p>

CC BY-SA 4.0
2023-05-16T19:05:55.617Z
2023-05-16T19:05:55.617Z
DLosc
CC BY-SA 4.0
2023-05-21T20:53:45.527Z
Cycles are also created by recursive definitions of functions.
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-16T20:26:15.787Z
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.
CPlus
<p>Many people have noted you can remove mutability, which gets rid of cycles. However, it’s not all mutability which causes cycle, just <em>aliased</em> mutability.</p>
<p>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.</p>

CC BY-SA 4.0
2023-05-16T23:19:05.240Z
2023-05-16T23:19:05.240Z
Charlie Lidbury
CC BY-SA 4.0
2023-05-16T23:31:18.013Z
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.
kaya3
<p><a href="https://mercurylang.org/" rel="nofollow noreferrer">Mercury</a> 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.</p>
<p>(Technical aside: See Charlie Lidbury's answer; what Mercury's mode checker specifically couldn't handle yet was aliasing of free variables.)</p>
<p>&quot;Sound&quot; dialects of Prolog also have no cyclic data structures, but it is enforced at run-time via the <a href="https://en.wikipedia.org/wiki/Occurs_check" rel="nofollow noreferrer">occurs check</a>. The ISO standard states that this behaviour is optional for normal unification, but also provides a sound variant <code>unify_with_occurs_check/2</code>, as well as <code>acyclic_term/1</code> which does exactly what you think it does.</p>

CC BY-SA 4.0
2023-05-16T23:13:21.890Z
2023-05-17T01:18:59.430Z
2023-05-17T01:18:59.430Z
Pseudonym
# Can "no cyclic data structures" be enforced at compile time?
Posted by: username_0 on 2023-05-16
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?
**Tags:** garbage-collection data-structures compiler-checks compilers
> **Comments:**
> **username_1**: I wouldn't be surprised if this is equivalent to the halting problem ...  
> **username_0**: @Glorfindel Well, many existing languages do have turing-complete type systems. Not sure if this would be that sort of situation (where you'd have to go way out of your way to actually take advantage of that) or if a busy beaver type thing could feasibly come up during compilation of normal code for detecting cyclic data structures.  
> **username_2**: This is more than just checking types, unless you encode closures’ capture lists in their types.  
> **username_3**: 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.  
> **username_0**: @Bbrk24 I suppose that'd be possible right?  
> **username_4**: Such structures are useful, though.  
> **username_0**: @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)  
> **username_5**: Another way to emulate cyclic data structures is to create an extra layer of indirection in user code: everything that can participate in a cycle lives in a flat data structure, and contains keys into that data structure. I'd imagine it comes with a performance hit, but depending on the structure it might still optimize well.  
> **username_0**: @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.  
> **username_6**: Note that this will make closures a bit tough to work with. You could either ban mutation involving closures or make each closure a separate type (like Rust does). Both are unappealing :(  
---
## 5 answers
### Answer by username_9 on 2023-05-16. Score: 26
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` or `List`. 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` can only hold references to `Foo` 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.
> **Comments:**
> **username_10** (2023-05-16): 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](https://ato.pxeger.com/run?1=PU85DsJADOz3FZYoCBI0qRASX-APIcwmC4sXbbw53kKTBp5Dz28wBJhuPJ6x53q_DFIHHsdbErtaPx8HWCp9aFJEttgYUvS0pV1gfMhbd8yIWZ9_9Tc4sA9l4an_j_pcfRONkBR58hljdf4_YWxmF2amAR1pckMNvF1FWESwuMIvCS2Y9MtU1eSEzq6qRddwJu9OoA7zFupXJUkhOFDBA4X9EaVMrb7lfiVf) doesn't appear to directly mutate any objects, but still produces a self-referential closure object.  
> **username_9** (2023-05-16): @pxeger Good point ─ there are more "objects" to consider than just what we normally think of by that word.  
---
### Answer by username_7 on 2023-05-16. Score: 10
Yes, we do this in [Roc](https://roc-lang.org). 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!
> **Comments:**
> **username_8** (2023-05-21): 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?  
---
### Answer by username_11 on 2023-05-16. Score: 6
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.)
> **Comments:**
> **username_12** (2023-05-16): 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.  
> **username_8** (2023-05-21): Cycles are also created by recursive definitions of functions.  
---
### Answer by username_13 on 2023-05-16. Score: 6
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.
> **Comments:**
> **username_9** (2023-05-16): 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.  
---
### Answer by username_14 on 2023-05-16. Score: 3
[Mercury](https://mercurylang.org/) 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](https://en.wikipedia.org/wiki/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.
---
