7 ms·

I've been wondering about garbage collection in pure functional languages lately. It is often said that statically typed pure functional languages allow the com

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?

jallmann 13y ago
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 https://github.com/pikatchu/LinearML
- danking00 13y ago
  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/ http://www.eecs.harvard.edu/~tov/pubs/dissertation/ [2] http://en.wikipedia.org/wiki/Substructural_type_system http://en.wikipedia.org/wiki/Substructural_type_system
- ithkuil 13y ago
  That's awesome! Any good pointers to interesting articles about that? I found this: http://www.eg.bucknell.edu/~lwittie/research/space04.pdf http://www.eg.bucknell.edu/~lwittie/research/space04.pdf
  - jallmann 13y ago
    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 http://homepages.inf.ed.ac.uk/wadler/papers/linear/linear.ps
dons 13y ago
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/parallel/local-gc.pdf http://research.microsoft.com/en-us/um/people/simonpj/papers...
- chowells 13y ago
  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.
  - ezyang 13y ago
    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".
miga 13y ago
And also there are interesting approaches to "GC optimizations", but so far unported to Haskell: http://www.it.edu/people/mael/mypapers/tldi03.pdf http://www.it.edu/people/mael/mypapers/tldi03.pdf
- fauigerzigerk 13y ago
  Thanks, unfortunately I'm getting a 404 Not Found when I click on the link...
  - mjn 13y ago
    Looks like the author changed institutions and the paper moved: http://www.elsman.com/tldi03.pdf http://www.elsman.com/tldi03.pdf
lmm 13y ago
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)
IsTom 13y ago
There are some things to gain, but they're implemented mostly by experimental languages, e.g. DDC has regions.

jallmann 13y ago

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 https://github.com/pikatchu/LinearML

danking00 13y ago
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/ http://www.eecs.harvard.edu/~tov/pubs/dissertation/ [2] http://en.wikipedia.org/wiki/Substructural_type_system http://en.wikipedia.org/wiki/Substructural_type_system
ithkuil 13y ago
That's awesome! Any good pointers to interesting articles about that? I found this: http://www.eg.bucknell.edu/~lwittie/research/space04.pdf http://www.eg.bucknell.edu/~lwittie/research/space04.pdf
- jallmann 13y ago
  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 http://homepages.inf.ed.ac.uk/wadler/papers/linear/linear.ps

dons 13y ago

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/parallel/local-gc.pdf http://research.microsoft.com/en-us/um/people/simonpj/papers...

chowells 13y ago
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.
- ezyang 13y ago
  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".

miga 13y ago

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

fauigerzigerk 13y ago
Thanks, unfortunately I'm getting a 404 Not Found when I click on the link...
- mjn 13y ago
  Looks like the author changed institutions and the paper moved: http://www.elsman.com/tldi03.pdf http://www.elsman.com/tldi03.pdf

lmm 13y ago

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)

IsTom 13y ago

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