[gclist] Is reachabilty decidable?

[Charles Fiterman]

We can clearly build trivial languages where reachabiltiy
is decidable. In useful languages it clearly is not.

  if (anUndecidableProposition())
    use(x);

The Church Turing theorem guarantees that in any system
at least as strong as arithmetic you can write 
anUndecidableProposition();

But we can make conservative assumptions which allow
the deletion of some objects. The most conservative
assumption is to never delete.

This is simply a quality of implementation issue. The
more we can delete without going too far the better.
At end of job everything is deleteable.

This is different from finalization issues where the
question is does object A require a (pre|post)finalized
version of object B. Here mutator semantics rules.
At end of job everything unfinalized must be finalized 
the only question is what order to do it in.

In finalizers the quality of implementation issue is to
run the finalizers as soon as we can but never sooner.
This is tied to the deletion issue.

It suddenly occurs to me that a compiler could discover
cases where a reference count was sufficient and
use that. Reference counting frees things as soon as
possible.
			-  
Charles Fiterman		Geodesic Systems
414 North Orleans Suite 410	Phone 312 832 1221 x223
Chicago IL 60610-4418		FAX   312 832 1230
				http://www.geodesic.com

A computer language without garbage collection
  is like a city without garbage collection.