How different is garbage collection in pure languages?

Question

In a pure language like Haskell, all data is immutable and no existing data structures can be changed in any way. Additionally, many algorithms on immutable data and functional programming patterns generate large amounts of garbage by nature (chains of map creating intermediate lists for example).

What strategies and techniques do garbage collectors employ in the face of purity that they wouldn't otherwise? What works very well in an impure language's GC that doesn't in a pure context? What other new problems do pure languages create for GCs?

Answer 1

The current implementation of ghc uses a strategy that only works because the language is pure functional and data is immutable: because no variable can ever be altered to refer to anything newer, objects only hold references to older objects, so it runs a generational garbage collector; since an object referred to by a higher generation cannot be deleted until that generation is GCd, it promotes objects to higher generations eagerly; and since nothing is going to alter references while the GC is sweeping them, it can run in parallel.

Here’s a paper with more detail.

Answer 2

In a pure language like Haskell, all data is immutable and no existing data structures can be changed in any way

Actually that is not generally true. Pure languages use non-strict (lazy) evaluation so the evaluation of potentially all subexpressions is deferred. Unevaluated expressions are generally heap allocated as a "thunk". When required the expression is evaluated and the thunk is mutated into the resulting value.

What strategies and techniques do garbage collectors employ in the face of purity that they wouldn't otherwise?

The only thing I can think of is black holes. I don't recall seeing anything else new on the GC side in the Haskell research papers.

What works very well in an impure language's GC that doesn't in a pure context?

The GC write barrier. Impure languages tend to write pointers into the heap a lot more so they tend to have their write barriers more heavily optimised.

Other GC algorithms such as mark-region are much more viable in the context of impure languages because they can have much lower allocation rates than pure languages.

What other new problems do pure languages create for GCs?

Pure languages are very rare so there is a lot less data on how pure programs use memory and, therefore, you are starting in a worse position when trying to write a GC for a pure language.