RE: Compile Time Garbage Collection impossible?

the.real.doctor.zoidberg asked:


> Why isn't Compile-Time-Garbage-Collection feasible? Consider a Java
> compiler which produces assembly code for a specific target instead of
> Java's bytecode cenario. The objective is to use Java without the need
> for a GC or VM.
>
> I'm asking why it isn't possible because otherwise there would be at
> least one compiler to use that technique, instead of having to run a
> GC in the VM.
>
> When a program is compiled, the compiler has to transverse all its
> code to ensure type safety (for safe languages), so what would be the
> problem in "freeing" objects after their scope, or even better, after
> the last reference in their scope?


The general case of static object lifetime analysis would imply a solution
to the Halting Problem.


Consider this case:


function foo (a is object_type_bar)


      if some_function(a) then
            add_to_some_global_container(a);
      else
            // do nothing
      end if


end function


Static analysis of some_function (in the general case) cannot tell us
whether some_function will return TRUE or FALSE based upon input of the
object a. In the case where it returns TRUE -- a is added to a global
container (and therefore must not be destroyed). In the case where it
returns FALSE, a might have no other references to it upon returning from
foo, and may be destroyed "at will".


This is a very "informal" treatment of the problem. For further
enlightenment, see:


http://en.wikipedia.org/wiki/Dead_code


Which contains this statement:


"Determining whether an arbitrary piece of code is unreachable code is
equivalent to solving the halting problem. This means that it is not
possible to correctly locate unreachable code in all cases."


In particular, see this example:


double x = sqrt(2);
if (x > 2)
    {
    xyz
    }


where we replace xyz with "add_to_some_global_container" and sqrt(2) with:


collatz_sequence_terminates(s)


Where s is some arbitrary Collatz sequence. (Do all Collatz sequences
terminate?)


Cheers.


--
Quinn Tyler Jackson

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