Re: Collective response to := messages

Re: Collective response to := messages

[Erland Sommarskog]

William Thomas Wolfe (billwolf@hubcap.clemson.edu) writes:
>     What is needed is a completion of the ADT paradigm, support for
>     which is the fundamental reason for the "limited private" feature.
>     Given that one must remember to destroy all non-predefined ADTs 
>     upon block exit, it is clear that the implications of this paradigm 
>     were not appropriately considered in the Ada 83 design. 

With other words, what you want is garbage collection. I'm quite
sure that the language designers knew about. Simula has had since
1967. Note that the language definition in no way forbids garbage
collection, but it does not require it. It says: 4.8(7) "An 
implementation may (but need not) reclaim the storage occupied by an 
object created by an allocator, once this object has become inaccessible".
In practice this means you must do all deallocating explictly if you
want to be partable.
  I think the reason why garbage collection is not required is that 
in some applications this is not very desireable from the point of 
view or performance. Typically you may not want it embedded real-time 
systems... Another thing is of course the implementation issue...

But as you point out, this is an important concept when implementing
abstract data types. I think that Ada should require garbage collection
and a pragma with which you could turn it off for critical code.
-- 
Erland Sommarskog
ENEA Data, Stockholm
sommar@enea.se
"Frequently, unexpected errors are entirely unpredictable" - Digital Equipment

Re: Collective response to := messages

[William Thomas Wolfe,2847,]

From article <4125@enea.se>, by sommar@enea.se (Erland Sommarskog):
> William Thomas Wolfe (billwolf@hubcap.clemson.edu) writes:
>>     What is needed is a completion of the ADT paradigm, support for
>>     which is the fundamental reason for the "limited private" feature.
>>     Given that one must remember to destroy all non-predefined ADTs 
>>     upon block exit, it is clear that the implications of this paradigm 
>>     were not appropriately considered in the Ada 83 design. 
# 
# With other words, what you want is garbage collection.  
# [...]  I think the reason why garbage collection is not required is that 
# in some applications this is not very desireable from the point of 
# view of performance. Typically you may not want it embedded real-time 
# systems... Another thing is of course the implementation issue...

   No, I do NOT want garbage collection.  Since GC cannot handle the
   problems of circular-list garbage without outrageous time expenditures,
   and for all the other reasons you mentioned above, GC is NOT desirable.
   Furthermore, GC encourages sloppy programming.  I'd be very happy to see
   GC explicitly PROHIBITED.


                                       Bill Wolfe

                               wtwolfe@hubcap.clemson.edu

Re: Collective response to := messages

[Richard A. O'Keefe]

In article <3733@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>   No, I do NOT want garbage collection.  Since GC cannot handle the
>   problems of circular-list garbage without outrageous time expenditures,

Are you up-to-date on this?  There has been a lot of work done on GC in
the last 5 years.

>   Furthermore, GC encourages sloppy programming.

How so?  Have you some data on this?  I very much prefer languages with
automatic storage management (Lisp, Pop, Prolog, Simula 67, SmallTalk, ...)
because there is a large class of mistakes you simply can't make (e.g.
referring to nonexistent storage) and the only real sacrifice in
expressiveness is that it is harder to write programs which crash when a
fixed-size buffer overflows (:-).  It would be a service if you could
elaborate on this:  if I knew what sort of sloppiness was encouraged I
could more effectively try to avoid it.

Re: Collective response to := messages

[William Thomas Wolfe,2847,]

From article <808@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe):
> In article <3733@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>>   No, I do NOT want garbage collection.  Since GC cannot handle the
>>   problems of circular-list garbage without outrageous time expenditures,
> 
> Are you up-to-date on this?  There has been a lot of work done on GC in
> the last 5 years.

    No, I'm not, but I'll bet GC still can't be done in O(n) time 
    with regard to the number of items of garbage, with constants
    no greater than the overhead of a deallocation...

>>   Furthermore, GC encourages sloppy programming.
> 
> It would be a service if you could elaborate on this [...]

    The programmer is Johnny-on-the-spot.  He/she KNOWS whether or not
    a given object is no longer needed.  All that is necessary is an 
    indication of this fact via the command DESTROY (Unneeded_Object).

    If the programmer is sloppy and leaves garbage lying all over the place,
    the "maid" must do all the hard work of deciding what to keep 
    and what to throw out.  Furthermore, this price must be paid
    repeatedly at execution time.  This is a heavy price to pay for
    not simply designing it right the first time.  

Re: Collective response to := messages

[Richard A. O'Keefe]

In article <3740@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>From article <808@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe):
>> It would be a service if you could elaborate on this [...]

>    The programmer is Johnny-on-the-spot.  He/she KNOWS whether or not
>    a given object is no longer needed.  All that is necessary is an 
>    indication of this fact via the command DESTROY (Unneeded_Object).

