Re: Static Garbage Collection

Le Mon, 25 May 2009 21:28:01 +0200, Matthias-Christian Ott a C)critB :


> Hi,
> today I stumbled upon a very intresting problem on garbage collection:
>
> Suppose we have a goto-free, pointer-less, static strongly typed
> programming language without any binary libraries (so all source code is
> available at compile time).
>
> Then we could construct the control flow graph for the entire programme.
>
> Couldn't we than statically (of course depending on conditions during
> runtime) determine the locations for the appropriate malloc() and free()
> calls, depending on if a referenced object is no longer used?
>
> The result would be same as if you manually managed you memory, so you
> would have no runtime overhead garbage collection, just for the tests of
> the user input, because we can predict everything that does not depend
> on user input at compile time.
>
> Regards,
> Matthias-Christian
> [This feels like it's equivalent to the halting problem which is known
> to be insoluble in the general case, albeit often soluble in specific
> instances. -John]


If you have a tree structure for your objects, it's obvious : you just
have to count reference on objects and then delete objects when the count
reach 0.


If you have a graph structure, it's quite difficult. If you have a loop
with your objects, you won't be able to delete it even if it's not
referenced anymore.


One way to solve the problem is to qualify references.
You can have mandatory references (from a local, a global or an argument).
You can have tree references (with such a reference you can only define
tree structure : only one tree reference on one object and no loops).
Then you can have share references (i.e. all the others references).


With this definitions, an object can be deleted only if there is no
mandatory nor tree references on it. If there is no mandatory nor tree
references then you have you cases :
- there is no share references on the object then you can delete it.
- there is at least one share reference left then you must check if you
can delete the object. For this case, it's a garbage collector problem.


With qualified references, you can reduce the needs for a garbage
collector but you still have a need for it.

Return to the comp.compilers page.
Search the comp.compilers archives again.