7
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Commented Feb 26 at 1:51
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chris Dodd
    Commented Feb 26 at 22:41
  • $\begingroup$ @ChrisDodd It counts as garbage collection if it is done at compile time? $\endgroup$
    – Delfin
    Commented Feb 27 at 0:14
  • $\begingroup$ @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? $\endgroup$
    – IMSoP
    Commented Feb 27 at 9:02
  • $\begingroup$ @IMSoP I yes like roc-lang.org does $\endgroup$
    – Delfin
    Commented Feb 27 at 15:38

2 Answers 2

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's what I said in "If they are not, would ..." $\endgroup$
    – user23013
    Commented Feb 27 at 0:48
3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ "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. $\endgroup$
    – Pseudonym
    Commented Feb 26 at 0:28
  • $\begingroup$ @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... $\endgroup$
    – Cort Ammon
    Commented Mar 13 at 14:04
  • $\begingroup$ ... 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) $\endgroup$
    – Cort Ammon
    Commented Mar 13 at 14:05
  • $\begingroup$ @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. $\endgroup$
    – Miss Understands
    Commented Jul 3 at 1:15
  • $\begingroup$ @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. $\endgroup$
    – Pseudonym
    Commented Jul 3 at 2:25

You must log in to answer this question.

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