the polish and tarnish (reverse polish) solution

[Eric Dean Tribble <tribble>]

Abstract: just about everyone pitched in to figure out when we can
purge an object from memory.  We needed to avoid purging a currently
executing object (cause then it might reference instance variable which
had since vanished).  In the process we figured out a way to change
the class of an object in place.  Finally, we discovered an even
bigger moose!  Many of our recursive algorithms might recur an
unbounded amount of time in worst case.  Even though the amortized cost
is O(log), the worst case could require an unbounded stack depth, and
could bring in an unbounded number of objects.  I will address this in
a separate message.

I don't remember who came up with what, so Thank You, MarkM, Michael, Hugh,
Roger, Ravi, ChrisH, me, and whoever I forgot.

Warning: terminology is subject to change :-)

We finally figured out as real cheap way to detect that an object is
in use.  We encode a single state bit in each Shepherd's
*vtable-pointer*.  For each Shepherd class there's two vtables.  One
is in an automatically generated class (call it A.  Call the other B).
'A' returns true for the 'isPolished' method.  Whenever an instance of
A gets sent an interesting message, it changes the class pointer of
the object to 'B' (the actual inmplementation class), and then resends
the message.  When the message returns, it changes the class pointer
back to 'A'.  As a result, anytime a message is currelty executing
inside the object, it will return false to asPolished (because that's
'B's implementation), and recursive calls to a 'B' object have no
overhead because 'B' just handles message normally.

How do we change the class of an object?  Each convertible object
class has a special single-argument constructor that takes an object
from which to convert.  It then constructs itself in place without
initializing any of the instance variable.  (Actually the constructor
has two arguemnts: the object to convert from, and a constant like
TCSJ that designates a become operation).  Smalltalk just has a
primitive for smashing the class pointer that we'll use.  It's amusing
that we could make the Smalltalk hack translate to the C++ hack :-)

Many messages to Shepherds don't require all this overhead.  Instance
variable access methods, for instance (:-), will never trigger a
purge, so it need not be protected by tarnishing and polishing.  These
methods are simply implemented the same in both the polished and
unpolished versions of the class.  Eventually we will mark more
methods a 'safe' (hopefully a statically checkeable property), but
right now I'll just treat methods that don't send any messages as safe.

Another trick we realized is that we don't need to plant bombs to
polish in-use objects when they get blasted out of.  All the blasts we
could think of (and we'll check this later) blast to a point in the
algorithm outside the Ent, so all the Shepherds inside the Ent are
*known* to be not-in-use, so they can be polished.  Therefore we don't
need to protect the class changing operation with a Bomb.  Likewise,
some other points in the algorithms may know that they just stopped
using an object, and so polish it (the splay routine, for example,
knows when it's done with an object, and knowns that no other part of
the algorithm can be using it).  This last trick is relatively unsafe
in the face of changing code, so we will avoid it unless we really
need it.

Finally, we realized that the disk storage stuff I've been building
probably has enough information to know when it's going to fill up the
URDI buffers, so we don't need a currently unimplemented feature of
URDI to handle 'mayCommit' operations that commit a consistent state
without waiting for it to go to disk.

dean