This simply isn't true.  If I write a library routine which is passed
some linked data structure, I may be able to tell whether my traversal
of it has finished, but that leaves me with no idea whatsoever of
whether I was given the last reference to it (in which case now is the
time to delete it) or not.  Or suppose some "object" has references to
some other objects, and I DESTROY(..) the first object.  Should it
DESTROY(..) the other objects?  In that case it may destroy things which
other objects still refer to!  But if it doesn't, and it held the only
references to those objects, their space will not be reclaimed.  Is
Johnny on the spot?  NO!  The programmer who coded the implementation
of that object has _no_idea_ how other programmers will use it.  There
has been quite a lot of discussion about this in comp.lang.c++ .

     Let me apply billwolf@hubcap's general principle to another case:

	The programmer is Johnny-on-the-spot.  He/she KNOWS whether a
	given object is an integer or a float.  All that is necessary
	is an indication of this fact via the use of + for integers
	and #+ for floats.  We don't need any of this strong typing
	nonsense!

Automatic storage management, like automatic operator selection, means
that the programmer misses an opportunity to make a mistake.  There 
_are_ garbage collection methods around where the overhead of
garbage collection is a constant times the cost of allocation.

ADA was explicitly designed not to require garbage collection.
Since it was meant to be useful for real-time work, that was appropriate.

Re: Collective response to := messages

[William Thomas Wolfe,2847,]

From article <812@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe):
> In article <3740@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>>From article <808@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe):
>>> It would be a service if you could elaborate on this [...]
> 
>>    The programmer is Johnny-on-the-spot.  He/she KNOWS whether or not
$>    a given object is no longer needed.  All that is necessary is an 
$>    indication of this fact via the command DESTROY (Unneeded_Object).
$ 
$ This simply isn't true.  If I write a library routine which is passed
$ some linked data structure, I may be able to tell whether my traversal
$ of it has finished, but that leaves me with no idea whatsoever of
$ whether I was given the last reference to it (in which case now is the
$ time to delete it) or not.  

      Whether or not the library routine should DESTROY its parameter
      depends on how the library routine is defined.  How about a
      more specific example?

# Or suppose some "object" has references to
# some other objects, and I DESTROY(..) the first object.  Should it
# DESTROY(..) the other objects?  In that case it may destroy things which
# other objects still refer to!  But if it doesn't, and it held the only
# references to those objects, their space will not be reclaimed.  

     Again, we need specifics here.  I hope you aren't talking about
     structural sharing here, which should NEVER be seriously contemplated.
 
% Is Johnny on the spot?  NO!  The programmer who coded the implementation
% of that object has _no_idea_ how other programmers will use it.  

     The implementor has no idea what *applications* the object will be
     used in, but has almost total control (the exceptions occur during
     parameter passing and block exit) over the operations of the ADT.

& There _are_ garbage collection methods around where the overhead of
& garbage collection is a constant times the cost of allocation.
 
     I specified O(n) with respect to the cost of each DEallocation,
     with the cost no higher than the overhead of doing the deallocation.
     This implies that the garbage collection routine has the ability to
     magically know the size and location of each and every piece of garbage,
     and has no need to examine any non-garbage. 

Re: Collective response to := messa

[ron]

Garbage collection certainly does not come for free, but it is extremely
useful.  It frees the programmer from the need to repeatedly write
sophisticated ADT deallocate routines and to deal with the potentially
massive book-keeping requirements for determining whether an object is in
fact garbage.  In general, lack of GC forces a programmer to invest a lot of
effort addressing issues that are not fundamentally related to the problem
domain.  My experience has also shown that problems of "slow heap leakage"
are among the hardest errors to correct.

An earlier posting claimed that a programmer should know what is and isn't
garbage, and that GC is therefore not needed.  This argument would never be
made by a programmer with experience writing serious applications using both
GC'd and non-GC'd languages.  It's quite possible that those without GC'd
programming experience don't even recognize the additional burden for what
it is.

I am not saying that garbage collection should or shouldn't be added to Ada.
I haven't really thought about all of the issues; there are clearly pros and
cons.  However, the argument against GC loses much of its credibility if
it contains an outright denial of the many positive aspects of GC.

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <124000026@inmet>, by ron@inmet.UUCP:
> 
> Garbage collection certainly does not come for free, but it is extremely
> useful.  It frees the programmer from the need to repeatedly write
> sophisticated ADT deallocate routines and to deal with the potentially
> massive book-keeping requirements for determining whether an object is in
> fact garbage.  In general, lack of GC forces a programmer to invest a lot of
> effort addressing issues that are not fundamentally related to the problem
> domain.  My experience has also shown that problems of "slow heap leakage"
> are among the hardest errors to correct.

   "Repeatedly" write sophisticated ADT deallocate routines??  The basic 
   idea is to write an ADT once and use it forever (i.e., until the next 
   language modification :-) ); where does "repeatedly" come in?

   Dealing with the details of allocation requires as much effort as  
   dealing with deallocation.  Perhaps you would say that any maintenance 
   of the structure used to represent your ADT is not fundamentally
   related to the problem domain.  If so, I will have to disagree.

   ADTs, and computer programs in general, are characterized by both
   time complexity and space complexity.  Making the tradeoffs between
   these forms of complexity is one of the most fundamental questions
   a programmer must deal with.  This is the topic of much, if not most, 
   of the literature regarding ADTs.

   Also, I disagree with the claim that a lot of effort is involved;
   in my experience, DESTROY routines are among the easiest to code.
   Usually, the ADT is defined recursively, lending itself to a very
   easy recursive destruction procedure; after that, just destroy
   any sub-ADTs in your descriptor, and from there it only takes one
   line of code to blow away the descriptor.  About the hardest part
   of the whole process is the tedium of looking through to see what
   fields are user-defined sub-ADTs, since they have to be explicitly
   destroyed due to Ada's lack of integration between UNCHECKED_DEALLOCATION
   and user-defined DESTROY procedures.


                                          Bill Wolfe

                                   wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[John Gateley]

