[gclist] Finalization and object orientation.

[Fergus Henderson]

Eliot Miranda <eliot@parcplace.com> wrote:
> 
> Hans Boehm wrote:
> > 
> > It would be hard to require it to do something precise without seriously
> > inhibiting optimization.  Certainly it could not require that unreachable
> > objects with finalize methods be finalized.  (Gosling, Joy, and Steele
> > define a reachable object to be one that "can be accessed in any potential
> > continuing computation from any live thread".  This is clearly undecidable
> > in general.)
> 
> It is undecidable only in systems allowing the computation (forgery) of
> object pointers.
>
> In languages like Java, Smalltalk, Self etc where one
> can only construct a valid pointer by instantiation, and where there is
> no computation on object pointers then it is impossible to forge or
> otherwise disguise pointers.  In this context it is a decidable problem
> (a scan followed by a trace will divide objects into reachable and
> unreachable ones).

No, Hans is right, reachability as defined above is in general
undecidable even in systems which don't allow forgery of object
pointers.  Unreachability is semidecidable, which is what enables
garbage collection to work, but reachability is not decidable. 
A scan followed by a trace will only divide objects into definitely
unreachable and possibly reachable.

Consider e.g.

	foo() {
		Object x = new Object;
		bar();
		x.do_something();
	}

If `bar()' cannot terminate, then `x' is unreachable as soon as
bar() has been entered.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.