[gclist] Finalization and object orientation.

[Eliot & Linda]

Hans Boehm wrote:
> 
> On Mar 28, 10:39am, Eliot & Linda wrote:
> 
> > So can we agree that in languages which reify execution state and
> > don't allow pointer forging that reachability is decidable?
> 
> I don't think so.  Whether or not the context will be accessed is certainly
> undecidable in general.  In special cases, an agressive collector/compiler
> might sometimes determine that it will not be accessed, and collect dead parts
> of the context.

No, it is decidable.  If one takes the last section of Smalltalk-80: The
Language and its Implementation (the "Blue Book") as an operational
semantics
for Smalltalk then the collector may not e.g. nil references from parts
of a context, and can only collect an entire context.

> I think you really have a different notion of reachability in mind.  I don't
> know how easy it is to formally define your notion for Smalltalk.

Well its true that Contexts make reachability very easy to determine. 
The
Blue Book definition provides an adequate formal semantics.

> Do contexts
> include compiler-introduced temporaries for subexpression results?  Is argument
> evaluation order defined?

Yes.  A context is a fixed-size stack (pre-initialized with the nil
object)
plus slots storing the method, instruction pointer, receiver and sending
context.  The compiler produces polish notation for this simple stack.
Any temporaries are pushed on the context's stack.  Evaluation order is
strictly left-to-right.  A send creates a new context whose sender is
the context that "did the send", copying arguments from one context to
the next.  Returning copies a result from the top context to the stack
of its
sender and makes the sender the current context.  The current context is
part of the root set.  Contexts can be captured, e.g. as part of the
environment of closures, or on process switch.  A process is simply an
object holding a linked-list of contexts.

In this simple model none of the decidability problems arise, but the
implementor is faced with considerable obstacles to achieve acceptable
performance.  But in the absence of optimizations that share temporary
locations or elide object instantiations one can easily maintain a
perfect
illusion of contexts when mapping execution to a real stack and register
set.

For accuracy I should say that ParcPlace's VisualWorks is the only
commercially available Smalltalk that supports contexts, since its
the only one to descend directly from the original PARC implementations.

I'd be interested in hearing from the Self community on whether their
aggressively-optimizing implementation attempted to preserve these
reachability properties.  I think it may not have been an issue since
I think Self never provided finalization.


>From your earlier post:

> This issue was discussed in Mark Weiser's and my SP&E '88 paper.  Is x seen
> by the garbage collector during the call to g in

> { T x; f(x); g("abc"); }

> For a naive compiler the answer is "yes".  For a CPS-based compiler, the answer
> is "no".  For a typical compiler with global register allocation the answer is
> "maybe".

Right. But which is more important, being able to rely on finalization,
or
speed?  Its certainly undecidable whether the performance gained by
optimizations that break decidable reachability outweigh those gained
through program simplifications made possible by decidable reachability!

Take the non-termination example
	v := e. c(); e
where c may not terminate.
You're the expert here, but it seems to me that except in the above
example
the cost of providing decidable reachability, e.g. by nilling registers
is minimal.

In the example above, it seems to me that e is reachable unless one
can solve the halting problem, so being concerned that e is not
reclaimed
when c does not terminate is being more than a little picky.  In
realistic
situations where resource usage is a concern one would not intensionally
fall into the above trap.

> There has been a significant amount of work on this kind of issue, especially
> in the context of ML and logic programming languages.  (E.g. there was a paper
> a few years back claiming significant space improvements in ML by treating
> variables and data structure components with unconstrained type as dead.  Since
> their type is unknown, they can'e be used for anything.  They can be safely
> reclaimed, in spite of the fact that this leaves "dangling" pointers.  Appel is
> careful to define a CPS-based notion of reachability for SML of NJ in order to
> avoid some problems they observed with early versions of their system.)


Are you referring to
	Benjamin Goldberg: Tag-Free Garbage Collection for
	Strongly Typed Programming Languages. 165-176, PLDI 91
(right next to your Mostly Parallel paper - shades of Princes Bride :))?

Seems a little different, but with the Tag-free scheme in the above,
ignoring the non-termination case, reachability is decidable from all
call-points in the program, no?

> I think that pointer-forging is really not relevant here.  Even in environments
> in which pointer-forging is an issue, I think we could all agree that legal
> programs shouldn't access objects through forged pointers, and hence the
> possibility shouldn't influence the notion of reachability.

Agreed.
_______________,,,^..^,,,_______________
Eliot Miranda, ParcPLace-Digitalk