In article <3832@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>From article <124000026@inmet>, by ron@inmet.UUCP:
>> 
>> Garbage collection certainly does not come for free, but it is extremely
>> useful.  It frees the programmer from the need to repeatedly write
>> sophisticated ADT deallocate routines and to deal with the potentially
>> [...]
>   "Repeatedly" write sophisticated ADT deallocate routines?? [...]
>    where does "repeatedly" come in?

The repeatedly comes in because you write more than one ADT, each requiring
a/many deallocation routines.

>   Dealing with the details of allocation requires as much effort as  
>   dealing with deallocation. [...]

This is not true. When you allocate an object, all you need is "free"
memory. The allocator does not have to worry about whether or not the
object is in use etc. Deallocation, when done correctly, requires some
sort of checking to make sure no currently in use object refers to the
object being deallocated. This is a much more complicated problem.

>   [...]
>   Also, I disagree with the claim that a lot of effort is involved;
>   in my experience, DESTROY routines are among the easiest to code.
>   Usually, the ADT is defined recursively, lending itself to a very
>   easy recursive destruction procedure; [...]

This method is fine, as long as no structures are shared. But when you
share structure, then the problem is more complex. A sub adt-object
can be used in more than one object. Deleting an object which contains
this sub-object may or may not require deleteing the sub object. One
answer is "reference counting", adding a field to each object which says
how many people refer to it. Automating this gives reference count
garbage collection, which is slower than the GC techniques in current
use. So if your programming style never uses shared structure, then you
don't need GC. If it does, then GC is a valuable time saving tool.

>                                          Bill Wolfe
>                                   wtwolfe@hubcap.clemson.edu

John Gateley
gateley@tilde.csc.ti.com

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <65475@ti-csl.CSNET>, by gateley@m2.csc.ti.com (John Gateley):
>>   Also, I disagree with the claim that a lot of effort is involved;
>>   in my experience, DESTROY routines are among the easiest to code.
>>   Usually, the ADT is defined recursively, lending itself to a very
>>   easy recursive destruction procedure; [...]
> 
> This method is fine, as long as no structures are shared. [...] 
> [...] if your programming style never uses shared structure, then you
> don't need GC. 

    Precisely.  

    Structural sharing is nothing more than a euphemism for hacking.  
    It is the spatial equivalent of what hackers enjoy doing with time 
    in the name of efficiency, in their unmitigated zeal to violate every
    form of abstraction, to throw all traces of readability and reliability 
    to the winds.  

    If GC were prohibited, it would infuriate all those who enjoy hacking
    with space as opposed to time.  Good.  Let them use C.  Ada is the
    language of those who appreciate that "abstraction is the fundamental
    tool with which complexity can be effectively managed", and recognize
    that to violate an abstraction (rather than design another which is
    more appropriate to their needs) is to be penny wise but pound foolish.

    Folks, space management in Ada is NOT that difficult.  I had problems with
    space management in Pascal, but Ada-based ADTs have basically made it
    into a non-issue.  The real challenges which remain are problems which
    are inherent in the language itself, such as getting local ADTs to be 
    properly destroyed as an automatic consequence of a block exit.

    I agree that existing tools for detecting space-wasting ADTs are 
    inadequate, but let's call for better debugging tools rather than
    going about advocating the practice of spewing garbage. 


    
                                        Bill Wolfe

                                 wtwolfe@hubcap.clemson.edu
 

Re: Garbage Collection

[Alexander Klaiber]

In article <3848@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>From article <65475@ti-csl.CSNET>, by gateley@m2.csc.ti.com (John Gateley):
>> This method is fine, as long as no structures are shared. [...] 
>> [...] if your programming style never uses shared structure, then you
>> don't need GC. 
>    Precisely.  
>    Structural sharing is nothing more than a euphemism for hacking.  
>    It is the spatial equivalent of what hackers enjoy doing with time 
>    in the name of efficiency, in their unmitigated zeal to violate every
>    form of abstraction, to throw all traces of readability and reliability 
>    to the winds.  

Apart from the amount of cheap flames you've thrown in, do you think you
REALLY have thought this out?

Sure, structure-sharing *is* sometimes used with the goal of conserving
memory, but there are cases where it is vital; especially when you're doing
object-oriented like programming.

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. And it is *NOT* very wise
to create one copy of each person for every mailing list that person appears
on: people can change the addresses and by having just *one* instance of
the person around, there is only *one* place where it needs to be changed
-- these changes will be completely transparent to the mailing lists or,
for that matter, *FOR ANY OTHER REFERENCES TO THE PERSON* that I might
later add to the system!

In a system such as this, I will need *some* form of keeping track just 
how many references to a given object (a person) exist, so I know when
I can safely deallocate it --- now one method is to have the programmer
take care of it, but that might require making the (mailinglist) and 
(person) know about each other, thus creating additional dependencies and
limiting further extensibility. The other method is to supply GC.

