<p>While thinking about garbage collection, I realized a simple fact that a garbage collector that is more than reference counting is needed because there are circular references, but there are technically no circular references in the basic (untyped) lambda calculus. All circular references are created using function substitution.</p>
<p>So I wonder whether it's possible to get a reasonable garbage collector, by <strong>hypothetically</strong> compiling all code to a <strong>hypothetical</strong> functional programming language that doesn't include extensions to have circular references. But it may need too much work for what a garbage collector is worth.</p>
<p>Meanwhile, in discussions about garbage collection, there are occasionally notes about functional programming languages, implying they may still be relevant.</p>
<p>Are garbage collectors more than reference counting relevant in functional programming languages? When are they relevant?</p>
<p>If they are relevant, is it because a specific feature X, such as memoization, made non-constant time garbage collection absolutely necessary? Or could we say, some other things like cache invalidation has replaced the position of garbage collection, but still had the merit of garbage collection?</p>
<p>If they are not relevant, would the ways simulating mutables always reference something that is actually not needed, to reintroduce garbage collection on the runtime level, or are the difficult situations in garbage collection always correspond to data structures inefficient to implement in pure functional languages, or is there something else, to block such attempts?</p>

<functional-programming><garbage-collection>
When do functional programming languages need advanced garbage collection?
CC BY-SA 4.0
2024-02-26T01:51:29.763Z
It's worth noting that non-circularity can be enforced by static analysis. Some languages do not have support for circular data structures (e.g. Mercury), and in others, non-circularity can be inferred in some cases by the type system.
Pseudonym
CC BY-SA 4.0
2024-02-26T22:41:08.683Z
It bothers me that people keep referring to "reference counting" as if it is not a mechanism for garbage collection.  It is merely one mechanism for garbage collection that has some strengths and drawbacks.
Chris Dodd
CC BY-SA 4.0
2024-02-27T00:14:57.170Z
@ChrisDodd It counts as garbage collection if it is done at compile time?
Delfin
CC BY-SA 4.0
2024-02-27T09:02:38.577Z
@Delfin If *what* is done at compile time? Garbage collection is about freeing memory, so it necessarily *acts* during the execution of the program. Do you mean that the compiler can know enough about the program to insert unconditional "free" instructions at points where reference counts are guaranteed to be zero for all possible program paths?
IMSoP
CC BY-SA 4.0
2024-02-27T15:38:20.533Z
@IMSoP I yes like https://www.roc-lang.org/ does
Delfin
CC BY-SA 4.0
2024-03-07T20:45:59.577Z
@delfin: All forms of garbage collection can benefit from compile-time optimization and analysis to reduce or eliminate runtime overhead.  There's nothing special about reference counting.
Chris Dodd
<p>There are a couple of things going on here:</p>
<p>First, most practical functional programming languages do support cyclic data. Either they include opt-in mutation, or they have some kind of (potentially-lazy) <code>let rec</code> construct, or both. So compiling to one of these languages isn't really sufficient to eliminate cycles, and idiomatic programs in these languages often work with cyclic data structures.</p>
<p>At the same time, reference counting is not universally better than tracing garbage collection even in the absence of cycles. Reference counting has much higher fixed overheads from all the counter updates (optimizations notwithstanding), and allocation in a tracing GC can be much more efficient (just a pointer bump in the nursery). Moving collectors (which essentially require some form of tracing) can also be better at avoiding heap fragmentation.</p>

CC BY-SA 4.0
2024-02-25T22:28:00.307Z
2024-02-26T03:58:14.417Z
2024-02-26T03:58:14.417Z
rpjohnst
CC BY-SA 4.0
2024-02-26T00:28:33.820Z
"Reference counting has much higher fixed overheads from all the counter updates"

