What would a language look like in which precise GC was implementable as a library?

Question

Suppose you have some programming language with manual memory management. What features does this language need to have in order to be able to implement precise garbage collection as a library, and not as a fundamental language construct?

By a precise GC I mean one where only pointers to the heap are traversed to ascertain which variables are or are not live.

Some additional considerations:

• C and C++ have the Boehm garbage collector, but I don't count this since it's not a precise GC. The Boehm collector assumes that anything on the stack that could be a pointer, based purely on memory alignment requirements, is a pointer. For example, any integer k such that (k % 4) == 0 looks at a bit level like a pointer, since pointers must be 4-byte aligned.
• magpie transforms existing C code to use a precise garbage collector. The generated C code has a lot of stubs for garbage collection, i.e. stuff for registering any stack pointers into the heap with the collector. I don't count this because no one could ever be expected to write code that way; it's more of a compilation target for other languages.

I imagine that such a language would need to have:

1. Macros or some form of metaprogramming, for encapsulating all of the extra code needed to do things like register GC roots.
2. Some reflective mechanism that allows you to inspect structs or unions; you need to determine which members are pointers.
3. Some reflective mechanism that allows you to examine the stack frame layout. This sounds a lot harder than 2.

I hope this isn't too vague or opinion-based but I've been wondering about it for a while.

Answer 1

I believe that this is possible, or at least nearly possible, in a language like Rust, though perhaps not necessarily in the sense you are thinking.

Rust actually has a GC library, though I can't say how precise it is. But the idea is that, there's a specific type Gc<T> for garbage-collected pointers to values of type T. So the metaprogramming that you're talking about doesn't happen

What makes it possible for this to be precise is Rust's ownership system: because of affine linear typing, every location in memory has at most one pointer to it, unless it's declared using an unsafe block (which is used to implement things like the Garbage collector). So if you have a pointer that's not wrapped in a Gc type, it gets deallocated as soon as it goes out of scope. So it's not possible to consider something as a pointer that isn't: either it's wrapped in the Gc type, or it's singly-owned and automatically deallocated.

Every type has an implicit drop method that's called when it goes out of scope, that deallocates things it points to. This drop method is aware of what is and isn't a pointer, which also helps with precision.

The language is strongly, statically typed, and unless you specifically are in an unsafe block, you can't cast things to other types, so it can be statically known what type a given chunk of memory has.

This isn't a drop-in transformer that lets you treat Non-GC code as Garbage collected. The programmer specifically specifies what values are collected. But given that, I think it has the potential to meet your criteria.

Answer 2

I think it is possible to implement a garbage collector in C++ without changing the language itself. But in order to use the garbage collector, one must restrict the programmer from using arbitrary language constructs. In particular, all memory allocation requests must be done through the allocation APIs given by the garbage collector, and all the access must be done through references that is managed by the garbage collector.