Now you *can* do without structure sharing by creating "deep copies" of
each reference to any given object --- but you will have to live with the
"updating problem" which is well-known in databases where multiple copies
of objects are kept.

The bottom line is that structure-sharing can be a valuable abstraction
tool, and one you apparently are not aware of.

>    If GC were prohibited, it would infuriate all those who enjoy hacking
>    with space as opposed to time.  Good.  Let them use C.  Ada is the

Why do you want to explicitly *prohibit* it?

>    Folks, space management in Ada is NOT that difficult.  

Depends on what kinds of applications you are writing.

Note that I do not ask that GC be *required* (obviously that would be rather
foolish in real-time applications), but it is sure nice to have it, since
it can greatly help to reduce the complexity of your programs by
eliminating all these storage-management chores and allowing you to
concentrate on the real problems.

It sure eliminates a *lot* of possibilities for errors and actually makes
programs much more reliable and readable. Maybe *you* are throwing
readability and reliability in the wind...



Alexander Klaiber
klaiber@june.cs.washington.edu


P.S.:
For complex applications as these, I tend to programm in Smalltalk
rather than in Ada, so I might be somewhat biased. But I *have* done
o-o programming in C++, and believe me, storage management can be
*nasty*!

Re: Garbage Collection

[William Thomas Wolfe,2847,]

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
 

Re: Garbage Collection

[Alexander Klaiber]

In article <8812131536.AA08238@galaxy.compass.com> worley@compass.UUCP (Dale Worley) writes:
>I will add that garbage collection is one of the greatest aids to
>readabilty and reliability, because it takes a complicated and
>error-prone part of programming (reclaiming storage) and eliminates it
>completely.  It probably shouldn't be required in Ada, but as an aid
>in programmability, it's great.

Thank you very much, exactly my point. At least I'm not alone :-)

==========================================================================
In article <3861@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>    No, this isn't structural sharing, because you are explicitly manipulating 

Call it what you want, the fact is that multiple references exist to one
object, thus making explicit (i.e. by the programmer) storage management
a nightmare and an unnecessary chore. GC deals with this situation easily.

>    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.  

That is, if you are willing to willing to pay the cost for the additional
data base lookup (usually an O(log n) operation), as well as the additional
complexity introduced in your program. 
I didn't say it couldn't be done without (what I call) structure sharing, 
I just wanted to point out that this would be a very intuitive approach 
and would probably lead to a very readable code.

The method of using key searches is, I believe, an unnecessary hack to
avoid multiple references. Why bother to include a full B-tree package
or such when we can do without? 

Clearly, there is a tradeoff between readability and efficiency. In my
version, I reduce efficiency by requiring garbage collection (although
there exist rather powerful and fast GC algorithms). Your proposal
would definitely increase the complexity of the program and, due to the
overhead of a DB-lookup, might actually run slower than the version with
GC --- depending on circumstances such as frequency of lookups in the 
database, size of the database (your program) vs. time required for GC, 
amount of garbage produced etc. (my program).

In my opinion, people tend to put too much emphasis on plain efficiency of
their programs and too little on issues such as readability, reliability
and extensibility --- and I contend that (depending on the application)
garbage collection *CAN* help to improve all of these.

Hence, it is *wrong* to flatly ignore GC; it sure has its place and,
especially in o-o systems, should be available as an option to the 
programmer. Now whether it should be required in *Ada* is a question of
just where Ada9x will go and not really my concern.



	Alexander Klaiber
	klaiber@june.cs.washington.edu

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <6713@june.cs.washington.edu>, by klaiber@june.cs.washington.edu (Alexander Klaiber):
> In article <8812131536.AA08238@galaxy.compass.com> worley@compass.UUCP (Dale Worley) writes:
>>I will add that garbage collection is one of the greatest aids to
>>readabilty and reliability, because it takes a complicated and
>>error-prone part of programming (reclaiming storage) and eliminates it
>>completely.  

    I don't see storage reclamation as being complicated or error-prone,
    but maybe that's because I'm so accustomed to dealing with it that
    it comes almost automatically.  Probably the most important reason,
    though, is that the ADT paradigm provides such a powerful mechanism
    for simplifying the situation.  I'm doing an ADT implementation
    right now (mergeable priority queues implemented as binomial forests),
    and I find it hard to believe that anyone could sit there and do an
    ADT implementation without being able to visualize the structure
    in question as the code is being generated.  Given that the implementor
    can visualize the structure, the process of destroying it seems trivial.

> In article <3861@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>>    No, this isn't structural sharing, because you are explicitly manipulating 
> 
> Call it what you want, the fact is that multiple references exist to one
> object, thus making explicit (i.e. by the programmer) storage management
> a nightmare and an unnecessary chore. GC deals with this situation easily.

    There's an even easier way to deal with it:

       *** Never let a pointer out of your sight ***

    Given that one is doing this, the question is reduced to managing
    local pointers to a local structure, which is quite easy.

>>    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.  
> 
> That is, if you are willing to willing to pay the cost for the additional
> data base lookup (usually an O(log n) operation)

     Not necessarily.  If all you're doing is insertions, deletions,
     and retrievals, a hashing implementation would give better results.

