Re: Garbage Collection

Re: Garbage Collection

[Erland Sommarskog]

I gave an example where I stored pointers in a tree, and tried
to make Bill Wolfe explain how this should work with his idea 
with deallocation on block exit. He answered, but I wouldn't 
say I'm satisfied... I still don't see where he is heading.

>   Since the user supplied an access type as the type of object to be
>   stored in the tree, the user bears full responsibility for making
>   responsible use of the fact that he/she is dealing with a tree of pointers.

Well, assume that Assign the procedure I write for Some_access_type 
(the type I store in the tree) is simply A := B. With your scheme I 
can't but see that the object I allocated is deallocated when I exit  
my procedure, although I still have a reference to it, stored in
the tree.
  Bill, tell me, what is wrong here? My understanding of your proposal,
or the program I have written? If you think the latter, explain to me
how the compiler should detect the error I'm doing. Or do you really 
think such an error should remain undiscovered until run-time? And
does that rhyme with your eagerness for simplify maintenance?

>> Several times in this discussion Bill Wolfe has claimed that 
>> garbage collection is a trouble-maker for maintainers. In what way? 
>
>      When there is great difficulty deciding whether a given object 
>      exists or not, the maintainer experiences great difficulty 
>      pinning down the precise state of the program.  

You have just given an excellent argument for garbage collection.
With garbage collection, only the objects that have references
exist. Without, there may be other objects that are unreachable.
With garbage collection you are sure of that all initiated non-null
references point to actual objects. Without, you may by mistake
be pointing straight into free space, or right in the middle of
some completely other kind of object. 
  The only incertainty you have with garbage collection is whether 
a non-referred object has yet been returned to free memory, depending
on wether the garbage collector has come there or not. But since 
the object no longer is part of the system, this question is of 
little interest.

>>   Much worse for maintainence is when the system dies with "System 
>> access violation" or "segmentation fault" from time to time and you 
>> don't know why. The reason may be that an allocated area was erroneously 
>> released and then reused and the original data, that someone appearently 
>> is relying in, has been over-written. Or because an already deallocated 
>> was deallocated a second time.

I forgot: When the system chokes with "heap full" and you as a maintainer
is trying to find where all space is being wasted. With garbage collection
you at least know that all this memory is being used. Without, you don't 
know if it is just memory leakage or real overuse.

>    DESTROY procedures are easy to write, need only be written once
>    per ADT, and can be reused indefinitely.  GC costs us the
>    computer time required to repeatedly determine which storage
>    is in use and which is not, and this cost must be paid repeatedly
>    AT RUN TIME.  Given that this PERMANENT, RUN_TIME COST can be
>    avoided by simply communicating the fact that a particular object
>    is no longer needed, GC is a rather costly crutch for lazy programmers. 

1) You have several times stated that the callers of your ADTs 
are responsible for that their destroy procedures are called.
So it's not only to write them. You must remember to call them
too. And when you forget, it takes time find out where.

2) Much of this talk reminds of what hear from C programmers when
range and type checking is being discussed. And the same arguments  
apply. If all programmers were skilled enough to do everything
right we wouldn't need Ada or high-level langauges at all. Actually,
if everyone else is taking help of computers these days, why shouldn't
programmers do?
  Just like range and type checking, garbage collection is a device
that increases our thrust in that the system does what we intended.

3) I recommend you to read "Object-Oriented Software Construction"
by Bertrand Meyer. There he explains why garbage collection is
necessary in an object-oriented system. He also describes how the
garbage collector is implemented in the Eiffel system. (Eiffel is
an object-oriented language, devised by Mr. Meyer, and comemercially
available.) 
-- 
Erland Sommarskog
ENEA Data, Stockholm              This signature is not to be quoted.
sommar@enea.se

Re: Garbage Collection

[Bill Wolfe]

From article <4200@enea.se>, by sommar@enea.se (Erland Sommarskog):
>>   Since the user supplied an access type as the type of object to be
>>   stored in the tree, the user bears full responsibility for making
>>   responsible use of the fact that he/she is dealing with a tree of pointers.
> 
> Well, assume that Assign the procedure I write for Some_access_type 
> (the type I store in the tree) is simply A := B. With your scheme I 
> can't but see that the object I allocated is deallocated when I exit  
> my procedure, although I still have a reference to it, stored in
> the tree.

    One more time.  A exists within the tree.  The tree is a PARAMETER.
    The tree is NOT a local variable.  Hence, upon exit from the ASSIGN
    procedure, A will not suffer deallocation.  Now what about B?  It's
    a parameter too, and also will not be deallocated.
 
>   Bill, tell me, what is wrong here? My understanding of your proposal,
> or the program I have written? 

    Your understanding of my proposal.  I'm having a really hard time
    trying to figure out what you're thinking of here.  I thought everything
    had been clearly defined in terms that any Pascal/Modula-2/Ada programmer
    would understand.

> I forgot: When the system chokes with "heap full" and you as a maintainer
> is trying to find where all space is being wasted. With garbage collection
> you at least know that all this memory is being used. Without, you don't 
> know if it is just memory leakage or real overuse.

     Advanced debugging tools should be used to address this issue.