That's a debatable point. Modern compiler developers know that counters don't need to be accurate all the time. As with concurrent tracing garbage collection, they only need to be set to conservative values at safe points, which leaves a lot of wiggle room for compiling away reference count manipulation. Buffering increments and decrements also helps with cycle collection because the buffered decrements are precisely the set of potential cycle heads to consider.
Pseudonym
CC BY-SA 4.0
2024-03-13T14:04:48.827Z
@Pseudonym I think there may be value in changing it to "Reference counting **may** have much higher..." but keeping the sentiment.  Correct me if I'm wrong, but it's pretty easy to construct cases where generational garbage collecting gets arbitrarily close to the minimum memory management cost (one pointer op per allocation + an arbitrarily small deallocation cost).  This, of course, assumes the compiler has done all the static analysis (for both the generational and the ref count versions we are talking about).  I think the debatable point is how often these optimal cases occur...
Cort Ammon
CC BY-SA 4.0
2024-03-13T14:05:34.183Z
... in practical usage of a language, and also what the other costs are that aren't associated with that trivialized use case (such as the cost of managing dirty bits)
Cort Ammon
CC BY-SA 4.0
2024-07-03T01:15:44.457Z
@Pseudonym >" counters don't need to be accurate all the time. " == The reference count to memory data, to see if it's still needed or should be collected? How do you figure that the counter doesn't need to be accurate all the time? If it's off by one, you have a memory leak.
Miss Understands
CC BY-SA 4.0
2024-07-03T02:25:46.387Z
@JessFuckett The key thing here is "all the time". The only reference counts that need to be completely accurate are "zero" and "one or more". For one simple example, if a reference to an object is passed in as a parameter to a function, and that reference then subsequently passed around among local variables, you don't need to increment/decrement the reference count for those local variables. Their lifetimes are subsumed by the lifetime of the function parameter.
Pseudonym
CC BY-SA 4.0
2024-07-03T07:30:48.870Z
@Pseudonym By God, you're right.  That's fascinating. Who keeps track of which blocks need to be ref-counted? The compiler, or is this dynamic runtime overhead?
Miss Understands
CC BY-SA 4.0
2024-07-03T11:20:00.090Z
@JessFuckett The point is that some increments and decrements can be optimised away.
Pseudonym
<blockquote>
<p>So I wonder whether it's possible to get a reasonable garbage collector, by hypothetically compiling all code to a functional programming language.</p>
</blockquote>
<p>This doesn't solve garbage collection; you will end up having to write a garbage collector in the target language, as part of your language's runtime library.</p>
<p>There are two types of memory leaks: those where memory is not freed despite being inaccessible via references (i.e. garbage), and those where memory remains accessible via references despite it no longer being needed. Either way, some value is created, and not explicitly or automatically freed, but also not used for the rest of the program.</p>
<p>Your compiler essentially converts all memory leaks into the second kind, because the leaks still logically exist in the program, but the target language cannot express the first kind of leak. The most obvious way this could happen is if an imperative program with mutable state is compiled to a functional program with an immutable &quot;state&quot; value which is updated (immutably); the state will retain all of the same data in memory that the original program did.</p>
<p>It's also worth noting that you can't rely on the existing runtime of the target language to solve this problem. All leaks in your compiled program will be leaks of the second kind, which cannot be solved by a language implementation, only prevented by the programmer (or in your case, the compiler, which knows enough about the source program to implement garbage collection for it). It's uncomputable in general to determine whether still-referenced memory will be later used by a program.</p>

CC BY-SA 4.0
2024-02-26T14:42:22.797Z
2024-02-26T19:00:18.810Z
2024-02-26T19:00:18.810Z
kaya3
CC BY-SA 4.0
2024-02-27T00:48:00.487Z
That's what I said in "If they are not, would ..."
user23013
# When do functional programming languages need advanced garbage collection?
Posted by: username_0 on 2024-02-24
While thinking about garbage collection, I realized a simple fact that a garbage collector that is more than reference counting is needed because there are circular references, but there are technically no circular references in the basic (untyped) lambda calculus. All circular references are created using function substitution.

So I wonder whether it's possible to get a reasonable garbage collector, by **hypothetically** compiling all code to a **hypothetical** functional programming language that doesn't include extensions to have circular references. But it may need too much work for what a garbage collector is worth.

Meanwhile, in discussions about garbage collection, there are occasionally notes about functional programming languages, implying they may still be relevant.

Are garbage collectors more than reference counting relevant in functional programming languages? When are they relevant?

If they are relevant, is it because a specific feature X, such as memoization, made non-constant time garbage collection absolutely necessary? Or could we say, some other things like cache invalidation has replaced the position of garbage collection, but still had the merit of garbage collection?

If they are not relevant, would the ways simulating mutables always reference something that is actually not needed, to reintroduce garbage collection on the runtime level, or are the difficult situations in garbage collection always correspond to data structures inefficient to implement in pure functional languages, or is there something else, to block such attempts?
**Tags:** functional-programming garbage-collection
> **Comments:**
> **username_1**: It's worth noting that non-circularity can be enforced by static analysis. Some languages do not have support for circular data structures (e.g. Mercury), and in others, non-circularity can be inferred in some cases by the type system.  
> **username_2**: It bothers me that people keep referring to "reference counting" as if it is not a mechanism for garbage collection.  It is merely one mechanism for garbage collection that has some strengths and drawbacks.  
> **username_3**: @ChrisDodd It counts as garbage collection if it is done at compile time?  
> **username_4**: @Delfin If *what* is done at compile time? Garbage collection is about freeing memory, so it necessarily *acts* during the execution of the program. Do you mean that the compiler can know enough about the program to insert unconditional "free" instructions at points where reference counts are guaranteed to be zero for all possible program paths?  
> **username_3**: @IMSoP I yes like https://www.roc-lang.org/ does  
> **username_2**: @delfin: All forms of garbage collection can benefit from compile-time optimization and analysis to reduce or eliminate runtime overhead.  There's nothing special about reference counting.  
---
## 2 answers
### Answer by username_8 on 2024-02-26. Score: 4
> So I wonder whether it's possible to get a reasonable garbage collector, by hypothetically compiling all code to a functional programming language.

