[gclist] Is reachabilty decidable?
Fri, 28 Mar 1997 15:01:32 -0600
We can clearly build trivial languages where reachabiltiy
is decidable. In useful languages it clearly is not.
The Church Turing theorem guarantees that in any system
at least as strong as arithmetic you can write
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
Charles Fiterman Geodesic Systems
414 North Orleans Suite 410 Phone 312 832 1221 x223
Chicago IL 60610-4418 FAX 312 832 1230
A computer language without garbage collection
is like a city without garbage collection.