> I didn't say it couldn't be done without (what I call) structure sharing, 
> I just wanted to point out that this would be a very intuitive approach 
> and would probably lead to a very readable code.

     I'd contest both claims; as a maintainer, I wouldn't want anything
     to get in the way of being able to pin down the state of that program
     precisely, with regard to both time AND SPACE.  For one who is
     accustomed to being able to nail down the precise state of a program,
     code from which it is impossible to "complete the picture" is
     highly counterintuitive, and will probably wind up being rewritten.

> The method of using key searches is, I believe, an unnecessary hack to
> avoid multiple references. Why bother to include a full B-tree package
> or such when we can do without? 

     How can you possibly analyze the space complexity of your program
     when you can't pin down the precise status of every entity???  You
     can't just wave your hands and say "Well, I'm using this much space,
     plus there's a bunch of space that may or may not be occupied..."!!

     And let's not forget the pure hell of doing a time analysis given
     that you can be interrupted unpredictably for garbage collection,
     the timing and duration of which is totally beyond your control,
     particularly in that it depends on how much memory happens to be
     currently installed on the executing system!!

> In my opinion, people tend to put too much emphasis on plain efficiency of
> their programs and too little on issues such as readability, reliability
> and extensibility 

     At last, something we can ALL agree on.  (I hope...!)


                                     
                                       Bill Wolfe

                                wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Stephe Leake]

In article <6713@june.cs.washington.edu> klaiber@june.cs.washington.edu (Alexander Klaiber) writes:

   Clearly, there is a tradeoff between readability and efficiency. In my
   version, I reduce efficiency by requiring garbage collection (although
   there exist rather powerful and fast GC algorithms). Your proposal
   would definitely increase the complexity of the program and, due to the
   overhead of a DB-lookup, might actually run slower than the version with
   GC --- depending on circumstances such as frequency of lookups in the 
   database, size of the database (your program) vs. time required for GC, 
   amount of garbage produced etc. (my program).

You are not reducing the complexity of the program; you are merely
hiding it in the vendor-supplied memory management package. If the
program is written correctly, the complexity can be hidden in a
user-supplied memory management package. Then there is no difference
in the readability of the application code, and the programmer has the
chance to tailor the garbage collection algorithm to the application.
Since there are many garbage collection algorithms (each posting here
seems to mention another one), it is clear that each will be suited to
certain applications. Better to require the programmer to choose the
algorithm, than to be tempted to "live with" the single vendor
supplied one. There is no way the vendor can take into account the
trade-offs you mention, but you can!

Stephe Leake 	(301) 975-3431 		leake@cme.nbs.gov
National Institute of Standards and Technology
(formerly National Bureau of Standards)
Rm. B-124, Bldg. 220
Gaithersburg, MD  20899

Re: Garbage Collection

[Thomas P. Morris]

In article <6713@june.cs.washington.edu>, klaiber@june.cs.washington.edu (Alexander Klaiber) writes:
> The method of using key searches is, I believe, an unnecessary hack to
> avoid multiple references. Why bother to include a full B-tree package
> or such when we can do without? 
> 
You mean to tell us that you =intend= to keep your "mailing" lists
=permanently in memory=? You're =never= going to write them to a permanent
file system/disk? Or that your never going to keep a list larger than can
be kept in memory? Really!  The method of using key searches is a useful
aid to designing a program to read from a database larger than you can
keep in memory, which needs to be permanent, and which ought to be well-
behaved in terms of no =clobbering= other processes' performance!

:-) Yeah, I know that the mailing list abstraction was only for an example.
But a fairly poor example if you wish to justify structure sharing, which
*has* its proper place...

> Clearly, there is a tradeoff between readability and efficiency. In my
> version, I reduce efficiency by requiring garbage collection (although
> there exist rather powerful and fast GC algorithms). Your proposal
> would definitely increase the complexity of the program and, due to the
> overhead of a DB-lookup, might actually run slower than the version with
> GC --- depending on circumstances such as frequency of lookups in the 
> database, size of the database (your program) vs. time required for GC, 
> amount of garbage produced etc. (my program).
> 
For something like a database system (i.e. mailing lists, again), I would
have to disagree that a keyed-search DB-lookup paradigm is necessarily
less readable or understandable or complex than having to pre-process
the databases (to create your structure sharing) to have direct access,
which might not be reasonable or possible with a *large* database.

Your points about speed of access are well taken, but consider the end
user aspects: how many folks are going to wait 10, or 20, or 30 minutes
for you to read in the external data, build your structure sharing
structures, and =then= process their mailing list (personnel records,
widget manufacturing data, etc), rather than using a relational database
paradigm, using keyed access to those external permanent files?

> In my opinion, people tend to put too much emphasis on plain efficiency of
> their programs and too little on issues such as readability, reliability
> and extensibility --- and I contend that (depending on the application)
> garbage collection *CAN* help to improve all of these.

  Yes and yes. The mailing list example is and unfortunate choice perhaps.
And some of us put also put an emphasis on how well a system works for
its intended end-users!
-----------------------------------------------------------------------------
Tom Morris                                 BITNET: TOM@UNCSPHVX
UNC School of Public Health                UUCP  : ...!mcnc!ecsvax!tpmsph
-----------------------------------------------------------------------------
-- 
-----------------------------------------------------------------------------
Tom Morris                                 BITNET: TOM@UNCSPHVX
UNC School of Public Health                UUCP  : ...!mcnc!ecsvax!tpmsph
-----------------------------------------------------------------------------

