Hacker News Reader

Comment by fauigerzigerk | Hacker News Reader

I've been wondering about garbage collection in pure functional languages lately. It is often said that statically typed pure functional languages allow the compiler to do a lot more correctness checking. Shouldn't the same formal reasoning features also enable much better garbage collection algorithms? Or would that be asking for a solution to the halting problem?

View on HN

There's lots of interesting optimizations enabled by immutable data. E.g. in generational collectors old data can never point at new data, which can be used to gain additional performance.

see e.g. http://research.microsoft.com/en-us/um/people/simonpj/papers...

Though the GHC runtime isn't an example of immutable data. Haskell code actually results in a lot of mutation behind the scenes. It's quite possible for older generations to point to data in newer generations in Haskell. It's even likely with some use patterns.

Given that you already know this, I assume you must be talking about strict functional languages specifically.

Are you referring to thunk update after lazy evaluation? This is a very special kind of mutation, because after the update, it is guaranteed never to be mutated again. This is quite helpful for generational GC, actually, and underlies the concept of "eager promotion".

With a purely linear type system, memory management could be handled statically, negating the need for traditional GC. The underlying behavior would be closer to C-style just-in-time {de-}allocation, or C++ RAII. LinearML is an attempt at this: https://github.com/pikatchu/LinearML

Regarding Linear Type Systems and friends I recommend reading parts of Jesse Tov's PhD thesis [1], "Practical Programming with Substructural Types". I found parts of it pretty accessible as an undergraduate. In particular he uses substructural types to put types on the network protocol of a server and client. Neat stuff.

There's also the wikipedia page on Substructural Types [2].

[1] http://www.eecs.harvard.edu/~tov/pubs/dissertation/

[2] http://en.wikipedia.org/wiki/Substructural_type_system

That's awesome! Any good pointers to interesting articles about that? I found this: http://www.eg.bucknell.edu/~lwittie/research/space04.pdf

Don't know of any articles, but there are a number of papers on linear logic and linear type theory. Most are pretty dense, but the first few pages of Wadler's "Linear types can change the world!" give a very readable overview of the area. http://homepages.inf.ed.ac.uk/wadler/papers/linear/linear.ps

It should, yes. AIUI the state of the art in the JVM is that we can do all the marking and sweeping in parallel, it's just heap compaction that requires a "stop the world" pause. If the VM had visibility over which objects were referentially transparent, it should be possible to compact those easily.

(Sadly even that doesn't mean a truly pauseless garbage collector - the "heap of non-referentially transparent objects" will still eventually fragment to the point of filling up)

And also there are interesting approaches to "GC optimizations", but so far unported to Haskell: http://www.it.edu/people/mael/mypapers/tldi03.pdf

Thanks, unfortunately I'm getting a 404 Not Found when I click on the link...

Looks like the author changed institutions and the paper moved: http://www.elsman.com/tldi03.pdf

There are some things to gain, but they're implemented mostly by experimental languages, e.g. DDC has regions.

Reply on news.ycombinator.com