[gclist] Finalization and object orientation.

Eliot & Linda elcm@pacbell.net
Fri, 28 Mar 1997 10:39:08 -0800

Fergus Henderson wrote:
> 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.

Right, I see.  My thinking is too coloured by Smalltalk and Self where
execution state is reified as objects (Contexts).  In these languages
reachability is decidable because the activation of a message is 
represented by object, and hence temporary references and the like are
just like any other references.  i.e. in foo above x is reachable as
long as the activation of foo is reachable.

So can we agree that in languages which reify execution state and
don't allow pointer forging that reachability is decidable?
Eliot Miranda, ParcPlace-Digitalk