Re: Garbage Collection

[John Gateley]

A good example of when garbage collection is needed for readability:
An infinite precision integer arithmatic package (or ADT, or module,
or whatever you want to call it). Infinite precision integers will
take up an unknown amount of memory to represent. Either you have to
explicitly deallocate them when you are done, or let GC take care of them.
But now consider the uses of integers in programs, they are used all over
the place, with no regard for careful deallocation. Converting a program
to use infinite precision integers will be very difficult, since it is
hard to figure exactly when the program is 'finished' with a particular
number.

John

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <65713@ti-csl.CSNET>, by gateley@m2.csc.ti.com (John Gateley):
> A good example of when garbage collection is needed for readability:
> An infinite precision integer arithmatic package (or ADT, or module,
> or whatever you want to call it). Infinite precision integers will
> take up an unknown amount of memory to represent. Either you have to
> explicitly deallocate them when you are done, or let GC take care of them.
> But now consider the uses of integers in programs, they are used all over
> the place, with no regard for careful deallocation. Converting a program
> to use infinite precision integers will be very difficult, since it is
> hard to figure exactly when the program is 'finished' with a particular
> number.

     The deallocation of every object in the local environment is
     performed as an automatic service when a procedure, function,
     or local block is exited.  This is not garbage collection,
     because the programmer has implicitly directed that the 
     destruction be performed.  

     Unfortunately, Ada does not provide a means of integrating ADT 
     destruction algorithms into the mechanism providing this service.  
     This is Language Issue 35 of the Ada Language Issues Working Group; 
     it is presently under editorial review, a step which is usually followed 
     by approval and then by submission to ADA-COMMENT, according to the 
     ALIWG handout I obtained at Tri-Ada '88.


                                         Bill Wolfe

                                 wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[John Gateley]

In article <3918@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>From article <65713@ti-csl.CSNET>, by gateley@m2.csc.ti.com (John Gateley):
>> [I say infinite precision arithmetic is a good example of why GC is needed
>>  sometimes].
>
>     The deallocation of every object in the local environment is
>     performed as an automatic service when a procedure, function,
>     or local block is exited.  This is not garbage collection,
>     because the programmer has implicitly directed that the 
>     destruction be performed.  

But, integers are not always deallocated. They may be returned as the
result of a function, assigned to global variables, placed in the 
heap as parts of other data objects etc. When you try and do the same
with infinite precision integers, then the deallocation you describe
does not work! You can always copy them for these purposes, but this
can be very space/time inefficient. It also requires extra effort (remembering
to copy them), unless Ada provides some technique for doing this automatically.
So, GC is a good way to handle this problem.

>     Unfortunately, Ada does not provide a means of integrating ADT 
>     destruction algorithms into the mechanism providing this service.  
>     This is Language Issue 35 of the Ada Language Issues Working Group; 
>     ...

Integers, however, are not deallocated when a block is exited (if they
have been saved elsewhere). So, I don't think this language issue
applies to the infinite precision integer case.

John
gateley@tilde.csc.ti.com

Re: Garbage Collection

[Bill Wolfe]

In article <65914@ti-csl.CSNET>, gateley@m2.csc.ti.com (John Gateley) writes:
> >> [I say infinite precision arithmetic is a good example of why GC is needed
> >>  sometimes].
> >
> >     The deallocation of every object in the local environment is
> >     performed as an automatic service when a procedure, function,
> >     or local block is exited.  This is not garbage collection,
> >     because the programmer has implicitly directed that the 
> >     destruction be performed.  
> 
> But, integers are not always deallocated. They may be returned as the
> result of a function, assigned to global variables, placed in the 
> heap as parts of other data objects etc. 

    What we are (presumably) discussing here is the space management 
    applying to literals and/or anonymous values of some arbitrary type.  
    During compilation, the compiler will evaluate each literal as 
    an anonymous value of the appropriate type.  Anonymous values differ 
    from named values only in that the programmer cannot explicitly refer 
    to them by name.

    Typically, literals are used in the construction of anonymous
    expressions which will ultimately serve as a value to be assigned.
    They are then being supplied as "in" parameters, and we have already
    discussed the proper method by which compilers should handle anonymous
    values passed as "in" parameters: they should be passed by handoff;
    since no external name exists, there is no need to set any external
    object to "undefined".  Since anonymous values cannot simply exist
    in mid-air, and must always be consumed in the course of some statement,
    we know that they will always be consumed.  By the rules of Ada, they
    cannot be supplied as "in out" or "out" parameters; hence, the mechanism
    described for handling anonymous values which are being passed as "in"
    parameters in a space-efficient manner serves to cover all cases, if
    we treat assignment as a procedure requiring an "in" parameter for the
    source value; otherwise, the extension to this case is straightforward. 

    Thus, we have completely described the space management applicable to
    literals and other anonymous values, such that these values can be
    managed effectively without any need for recourse to garbage collection.

    All that is needed is a tighter definition of what happens to an 
    anonymous value which is passed as an "in" parameter.  Note that
    this analysis does not depend upon the amount of space which must
    be used to contain any given anonymous value.



                                           Bill Wolfe

                                   wtwolfe@hubcap.clemson.edu

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

