Keys are references, too (was Re: Garbage Collection)

[bbadger@x102c.uucp (Badger BA 64810)]

In article <3861@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>From article <6702@june.cs.washington.edu>, by klaiber@june.cs.washington.edu (Alexander Klaiber):
>> Assume I maintain mailing-lists of people and I represent the lists by
>> pointers to objects representing one person each; i.e.
>> type person is (some adt)
>> type mailinglist is new list(person);
>> Now if I have more than one mailing-list, obviously I have structure-sharing: 
>> a given person may appear on more than one list. 
>
> No, this isn't structural sharing, because you are explicitly manipulating 
> a list of pointers.  Structural sharing occurs when you have two objects, 
> A and B, and making some modification to B causes a modification to A as 
> well, because they share a portion of their structure.  The structure
> of a pointer is simply the address field, and the address fields are not
> being shared.  Now if we had two ADTs, both implemented by *hidden*
> pointers, and assignment failed to result in a deep copy, then THAT 
> would be structural sharing. 
>
> In this particular instance, it would be best to store the key by which
> a person could be identified (social security number, for example) in
> the list, and then using the key to retrieve the current address from
> the Person database.  Thus, a mailing list would be a list of social
> security numbers. 
>   
>
>                                            Bill Wolfe
>
>                                    wtwolfe@hubcap.clemson.edu
Mr. Wolfe does not (here) recognize the social security number (SSN) as 
another form of access mechanism.  *Any* means by which a symbol can be 
introduced to stand in as the ``name'' of the actual object will introduce 
the ability to ``share'' the object by mentioning the name in two places.  
Just because the SSN is not a memory address pointer, does not mean that 
sharing is not taking place.  (As an aside, the Ada LRM is careful not to call
access types ``pointers'' for a similar reason:  access types may turn out
to *not* be implemented as a memory pointer.)

Another key thing that Mr. Wolfe does not address is the problem of deciding
*when* to destroy an object.  Sure, it's easy enough, in most cases, to write 
a destruction routine, but you can't always wait until passing out of the 
scope of the visibility of the ADT to clean up.  This is where all the 
reference counts and other garbage collection mechanisms come in:  determining
that it is *SAFE* to reclaim storage.  Mr. Wolfe's database design has the 
same problem:  It's easy to remove the personnel record, but you may only 
do so when the SSN is not referenced any more.  

Leaving this decision up to the clients of the ADT, say by providing explicit
DESTROY(X) calls, just pushes this burden on the programmer of the client.  
In many cases, there is a clear and efficient way to determine when it is 
safe to destroy objects.  Fine!  Those cases can be explicitly managed by 
the programmer. A good garbage collector should not waste time  attemting 
to garbage-collect over programmer-managed data.  Perhaps a pragma(NO_GC,type);
would be helpful to the compiler.  

You have to show that GC is *never* worthwhile to justify *prohibiting* it 
from the language.  It seems to me that investing a lot of serious effort to 
get a really good GC algorithm built into the language would be much better 
than expecting "average" programmers to correctly implement proper storage 
reclamation for each ADT they'd like to use which requires memory allocation.
Even if not every compiler vender has ``the world's best'' memory reclamation,
it will be easier to select one that does, based on professional reviews, 
than to implement it yourself.



Bernard A. Badger Jr.	407/984-6385          |``Use the Source, Luke!''
Secure UNIX Products                          |It's not a bug; it's a feature!
Harris GISD, Melbourne, FL                    |Buddy, can you paradigm?
Internet: bbadger@cobra@trantor.harris-atd.com|Recursive:  see Recursive.