The halting problem and garbage collection

At Talk Day, after Brandon Bradley’s talk about the halting problem, Martha Kelly asked: if it’s impossible to predict the future course of an arbitrary program, how can garbage collectors tell which objects will be used and which can be collected?

Martha’s right. There is a connection!

    function easy() {
        var obj = new Object;
        gc();
    }

If gc() does garbage collection, then certainly it could collect the new Object, since we are never going to use it. But many garbage collectors will not collect it yet, since there is still a variable referring to that object.

You might think, well, those garbage collectors are stupid. If I ever wrote a garbage collector, it would be perfectly precise, retaining only objects that the program will use in the future, and collecting all others.

Alas, there’s a simple halting-problem-like proof that a perfectly precise garbage collector is impossible.

    function hard() {
        var obj = new Object;
        var objWasGarbage = isThisObjectGarbageOrNot(obj);
        gc();
        if (objWasGarbage)
            alert(obj);
    }

The Catch-22 goes like this:

• If isThisObjectGarbageOrNot(obj) returns true, then the Object is not garbage. It will be used later by alert(obj).
• But if it returns false, then the object really is garbage: it will never be used.

So it seems the function isThisObjectGarbageOrNot() cannot possibly live up to its name in this case. But that is exactly the function which our perfect garbage collector would need in order to do its job perfectly! Therefore a perfect GC cannot exist.

Real GCs err on the side of caution and retain any objects that aren’t known to be garbage. They use reachability as a (conservative) estimate of which objects the program will use in the future.