[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.

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

[William Thomas Wolfe,2847,]

From article <1407@trantor.harris-atd.com>, by bbadger@x102c.uucp (Badger BA 64810):
> 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.  

    If I have an object A, and pointers to that object P1 and P2, then
    I have three distinct objects, none of which share structure.

    If I have objects B and C, such that a modification to B results also
    in a modification of C, then this is structural sharing.  

> 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 why users can explicitly call DESTROY when the object is 
    no longer needed.

> 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.  

    Not true.  If the SSN refers to a person who is dead, then that fact 
    can be delivered as the database's response.  If the SSN refers to a
    person who has been deleted from or never existed in the database, then
    this can be delivered as the database's response, perhaps by raising an
    exception.  The database manager must decide how keys are to be managed, 
    and users of those keys must follow the database manager's directives.

> 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.  

    If the programmer wishes to maximize space efficiency, explicit calls
    to DESTROY can be made when appropriate.  The block exit mechanism
    provides a convenient mechanism by which this directive can be given
    implicitly but unambiguously, with precisely known timing.

> 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.

    Implementing proper storage allocation is the responsibility of the
    person who designs the ADT.  I think average, below average, and
    barely-above-brain-dead programmers can all comprehend the fact that
    objects must be both created and destroyed; they are created upon 
    declaration, and destroyed either by calling DESTROY or as an implicit
    consequence of block exit.

> 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.

    OK, all those who think it's just TERRIBLE to have to actually program 
    for reuseability can *purchase* generic ADTs, a/k/a software components.

    Then you can select the components you need, based on professional
    reviews, rather than implementing them yourself.  (Satisfied?)

    Wizard Software and Lib Systems are two vendors which supply such ADTs;
    anyone considering such a purchase should seek out professional reviews,
    since I write my own ADTs and therefore I have absolutely no experience 
    with and do not in any way endorse either firm's products.

    I might add that Jean Ichbiah explicitly predicted, long ago, the
    emergence of a software components industry, based upon the generic
    features of the (then-new) Ada language.  Slowly but surely, his 
    prediction is being fulfilled.



                                            Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <6702@june.cs.washington.edu>, by klaiber@june.cs.washington.edu (Alexander Klaiber):
> 
> Why do you want to explicitly *prohibit* it [garbage collection]?
> 

    Basically, I charge garbage collection with the same crime that
    the GOTO was charged with: its sole function is to facilitate
    UNDISCIPLINED programming.  From Tremblay and Sorenson, 1985:

       A common thought among proponents of the GOTO is: "I just
       might need it; something might come up".  The answer to
       this appears to be: "Nothing ever does".

    If this charge can be successfully prosecuted, then garbage
    collection will face the same penalty: the total elimination 
    of the facility, in favor of a more disciplined environment.



                                          Bill Wolfe

                                  wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Richard A. O'Keefe]

In article <3865@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>    Basically, I charge garbage collection with the same crime that
>    the GOTO was charged with: its sole function is to facilitate
>    UNDISCIPLINED programming.  From Tremblay and Sorenson, 1985:

This is completely back-to-front.  Doing your own storage management
is like doing your own stack management instead of using procedure calls.
If you want to compare garbage collection with a control structure,
compare it with resursive procedures.

>    If this charge can be successfully prosecuted, then garbage
>    collection will face the same penalty: the total elimination 
>    of the facility, in favor of a more disciplined environment.

I think it would be very hard to accuse functional programming languages
like ML of providing an _un_disciplined environment.  Yet automatic storage
control is vital to them.  A word about the history of ML may make this
clearer.  ML was originally the MetaLanguage of Edinburgh LCF, a system
for doing proofs about computations.  It is strongly typed, because it
was important that anything the system claimed to be a proof should be a
valid proof.  There is a basic set of proof-forming operations which are
known to be valid.  The language cannot permit changes to elements of a
data structure, otherwise the arguments to a proof might be changed after
the proof was constructed, rendering it invalid.  "deallocate" simply
doesn't make sense in that kind of environment.  Storage management is
particularly easy in a language without side effects to data structures.

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <864@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe):
> In article <3865@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>>    Basically, I charge garbage collection with the same crime that
>>    the GOTO was charged with: its sole function is to facilitate
>>    UNDISCIPLINED programming.  From Tremblay and Sorenson, 1985:
> 
> This is completely back-to-front.  Doing your own storage management
> is like doing your own stack management instead of using procedure calls.

     Procedure calls are used to manage the complexity of creating the
     structure and of maintaining it.  They should also be used to
     manage its destruction.  This is clear and consistent, and promotes
     readable and reliable operations on a well-defined structure with
     well-defined space/time properties.

> I think it would be very hard to accuse functional programming languages
> like ML of providing an _un_disciplined environment.  [...] 
> Storage management is particularly easy in a language without 
> side effects to data structures.

     OK, try getting a referentially transparent language to
     handle systems which are not static, but change over time.

     With increased power comes increased responsibility.   


                                      Bill Wolfe

                              wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[ryer]

