[gclist] Finalization and object orientation.

[Eliot & Linda]

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