Implement reference counting about purec HOT 10 CLOSED

This feature has been completed! 🎉

I am very happy with the state of the project now. All packages featured in the bundled package-set build fine and their test suits run fine without leaking. Additionally, all upstream tests are passing incl. leak checks. In addition to the reference counting GC it's also possible to alternatively enable the tracing GC instead if required. The resulting binaries are small and perform at least on par with the JS equivalent. There's undoubtedly more optimizations that could be done, at the corefn level, the support library level and code-gen level, but so far the code is reasonably optimized and performing well enough for this to be a useful backend.

from purec.

One thing to consider is that you still have to handle cyclical references somehow.

from purec.

I am trying to think of a PureScript program that would result in cyclic references, do you have an example on top of your head?

from purec.

Cyclical references require mutation, so it can be done with Lazy or a Ref. For example, anything that uses Lazy.fix is cyclical https://github.com/purescript/purescript-control/blob/v4.1.0/src/Control/Lazy.purs#L22-L25.

from purec.

So a Ref would point to itself either directly or indirectly? I think we could get away with a warning not to do that and information on how to probe for leaks (or assume that knowledge, given the context). I cannot see the cycle using Lazy.fix, however. Do you mind explaining it to me?

from purec.

The cycle depends on the implementation of defer, which is usually at some point tied with a Data.Lazy. Probably the simplest example with lazy lists is:

xs = defer \_ -> cons 42 xs

This will be a single cons node that points back to itself.

from purec.

You can tie knots with Ref mutation.

data MutableList a = Nil | Cons a (Ref (MutableList a))

loop = do
  tail <- Ref.new Nil
  let list = Cons 42 tail
  Ref.write list tail
  pure tail

from purec.

Thank you for elaborating on this. Given they both require mutation (and therefore FFI), I doubt we can statically pick up on those. I wonder if going hybrid would be possible, such that FFI allocated values could be gc-allocated or require an explicit release function be called on them.

from purec.

I haven't read it yet, but collecting cycles seems to be a solved problem as well: https://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf. From a bit of research many languages take this approach - python and php to name a prominent few.

from purec.

Congrats!

from purec.