>>    DESTROY procedures are easy to write, need only be written once
>>    per ADT, and can be reused indefinitely.  GC costs us the
>>    computer time required to repeatedly determine which storage
>>    is in use and which is not, and this cost must be paid repeatedly
>>    AT RUN TIME.  Given that this PERMANENT, RUN_TIME COST can be
>>    avoided by simply communicating the fact that a particular object
>>    is no longer needed, GC is a rather costly crutch for lazy programmers. 
> 
> 1) You have several times stated that the callers of your ADTs 
> are responsible for that their destroy procedures are called.
> So it's not only to write them. You must remember to call them
> too. And when you forget, it takes time find out where.

   I'm TRYING to get Ada to integrate the automatic destruction of local
   variables which occurs during block exit with ADT destruction procedures,
   so the user can rely on the implicit deallocation request associated
   with block exit.  Let me give a concrete example:

      procedure EXAMPLE (A : in out ADT);

         B : ADT;
         C : INTEGER;

      [body of procedure EXAMPLE]

    Now when the body of procedure EXAMPLE has finished executing,
    in current Ada C will be properly destroyed, but B will not.
    If B is implemented as a pointer to something, that pointer will
    be destroyed, and everything it pointed to will become garbage.
    By integrating the DESTROY procedure into block exit, everything
    B pointed to will be deallocated as well.  Since A is a parameter,
    it is not part of the locally defined environment; it is instead
    part of the caller's environment, and will stay that way.  In the
    revised version, the "right" DESTROY procedure will apply to B
    as well as C, thus enabling the use of implicit destruction,
    which is the most frequently used method of destruction. 

> 3) I recommend you to read "Object-Oriented Software Construction"
> by Bertrand Meyer. There he explains why garbage collection is
> necessary in an object-oriented system. He also describes how the
> garbage collector is implemented in the Eiffel system. (Eiffel is
> an object-oriented language, devised by Mr. Meyer, and comemercially
> available.) 

   I'm quite aware of Eiffel, and I have just shown (in another article)
   how reliance upon garbage collection is a sure way to get your ADT
   rejected by users who are programming critical applications.  This
   same argument applies to Eiffel and the other members of the peanut
   gallery; they are unsuitable for critical applications, among their
   many other flaws.  May I suggest David Harland's "Concurrency and 
   Programming Languages"?

   Representation of classes of types is better accomplished through a
   synthesis approach, rather than an inheritance approach; however, this
   is presently a research topic.  Followups on this to comp.lang.sigplan
   or e-mail, please.  


                                        Bill Wolfe

                                 wtwolfe@hubcap.clemson.edu

Re: Life under implicit destruction

[William Thomas Wolfe,2847,]

From article <3996@hubcap.UUCP>, by wtwolfe@hubcap.UUCP (Bill Wolfe):
> From article <4200@enea.se>, by sommar@enea.se (Erland Sommarskog):
>> 1) You have several times stated that the callers of your ADTs 
>> are responsible for that their destroy procedures are called.
>> So it's not only to write them. You must remember to call them
>> too. And when you forget, it takes time find out where.

   Allow me to summarize Life Under Implicit Destruction, with
   particular regard to programmer's responsibilities.

      1) The responsibility for managing storage falls almost
         completely upon ADT designers.  They must write all
         code having to do with allocating and deallocating
         (and reusing old) storage associated with their ADT.

      2) Users of the ADTs (application programmers) have only two
         reasons for manually invoking DESTROY procedures:

            a) Space is so tight that storage for every object must
               be reclaimed the moment it is no longer useful.

            b) To communicate to the maintainer and to the compiler
               that a given variable is "dead".

      3) Barring either of the two situations above, application programmers
         will be concerned with space only in that they must create the
         variables that they use, which is one of the effects of declaring
         a variable (LRM 3.2.1 (7)).  Currently, they are already accustomed
         to declaring/creating their variables, so no additional work there.

   To summarize, given the integration of ADT destruction routines into
   block exit, application programmers will have NO (count 'em, none) 
   additional responsibilities, provided that they use ADTs rather than
   trying to play with pointers themselves.  

   There are a few situations, such as construction of abstract syntax
   trees in a compiler, in which application programmers really cannot
   depend on ADTs to isolate them from data structure management.  In
   such cases, it may be best to borrow an ADT designer (a person who
   is very much accustomed to space management) and have that person
   desk-check and debug the final code with regard to space management;
   perhaps the application programmers did OK by themselves, and I would
   certainly hope that they did, but judging from the howls of protest
   concerning how difficult it is to manage storage, I now tend to doubt
   that the average applications programmer without ADT design experience
   is capable of handling storage management in a professional manner.

   (I hope I'm wrong; if anyone thinks storage management should be
   within the intellectual capability of the average applications
   programmer to handle, please speak up!)
 
   The ADT designers have the reponsibility of managing storage, but
   since they must satisfy the real-time programmers, they have this
   responsibility already.

   Since GC is worthless to an ADT designer, and application programmers
   won't generally be doing things that would require GC anyway (and
   I've outlined the contingency plan for when they do), there is 
   simply no need for garbage collection.  It gives us only a permanent, 
   run-time cost, and no useful benefit, especially since it must waste 
   most of its time looking at storage which is being managed ALREADY
   by the combination of scope management rules and ADT designers.



                                            Bill Wolfe

                                     wtwolfe@hubcap.clemson.edu