This doesn't solve garbage collection; you will end up having to write a garbage collector in the target language, as part of your language's runtime library.

There are two types of memory leaks: those where memory is not freed despite being inaccessible via references (i.e. garbage), and those where memory remains accessible via references despite it no longer being needed. Either way, some value is created, and not explicitly or automatically freed, but also not used for the rest of the program.

Your compiler essentially converts all memory leaks into the second kind, because the leaks still logically exist in the program, but the target language cannot express the first kind of leak. The most obvious way this could happen is if an imperative program with mutable state is compiled to a functional program with an immutable "state" value which is updated (immutably); the state will retain all of the same data in memory that the original program did.

It's also worth noting that you can't rely on the existing runtime of the target language to solve this problem. All leaks in your compiled program will be leaks of the second kind, which cannot be solved by a language implementation, only prevented by the programmer (or in your case, the compiler, which knows enough about the source program to implement garbage collection for it). It's uncomputable in general to determine whether still-referenced memory will be later used by a program.
> **Comments:**
> **username_0** (2024-02-27): That's what I said in "If they are not, would ..."  
---
### Answer by username_5 on 2024-02-25. Score: 3
There are a couple of things going on here:

First, most practical functional programming languages do support cyclic data. Either they include opt-in mutation, or they have some kind of (potentially-lazy) `let rec` construct, or both. So compiling to one of these languages isn't really sufficient to eliminate cycles, and idiomatic programs in these languages often work with cyclic data structures.

At the same time, reference counting is not universally better than tracing garbage collection even in the absence of cycles. Reference counting has much higher fixed overheads from all the counter updates (optimizations notwithstanding), and allocation in a tracing GC can be much more efficient (just a pointer bump in the nursery). Moving collectors (which essentially require some form of tracing) can also be better at avoiding heap fragmentation.
> **Comments:**
> **username_1** (2024-02-26): "Reference counting has much higher fixed overheads from all the counter updates"

That's a debatable point. Modern compiler developers know that counters don't need to be accurate all the time. As with concurrent tracing garbage collection, they only need to be set to conservative values at safe points, which leaves a lot of wiggle room for compiling away reference count manipulation. Buffering increments and decrements also helps with cycle collection because the buffered decrements are precisely the set of potential cycle heads to consider.  
> **username_6** (2024-03-13): @Pseudonym I think there may be value in changing it to "Reference counting **may** have much higher..." but keeping the sentiment.  Correct me if I'm wrong, but it's pretty easy to construct cases where generational garbage collecting gets arbitrarily close to the minimum memory management cost (one pointer op per allocation + an arbitrarily small deallocation cost).  This, of course, assumes the compiler has done all the static analysis (for both the generational and the ref count versions we are talking about).  I think the debatable point is how often these optimal cases occur...  
> **username_6** (2024-03-13): ... in practical usage of a language, and also what the other costs are that aren't associated with that trivialized use case (such as the cost of managing dirty bits)  
> **username_7** (2024-07-03): @Pseudonym >" counters don't need to be accurate all the time. " == The reference count to memory data, to see if it's still needed or should be collected? How do you figure that the counter doesn't need to be accurate all the time? If it's off by one, you have a memory leak.  
> **username_1** (2024-07-03): @JessFuckett The key thing here is "all the time". The only reference counts that need to be completely accurate are "zero" and "one or more". For one simple example, if a reference to an object is passed in as a parameter to a function, and that reference then subsequently passed around among local variables, you don't need to increment/decrement the reference count for those local variables. Their lifetimes are subsumed by the lifetime of the function parameter.  
> **username_7** (2024-07-03): @Pseudonym By God, you're right.  That's fascinating. Who keeps track of which blocks need to be ref-counted? The compiler, or is this dynamic runtime overhead?  
> **username_1** (2024-07-03): @JessFuckett The point is that some increments and decrements can be optimised away.  
---
