* Re: Collective response to := messages
@ 1988-12-03 22:53 Erland Sommarskog
1988-12-04 20:41 ` William Thomas Wolfe,2847,
0 siblings, 1 reply; 29+ messages in thread
From: Erland Sommarskog @ 1988-12-03 22:53 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Collective response to := messages
1988-12-03 22:53 Collective response to := messages Erland Sommarskog
@ 1988-12-04 20:41 ` William Thomas Wolfe,2847,
1988-12-05 5:47 ` Richard A. O'Keefe
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-04 20:41 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Collective response to := messages
1988-12-04 20:41 ` William Thomas Wolfe,2847,
@ 1988-12-05 5:47 ` Richard A. O'Keefe
1988-12-05 12:45 ` William Thomas Wolfe,2847,
0 siblings, 1 reply; 29+ messages in thread
From: Richard A. O'Keefe @ 1988-12-05 5:47 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Collective response to := messages
1988-12-05 5:47 ` Richard A. O'Keefe
@ 1988-12-05 12:45 ` William Thomas Wolfe,2847,
1988-12-06 1:54 ` Richard A. O'Keefe
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-05 12:45 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Collective response to := messages
1988-12-05 12:45 ` William Thomas Wolfe,2847,
@ 1988-12-06 1:54 ` Richard A. O'Keefe
1988-12-06 20:43 ` William Thomas Wolfe,2847,
1988-12-07 15:22 ` Collective response to := messa ron
0 siblings, 2 replies; 29+ messages in thread
From: Richard A. O'Keefe @ 1988-12-06 1:54 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Collective response to := messages
1988-12-06 1:54 ` Richard A. O'Keefe
@ 1988-12-06 20:43 ` William Thomas Wolfe,2847,
1988-12-07 15:22 ` Collective response to := messa ron
1 sibling, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-06 20:43 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Collective response to := messa
1988-12-06 1:54 ` Richard A. O'Keefe
1988-12-06 20:43 ` William Thomas Wolfe,2847,
@ 1988-12-07 15:22 ` ron
1988-12-11 19:11 ` Garbage Collection William Thomas Wolfe,2847,
1 sibling, 1 reply; 29+ messages in thread
From: ron @ 1988-12-07 15:22 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-07 15:22 ` Collective response to := messa ron
@ 1988-12-11 19:11 ` William Thomas Wolfe,2847,
1988-12-12 5:29 ` John Gateley
` (2 more replies)
0 siblings, 3 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-11 19:11 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-11 19:11 ` Garbage Collection William Thomas Wolfe,2847,
@ 1988-12-12 5:29 ` John Gateley
1988-12-12 18:19 ` William Thomas Wolfe,2847,
1989-01-02 17:51 ` ryer
1989-01-06 16:58 ` ryer
2 siblings, 1 reply; 29+ messages in thread
From: John Gateley @ 1988-12-12 5:29 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-12 5:29 ` John Gateley
@ 1988-12-12 18:19 ` William Thomas Wolfe,2847,
1988-12-13 1:02 ` Alexander Klaiber
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-12 18:19 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-12 18:19 ` William Thomas Wolfe,2847,
@ 1988-12-13 1:02 ` Alexander Klaiber
1988-12-13 18:37 ` William Thomas Wolfe,2847,
1988-12-13 20:22 ` Garbage Collection William Thomas Wolfe,2847,
0 siblings, 2 replies; 29+ messages in thread
From: Alexander Klaiber @ 1988-12-13 1:02 UTC (permalink / raw)
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*!
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 1:02 ` Alexander Klaiber
@ 1988-12-13 18:37 ` William Thomas Wolfe,2847,
1988-12-13 23:36 ` Alexander Klaiber
` (2 more replies)
1988-12-13 20:22 ` Garbage Collection William Thomas Wolfe,2847,
1 sibling, 3 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-13 18:37 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 1:02 ` Alexander Klaiber
1988-12-13 18:37 ` William Thomas Wolfe,2847,
@ 1988-12-13 20:22 ` William Thomas Wolfe,2847,
1988-12-14 6:40 ` Richard A. O'Keefe
1 sibling, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-13 20:22 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 18:37 ` William Thomas Wolfe,2847,
@ 1988-12-13 23:36 ` Alexander Klaiber
1988-12-14 3:26 ` William Thomas Wolfe,2847,
` (2 more replies)
1988-12-14 23:30 ` John Gateley
1988-12-16 0:49 ` Keys are references, too (was Re: Garbage Collection) Badger BA 64810
2 siblings, 3 replies; 29+ messages in thread
From: Alexander Klaiber @ 1988-12-13 23:36 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 23:36 ` Alexander Klaiber
@ 1988-12-14 3:26 ` William Thomas Wolfe,2847,
1988-12-14 17:16 ` Stephe Leake
1988-12-15 14:43 ` Thomas P. Morris
2 siblings, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-14 3:26 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 20:22 ` Garbage Collection William Thomas Wolfe,2847,
@ 1988-12-14 6:40 ` Richard A. O'Keefe
1988-12-14 17:43 ` William Thomas Wolfe,2847,
0 siblings, 1 reply; 29+ messages in thread
From: Richard A. O'Keefe @ 1988-12-14 6:40 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 23:36 ` Alexander Klaiber
1988-12-14 3:26 ` William Thomas Wolfe,2847,
@ 1988-12-14 17:16 ` Stephe Leake
1988-12-15 14:43 ` Thomas P. Morris
2 siblings, 0 replies; 29+ messages in thread
From: Stephe Leake @ 1988-12-14 17:16 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-14 6:40 ` Richard A. O'Keefe
@ 1988-12-14 17:43 ` William Thomas Wolfe,2847,
0 siblings, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-14 17:43 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 18:37 ` William Thomas Wolfe,2847,
1988-12-13 23:36 ` Alexander Klaiber
@ 1988-12-14 23:30 ` John Gateley
1988-12-15 19:25 ` William Thomas Wolfe,2847,
1988-12-16 0:49 ` Keys are references, too (was Re: Garbage Collection) Badger BA 64810
2 siblings, 1 reply; 29+ messages in thread
From: John Gateley @ 1988-12-14 23:30 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-13 23:36 ` Alexander Klaiber
1988-12-14 3:26 ` William Thomas Wolfe,2847,
1988-12-14 17:16 ` Stephe Leake
@ 1988-12-15 14:43 ` Thomas P. Morris
2 siblings, 0 replies; 29+ messages in thread
From: Thomas P. Morris @ 1988-12-15 14:43 UTC (permalink / raw)
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
-----------------------------------------------------------------------------
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-14 23:30 ` John Gateley
@ 1988-12-15 19:25 ` William Thomas Wolfe,2847,
1988-12-19 16:12 ` John Gateley
0 siblings, 1 reply; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-15 19:25 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Keys are references, too (was Re: Garbage Collection)
1988-12-13 18:37 ` William Thomas Wolfe,2847,
1988-12-13 23:36 ` Alexander Klaiber
1988-12-14 23:30 ` John Gateley
@ 1988-12-16 0:49 ` Badger BA 64810
1988-12-18 18:42 ` William Thomas Wolfe,2847,
2 siblings, 1 reply; 29+ messages in thread
From: Badger BA 64810 @ 1988-12-16 0:49 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Keys are references, too (was Re: Garbage Collection)
1988-12-16 0:49 ` Keys are references, too (was Re: Garbage Collection) Badger BA 64810
@ 1988-12-18 18:42 ` William Thomas Wolfe,2847,
0 siblings, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1988-12-18 18:42 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-15 19:25 ` William Thomas Wolfe,2847,
@ 1988-12-19 16:12 ` John Gateley
1988-12-20 19:34 ` Bill Wolfe
0 siblings, 1 reply; 29+ messages in thread
From: John Gateley @ 1988-12-19 16:12 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-19 16:12 ` John Gateley
@ 1988-12-20 19:34 ` Bill Wolfe
0 siblings, 0 replies; 29+ messages in thread
From: Bill Wolfe @ 1988-12-20 19:34 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-11 19:11 ` Garbage Collection William Thomas Wolfe,2847,
1988-12-12 5:29 ` John Gateley
@ 1989-01-02 17:51 ` ryer
1989-01-05 8:31 ` William Thomas Wolfe,2847,
1989-01-06 16:58 ` ryer
2 siblings, 1 reply; 29+ messages in thread
From: ryer @ 1989-01-02 17:51 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1989-01-02 17:51 ` ryer
@ 1989-01-05 8:31 ` William Thomas Wolfe,2847,
0 siblings, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-05 8:31 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1988-12-11 19:11 ` Garbage Collection William Thomas Wolfe,2847,
1988-12-12 5:29 ` John Gateley
1989-01-02 17:51 ` ryer
@ 1989-01-06 16:58 ` ryer
1989-01-08 19:24 ` William Thomas Wolfe,2847,
2 siblings, 1 reply; 29+ messages in thread
From: ryer @ 1989-01-06 16:58 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: Garbage Collection
1989-01-06 16:58 ` ryer
@ 1989-01-08 19:24 ` William Thomas Wolfe,2847,
0 siblings, 0 replies; 29+ messages in thread
From: William Thomas Wolfe,2847, @ 1989-01-08 19:24 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 29+ messages in thread
end of thread, other threads:[~1989-01-08 19:24 UTC | newest]
Thread overview: 29+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1988-12-03 22:53 Collective response to := messages Erland Sommarskog
1988-12-04 20:41 ` William Thomas Wolfe,2847,
1988-12-05 5:47 ` Richard A. O'Keefe
1988-12-05 12:45 ` William Thomas Wolfe,2847,
1988-12-06 1:54 ` Richard A. O'Keefe
1988-12-06 20:43 ` William Thomas Wolfe,2847,
1988-12-07 15:22 ` Collective response to := messa ron
1988-12-11 19:11 ` Garbage Collection William Thomas Wolfe,2847,
1988-12-12 5:29 ` John Gateley
1988-12-12 18:19 ` William Thomas Wolfe,2847,
1988-12-13 1:02 ` Alexander Klaiber
1988-12-13 18:37 ` William Thomas Wolfe,2847,
1988-12-13 23:36 ` Alexander Klaiber
1988-12-14 3:26 ` William Thomas Wolfe,2847,
1988-12-14 17:16 ` Stephe Leake
1988-12-15 14:43 ` Thomas P. Morris
1988-12-14 23:30 ` John Gateley
1988-12-15 19:25 ` William Thomas Wolfe,2847,
1988-12-19 16:12 ` John Gateley
1988-12-20 19:34 ` Bill Wolfe
1988-12-16 0:49 ` Keys are references, too (was Re: Garbage Collection) Badger BA 64810
1988-12-18 18:42 ` William Thomas Wolfe,2847,
1988-12-13 20:22 ` Garbage Collection William Thomas Wolfe,2847,
1988-12-14 6:40 ` Richard A. O'Keefe
1988-12-14 17:43 ` William Thomas Wolfe,2847,
1989-01-02 17:51 ` ryer
1989-01-05 8:31 ` William Thomas Wolfe,2847,
1989-01-06 16:58 ` ryer
1989-01-08 19:24 ` William Thomas Wolfe,2847,
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox