Lambda the Ultimate

What is the state of the art? The Cheng-Blelloch collector?

Metronome, Schism, Pauseless, and more.

I don't see how the tight restrictions create doubt about the claim itself. I think we're all agreeing that a truly immutable memory model enables simpler memory management, but you're mentioning that these systems are essentially nonexistent "in the wild". I think this is also true*, but doesn't invalidate the claim except insofar as it was linked to some assertion of wider current practical application. I think it is important to keep track of these results, though, so the interested language-environment developer can make the best tradeoff decisions between pure and impure systems. I'd definitely be interested in seeing what the state of the art is.

* I recently talked about immutable-memory garbage collection with J Moore in the context of ACL2, one of the most "purely functional" programming environments in actual and heavy use. He mentioned that immutable memory algorithms rarely apply to ACL2 as they mangle the heap "under the covers" with imperative code to achieve practical performance.

Perhaps 'misleading' would be a better adjective than 'dubious'. The claim voiced by Ben has been uttered by many others over years, to the extent that many people assume languages like Haskell take significant advantage of it.

This is changing, but I think is mostly an artifact of the GC community focusing on GC for Java-like languages. Important Haskell figures are getting into the game these days, e.g.

"Multicore Garbage Collection with Local Heaps" Simon Marlow and Simon Peyton Jones in ISMM 2011 (sorry, couldn't find a PDF as yet).

E.g. there are some real-time and concurrent GCs that use employ replication, which is considerably easier if said replicated objects are immutable. IIRC Schism, which is for Java, uses limited replication of arraylet spines, which are the only truly immutable kind of data structure it manages.

I heavily use replication of immutable value structures for distributed programming, and I agree that this can modularize some GC - essentially, we can potentially collect independent heaps at cost of redundant space and time to perform copies.

OTOH, if we need replication then we certainly have concurrency in the model (and thus will have plenty of mutable objects to deal with anyway). Also, replication does not mix happily with laziness.

I don't think concurrency implies lots of mutable objects necessarily, but the context I was referring to is a concurrent collector that replicates immutable objects. In this type of GC, parts of the application may still refer to older versions of the replicated object while other parts may refer to the replicated (new) version of the object. Obviously if it is immutable the application can't tell the difference. The GC just has to guarantee that the older versions of the object will eventually be collected, perhaps one or two GC cycles later. This requires more slack heap space but allows the concurrent GC to have a more efficient (or perhaps no) read barrier.

Developing a GC that is 'aware' of which objects are mutable and which are not, and can take appropriate advantage, introduces its own form of complexity. That complexity might be worth some alleged performance benefits, but does undermine an argument that GC is somehow 'easier'. We don't need pervasive mutability before we pay for mutability.

I think we'd get a better GC argument out of sub-structural constraints - linearity, regions, connections, et cetera.

You bring up laziness and parallel evaluation as a counter-arguments to his claim that immutability makes GC an easier problem. I don't get it -- to me this looks like you are making a (bad) choice of evaluation strategy on purpose, and from that we are to infer that his claim is somehow irrelevant/wrong.

I think it's safe to claim that we can certainly build many real (and relevant) systems in Haskell or Clean, which are brilliant examples of pure programming languages out there in the wild. There are also strict (and pure) languages out there, but they are certainly not as widely used as the two previous examples. Habit was mentioned here on LtU a while ago.

This is a by no means any hard evidence, but I'm prepared to accept that it seems likely from what we know right now that we can build real and relevant systems in Habit or other pure languages as well. There should be less mutation since no laziness is involved, and that in turn should allow the GC constructor to optimize the common case -- which is immutable data. The GC still needs to handle the mutable case, but it might suffice with slow code that is "obviously correct" or "easy" to prove.

Haskell and Clean do not benefit from purity wrgt. garbage collection. Clean uses linearity (uniqueness typing) to support in-place updates. Haskell achieves the same with STRef, IORef, along with laziness and parallel evaluation and cyclic references.

The claim doesn't regard whether we can build relevant systems in pure languages, only whether immutability simplifies GC in practice. It doesn't, or at least I've not seen a benefit in any language that ever made it out of the lab.

Certainly, many garbage collectors are optimized for the common case of immutable data. That doesn't make GC easier, but it does affect design choice. Working with immutable data has its own price: you'll tend to produce a lot more garbage.

The Rust language, recently from Mozilla, includes an acyclic heap of immutable data that is handled specially by the GC (it's ref-counted).

What benefit is the 'immutability' offering to the GC?

How are you going to maintain the acyclic invariant if mutation can introduce cycles? (I know you're aware of the obvious issue, so this is an honest question).

BTW: It's also possible to detect cycles at data construction time, allowing 'letrec' style sharing while also getting a simple one pass mark and sweep or ref counted garbage collector (with a little extra overhead to keep the strongly connected components identified).

You can prevent generating cycles via linearity, or other sub-structural types (such as generating a 'height' attribute for types as seen in finger trees, B-trees, or non-homogeneous lists), or various other mechanisms. If maintaining the acyclic constraint is all you're worried about, immutability is both an excessive constraint, and seemingly orthogonal.

There are many good reasons for purity, of course, but I'm just not seeing how avoiding cycles is among them.

a little extra overhead to keep the strongly connected components identified

This isn't making GC any easier. ;-)

Certainly, you can prevent cycles with various mechanisms, but Rust does it with immutability. I'm not a Rust developer, but I don't think they want to add the fancier substructural features you're talking about.

..benefit in any language that ever made it out of the lab.

There's plenty of non-lazy impure languages that are used in the wild. There's also some lazy and pure languages used in the wild. For some reason there aren't many non-lazy and pure languages around, even in a research setting. I think that is a partial answer to why there haven't really been any non-lazy and pure languages that has made it out of the lab. Beyond this - we all know that market share is not only based on technical merits.

Working with immutable data has its own price: you'll tend to produce a lot more garbage.

Working with immutable data has its own benefits: there is plenty of room for radical optimizations like deforestation.

Sure, immutability doesn't much help GC in practice largely because state-of-the-art languages do not constrain themselves to take advantage of it. But why should they? Why constrain yourself to improve GC a little when you could be focusing on parallelism, reactivity, hot-spot compilation, and other features that will inevitably utilize mutable shared memory under-the-hood? Technical merits are not necessarily on the side of dubious optimizations for GC.

If we want to see major GC improvements, I believe the winning approach will simply be a more explicit, declarative model of resource costs and consumption... e.g. linear logic, temporal logic, Kleisli arrows or others that allow static analysis of resources used, et cetera. We can simplify GC, or even eliminate need for it (e.g. generating fixed-memory processes for mission-critical systems).

Working with immutable data has its own benefits

I agree! But the question here is whether there are practical benefits for garbage collection that will survive 'in the wild'.