Currently, Ada neither requires nor precludes garbage collection.  For 
example, the Symbolics Ada compiler provides it (as well they should), but
none of the eight cross-compilers for the 1750A computer does (as they 
shouldn't).

What are you (any of you) proposing?  That ALL Ada compilers should have
garbage collection?  Than no Ada compilers should be allowed to have it?
Pragmas?

Each day I find a new collection of comments on this note, debating the
goodness of garbage collection in the abstract.  I think that the Ada 
language has already taken the only defensible position, and would be
happy to explain why if anyone wants to take a different concrete position.

Mike "speaking only for myself" Ryer
Intermetrics, Inc.

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <124000028@inmet>, by ryer@inmet.UUCP:
> Currently, Ada neither requires nor precludes garbage collection.  [...] 
> What are you (any of you) proposing?  That ALL Ada compilers should have
> garbage collection?  Than no Ada compilers should be allowed to have it?
> Each day I find a new collection of comments on this note, debating the
> goodness of garbage collection in the abstract.  I think that the Ada 
> language has already taken the only defensible position, and would be
> happy to explain why if anyone wants to take a different concrete position.

    OK, I'll take the position that Ada should be defined such that
    no Ada compilers should be allowed to have garbage collection.

    I charge that GC encourages the production of sloppy code which
    is difficult to maintain and which compiles into permanently inefficient
    programs, that code can be written by space-conscious programmers
    at least as fast as by those who use GC as a crutch, and that such
    code will require less debugging time due to the more complete 
    understanding of the problem which is possessed by a programmer 
    who comprehends all aspects (both space and time) of his/her code,
    and that GC retards portability by making code non-reuseable from
    the perspective of real-time programmers.

    For all these reasons, I conclude that GC should be prohibited, 
    just as the GOTO should be (but unfortunately, is not yet) prohibited. 
    
    Your turn.



                                            Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[ryer]

Why some Ada compilers should be allowed to perform garbage collection:

a. Because they are to generate code that coexists in an environment with
languages like LISP where garbage collection is assumed.  They want to
operate on data structures shared with other languages.

b. Because the current world supply of "reusable" Ada components have
not all been written carefully for space management, and in prototyping
any reusable component (that works) may be better than none.

c. Because some users are very unconcerned with the efficiency or
reusability of their programs.  This applies to the run-only-once
programs such as in a training environment, or where a computer is used
as an oversized desk calculator just to obtain numeric answers.  It may
be that all computer science students should become careful implementers
of ADTs.  I doubt that all particle physicists need to develop this
discipline even though they may write substantial programs.

d. It Is FEASIBLE for the computer to do a good job of garbage collection
automatically and it does reduce the size of the source code which does
tend to reduce the life cycle cost of owning that code.  It may increase
execution time but some users will prefer this tradeoff.

Therefore, garbage collection should not be prohibited, even though it
is inappropriate and harmful in some cases.  Different applications
can benefit from different compilers.

Mike Ryer
Intermetrics

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <124000031@inmet>, by ryer@inmet.UUCP:
> 
> Why some Ada compilers should be allowed to perform garbage collection:
> 
> a. Because they are to generate code that coexists in an environment with
> languages like LISP where garbage collection is assumed.  They want to
> operate on data structures shared with other languages.

     Assume that the Ada code cleans up after itself.  Then that code
     can exist perfectly in a Lisp environment; since it does not
     contribute to the garbage problem, the Ada code will be a
     very welcome guest indeed.  

> b. Because the current world supply of "reusable" Ada components have
> not all been written carefully for space management, and in prototyping
> any reusable component (that works) may be better than none.

     However, I'll bet that most have.  At any rate, once New Ada
     emerges, you can bet there will be an immediate upgrading
     taking place among all the component vendors; the upgraded
     components will be available long before the New Ada compilers.

> c. Because some users are very unconcerned with the efficiency or
> reusability of their programs.  This applies to the run-only-once
> programs such as in a training environment, or where a computer is used
> as an oversized desk calculator just to obtain numeric answers.  It may
> be that all computer science students should become careful implementers
> of ADTs.  I doubt that all particle physicists need to develop this
> discipline even though they may write substantial programs.

     Let's face it: with generics, multitasking, and so on, Ada is
     a language for professionals.  Most nonprofessionals should be using
     application-specific languages, which are implemented in... Ada. 

     Particle physicists usually require high-performance software,
     and they should therefore turn to professional application developers.

> d. It Is FEASIBLE for the computer to do a good job of garbage collection
> automatically and it does reduce the size of the source code which does
> tend to reduce the life cycle cost of owning that code.  It may increase
> execution time but some users will prefer this tradeoff.

     The reduction in size is trivial.  Additionally, I contend that there
     are positive side effects with regard to a more complete programmer
     understanding of the problem, which leads to better overall code.

     Furthermore, the use of the ADT paradigm, in conjunction with 
     the automatic destruction of local environments, means that
     application programmers will almost never have to deal with deallocation
     on an explicit basis anyway.  This will provide positive incentive
     to use professionally designed ADTs, leading once again to higher-
     quality code.

> Therefore, garbage collection should not be prohibited, even though it
> is inappropriate and harmful in some cases. 

     I'll heartily agree that GC is inappropriate and harmful, but
     you still haven't proven your case.


                                     Bill Wolfe

                              wtwolfe@hubcap.clemson.edu