garbage collection

garbage collection

[Ronald Ayoub]

In the book "Programming in Ada 95" by Barnes he says:

If an allocated object becomes inaccessbile becasue no declard objects refer
to it directly or indirectly then the storage it occupies may be reclaimed
so that it can be reused for other objects. An implementation may (but need
not) provide garbage collection for this.

I need this to be clarified for me. If an implementation doesn't provide 
garbage collection then that storage is forever lost, is that correct? Or
does this mean that it may not be garbage collected but when a call to new
is executed it is at that time scene as available. Please clarify. This seems
like a real bad idea not to have some form of garbage collection inforced.

Ron

Re: garbage collection

[Robert I. Eachus]

Ronald Ayoub wrote:
 
> I need this to be clarified for me. If an implementation doesn't provide
> garbage collection then that storage is forever lost, is that correct? Or
> does this mean that it may not be garbage collected but when a call to new
> is executed it is at that time scene as available. Please clarify. This seems
> like a real bad idea not to have some form of garbage collection inforced.

   The correct answer is c) All Ada compilers provide some forms of
storage management, and most Ada programs lose no storage.  But very few
Ada implementations support compacting garbage collectors.

   I could go into all the gory details, but that about sums it up.  The
validation tests do include several tests to insure that storage is not
lost in many common situations, but there is no requirement that storage
be freed the moment their are no more references.  Many Ada compilers
instead free the storage when the access type goes out of scope for some
or all types.

   Why?  Three reasons.  Freeing the storage when the type goes out of
scope allows for predictable storage reclamation which is very useful in
real-time code.  Second, the user can easily manage storage for any type
the way he wants to.  Insisting on "full" garbage collection would limit
the user's choices.

   And finally, Ada allows return values from functions which are
unbounded, and for which the storage is "automagically" managed.  If you
define a function which returns a string in Ada, there is no need for
explicit alloc and free calls or the equivalent.  So in ninety percent
or more of the cases where you need garbage collection in other
languages, you don't even need explicit allocations in Ada.

-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: garbage collection

[Gautier]

>    Why?  Three reasons.  Freeing the storage when the type goes out of
> scope allows for predictable storage reclamation which is very useful in
> real-time code.  Second, the user can easily manage storage for any type
> the way he wants to.  Insisting on "full" garbage collection would limit
> the user's choices.

BTW: is it possible to prove that an object is not more accessed 
(of course: as long as its type exists) ? It's so easy to copy a pointer...

-- 
Gautier

Re: garbage collection

[Robert I. Eachus]

> BTW: is it possible to prove that an object is not more accessed
> (of course: as long as its type exists) ? It's so easy to copy a pointer...

  Which is why Ada has access types instead. ;-)  Seriously, if an
access type goes out of scope, then it is legitimate to recover all
storage associated with the type.  If you have gone and done something
like using Unchecked_Conversion to convert to a different access type,
well, you asked for it.  (You can get into similar trouble by saving
addresses.

  The whole idea is that access types are safe as long as you don't go
outside the rules.

-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: garbage collection

[Keith Thompson]

"Robert I. Eachus" <eachus@mitre.org> writes:
[...]
>    I could go into all the gory details, but that about sums it up.  The
> validation tests do include several tests to insure that storage is not
> lost in many common situations, but there is no requirement that storage
> be freed the moment their are no more references.  Many Ada compilers
> instead free the storage when the access type goes out of scope for some
> or all types.
> 
>    Why?  Three reasons.  Freeing the storage when the type goes out of
> scope allows for predictable storage reclamation which is very useful in
> real-time code.  Second, the user can easily manage storage for any type
> the way he wants to.  Insisting on "full" garbage collection would limit
> the user's choices.
[...]

BTW, in my experience most access types don't go out of scope until
the program terminates, because they're declared in library-level
packages.  The automated reclamation can only take place if the access
type is declared directly or indirectly within a subprogram or a task
body (there may be other cases).

(I'm not sure how typical my experience is; how common is it to
declare an access type within a subprogram?)

Note that declaring an access *object* within a subprogram doesn't let
the storage it refers to be reclaimed; the access value could have
been copied to an object in an outer scope before the subprogram
completed.

>    And finally, Ada allows return values from functions which are
> unbounded, and for which the storage is "automagically" managed.  If you
> define a function which returns a string in Ada, there is no need for
> explicit alloc and free calls or the equivalent.  So in ninety percent
> or more of the cases where you need garbage collection in other
> languages, you don't even need explicit allocations in Ada.

Right, I think this is the biggest reason that the lack of garbage
collection in most Ada implementations isn't (much of) a problem.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Robert Dewar]

In article <yec9076vqly.fsf@king.cts.com>,
  Keith Thompson <kst@cts.com> wrote:
> BTW, in my experience most access types don't go out of scope
> until
> the program terminates, because they're declared in
> library-level
> packages.  The automated reclamation can only take place if
> the access
> type is declared directly or indirectly within a subprogram or
> a task
> body (there may be other cases).

True, but the one familiar case in which access types are
declared locally is *precisely* when you want to take advantage
of the compiler being able to free everything on scope exit.
Of course you have to make sure that your compiler has this
capability (GNAT does, I don't know about other Ada 95
compilers).


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[tmoran]

> If an implementation doesn't provide garbage collection then that
> storage is forever lost, is that correct?

No.  When the access type goes out of scope there is clearly no way
the storage can be on the target end of a pointer, so the
implementation should free that storage.  With the 'Storage_Size
attribute on the access type, "the storage for the pool is reclaimed
when the master containing the declaration of the access type is
left".  If that's not soon enough, you have several options,
including:

1) Ada.Unchecked_Deallocation (the equivalent of "free"), if you are
careful not to deallocate and later refer to the same storage.

2) Use a controlled type so your Finalize routine can recycle storage.

3) Do your own storage management for the relevant types using the
Storage_Pool facility.  See Barnes, section 21.4 for a good
discussion of storage management.

4) The most straightforward way, as has been pointed out, is not to
use "new" unnecessarily.  Since you can declare dynamically sized
things inside a subroutine, and can nest subroutines, storage that
is allocated in a stack-like (first allocated is last deallocated)
style can normally be handled with simple declarations, without the
overhead or dangers of "new".  With tasks, you can even have several
separate stack-like allocations going on at once.

Re: garbage collection

[Keith Thompson]

tmoran@bix.com writes:
> > If an implementation doesn't provide garbage collection then that
> > storage is forever lost, is that correct?
> 
> No.  When the access type goes out of scope there is clearly no way
> the storage can be on the target end of a pointer, so the
> implementation should free that storage.

Just to clarify, most implementations don't actually do this.  Thus,
under most Ada implementations, storage *will* be "forever lost" if
you allocate it and don't explicitly deallocate it.  (Well, "forever"
usually means "until the program terminates".)

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Tucker Taft]

Keith Thompson wrote:
> 
> tmoran@bix.com writes:
> > > If an implementation doesn't provide garbage collection then that
> > > storage is forever lost, is that correct?
> >
> > No.  When the access type goes out of scope there is clearly no way
> > the storage can be on the target end of a pointer, so the
> > implementation should free that storage.
> 
> Just to clarify, most implementations don't actually do this.  Thus,
> under most Ada implementations, storage *will* be "forever lost" if
> you allocate it and don't explicitly deallocate it.  (Well, "forever"
> usually means "until the program terminates".)

In Ada 95, implementations are required to reclaim the storage associated
with an access type if the 'Storage_Size attribute is specified (which
Tom also mentioned, by the way).  If no 'Storage_Size is specified, then
you are correct that most Ada 95 compilers don't reclaim the storage
automatically when leaving the scope of the access type.

> --
> Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
> San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
> One of the great tragedies of ancient history is that Helen of Troy
> lived before the invention of the champagne bottle.

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: garbage collection

[Robert Dewar]

In article <37BC2203.328E6338@averstar.com>,
  Tucker Taft <stt@averstar.com> wrote:
> Keith Thompson wrote:
> >
> > tmoran@bix.com writes:
> > > > If an implementation doesn't provide garbage collection
then that
> > > > storage is forever lost, is that correct?
> > >
> > > No.  When the access type goes out of scope there is
clearly no way
> > > the storage can be on the target end of a pointer, so the
> > > implementation should free that storage.
> >
> > Just to clarify, most implementations don't actually do
this.  Thus,
> > under most Ada implementations, storage *will* be "forever
lost" if
> > you allocate it and don't explicitly deallocate it.  (Well,
"forever"
> > usually means "until the program terminates".)
>
> In Ada 95, implementations are required to reclaim the storage
associated
> with an access type if the 'Storage_Size attribute is
specified (which
> Tom also mentioned, by the way).  If no 'Storage_Size is
specified, then
> you are correct that most Ada 95 compilers don't reclaim the
storage
> automatically when leaving the scope of the access type.

Ada compilers have differed here. The old Alsys compilers always
used to automatically free local access stuff on exit. The
trouble is that people are quite used to controlling this
memory manually, and in this case you do add quite a bit
of overhead by arranging for the automatic release.

We went backwards and forwards on what the default should be
in GNAT, and decided finally that the default was not to free
this storage, however, it is trivial to specify that the space
for a local access collection SHOULD be freed on access by
using:

   for access_type_name'Storage_Pool
     use System.Pool_Local.Unbounded_Reclaim_Pool;

Probably a good idea would be to add a configuration pragma
that made this pool assignment the default.

By the way, a recommendation is to look through the collection
of storage pool implementations provided in GNAT, there is a lot
of useful functionality there, including a very useful debug
pool that checks for correct storage handling.

P.S. Ada 83 also required that access types with an explicit
storage size be freed on scope exit. The Ada 83 RM strongly
suggests that this should be the default for all access types,
but stops short of requiring this. Even the implication is
removed from the Ada 95 RM.

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[Robert Dewar]

In article <37BC2203.328E6338@averstar.com>,
  Tucker Taft <stt@averstar.com> wrote:
> Keith Thompson wrote:
> >
> > tmoran@bix.com writes:
> > > > If an implementation doesn't provide garbage collection
then that
> > > > storage is forever lost, is that correct?
> > >
> > > No.  When the access type goes out of scope there is
clearly no way
> > > the storage can be on the target end of a pointer, so the
> > > implementation should free that storage.
> >
> > Just to clarify, most implementations don't actually do
this.  Thus,
> > under most Ada implementations, storage *will* be "forever
lost" if
> > you allocate it and don't explicitly deallocate it.  (Well,
"forever"
> > usually means "until the program terminates".)
>
> In Ada 95, implementations are required to reclaim the storage
associated
> with an access type if the 'Storage_Size attribute is
specified (which
> Tom also mentioned, by the way).  If no 'Storage_Size is
specified, then
> you are correct that most Ada 95 compilers don't reclaim the
storage
> automatically when leaving the scope of the access type.

Ada compilers have differed here. The old Alsys compilers always
used to automatically free local access stuff on exit. The
trouble is that people are quite used to controlling this
memory manually, and in this case you do add quite a bit
of overhead by arranging for the automatic release.

We went backwards and forwards on what the default should be
in GNAT, and decided finally that the default was not to free
this storage, however, it is trivial to specify that the space
for a local access collection SHOULD be freed on access by
using:

   for access_type_name'Storage_Pool
     use System.Pool_Local.Unbounded_Reclaim_Pool;

Probably a good idea would be to add a configuration pragma
that made this pool assignment the default.

By the way, a recommendation is to look through the collection
of storage pool implementations provided in GNAT, there is a lot
of useful functionality there, including a very useful debug
pool that checks for correct storage handling.

P.S. Ada 83 also required that access types with an explicit
storage size be freed on scope exit. The Ada 83 RM strongly
suggests that this should be the default for all access types,
but stops short of requiring this. Even the implication is
removed from the Ada 95 RM.

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[tmoran]

> > No.  When the access type goes out of scope there is clearly no way
> > the storage can be on the target end of a pointer, so the
> > implementation should free that storage.
>
> Just to clarify, most implementations don't actually do this.
  Why?  Is an implementation not easy, efficient, and predictable?
And of course overidable by the user simply by raising the
level where the access type is declared.
  It seems undesirable to have to specify a number, big enough, but
not too big, for the amount of storage needed when you merely want
to get automatic deallocation.

Re: garbage collection

[Keith Thompson]

tmoran@bix.com writes:
> > > No.  When the access type goes out of scope there is clearly no way
> > > the storage can be on the target end of a pointer, so the
> > > implementation should free that storage.
> >
> > Just to clarify, most implementations don't actually do this.
>   Why?  Is an implementation not easy, efficient, and predictable?
> And of course overidable by the user simply by raising the
> level where the access type is declared.
>   It seems undesirable to have to specify a number, big enough, but
> not too big, for the amount of storage needed when you merely want
> to get automatic deallocation.

I just realized that I had mis-read the article to which I was
responding.  What "most implementations don't actually do" is general
garbage collection, i.e., freeing allocated memory after it becomes
inaccessible.  Freeing allocated memory when leaving the scope of an
access type is much easier.

I *think* that most implementations don't even do this, but I'm not as
sure on this point.  It does impose a little extra overhead, in both
time and space.

Specifying the 'Storage_Pool attribute is a very powerful and
under-used feature, IMHO.  The biggest obstacle to its use, I suspect,
is the need to implement the Storage_Pool operations.

If System.Storage_Pools also provided routines for dereferencing
access values (perhaps one each for reading and writing), and perhaps
also for initialization and finalization of access objects, it would
be even more powerful.  I haven't entirely thought this through, so it
may be a bad idea for some reason.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Matthew Heaney]

In article <yecwvuqhrkx.fsf@king.cts.com> , Keith Thompson <kst@cts.com>  
wrote:

> Specifying the 'Storage_Pool attribute is a very powerful and
> under-used feature, IMHO.  The biggest obstacle to its use, I suspect,
> is the need to implement the Storage_Pool operations.

One thing I miss is not having a set of nameable, pre-defined storage pools.
You have that in GNAT, but it's not really portable because of certain
low-level calls (to a C routine called "_gnat__allocate", or something like
that).


> If System.Storage_Pools also provided routines for dereferencing
> access values (perhaps one each for reading and writing), and perhaps
> also for initialization and finalization of access objects, it would
> be even more powerful.  I haven't entirely thought this through, so it
> may be a bad idea for some reason.

That's one nice thing about C++.  You can implement a pointer abstraction
that has a syntax identical to a built-in pointer.  In Ada95, you have to
implement a "handle" type that provides a dereference operator:

  type T (<>) is limited private;

  type T_Access is access all T;

  type T_Handle is private;

  function "+" (Handle : T_Handle) return T_Access;

All the primitive operations of T take access parameters, since we're always
dealing with pointers to T:

  procedure Op (O : access T);

  function Get_Attribute (O : access T) return Attr_T;

You also have constructor(s) that return a handle object:

  function New_T return T_Handle;  -- not T_Access


All the actual garbage collection is associated with T_Handle, since there's
no way to do that with the access type T_Access directly.  (Which is how
Ada95 differs from C++.)

I use this technique to implement reference-counting for on-the-heap
abstractions, so that when the count drops to zero the memory is
automatically reclaimed.  See the patterns archives for lots of examples.

<http://www.acm.org/archives/patterns.html>

The only trap door in this scheme is that there's no way to prevent the
client from manipulating the access object directly, say, by making a copy.
It has to be understood by users that that is something you never do with a
handle-based abstraction.

It would be swell if the language were amended to make access types limited;
this would prevent any problems engendered by accidental copying of access
objects.

--
Matt

It is impossible to feel great confidence in a negative theory which has
always rested its main support on the weak points of its opponent.

Joseph Needham, "A Mechanistic Criticism of Vitalism"

Re: garbage collection

[Keith Thompson]

"Matthew Heaney" <matthew_heaney@acm.org> writes:
[...]
> It would be swell if the language were amended to make access types limited;
> this would prevent any problems engendered by accidental copying of access
> objects.

Not all access types, I hope; sometimes you do want to copy access
values!

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Robert Dewar]

In article <yecvha9izs6.fsf@king.cts.com>,
> "Matthew Heaney" <matthew_heaney@acm.org> writes:
> [...]
> > It would be swell if the language were amended to make
access types limited;
> > this would prevent any problems engendered by accidental
copying of access
> > objects.

There has *got* to be a smiley missing here. It is inconceivable
to make this change to the language (all access types limited)
and would be HIGHLY undesirable.

Presumably, if the above is not a joke (which it might be,
I am not sure), it is a proposal for some kind of extension
involving limited access types.

Actually I think the reasonable thing to do is to extend the
storage pool abstraction so that a version of it contains
a copy operation that is called for all implicit copies of
the given access value. You probably want to introduce some
general controlled notion here.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[Matthew Heaney]

In article <7pmad9$jnq$1@nnrp1.deja.com> , Robert Dewar 
<robert_dewar@my-deja.com>  wrote:

>>> It would be swell if the language were amended to make access types limited;
>>> this would prevent any problems engendered by accidental copying of access
>>> objects.
>
> There has *got* to be a smiley missing here. It is inconceivable
> to make this change to the language (all access types limited)
> and would be HIGHLY undesirable.

Oh dear, I seemed to have confused people.

No, I certainly don't mean make *all* access types limited.  Only those
access types specifically marked as limited, a la limited record types.

> Presumably, if the above is not a joke (which it might be,
> I am not sure), it is a proposal for some kind of extension
> involving limited access types.

Yes, it is a proposal for an extension involving limited access types.

> Actually I think the reasonable thing to do is to extend the
> storage pool abstraction so that a version of it contains
> a copy operation that is called for all implicit copies of
> the given access value. You probably want to introduce some
> general controlled notion here.

That would be really slick: being able to make access types controlled
directly, instead of having to wrap the access object in a some kind of
controlled abstraction (what I usually call a "handle").

--
Matt

It is impossible to feel great confidence in a negative theory which has
always rested its main support on the weak points of its opponent.

Joseph Needham, "A Mechanistic Criticism of Vitalism"

Re: garbage collection

[Matthew Heaney]

In article <yecvha9izs6.fsf@king.cts.com> , Keith Thompson <kst@cts.com>  
wrote:

> "Matthew Heaney" <matthew_heaney@acm.org> writes:
> [...]
>> It would be swell if the language were amended to make access types limited;
>> this would prevent any problems engendered by accidental copying of access
>> objects.
>
> Not all access types, I hope; sometimes you do want to copy access
> values!

Yes, of course.  Something like:

  type T_Access is limited access all T;

This proposal has also been bandied about for another reason: it has been
proffered as part of the solution to the problem of not being able to take
the 'Access of a local subprogram.


--
Matt

It is impossible to feel great confidence in a negative theory which has
always rested its main support on the weak points of its opponent.

Joseph Needham, "A Mechanistic Criticism of Vitalism"

Re: garbage collection [storage pools]

[Robert Dewar]

In article <37be0c85@news1.us.ibm.net>,
  "Matthew Heaney" <matthew_heaney@acm.org> wrote:
> One thing I miss is not having a set of nameable, pre-defined
> storage pools.
> You have that in GNAT, but it's not really portable because of
> certain
> low-level calls (to a C routine called "_gnat__allocate", or
> something like
> that).

Well it is unlikely that implementations of storage pools
will be completely portable in any case, because they will
undoubtedly do implementation defined stuff using unchecked
conversions, address arithmetic, calls to library routines
etc. So it is probably not a good idea to try to insist on
portable implementations.

It would be VERY nice to have a standard set of storage pools
with standard interfaces. This is an excellent area to suggest
to the ARG for future standardization.

In GNAT, we provide the following

Stack_Bounded_Pool
  really intended only for internal use, implements the
  allocation strategy for fixed size objects when a storage
  size clause is present.

Unbounded_No_Reclaim_Pool
  again really intended for internal use, this is the default
  storage pool that simply allocates from the heap

Unbounded_Reclaim_Pool
  this is the one that I have mentioned before, it provides a
  local allocation capability where the objects are all freed
  automatically on scope exit

Checked_Pool
  this is like the standard unbounded no reclaim pool, but has a
  dereference procedure that is called on each dereference of an
  object in the pool. This is still an abstract pool, the user
  must specialize it with an appropriate extension to provide
  a useful definition for dereference. This is really a language
  extension (of the allowed kind, provided by a package).

Debug_Pool
  this is like the standard unbounded no reclaim pool, but
  it maintains extra overhead to do full validity checking
  on all operations. This is useful for tracking down
  storage leaks.

One can think of many more useful pools, most notably one that
provides defined worst case bounded time performance for real
time use.

It would also be useful to standardize a pragma to override
the normal default storage pool (we plan adding such a pragma
to the next version of GNAT).

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection [storage pools]

[Simon Wright]

Robert Dewar <dewar@gnat.com> writes:

> It would be VERY nice to have a standard set of storage pools
> with standard interfaces. This is an excellent area to suggest
> to the ARG for future standardization.

I would strongly support this idea.

-- 
Simon Wright                        Work Email: simon.j.wright@gecm.com
Alenia Marconi Systems                         Voice: +44(0)1705-701778
Integrated Systems Division                      FAX: +44(0)1705-701800

Re: garbage collection

[Robert Dewar]

In article <37be0c85@news1.us.ibm.net>,
  "Matthew Heaney" <matthew_heaney@acm.org> wrote:
> That's one nice thing about C++.  You can implement a pointer
> abstraction that has a syntax identical to a built-in pointer.
> In Ada95, you have to implement a "handle" type that provides
> a dereference operator:

Not in GNAT, simply derive from the Checked_Pool abstraction,
providing an appropriate Dereference function.

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[Brian Rogoff]

On 20 Aug 1999, Keith Thompson wrote:
> Specifying the 'Storage_Pool attribute is a very powerful and
> under-used feature, IMHO.  The biggest obstacle to its use, I suspect,
> is the need to implement the Storage_Pool operations.
> 
> If System.Storage_Pools also provided routines for dereferencing
> access values (perhaps one each for reading and writing), and perhaps
> also for initialization and finalization of access objects, it would
> be even more powerful.  I haven't entirely thought this through, so it
> may be a bad idea for some reason.

See a discussion of this in comp.lang.ada, Nov '96, in a thread named 
"Garbage Collection in Ada". 

-- Brian

Re: garbage collection

[Robert Dewar]

In article <vvhv3.214$36.49923@typhoon-sf.snfc21.pbi.net>,
  tmoran@bix.com wrote:
> > Just to clarify, most implementations don't actually do
> > this.
>   Why?  Is an implementation not easy, efficient,
> and predictable?

Easy: fairly so, look at System.Pool_Local in the GNAT sources
(s-pooloc.ads). Not that complex. The body is 189 lines, perhaps
only 60 lines or so of actual code.

Predictable: sure

Efficient: there's the rub, there is significant overhead from
arranging for the automatic release, both in space and time. We
found that most existing code does NOT assume this automatic
release, and it clearly makes no sense to use this pool by
default if the program does all its own deallocation.

> And of course overidable by the user simply by raising the
> level where the access type is declared.
>   It seems undesirable to have to specify a number, big
enough, but
> not too big, for the amount of storage needed when you merely
want
> to get automatic deallocation.

No, that's not the way to do it (using Storage_Size). Only
use a Storage_Size where it really does make sense to allocate
in a fixed length area on the stack. Instead use a storage
pool. If you are using GNAT, just do

  for this_access_type'Storage_Pool
    use System.Pool_Local.Unbounded_Reclaim_Pool;

and of course do a "with" of System.Pool_Local.

If you are using some other compiler that does not provide this
very useful capability, then you need to write your own storage
pool implementation (the one with GNAT may work, but you can't
assume that library routines supplied with GNAT will work
unchanged with other compilers (*) since they may depend on
GNAT specific features -- I don't know if this one does or not).

Robert Dewar
Ada Core Technologies

(*) People sometimes make the mistake of assuming that because
the GNAT runtime is written in Ada, it can automatically be used
with other compilers. Sometimes this is the case (indeed one
other vendor was routinely supplying some of the GNAT math
routines for a while, to plug holes in their own run-time, they
may still do this, I don't know ...)

But on the other hand, sales folks for that same vendor were
telling people: "DOn't worry about the information systems
annex, we don't provide it, but if you need it, you can just
pick up the GNAT routines and use them with our compiler."
Unfortunately that is definitely not the case. In the first
place, the underlying compiler must support 18-digit decimal
scaled arithmetic. Secondly, the implementation relies on
GNAT specific stuff, e.g.

   procedure Divide
     (Dividend  : in Dividend_Type;
      Divisor   : in Divisor_Type;
      Quotient  : out Quotient_Type;
      Remainder : out Remainder_Type)
   is
      --  We have a nested procedure that is the actual
      --  intrinsic divide.
      --  This is required because in the current RM, Divide
      --  itself does
      --  not have convention Intrinsic.

      procedure Divide
        (Dividend  : in Dividend_Type;
         Divisor   : in Divisor_Type;
         Quotient  : out Quotient_Type;
         Remainder : out Remainder_Type);

      pragma Import (Intrinsic, Divide);

   begin
      Divide (Dividend, Divisor, Quotient, Remainder);
   end Divide;

Now it would be possible to implement a non-intrinsic divide,
but it would be gruesomely inefficient. This is simply a divide
operation, and really needs to be specialized by the compilers
code generator. Trying to do this with portable Ada is just
at the wrong level!


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Default Storage Pool (was Re: garbage collection)

[Simon Wright]

Robert Dewar <dewar@gnat.com> writes:

>   for this_access_type'Storage_Pool
>     use System.Pool_Local.Unbounded_Reclaim_Pool;
> 
> and of course do a "with" of System.Pool_Local.
> 
> If you are using some other compiler that does not provide this
> very useful capability, then you need to write your own storage
> pool implementation (the one with GNAT may work, but you can't
> assume that library routines supplied with GNAT will work
> unchanged with other compilers (*) since they may depend on
> GNAT specific features -- I don't know if this one does or not).

It would have been very helpful for the Booch Components if all
compilers provided a (standardised, if at all possible) mechanism to
access their default Storage Pool. We had to muck around with indirect
means of finding it, which triggered problems in several compilers.

(BTW, Unbounded_Reclaim_Pool extends Unbounded_No_Reclaim_Pool which
uses gnat_malloc, gnat_free so there would be some work to do to use
them with another compiler -- 3.11p)

Re: Default Storage Pool (was Re: garbage collection)

[Robert A Duff]

Simon Wright <simon@pogner.demon.co.uk> writes:

> It would have been very helpful for the Booch Components if all
> compilers provided a (standardised, if at all possible) mechanism to
> access their default Storage Pool.

There is no requirement that the compiler only have one default pool.

But you can say:

    type T1 is access ...;
    ...
    type T2 is access ...;
    for T2'Storage_Pool use T1'Storage_Pool;

- Bob
-- 
Change robert to bob to get my real email address.  Sorry.

Re: garbage collection

[Pascal MALAISE]

Ronald Ayoub wrote:
...
> If an implementation doesn't provide
> garbage collection then that storage is forever lost, is that correct? Or
> does this mean that it may not be garbage collected but when a call to new
> is executed it is at that time scene as available. Please clarify. This seems
> like a real bad idea not to have some form of garbage collection inforced.

The most portable approach is not to depend on a potential garbage
collector
in the runtime and keep a free list of unused chunks. With this mecanism
a process has at least a measurable and maximum (even if not optimized)
virtual size.


-- Allocates and frees cells of data access,
--  using a free list to re-use free cells.
generic
  type DATA_TYPE is private;
  type DATA_ACCESS_TYPE is access DATA_TYPE;

package DYN_DATA is

  -- Allocates a new cell.
  -- The result is the access to a pre allocated area for DATA_TYPE.
  function ALLOCATE return DATA_ACCESS_TYPE;

  -- Allocates a new cell and fills it with DATA
  -- The result is the access to a pre allocated area for DATA_TYPE,
  --  storing DATA
  function ALLOCATE (DATA : DATA_TYPE) return DATA_ACCESS_TYPE;

  -- Frees a cell. DATA_ACCESS is set to null.
  procedure FREE (DATA_ACCESS : in out DATA_ACCESS_TYPE);

end DYN_DATA;

6 ada instructions.
Body available on request. It does not depend on any package and has 37
ada instructions :-)

Of course, if you claim some chunks and release them, then claim for
other chunks of
another type (even the same size), some new data is allocated that a
garbage collector
would have re-used. That's the drawback.
But the old chucks are only swap usage, aren't they?

-- 
Pascal MALAISE
(priv) mailto:malaise@magic.fr
(prof) mailto:malaise@fr.airsysatm.thomson-csf.com

Re: garbage collection

[David Botton]

Perhaps send the package to AdaSource@AdaPower.com and make your code
available to the world :)

David Botton

Pascal MALAISE wrote in message <37BAFA16.3138228B@magic.fr>...

>6 ada instructions.
>Body available on request. It does not depend on any package and has 37
>ada instructions :-)

Re: garbage collection

[Gisle S�lensminde]

In article <7pe93j$ehg$1@dailyplanet.wam.umd.edu>, Ronald Ayoub wrote:
>In the book "Programming in Ada 95" by Barnes he says:
>
>If an allocated object becomes inaccessbile becasue no declard objects refer
>to it directly or indirectly then the storage it occupies may be reclaimed
>so that it can be reused for other objects. An implementation may (but need
>not) provide garbage collection for this.
>
>I need this to be clarified for me. If an implementation doesn't provide 
>garbage collection then that storage is forever lost, is that correct? Or
>does this mean that it may not be garbage collected but when a call to new
>is executed it is at that time scene as available. Please clarify. This seems
>like a real bad idea not to have some form of garbage collection inforced.
>
>Ron

This is one of the strange things with Ada. Nearly all textbooks are
giving you the impression that garbage collection is common in
Ada compilers, and that maybe some compilers not has implemented
GC, since the standard allows an implemention to not implement it.    
  
The fact is that hardly any Ada compilers have GC. The only ones I know    
about is those targeted for java virtual machine bytecode, where the
virtual machine implements GC. (appletmagic and soon? jgnat)

The reason is of cause that GC  not is desireable for most realtime
systems, which is the traditional area for Ada, but for many other tasks,
GC is a good thing. However, I miss GC less in Ada then in many other
languages, because you are less dependent on dynamic memory then in 
most other languages, and controlled types can be used to automaticly
free memory when they goes out of scope or are assigned to. 

--
Gisle S�lensminde ( gisle@ii.uib.no )   

Re: Garbage Collection

[H Brett Bolen]

Hows that saying go?

   The smalltalk programer says garbarge collection is too important
   do be done by the programmer, while the c programmer say's its
   too important to be done by the machine.

Should we add:

   The ada programmer says garbage collection os too important
   to be done at all.

Or maybe we should change 'important' to 'complex'.

More flame food.

b\253
-- 
b\253              | Take Chances, Make Mistakes 
brettb@cpcug.org   | Get Messy    
brett bolen        |     - Ms Frizzle - MSB
Walrus Consulting  | http://www.cpcug.org/user/brettb

Re: Garbage Collection

[Erland Sommarskog]

This is where this discussion ends for my part. It has been going
on far too long. It seems quite obvious that no one here, at least
not me, will succeed in converting Bill Wolfe to believe that garbage 
collection is good. And it does not seem like he will convert anyone 
either.

I'm glad to hear that Reference.all will survive the block exit.
I am still a little puzzled, though. Assume that instead of a "simple 
pointer" we actually have a linked list, declared as (limited) 
private in some package. Then, it's Destroy routine will be called
at block exit. Now, I don't know how you folks write your Assign
procedures for linked lists, but I do simple pointer copying. (And
I assume that Bill Wolfe does the same, since he is so keen on that
his ADTs will be useful in a real-time environment. Copying value
and allocating memory for the new lists would be as harmful as
garbage collection, if not worse.) This means of course that my
implicit Destroy procedure must be just NULL(*). Then I have an another
for the user to call when is tired of his list.
  Excuse me, but is call-destroy-on-block-exit really a useful device? 
Seems like adding something to the langauge which you almost should never 
use. 

And same goes for the user to supply a Destroy procedure to the 
generic package. Since its body often will be NULL, its appearance
in the instantiating package is just white noise.

(*) This isn't really true. If the reference assignment also includes
updating of reference counters, we can check them in the Destroy
procedure. We have now drifted in to the land of poor man's garbage
collection, where to have to very careful everytime so we are not
doing something stupid.

Finally, Bill Wolfe has claimed that not having garbage collection
helps the programmer to understands all aspects of his code, both
time and space. Eh, there are some more aspects on the code than
so. For example, that it really does what it supposed to. It may very
elegantly sweep away all used memory and that, but tell us that
2 + 2 = 5. No good program. Fact is, in many applications, space is
seldom an important problem, if at all. All you want to be sure of
is that you really got rid all of you allocated, so that your interactive
user donesn't get a dump after five hours work.

And, oh, the world is not divided into ADT implementors and application
programmers. It just doesn't look that way.
-- 
Erland Sommarskog
ENEA Data, Stockholm              This signature is not to be quoted.
sommar@enea.se

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <4232@enea.se>, by sommar@enea.se (Erland Sommarskog):
> I'm glad to hear that Reference.all will survive the block exit.
> I am still a little puzzled, though. Assume that instead of a "simple 
> pointer" we actually have a linked list, declared as (limited) 
> private in some package. Then, it's Destroy routine will be called
> at block exit. Now, I don't know how you folks write your Assign
> procedures for linked lists, but I do simple pointer copying. 

    I copy the values, whatever they are.  If they are pointers,
    then pointers will be copied.  If they are ADTs, then ADTs
    will be copied.  If the user can't tolerate the costs of copying,
    the user is free to make his/her list a list of pointers rather
    than a list of objects.  

    Pointer copying constitutes structural sharing, which is unacceptable;
    if a user updates the copy, that must not propagate back to the original.

> Finally, Bill Wolfe has claimed that not having garbage collection
> helps the programmer to understands all aspects of his code, both
> time and space. Eh, there are some more aspects on the code than
> so. For example, that it really does what it supposed to. It may very
> elegantly sweep away all used memory and that, but tell us that
> 2 + 2 = 5. No good program. Fact is, in many applications, space is
> seldom an important problem, if at all. All you want to be sure of
> is that you really got rid all of you allocated, so that your interactive
> user donesn't get a dump after five hours work.

    Precisely why implicit destruction is a valuable aid to programmers,
    leaving them secure in the knowledge that whatever local variables
    they create will be automatically destroyed upon block exit, and free
    to concentrate on the other aspects of the application such as how
    much space the procedure will consume while it is active, which then
    feeds into the overall order-of-magnitude figure for space consumption.  



                                  Bill Wolfe

                           wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Erland Sommarskog]

For the third time I asked Bill Wolfe how his idea with deallocation
on block exit. With his last answer, I realized that due to unclarity
from my side, he may have misunderstood my example. My apologies to
you all, and Bill in particular. 

So I try again, and see if I can get it right:
We have:
     Generic
        Data_type is limited private;
        with Assign, "<", ">"    -- What you expect 
     Package Binary_trees is
        Tree_type is private;
        Procedure Insert(Tree in out : Tree_type; Data : in Data_type);
        ...
     End Binary_trees;
     
     Package Use_trees is  -- Could be a procedure. Could be generic.
        Type Any_type;     -- Could also be generic parameter, or imported.
        Type Some_type;
        Type Some_access_type is access Some_type;
        Procedure Assign(A : in out Some_access_type; 
                         B : in     Some_access_type) is 
        Begin A := B End Assign; 
        -- Also add "<" ">" to mean comparison on Any_type here.
        Package Tree_handler is new Binary_trees(Some_access_type, Assign);
        ...
        Procedure Put_something_in_tree(Tree : in out Tree_type;
                                        Anything : Any_type) is
        Reference : Some_access_type;                                
        Begin                                 
           Reference := new Some_type;
           Do_something(Reference.all, Anything);
           Tree_handler.Insert(Tree, Reference);
        End;
        ...
    End Use_trees;
    
Question: What happens with Reference.all when Put_something_in_tree
is exited? I read your proposal as that it should be deallocated, 
which would be disastrous. Or is this a misunderstanding from my 
side? If it is not: is this code erroneous with your scheme? 
  Side note: you said that the tree package should take a Destroy
procedure. For what benefit? You can't automatically call it when
your Destroy_tree is called. The caller might refer to the stored 
objects in some other place. Or does your Destroy_tree have a special
parameter to control this? Seems like adding two parameters (one
generic and one routine) that aren't necessary, but clutters up the
user's code. The user can always traverse the tree and destroy what
he has there.
-- 
Erland Sommarskog
ENEA Data, Stockholm              This signature is not to be quoted.
sommar@enea.se

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <4222@enea.se>, by sommar@enea.se (Erland Sommarskog):
> [Still discussing Erland's example regarding automatic destruction
>  of a local environment upon block exit.  Erland now states precisely
>  that he is instantiating a tree which stores objects of type pointer;
>  in other words, we are dealing with a tree of pointers.  The example
>  continues with a situation in which a pointer is being inserted into
>  the tree.]
>
>         Procedure Put_something_in_tree(Tree : in out Tree_type;
>                                         Anything : Any_type) is
>         Reference : Some_access_type;                                
>         Begin                                 
>            Reference := new Some_type;
>            Do_something(Reference.all, Anything);
>            Tree_handler.Insert(Tree, Reference);
>         End;
>     
> Question: What happens with Reference.all when Put_something_in_tree
> is exited? I read your proposal as that it should be deallocated, 
> which would be disastrous. Or is this a misunderstanding from my 
> side? If it is not: is this code erroneous with your scheme? 

   It is a misunderstanding from your side.  I stated in the preceding
   version of the example (or maybe the first version, or both) that
   since Reference is a simple pointer, destruction of Reference consists
   only of eliminating the space occupied by the pointer, and does not
   imply destruction of what Reference points to.  Now let's consider: 

      procedure EXAMPLE (INPUT : SOME_ADT) is

         TEMP : SOME_ADT;    -- now TEMP happens to be *implemented*
                             --  as a pointer to TEMP's descriptor,
                             --  which in turn contains other pointers
                             --  to TEMP's value.  But since TEMP is
                             --  limited private, our user doesn't know that.

         ACCESS_AN_INTEGER : access INTEGER;   -- a local object
         
      begin
         ASSIGN (TEMP, SOME_OPERATION (SOME_ADT)); 
         ACCESS_AN_INTEGER := new INTEGER := SIZE_OF (TEMP);    
            -- notice the allocation...
         DO_SOMETHING_WITH (TEMP, SOME_ADT, ACCESS_AN_INTEGER);
         DO_SOMETHING_ELSE_WITH (TEMP, ACCESS_AN_INTEGER);
            --
            -- notice failure to deallocate ACCESS_AN_INTEGER.all...
            --
      end EXAMPLE;  -- OK, now at this point we are done with TEMP.  It is a 
                    --   local variable, and therefore its DESTROY procedure 
                    --   will be automatically invoked.  We are also done with 
                    --   ACCESS_AN_INTEGER, so ACCESS_AN_INTEGER will also be 
                    --   destroyed.  But since ACCESS_AN_INTEGER is only a 
                    --   pointer, this leaves the integer value to become 
                    --   garbage!  We conclude that our user requires 
                    --   more programming experience, so that he/she 
                    --   might more completely comprehend the characteristics 
                    --   of the programming tool known as the pointer.

>   Side note: you said that the tree package should take a Destroy
> procedure. For what benefit? You can't automatically call it when
> your Destroy_tree is called. The caller might refer to the stored 
> objects in some other place. 

    You're forgetting that the caller completely controls what happens
    inside that caller-supplied DESTROY procedure!  If the caller so
    desires, the DESTROY procedure can consist of a null statement;
    then only the routine destruction of the space occupied by the
    pointer will occur, as an effect of the call to UNCHECKED_DEALLOCATION
    which destroys the space occupied by the record describing a given node.

    Secure in the knowledge that the caller is responsible for prescribing
    the destruction procedure, Destroy_Tree will in fact call Destroy
    automatically on each and every instance of a stored object.



                                        Bill Wolfe

                                wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Barry Margolin]

In article <4041@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>         ASSIGN (TEMP, SOME_OPERATION (SOME_ADT)); 
>         ACCESS_AN_INTEGER := new INTEGER := SIZE_OF (TEMP);    
>            -- notice the allocation...
>         DO_SOMETHING_WITH (TEMP, SOME_ADT, ACCESS_AN_INTEGER);
>         DO_SOMETHING_ELSE_WITH (TEMP, ACCESS_AN_INTEGER);
>            --
>            -- notice failure to deallocate ACCESS_AN_INTEGER.all...

But what if DO_SOMETHING_WITH and/or DO_SOMETHING_ELSE_WITH makes a
copy of its third parameter in some permanent data structure?  If
ACCESS_AN_INTEGER.all were to be deallocated at this point, you would
end up with a dangling pointer.  Or should these routines be required
to also copy THIRD_ARGUMENT.all, too?

My understanding is that the Ada designers didn't originally espouse
manual deallocation (hence the name UNCHECKED_DEALLOCATION) because it
is an easy way to write erroneous programs, and there's no way to
statically check for this error at compile time.  Forgetting to
deallocate something also produces an incorrect program (in non-GC
environments), but the failure modes are less frequent.  Also, there's
a relatively simple way to fix the out-of-memory problem that results:
add more memory; finding dangling references is often much harder.

I've used both GC and non-GC languages.  I've done lots of programming
in PL/I, and now I'm a Lisp programmer.  Personally, I've had few
problems with dangling pointers in PL/I, but most of the programming
didn't make use of ADT-style programming.  The one ADT-style PL/I
program I was involved with (the Multics mail system utilities) solved
its problem by using reference counts (luckily, there are no potential
circular reference chains) in all the data structures.

But I've also seen the freedom allowed by a garbage collector in the
Symbolics Lisp Machine software.  It means that unrelated programs can
share data structures without preplanning.  A fundamental assumption
of manual deallocation is that when the allocator of a structure is
through with it, so is everyone else.  But when references to these
structures are passed around the references may be copied.  Unless you
want to require everyone to copy those structures you can't assume
that the allocator knows when it's safe to deallocate.

By the way, for systems programming and performance purposes, the
Symbolics environment provides a number of manual
allocation/deallocation mechanisms.  A facility called "resources"
allows you to maintain a free-list of similar structures, and allocate
and deallocate from that list instead of from the heap.  This tends to
be used for large structures that are allocated and become garbage at
a very high rate, such as network packets and disk buffers.  There's
even a primitive for deallocating a structure from the heap, although
in the current implementation it does nothing if the structure isn't
the youngest object in its region of the heap, because it simply moves
the region's allocation pointer to the beginning of the object (if it
were to do this with a non-youngest object, it would deallocate
younger objects in the process); I've never actually seen this
facility used, though, and I think it's only there for compatibility
with PDP-10 MacLisp (the MacLisp GC put garbage onto a free-list, and
there was a primitive to add an arbitrary object to this).

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <35278@think.UUCP>, by barmar@think.COM (Barry Margolin):
> In article <4041@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>>         ASSIGN (TEMP, SOME_OPERATION (SOME_ADT)); 
>>         ACCESS_AN_INTEGER := new INTEGER := SIZE_OF (TEMP);    
>>            -- notice the allocation...
>>         DO_SOMETHING_WITH (TEMP, SOME_ADT, ACCESS_AN_INTEGER);
>>         DO_SOMETHING_ELSE_WITH (TEMP, ACCESS_AN_INTEGER);
>>            --
>>            -- notice failure to deallocate ACCESS_AN_INTEGER.all...
> 
> But what if DO_SOMETHING_WITH and/or DO_SOMETHING_ELSE_WITH makes a
> copy of its third parameter in some permanent data structure?  If
> ACCESS_AN_INTEGER.all were to be deallocated at this point, you would
> end up with a dangling pointer.  Or should these routines be required
> to also copy THIRD_ARGUMENT.all, too?

    Some of you appear to be laboring under the false impression that
    when one passes a pointer into a procedure, one will have no idea
    what is to be done with that pointer.  Let me assure you that before
    I pass a pointer into *any* procedure, that procedure had damn well
    better declare its intentions with respect to that pointer.  Some
    possibilities are:

       -- The pointer must be the sole pointer to the object in question.
       -- This procedure then claims sole possession of that object;
       -- the pointer you pass in will therefore be read and then set to null.

       -- The pointer will be maintained as a reference to the object in qu
       -- question.  The caller is responsible for ensuring that the object
       -- is not destroyed without first making a call to REMOVE_OBJECT
       -- in order to destroy this reference to the object in question.

       -- The pointer must be the sole pointer to the object in question.
       -- This procedure will read the object pointed to, and then destroy it;
       -- the pointer you pass in will therefore be read and then set to null.

   ***********************************************
   ** The answer, my friends, is DOCUMENTATION. **
   ***********************************************
 
> My understanding is that the Ada designers didn't originally espouse
> manual deallocation (hence the name UNCHECKED_DEALLOCATION) because it
> is an easy way to write erroneous programs, and there's no way to
> statically check for this error at compile time.  

    Failure to deallocate is a logic error; like other logic errors,
    they are best detected by desk checking (primary line of defense),
    and by using a debugger as a last resort.

> I've used both GC and non-GC languages.  I've done lots of programming
> in PL/I, and now I'm a Lisp programmer.  Personally, I've had few
> problems with dangling pointers in PL/I, but most of the programming
> didn't make use of ADT-style programming.  

     Personally, I've had no problems with dangling pointers in Ada,
     due to the complexity management provided by the ADT paradigm.

> But I've also seen the freedom allowed by a garbage collector in the
> Symbolics Lisp Machine software.  It means that unrelated programs can
> share data structures without preplanning.  

     You mean "without documentation".  Thanks, but no thanks. 

A fundamental assumption
> of manual deallocation is that when the allocator of a structure is
> through with it, so is everyone else.  But when references to these
> structures are passed around the references may be copied.  Unless you
> want to require everyone to copy those structures you can't assume
> that the allocator knows when it's safe to deallocate.

     Sure I can, provided the lost art of documentation is practiced
     from time to time...  (Gee, I sure hope I don't ever have to 
     program with YOUR colleagues...)



                                        Bill Wolfe

                                 wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Barry Margolin]

In article <4050@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>A fundamental assumption
>> of manual deallocation is that when the allocator of a structure is
>> through with it, so is everyone else.  But when references to these
>> structures are passed around the references may be copied.  Unless you
>> want to require everyone to copy those structures you can't assume
>> that the allocator knows when it's safe to deallocate.
>
>     Sure I can, provided the lost art of documentation is practiced
>     from time to time...  (Gee, I sure hope I don't ever have to 
>     program with YOUR colleagues...)

I had a feeling you'd say that.  Unfortunately, at the time, I
couldn't think of a better example.  Here's one (I hope):

There are several programs running in a common address space.  Call
them COMMAND_PROCESSOR, COMPILER, and EDITOR.  There is a global data
structure, COMPILER_WARNINGS; the operations on this database include
adding warnings, selecting warnings based on various criteria, and
deleting selected warnings from the database.  COMPILER adds warnings,
as one would expect.  EDITOR has operations that make use of the data
in COMPILER_WARNINGS; for instance, you can display the warnings for
the current file and have the editor position you to the appropriate
source line.  And COMMAND_PROCESSOR has a command to clear out
COMPILER_WARNINGS (which selects all warnings and then deletes them).

The natural way to implement the COMPILER_WARNINGS database is as an
array or list of pointers to warning structures.  The ADD operation
copies the pointer it's given, and is documented so that the caller
knows not to try to deallocate the object it added.  SELECT simply
returns newly allocated pointers to the selected warnings.  DELETE
objviously should deallocate the pointer and remove it from
COMPILER_WARNINGS, but what about pointer.all?

If someone has called SELECT and it has returned a pointer to a
particular warning, DELETE should not deallocate pointer.all, because
there is another handle to it.  EDITOR should be permitted to continue
to display and manipulate selected warnings even if they've since been
deleted from the global database.

Reference counts can be used to make this work.  Every time a warning
is selected, its reference count can be incremented, and it can be
decremented when it is DELETEd, and DELETE can deallocate pointer.all
when it drops below 0.  Callers of SELECT are required to DELETE all
the selected warnings when they are done with them.  There would also
need to be a different DELETE operation to specify that it should be
removed from the COMPILER_WARNINGS database, to be used by the
COMMAND_PROCESSOR command.  But I don't think this is what you are
advocating.

Can this be solved with only documentation?  Or is this an ugly
example that only a Lisp afficionado would think is clean?

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <35300@think.UUCP>, by barmar@think.COM (Barry Margolin):
> There are several programs running in a common address space.  Call
> them COMMAND_PROCESSOR, COMPILER, and EDITOR.  There is a global data
> structure, COMPILER_WARNINGS; the operations on this database include
> adding warnings, selecting warnings based on various criteria, and
> deleting selected warnings from the database.  COMPILER adds warnings,
> as one would expect.  EDITOR has operations that make use of the data
> in COMPILER_WARNINGS; for instance, you can display the warnings for
> the current file and have the editor position you to the appropriate
> source line.  And COMMAND_PROCESSOR has a command to clear out
> COMPILER_WARNINGS (which selects all warnings and then deletes them).
> 
% The natural way to implement the COMPILER_WARNINGS database is as an
% array or list of pointers to warning structures.  The ADD operation
% copies the pointer it's given, and is documented so that the caller
% knows not to try to deallocate the object it added.  SELECT simply
% returns newly allocated pointers to the selected warnings.  DELETE
% objviously should deallocate the pointer and remove it from
% COMPILER_WARNINGS, but what about pointer.all?
% 
% If someone has called SELECT and it has returned a pointer to a
% particular warning, DELETE should not deallocate pointer.all, because
% there is another handle to it.  EDITOR should be permitted to continue
% to display and manipulate selected warnings even if they've since been
% deleted from the global database.   [...]
% 
% Can this be solved with only documentation?  Or is this an ugly
% example that only a Lisp afficionado would think is clean?

    It's in severe need of a cleanup.

    If I understand the problem correctly, we have a command processor,
    a compiler, an editor, and some set of files upon which the compiler
    and editor are to operate.  When a file is sent through the compiler,
    the compiler generates a warning structure with respect to that file.
    The editor then makes use of these warning structures during debugging.
    Furthermore, a command exists whereby the warning structures for given 
    files are destroyed, and this command must not interfere with editor
    processes which are still alive.

    Let's assume the existence of a suitably implemented warning container,
    which has been appropriately hardened for use as a shared variable.
    Our compiler proceeds by read-locking the file and write-locking the
    warning structure; having acquired the locks, the warning structure
    for that particular file is updated, and the locks are then released.
    Our editor proceeds by write-locking the file and read-locking the
    warning structure, updating the file, and then releasing all locks.
    Our warning destroyer proceeds by write-locking and then destroying
    the specified warning structure(s).

    That was almost too easy.  Did I misunderstand the problem?



                                       Bill Wolfe

                                wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Barry Margolin]

In article <4054@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>    Let's assume the existence of a suitably implemented warning container,
>    which has been appropriately hardened for use as a shared variable.
>    Our compiler proceeds by read-locking the file and write-locking the
>    warning structure; having acquired the locks, the warning structure
>    for that particular file is updated, and the locks are then released.
>    Our editor proceeds by write-locking the file and read-locking the
>    warning structure, updating the file, and then releasing all locks.
>    Our warning destroyer proceeds by write-locking and then destroying
>    the specified warning structure(s).
>
>    That was almost too easy.  Did I misunderstand the problem?

First of all, whether the file is locked is immaterial to the
discussion (I never actually said that the compiler compiles files --
in Lisp the compiler can also be invoked on in-core interpreted
functions, and many Lisp programming environments allow in-core editor
buffers to be compiled).

However, I did imagine locking of the COMPILER_WARNINGS database.  I
expected that it would be read-locked during the operation of the
SELECT operation, and write-locked during ADD and DELETE.  But once
SELECT returns, the lock would be released.  The lock serves to
protect the collection structure (either an array or linked list,
probably), but not the individual elements (since there are no
operations that modify an existing warning object).

So, I envision that the editor proceeds by read-locking the warnings
structure, selecting the appropriate warnings, and then releasing the
lock.  It then displays the selected warnings to the user and allows
him to perform operations such as "go to line referenced in next
warning".

In many traditional systems the warnings database is a text file
containing the output of the compiler, and the SELECT operation works
by reading this file and parsing it into a set of warnings structures
internal to the editor.  The command processor's DELETE_WARNINGS
operation is then just a Delete File command.  However, this mechanism
effectively involves a copy operation (the contents of the warning
file are copied into the editor's memory), and it is this copy that
I'm trying to avoid by having the editor and compiler in the same
address space and allowing them to share the warning object
structures.

If we do put read and write locks on the individual warning objects,
we have effectively implemented reference counts.  The multiple-reader
locking schemes I'm familiar with increment a counter or add an
element to some list every time a reader grabs the lock, and do the
opposite when unlocking, so that they will know when all the readers
are gone.  So, if your answer is that reference counts are the right
solution, just say so.  It's possibly the case that all well-designed
applications can be implemented using either manual or ref-count-based
deallocation.  However, reference counts add a significant fixed
overhead to every assignment of a ref-count-protected data type; what
was probably a single instruction becomes:
	if target not null
	   decrement target.refcount
	   if target.refcount = 0 then deallocate target.all
	increment source.refcount
	target = source

Most modern GC schemes have time overhead that is a function (often
linear) of the frequency of allocation.  Since assignments are
always more frequent than allocations, and I suspect usually MUCH more
frequent, this difference is important.

Ada prevents many of the worst types of pointer problems by only
allowing pointers to be created by the heap allocation primitive
(NEW).  In other languages, where pointers to existing objects may be
created (C's "&", PL/I's "ADDR") things can get pretty bad without a
GC.  I ran into such a problem last year when I was trying to use a
subroutine library originally designed for display of a database in a
facility for editing that database.  The database is implemented as a
text file, with each line representing a record, and each field of the
record separated by a delimiter character.  The programs are in C, and
the subroutine for reading the database into memory read each line
into a newly allocated string, replaced each delimiter with a null
character (C's string terminator), and allocated structures containing
pointers to the first character of each field.  This was fine for the
read-only applications, as they could simply deallocate all the
strings and record structures that were allocated (they didn't
actually bother, since the programs run on Unix and they depended on
everything being deallocated when the program terminated).  I tried to
write a program that reads in this database and then allows the user
to edit fields.  If the new field value is shorter than the original,
I simply overwrote the original value; if not, I allocated a new
string for the new value, and changed the record's field pointer to
point there instead of into the middle of the original line.  But when
it came time to deallocate, I needed to know whether individual fields
needed to be deallocated independently of the lines.  Had I gotten
around to finishing this program, I probably would have added a
parallel data structure containing flags indicating whether each field
had been reallocated.

In general, what I see coming out of this is that manual deallocation
may always be possible, but it frequently requires a non-trivial
amount of extra coding to provide bookkeeping to let the program know
when it is safe to deallocate things.  Remember, every additional line
of code in a program increases its complexity and is another potential
failure point.  And details such as storage management are generally
uninteresting to the application programmer, who is probably more
interested in the problem domain, so it is likely that he won't be as
careful when designing, coding, and testing them (storage management
is also difficult to test, unless you or the runtime library include
extra mechanisms just to improve debuggability).  Garbage collectors,
on the other hand, are usually implemented by system programmers who
find them interesting and can be expected to care enough to do the
very best.  And if you don't think these psychological factors are
important, then you're working with programmers of a different species
than I'm familiar with (that reminds me, I wonder where my "Psychology
of Computer Programming" is -- probably in my parents' house,
unfortunately, or I'd look up references), and I wouldn't want to work
with them!

In conclusion, I expect that I can manage storage as well as you can.
And I could also manually convert a number to a character string and
send these characters to an I/O device.  Every major language provides
runtime support for the latter so we don't all have to waste our time
writing it.  What's so special about storage management that we
should all be burdened with it?

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <35328@think.UUCP>, by barmar@think.COM (Barry Margolin):
> First of all, whether the file is locked is immaterial to the
> discussion (I never actually said that the compiler compiles files --
> in Lisp the compiler can also be invoked on in-core interpreted
> functions, and many Lisp programming environments allow in-core editor
> buffers to be compiled).

    Whatever is being processed, be it a file or something else,
    would have to be locked.  If it is already inaccessible to
    all other processes, then it is continuously locked already.

> [discussion of copying vs. read-locking]

    All editors I know of work by copying the targeted file into
    memory, holding it there while it's being modified, and then
    writing it back to the file.  Another approach is the locking
    mechanism.  Since compiler warnings generally amount to very
    small text files, I'd probably go the copying route if locking
    /unlocking consumed too much time.  However, a good argument 
    can also be made that there should not be 3 million people 
    simultaneously editing and/or compiling the same file anyway, 
    so it probably makes little difference which method is chosen. 

> Most modern GC schemes have time overhead that is a function (often
> linear) of the frequency of allocation.  Since assignments are
> always more frequent than allocations, and I suspect usually MUCH more
> frequent, this difference is important.

    No, not just the frequency of allocation.  GC's performance also
    depends upon the frequency of running out of memory.  Furthermore,
    GC is a global mechanism, and it wastes much time scanning space
    which is already being properly managed.  
 
> the subroutine for reading the database into memory read each line
> into a newly allocated string, replaced each delimiter with a null
> character (C's string terminator), and allocated structures containing
> pointers to the first character of each field.  This was fine for the
> read-only applications, as they could simply deallocate all the
> strings and record structures that were allocated (they didn't
> actually bother, since the programs run on Unix and they depended on
> everything being deallocated when the program terminated).  I tried to
> write a program that reads in this database and then allows the user
> to edit fields.  If the new field value is shorter than the original,
> I simply overwrote the original value; if not, I allocated a new
> string for the new value, and changed the record's field pointer to
> point there instead of into the middle of the original line.  But when
> it came time to deallocate, I needed to know whether individual fields
> needed to be deallocated independently of the lines.  Had I gotten
> around to finishing this program, I probably would have added a
> parallel data structure containing flags indicating whether each field
> had been reallocated.

     Why was each line read into a newly allocated monolithic string,
     with pointers into this string?  It would seem far more sensible
     to read each *field* into a newly allocated string; then when we
     need to revise a field to a larger value, deallocate the old string 
     and allocate a new one.  Flags are not necessary.

> In general, what I see coming out of this is that manual deallocation
> may always be possible, but it frequently requires a non-trivial
> amount of extra coding to provide bookkeeping to let the program know
> when it is safe to deallocate things.  Remember, every additional line
> of code in a program increases its complexity and is another potential
> failure point.  And details such as storage management are generally
> uninteresting to the application programmer, who is probably more
> interested in the problem domain

     Which is why application programmers should make use of ADTs,
     which encapsulate and hide the details of storage management.

> In conclusion, I expect that I can manage storage as well as you can.
> And I could also manually convert a number to a character string and
> send these characters to an I/O device.  Every major language provides
> runtime support for the latter so we don't all have to waste our time
> writing it.  What's so special about storage management that we
> should all be burdened with it?

    Conversion of a number to a character string will perform identically
    whether we use a system routine or code that same routine ourselves.

    Deallocation of storage is a one-time cost (and a small one at that)
    if done by the programmer.  Given the implicit destruction of local
    environments and the use of ADTs, application programmers will 
    practically never have to do any explicit deallocation anyway.  
    When it is necessary, it's not that difficult.  In the database example,
    a single line of code would suffice.



                                     Bill Wolfe

                               wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Barry Margolin]

In article <4066@hubcap.UUCP> billwolf@hubcap.clemson.edu writes:
>From article <35328@think.UUCP>, by barmar@think.COM (Barry Margolin):
>> First of all, whether the file is locked is immaterial to the
>> discussion (I never actually said that the compiler compiles files --
>> in Lisp the compiler can also be invoked on in-core interpreted
>> functions, and many Lisp programming environments allow in-core editor
>> buffers to be compiled).
>
>    Whatever is being processed, be it a file or something else,
>    would have to be locked.  If it is already inaccessible to
>    all other processes, then it is continuously locked already.

The reason I said it was immaterial was because we are discussing
garbage collection and structure sharing, not file management.

>
>> [discussion of copying vs. read-locking]
>
>    All editors I know of work by copying the targeted file into
>    memory, holding it there while it's being modified, and then
>    writing it back to the file.  Another approach is the locking
>    mechanism.  Since compiler warnings generally amount to very
>    small text files, I'd probably go the copying route if locking
>    /unlocking consumed too much time.  However, a good argument 
>    can also be made that there should not be 3 million people 
>    simultaneously editing and/or compiling the same file anyway, 
>    so it probably makes little difference which method is chosen. 

And you're still harping on how the editor manages the file.  The
whole point of my example was on how the editor, compiler and command
processor, running in the same address space (the compiler could be
invoked as a subroutine by the editor, for instance), share the
in-memory warnings database.  3 million people aren't editing and
compiling the same file, but one user is, and he may tell the command
processor to delete the compiler warnings before he's finished
scanning through them in the editor (because he doesn't want them
cluttering up the database if he asks for other compiler warnings to
be displayed).

>> Most modern GC schemes have time overhead that is a function (often
>> linear) of the frequency of allocation.  Since assignments are
>> always more frequent than allocations, and I suspect usually MUCH more
>> frequent, this difference is important.
>
>    No, not just the frequency of allocation.  GC's performance also
>    depends upon the frequency of running out of memory.  Furthermore,
>    GC is a global mechanism, and it wastes much time scanning space
>    which is already being properly managed.  

Real-time GC mechanisms are defined to do a bounded amount of work PER
ALLOCATION.  Decent GC mechanisms can be told to ignore manually
managed space.  And generational and ephemeral GC mechanisms
concentrate their efforts on memory most likely to contain garbage.

>     Why was each line read into a newly allocated monolithic string,
>     with pointers into this string?  It would seem far more sensible
>     to read each *field* into a newly allocated string; then when we
>     need to revise a field to a larger value, deallocate the old string 
>     and allocate a new one.  Flags are not necessary.

Probably because the language's runtime library provides operations
for reading by lines and for searching strings.  A program that uses
standard library routines is easier to read than one that uses its
own.

I admit that the database package was not written wonderfully (the guy
who wrote it is primarily a Lisp programmer, but he was one of the few
people in our company willing to write C utilities at the time).  It's
a locally-used facility, not part of any product, so high quality was
not the top priority.

>     Which is why application programmers should make use of ADTs,
>     which encapsulate and hide the details of storage management.

No.  The application programmer must still know when to call the ADT's
DESTROY procedure, or know to call the LOCK and UNLOCK procedures,
etc.

>    Deallocation of storage is a one-time cost (and a small one at that)
>    if done by the programmer.  Given the implicit destruction of local
>    environments and the use of ADTs, application programmers will 
>    practically never have to do any explicit deallocation anyway.  
>    When it is necessary, it's not that difficult.  In the database example,
>    a single line of code would suffice.

You continue with this "one-time cost" fallacy.  It is a cost that
must be paid at least every time an ADT is designed and implemented,
and it also adds complexity that must be borne by the users of the
ADT.  GC is truly a one-time cost (per runtime implementation).


Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <35340@think.UUCP>, by barmar@think.COM (Barry Margolin):
> 3 million people aren't editing and
> compiling the same file, but one user is, and he may tell the command
> processor to delete the compiler warnings before he's finished
> scanning through them in the editor (because he doesn't want them
> cluttering up the database if he asks for other compiler warnings to
> be displayed).

    Why doesn't the editor do the deletion of warnings?  If the editor
    is already providing a "search for next warning" function, it should
    provide the "delete warning" function as well.  Then we wouldn't have
    to deal with shared variables at all, although your later comments do
    make the whole question moot.

> Real-time GC mechanisms are defined to do a bounded amount of work PER
> ALLOCATION.  [....]  And generational and ephemeral GC mechanisms
> concentrate their efforts on memory most likely to contain garbage.

    Could you send me a detailed explanation of these mechanisms?

> Decent GC mechanisms can be told to ignore manually managed space.  

    If this means that I can specify that my allocation requests carry
    the condition that the GC mechanism will stay away from the space
    I receive, then I'll be happy to change my position on garbage collection.

    (Erland, you may have spoken too soon!)

    HOWEVER.  There are still things that need changing.  There still needs
    to be implicit destruction of local environments via calls to DESTROY
    routines.  Parameter passing is still ambiguous with respect to storage
    utilization.  In general, I can live with GC being required IFF I can
    also exert total control over when, how, and for how long every piece
    of space is occupied, and I can determine exactly how much space is
    being used implicitly and for how long.  

    If what you say is true, then nothing prevents me from designing an 
    entire system in which GC is completely absent and for which I can make 
    firm statements regarding the system's time and space characteristics; 
    even though the compiler is required to provide GC for those who wish
    to use it, the programmer can require the compiler to provide a
    local environment in which GC is prohibited.  This I can live with.  



                                              Bill Wolfe

                                       wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Barry Margolin]

In article <4073@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>    Why doesn't the editor do the deletion of warnings?  If the editor
>    is already providing a "search for next warning" function, it should
>    provide the "delete warning" function as well.  Then we wouldn't have
>    to deal with shared variables at all, although your later comments do
>    make the whole question moot.

Who said that the editor doesn't provide for deletion of warnings,
too?  But that shouldn't prevent the command processor from also
deleting them.

>> Real-time GC mechanisms are defined to do a bounded amount of work PER
>> ALLOCATION.  [....]  And generational and ephemeral GC mechanisms
>> concentrate their efforts on memory most likely to contain garbage.
>
>    Could you send me a detailed explanation of these mechanisms?

The canonical reference for real-time GC is a paper, about 10 years
old, by Henry Baker.  I don't know the exact reference, but the title
included the phrases "Garbage Collection" and "Real-time", and it was
probably in something like a proceedings of a POPL conference.  The
general idea of these mechanisms is that every time an object is
allocated up to N words are scanned for non-garbage objects to be
copied.

My reference for ephemeral GC is David Moon's paper, approximately
titled "Garbage Collection in Large Virtual Memory Systems", which is
in the proceedings of the first (or maybe second) ACM Lisp Conference.
I don't know what the references for generational GC's are; recent
Lisp and Functional Programming Conference proceedings are probably a
good place to look.

>> Decent GC mechanisms can be told to ignore manually managed space.  
>
>    If this means that I can specify that my allocation requests carry
>    the condition that the GC mechanism will stay away from the space
>    I receive, then I'll be happy to change my position on garbage collection.

Well, the GC implementation that I'm most familiar with is the
Symbolics 3600.  This architecture organizes the address space into
logical entities called "areas".  Each area can be flagged as either
dynamic or static, the latter indicating that garbage should not be
collected there.  The GC still has to scan through static areas to see
whether they contain references to objects in dynamic areas, though;
otherwise the GC might create a dangling reference.

In the Symbolics system, the primary use of static areas is to prevent
pure code pages that are paged directly out of load files from being
copied into swap space.  They are also used for holding I/O buffers,
which are manually reused and therefore never become garbage.  The
features they are missing for your purposes are sophisticated
allocation and deallocation primitives; the only primitives the Lisp
Machine provides always allocate and deallocate space at the end of an
area, because the system depends on the GC to free up interior space.
But you could easily build a sophisticated allocator that manages its
own space inside a static area.

>    HOWEVER.  There are still things that need changing.  There still needs
>    to be implicit destruction of local environments via calls to DESTROY
>    routines.  Parameter passing is still ambiguous with respect to storage
>    utilization.  In general, I can live with GC being required IFF I can
>    also exert total control over when, how, and for how long every piece
>    of space is occupied, and I can determine exactly how much space is
>    being used implicitly and for how long.  

Lisp-like languages provide for this by providing macros that
encapsulate the allocation and deallocation of objects.  For example,
in Common Lisp one can write:

	(WITH-OPEN-FILE (variable file-name options...)
	  body...)

This opens the specified file, assigns the stream to the variable,
executes the body, and then closes the file.  And it guarantees that
the file will be closed no matter how the environment is exited.  This
is generally implemented using Lisp's UNWIND-PROTECT primitive, which
allows arbitrary code to be executed when an environment is being
exited.

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

Re: Garbage Collection

[Erland Sommarskog]

Mike Ryer (ryer@inmet.UUCP) writes:
>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?

I know about nothing about 1750, but I assume it's typically used
for those "embedded systems" that Ada was intended for. I can agree
that garbage collection is virtually of no interest on such a machine
and not worth the development costs.
  On the other hand if I want to port my interactive program from VAX/VMS
to SunOS, I can't with the rules of today rely on garbage collection, 
but have to stick to Unchecked_deallocation.
  So it would be nice if garbage collection was required to be available, 
or at least recommended. How it should be controlled (on or off) is a more 
tricky question. Pragmas is maybe not the best of ideas since to some extent 
it applies to the entire system.
  Of course, if practice turns out that all compilers except those for 
strict real-time use have garbage collection, then such a rule in the
LRM is unnecessary. Unfortunately, this doesn't seems to be the case
today.
-- 
Erland Sommarskog
ENEA Data, Stockholm              This signature is not to be quoted.
sommar@enea.se

Re: Garbage Collection

[Erland Sommarskog]

I'm trying to get Bill Wolfe to explain how he his deallocation-on-
block-exit scheme would work in an example I had. For brevity I
deleted my example in my last article. Apparently that was a fatal
mistake, because the answer I got wasn't even close the question.
So, my apologies, I repeat the exmample with some clarifcations.

We have:
   Generic 
      Data_type is limited private;
      Procedure -- Assign, "<" and ">" 
   Package Tree_handler
      Tree_type is private;
      
Assume further that we instantiate this package with Some_access_type, 
it could be an imported limited type, it could be a locally defined.
Then we have the procedure:

    Procedure Insert_data_to_tree(Tree : in out Tree_type;
                                  Data_of_some_sort : in Any_type); 
    Reference : Some_access_type;
    Begin
       Reference := new Some_type;  -- Or subprogram call for external type
       Prepare(Reference, Data_of_some_sort);
       Insert(Tree, Reference);
    End Insert_data_to_tree;
    
The Assign procedure which we provide when we instantiate the tree handler 
is simply:
   Procedure Assign(A : in out Some_access_type; B : in Some_access_type) is
   Begin
      A := B;
   End Assign;
   
Now, what happens with Reference.all on exit of Insert_to_data_tree, with    
your scheme? (Assume there is no user-written DESTROY procedure.) Would
Reference.all be deallocated although there still is a living reference  
to it in Tree? Or will it be ignored in any case? Or are you having a
reference count hidden somewhere to save you? 

Another interesting issue is: When Tree drops from the stack what happens
with our little object at this occassion? The Tree's DESTROY procedure
cannot know anything about it, so we have to traverse the tree and deallocate
all referd objects ourselves. (And pray we haven't inserted some of them
in a queue somewhere else too!) With garbage collection...

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

So why can't these "advanced debugging tools" be used to "pin down
the exact state of the system" when we have garbage collection?

>   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

I assume with critical mean time-critical here. If the issue is 
reliability or space, garbage collection is only there to help you.

There is good chance that your ADT will be rejected anyway. The critical 
developper looks at you and says: "You use Unchecked_dellocation? Sorry, 
then I can't use your ADT. Memory fragmention will cause too great a 
time penalty when the system have lived for a while." So you return and 
implement a free-list and try again. The developper looks at you: "You 
have an internal task for the free-list?" "Eh, no" "You must have that,
else all will be a mess if two tasks access the list simultaneously."
So you end up with with adding this task, and your critical developper
is satisfied. (Reservation: My experience of tasking in Ada is not
that great. Possibly the SHARED pragma could help, but I doubt.)
  Then you come to me who is writing an interactive data-base application 
for VAX/VMS and give me your ADT. It looks nice so I use it. Some time
later my users complains: the reponse time is too long. What have
you done? Being equipped with good tools I re-link the system with 
PCA (a profiler for VMS) to find the bottle-neck. And I to my surprise 
I find that rendez-vous are taking place in the system. "Ah, that why 
it's slow, but where do they come from?" Soon your ADT is found to be 
guilty. And just a little later your ADT is edited to be taskless, and my 
users are happy again. (Until they get dumps because memory is full,
because I forgot to call one of your damned Destroy routines somewhere.)

The lesson to learn is that it is very hard to satisfy everyone. 
And you end up with two versions anyway. Given that there are
many shops who never will write an application were garbage
collection is unacceptable, ADTs relying on its presence will
still have a wide use. Probably more use than ADTs using tasks
to protect free lists. (I have reponse times to think of, but garbage 
collection is no problem. With the collector running as coroutine 
like in the Eiffel system, it can work while I'm waiting for input.)

There is a solution that gives us a possibility to use the same 
implementation of the ADT above. And that solution is, yes you guessed
it: garbage collection. You provide your ADT with a Destroy procedure
that your critical developper uses. (As long your block-exit scheme 
doesn't work properly, he has to call it explicitly. I doubt he 
would accept your idea anyway.) I, in my turn, give a damn about it. 
All I want is that the task should not be used, which you can have
a special call for. Then I just set the garbage_collection flag in 
my system configuration file. 

-- 
Erland Sommarskog
ENEA Data, Stockholm              This signature is not to be quoted.
sommar@enea.se

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <4206@enea.se>, by sommar@enea.se (Erland Sommarskog):
> I'm trying to get Bill Wolfe to explain how he his deallocation-on-
> block-exit scheme would work in an example I had. [...] 
> I repeat the exmample with some clarifcations.
> 
> We have:
>    Generic 
>       Data_type is limited private;
>       Procedure -- Assign, "<" and ">" 
>    Package Tree_handler
>       Tree_type is private;
>       
> Assume further that we instantiate this package with Some_access_type, 
> it could be an imported limited type, it could be a locally defined.
> Then we have the procedure:
> 
>     Procedure Insert_data_to_tree(Tree : in out Tree_type;
>                                   Data_of_some_sort : in Any_type); 
                                                           ^^^^^^^^

                                        You mean Data_type, right?

>     Reference : Some_access_type;

                     How about "access Data_Type"?  It is illegal to
                     reference Some_access_type directly, since it
                     is not a generic formal parameter.  We can only 
                     reference Data_Type, which in this particular 
                     instantiation will refer to Some_access_type.

>     Begin
>        Reference := new Some_type;  -- Or subprogram call for external type

           Let's say "Reference := new Data_Type;", to make things legal.

>        Prepare(Reference, Data_of_some_sort);

           Prepare is not a generic parameter; I frankly don't see
           why you need a call to such a procedure anyway.  I'll replace
           it with "Assign (Reference.all, Data_of_some_sort);". 
 
>        Insert(Tree, Reference);

           What exactly is Insert doing?  It would make more sense to write:

            begin
              -- find the node for which the new value is to
              --   become either the leftmost or rightmost child,
              --   create a new child, and assign the new data value
              --   to the appropriate field of the new node.  At some
              --   point in this process, there may be some pointer 
              --   manipulations; it really doesn't matter where.  But
              --   let's assume the tree is initially empty.  Then, 
              TREE := new BINARY_TREE_NODE;
              ASSIGN (NEW_NODE.DATA_VALUE, DATA_OF_SOME_SORT);
              -- since pointer types are automatically initialized to
              --   null, we don't have to worry about initializing
              --   the left child and right child fields, so we're done.
           end INSERT;
 
>     End Insert_data_to_tree;
>     
> The Assign procedure which we provide when we instantiate the tree handler 
> is simply:
>    Procedure Assign(A : in out Some_access_type; B : in Some_access_type) is
>    Begin
>       A := B;
>    End Assign;
>    
> Now, what happens with Reference.all on exit of Insert_to_data_tree, with    
> your scheme? (Assume there is no user-written DESTROY procedure.) Would
> Reference.all be deallocated although there still is a living reference  
> to it in Tree? 

      First of all, I always require the user to pass in a DESTROY procedure.
      So my initial reaction is that this is a malformed ADT.  But let's
      assume the existence of such a malformed ADT.  We'll assume further
      that we have a pointer variable such as Reference.  Destruction of
      a pointer consists simply of destroying the pointer, and does not
      imply destruction of what it points to.  Destruction of an ADT
      which happens to be implemented via an initial pointer (as in Tree)
      does imply destroying the transitive closure of what it points to.

>>> 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.
> 
> So why can't these "advanced debugging tools" be used to "pin down
> the exact state of the system" when we have garbage collection?

     They can, but only the exact state of one particular execution,
     and not the precise state of the theoretical system in general.

     A debugging tool exists simply to help you find errors which show
     up in one particular situation.  It does not help you understand
     the piece of software as a theoretical structure, which is essential
     if one is to perform nontrivial modifications to a system.  It is
     this theoretical imprecision which causes problems.

> 
>>   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
> 
> There is good chance that your ADT will be rejected anyway. The critical 
> developper looks at you and says: "You use Unchecked_dellocation? Sorry, 
> then I can't use your ADT. Memory fragmention will cause too great a 
> time penalty when the system have lived for a while." 

     Allocation/deallocation routines exists which automatically
     collapse adjacent blocks of free storage into larger blocks,
     which minimizes the problem.  In general, this is the *compaction*
     question, which is orthogonal to the GC question.  It is properly
     directed at the allocation/deallocation system and not at the
     ADT designer.  It is conceivable that an allocation/deallocation
     system could be designed in such a way as to spread the costs of
     compaction evenly over each allocation/deallocation request, thus
     meeting all requirements at the same time. 


                                            Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu

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: Garbage Collection

[Erland Sommarskog]

Bill Wolfe (wtwolfe@hubcap.UUCP) first said:
>>>     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.  

I tried to understand:
>> I read this as "on block exit all memory allocated to variables
>> declared in that block should be deallocated". 
>>   Isn't this very dangerous? What if programmer copied the object to
>> a variable declared in a outer block? Or stored it in a table of some
>> sort in a subprogram call made in block? 

And Bill explains:
>   Not at all.  If a programmer assigns the value stored in some local
>   object to some nonlocal object, then we simply have a new value for
>   a nonlocal object, assuming we have not engaged in the foul practice
>   of structural sharing.  Those who engage in structural sharing will
>   get the run-time errors they deserve for engaging in such space-hacking. 


And I still don't understand. Let's say we have a tree handler
   Generic 
      Data_type is limited private;
      Procedure -- Assign, "<" and ">" 
   Package Tree_handler
      Tree_type is private;
Assume further that we instantiate this package with Some_access_type, 
it could be an imported limited type, it could be a locally defined.
Then we have the procedure:

    Procedure Insert_data_to_tree(Tree : in out Tree_type;
                                  Data_of_some_sort : in Any_type); 
    Reference : Some_access_type;
    Begin
       Reference := new Some_type;  -- Or subprogram call for external type
       Prepare(Reference, Data_of_some_sort);
       Insert(Tree, Reference);
    End Insert_data_to_tree;
    
According to Bill the data allocated to Reference should be freed when 
we exit this procedure, but if Insert does what we think this is of
course a severe error. Where did I go wrong? Did I plead guilty to
structure sharing just because I inserted a pointer to a tree? 
  Or does Bill mean that when Reference is inserted to the tree that 
Reference.all should be inserted to the tree, not the pointer itself?
But what if I also insert the reference into another tree (or some other 
structure) and then modify the referred data (some counter, for instance) 
and want this change to appear in both places?
  Note also that in this example, there are no side effects. We are only
dealing with local variables and paramerters. And still deallocation
on block exit is completely wrong. (And there is no way the compiler
could deduce that Insert really saves Reference somewhere.)

Several times in this discussion Bill Wolfe has claimed that 
garbage collection is a trouble-maker for maintainers. In what 
way? I can only see one: If the system due to a heavy use of memory
is spending a lot of time on garbage collecttion, something must be 
done. But in this case the problem is often quite easy to spot.
  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.
  Bill Wolfe is trying to outline some alternative, but I
think he has to think more about, until it is equally safe.
(And really, I don't think he should. He is just reinventing
the wheel.)
  
Bill Wolfe said earlier that garbage collection encourages  
sloppy programming. Whether it is sloppy or not, I don't care,
but obviously garbage collection is taking a lot of the burden
of the programmer's shoulder and the maintainer's too. Why
should a programmer waste time bothering about something that
the computer could do much safer for him? After all, the  
programmer does not work for free.

So to conclude: I think Ada should require garbage collection
that could be disabled with a pragma for critical applications.
As it is now a portable application cannot rely on it, with
all the troubles explicit deallocation implies.
-- 
Erland Sommarskog
ENEA Data, Stockholm              This signature is not to be quoted.
sommar@enea.se

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <4195@enea.se>, by sommar@enea.se (Erland Sommarskog):

 [Erland describes a situation in which a user instantiates a tree 
  structure over an access type, and then considers the insertion
  procedure with which the user inserts an object into the tree]

> According to Bill the data allocated to Reference [in the example,
> a pointer to the user's object] should be freed when 
> we exit this procedure, but if Insert does what we think this is of
> course a severe error. Where did I go wrong? Did I plead guilty to
> structure sharing just because I inserted a pointer to a tree? 
>   Or does Bill mean that when Reference is inserted to the tree that 
> Reference.all should be inserted to the tree, not the pointer itself?
> But what if I also insert the reference into another tree (or some other 
> structure) and then modify the referred data (some counter, for instance) 
> and want this change to appear in both places?
>   Note also that in this example, there are no side effects. We are only
> dealing with local variables and paramerters. And still deallocation
> on block exit is completely wrong. (And there is no way the compiler
> could deduce that Insert really saves Reference somewhere.)

   The user has supplied the limited private type STORED_OBJECT, and
   defined assignment over this object.  Let's assume that the tree
   is implemented in terms of a record structure, one field of which
   is a STORED_OBJECT.  In the INSERT_ITEM procedure, the user sends
   "in out TREE_TYPE; in STORED_OBJECT".  The tree is modified as follows:
   a new record is created to represent a new node of the tree.  The 
   statement ASSIGN (NEW_NODE.STORED_ITEM, NEW_OBJECT) is executed,
   along with whatever pointer manipulations are necessary to maintain
   the structure of the tree.  

   Now we proceed to block exit.  Since the tree and the new object are
   *parameters* and not local variables, they are not subject to the
   automatic destruction which applies to the block's local variables.

   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.

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

      There are basically two cases in which this can happen:

         1) When an inexperienced ADT designer is in the process 
            of acquiring the mental discipline required of anyone
            who programs pointer-based structures.  To avoid this,
            purchase ADTs from professional houses or use experienced
            ADT designers.  Otherwise, it's a cost of professional training.

         2) When a user has engaged in S T R U C T U R A L  S H A R I N G.

                   *** Don't engage in structural sharing ***

> Bill Wolfe said earlier that garbage collection encourages  
> sloppy programming. Whether it is sloppy or not, I don't care,

    Obviously.

> Why should a programmer waste time bothering about something that
> the computer could do much safer for him? After all, the  
> programmer does not work for free.

    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. 



                                             Bill Wolfe

                                     wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Snorri Agnarsson]

From article <3985@hubcap.UUCP>, by billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,):
>       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.  

 Exactly - and garbage collection is precisely what you need to get rid
 of this difficulty.
 When you have garbage collection there is no difficulty in determining
 whether an object exists or not.  It exists if you have some way to
 refer to it, otherwise not.

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

 The PERMANENT, RUN_TIME COST is very often much worse if you use the
 methods Mr. Wolfe dogmatically demands.  For example if you have a program
 which does calculations with indefinite size integers, then each new integer
 value computed is most appropriately stored in a new area in the heap.
 If you disallow sharing then each assignment must create a new area.
 This is costly.  Each time you stop using an integer variable you must
 deallocate it.  This is costly.
 If you have a simple copying garbage collector and allow sharing, which
 by the way is not dangerous at all in this case at least, you don't have
 the abovementioned costly operations, but instead you have a simple garbage
 collection which will in my experience be infrequent (e.g. every ten seconds
 for a program doing intensive calculations with 10000 digit integers) and 
 fast (less than a fraction of a second for each collection).  And this
 is on a machine with small memory (a PC with 640KB memory).

 Memory management is one of the most difficult things for programmers to
 do correctly and efficiently.  Garbage collection certainly takes this
 burden from the programmer and allows him to think in more abstract terms.

 In my opinion reusable software components can not be adequately created
 in languages that do not have good automatic memory management.
 In this respect Ada is a failure unless garbage collection is required.
 The C++ approach of using destructors is costly both in memory and time
 and does not really solve the problem, although it is better than nothing.

 It is regrettable in my opinion that the issue of garbage collection
 is so much misunderstood.  It is also regrettable that proponents of
 the various interesting new programming methodologies do not push
 garbage collection as an issue.  Functional programming, logic
 programming and object oriented programming have only one thing in
 common; reliance on garbage collection.  None of those methodologies
 would have much use in my opinion if it were not for garbage collection.
 And, I repeat: reusable modules (that includes generic packages) are
 almost useless in languages with no garbage collection compared to
 the use you can get in languages having garbage collection.

 
-- 
Snorri Agnarsson                        --  snorri@rhi.is
Raunvisindastofnun Haskolans      
Dunhaga 3
IS-107 Reykjavik ICELAND

Re: Garbage Collection

[Bill Wolfe]

From article <692@krafla.rhi.hi.is>, by snorri@rhi.hi.is (Snorri Agnarsson):
> From article <3985@hubcap.UUCP>, by billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,):
>>       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.  
> 
>  Exactly - and garbage collection is precisely what you need to get rid
>  of this difficulty.
>  When you have garbage collection there is no difficulty in determining
>  whether an object exists or not.  It exists if you have some way to
>  refer to it, otherwise not.

     So basically you have to sit there and total up the references to
     every piece of space manually.  Sounds like fun.  Got an algorithm
     for doing this in constant time?  If not, there is "great difficulty
     pinning down the precise state of the program". 
 
>>     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. 
> 
>  The PERMANENT, RUN_TIME COST is very often much worse if you use the
>  methods Mr. Wolfe dogmatically demands.  For example if you have a program
>  which does calculations with indefinite size integers, then each new integer
>  value computed is most appropriately stored in a new area in the heap.
>  If you disallow sharing then each assignment must create a new area.

      Consider what happens to the storage associated with the old value
      of the target of the assignment statement.  The ASSIGN procedure
      can reuse it directly rather than deallocating and reallocating it.
      
>  Memory management is one of the most difficult things for programmers to
>  do correctly and efficiently.  Garbage collection certainly takes this
>  burden from the programmer and allows him to think in more abstract terms.

     Space is an important part of the abstraction.  And I challenge the
     claim that memory management is difficult.  One need only deal with
     a single structural model within the ADT; in the course of writing
     that ADT's implementation, one will become thoroughly familiar with
     that structure, and there should be no difficulty deciding when a
     part of it is no longer needed.

>  In my opinion reusable software components can not be adequately created
>  in languages that do not have good automatic memory management.

    In my opinion, reliance upon garbage collection is the single best
    way to create an inferior ADT implementation which will be totally
    rejected by anyone who is programming critical applications.  

>  In this respect Ada is a failure unless garbage collection is required.

    In this respect garbage collection is a total failure and should
    NEVER be required.  In the interests of seeing to it that portability
    to the critical-application environment is always possible, GC should
    be PROHIBITED.

>  It is regrettable in my opinion that the issue of garbage collection
>  is so much misunderstood.  

    Particularly by people who have no understanding of the issues
    applying to proper ADT design.

>  It is also regrettable that proponents of
>  the various interesting new programming methodologies do not push
>  garbage collection as an issue.  Functional programming, logic
>  programming and object oriented programming have only one thing in
>  common; reliance on garbage collection.  None of those methodologies
>  would have much use in my opinion if it were not for garbage collection.

    They don't have much use anyway.  See David Harland's "Concurrency
    and Programming Languages".


                                            Bill Wolfe

                                     wtwolfe@hubcap.clemson.edu

Re: Garbage Collection

[Bob Hathaway]

>According to Bill the data allocated to Reference should be freed when 
>we exit this procedure, but if Insert does what we think this is of
>course a severe error. Where did I go wrong? Did I plead guilty to

I think Bill meant deallocation should only occur if an object is no
longer accessible at the end of a subprogram or block, and Reference is 
accessible.  Subprogram and block exit is a very convenient time to perform 
clean-up of access types.  If Ada had an Adt construct for the "completion of
the Adt paradigm", we could specify a termination procedure for Adts which
could also be called at scope exit.  I agree that Adts/objects are an important
enough programming development to justify a new language construct.  I've 
worked with over 200,000 lines of code which used the older data-structure
oriented design and found the greatest problem in understanding and working
with these programs was caused by the use of global variables and the 
indescriminant access and modification of data-structures which were not 
implemented as Adts.  Such data-structures are poorly defined and lead to
code which is hard to read.

For my own opinion on the garbage collection discussion, I think a destroy 
procedure is desirable.  Adts need to be explicitly deallocated for long 
running daemons or loops even while objects are still accessible.  While 
calling a procedure or declaring objects in a local block from within a loop
allows automatic deallocation of objects, I'd rather use scope rules and 
subprograms for creating environments and performing actions and not for 
storage (de)allocation.  Also, I think Adt operations should include a destroy
procedure for completeness. If space management is not a problem the destroy 
procedure does not have to be called.  Concerning working sets, if a page is 
not accessed it will not reside in memory for long and should not cause a 
virtual space management problem.

I strongly agree with assignment operator overloading, and another
powerful extension is to allow any name/operator to be overloadable.

For yet another Ada 9X extension, I propose procedural variables.  As in 
Modula procedural variables can be limited to top level procedures but formal
parameter names must be included for named parameter association.  Here is an
example declaration:
    type insertNode_procedure = procedure (adt : in out structure,
					   node : in node);
Variables of type insertNode_procedure can be assigned to any procedure with
the same parameter type structure (type domain).  Procedural variables can
avoid the redundant use of case statements by allowing an operation to be 
stored within an Adt.  It also allows individually parameterizable and 
reprogrammable Adts since operations can be provided to alter the Adts actions
or structure.  Generic subprogram parameters can only allow Adts to be set 
once for any instantiation.  I use procedural variables and function pointers
in Adts frequently when programming in languages other than Ada and am 
convinced they are an elegant way to model Adt actions.

                                         Bob Hathaway
                                         rjh@purdue.edu

Re: Garbage Collection

[Erland Sommarskog]

Sworn enemy to garbage collection Bill Wolfe writes:
>     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.  

I read this as "on block exit all memory allocated to variables
declared in that block should be deallocated". 
  Isn't this very dangerous? What if programmer copied the object to
a variable declared in a outer block? Or stored it in a table of some
sort in a subprogram call made in block? 
-- 
Erland Sommarskog
ENEA Data, Stockholm
sommar@enea.se
"Frequently, unexpected errors are entirely unpredictable" - Digital Equipment

Re: Garbage Collection

[Bill Wolfe]

From article <4176@enea.se>, by sommar@enea.se (Erland Sommarskog):
> Sworn enemy to garbage collection Bill Wolfe writes:
>>     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.  
> 
> I read this as "on block exit all memory allocated to variables
> declared in that block should be deallocated". 
>   Isn't this very dangerous? What if programmer copied the object to
> a variable declared in a outer block? Or stored it in a table of some
> sort in a subprogram call made in block? 

   Not at all.  If a programmer assigns the value stored in some local
   object to some nonlocal object, then we simply have a new value for
   a nonlocal object, assuming we have not engaged in the foul practice
   of structural sharing.  Those who engage in structural sharing will
   get the run-time errors they deserve for engaging in such space-hacking. 

   Now there is, of course, the problem that the practice of assigning to
   nonlocal objects is somewhat distasteful, since this amounts to a
   "side effect" of a procedure or function.  The rap on side effects
   is that they frequently are not properly documented, and thus make
   a major contribution to the difficulty of understanding a program.

   In addition, optimizing compilers find it difficult to completely 
   define the relationship between procedures or functions and their
   enclosing environment, thus making the relevant optimizations costly.

   So... language designers to the rescue!!!  The solution to this
   problem has been discussed in recent issues of Sigplan Notices,
   and it is this:  Provide a scheme whereby procedures and functions
   have, by default, no relationship to their surrounding environment
   other than that which is explicitly documented in the parameter
   structure.  Then provide a facility whereby one can explicitly
   "poke holes in the shield" for selected external objects.  

   The maintainers are happy, because for once they can read the
   specification of a procedure or function and be certain that
   it does nothing which is not documented in that specification.

   The writers of optimizing compilers are absolutely ecstatic.  

   And the programmers can do their debugging faster as well.  

   But sadly for the programmers who pride themselves on obscure code, 
   there is now one less form of sloppiness available for their use.

   Oh, well, perhaps they'll find some comfort in C...


                                  
                                       Bill Wolfe

                               wtwolfe@hubcap.clemson.edu
 

Re: Garbage Collection

[Erland Sommarskog]

Bill Wolfe (wtwolfe@hubcap.clemson.edu) refuses to see the point with
garbage collection:
>   "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?

But you have to write the same boring code for every ADT you implement!
That was what ron@inmet was talking about.

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

If it is just as easy as that. Let's say that you write a package for
double-linked lists. You provide a procedure for taking an element
out of a list. Should you free the memory allocated? You don't know
because the caller may or may not still keep an reference to the
element. He may be totally uninterested in it, but he may also want
to insert it in another list.  
  So you end up providing another procedure for deallocating the element,
which the user must to remember to call, unless he wants his memory
resources run low.
  And same goes for every ADT you define. You must provide a deallocation
routine that the user must remember to call. What worse is, the user  
may notice if he omits the call, because the implementation of the 
ADT is a static type, and the deallocation is void. And when he is
ready with his tests, you change the implementation, and his program
blows the memory.

Although you refuse to see it, garbage collection saves the programming
community from a lot of headache and true object-oriented programming
would be impossible without it.



-- 
Erland Sommarskog
ENEA Data, Stockholm
sommar@enea.se
"Frequently, unexpected errors are entirely unpredictable" - Digital Equipment

Re: Garbage Collection

[William Thomas Wolfe,2847,]

From article <4159@enea.se>, by sommar@enea.se (Erland Sommarskog):
> But you have to write the same boring code for [destroying]
> every ADT you implement!

     If there were an ability to iterate over the fields of a
     generic record parameter, standard generics for recursively
     destroying certain classes of structures (e.g., n-ary trees)
     could be written, thus automating the process to some extent.  

     The reason we must suffer writing the same code repeatedly is that 
     Ada does not permit us to abstract over arbitrary record structures. 

> Let's say that you write a package for double-linked lists. You provide 
> a procedure for taking an element out of a list. Should you free the 
> memory allocated? You don't know because the caller may or may not still 
> keep an reference to the element. He may be totally uninterested in it, 
> but he may also want to insert it in another list.  

    When the list is instantiated, the user tells us what type of object
    is to be kept in the list, and provides us with procedures for
    assignment and equality.  Objects are copied into and out of the list.  
    When an object is to be removed from the list, the local copy of the
    object which is stored within the list is destroyed.  Now if the
    user wants, a pointer type can be supplied as the type of object
    to be listed, and the user-supplied equality function can compare
    the objects pointed to rather than the pointers themselves.  The
    user then bears all responsibility for managing the "external storage",
    and can track his/her own references.

    There is no implementor's dilemma here whatsoever.


                                          Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu
 

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

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

Re: From Modula to Oberon

[Denis Fortin]

In article <272@fang.ATT.COM> cbseeh@fang.ATT.COM (Edmund E Howland) writes:
>>> [talking about the definition of the Oberon language posted recently
>>>  to comp.lang.modula2]

>> In my opinion Oberon is a significant improvement over Pascal, Modula-2 
>> and Ada in one respect:  It has automatic garbage collection.  This feature
>> is enough to choose Oberon over the other three.  
> 
>Huh?
>Since when have these three ever had a need for garbage collection?
>I am not too familiar with Ada, but garbage collection exists in
>languages for whom dynamic binding is a way of life, not an option.

(note: the stuff below applies equally well to Modula-2 or Ada, although
       it is a bit more Ada-specific)

Actually, Ada *allows* but does not not *require* the existence of a
garbage collector (LRM section 4.8 paragraph 7).  While I agree that for
real-time embedded applications, a garbage collector can be annoying
(though there are incremental algorithms that make this less true), in a
language that encourages information-hiding, a good garbage collector is
almost a must (in my opinion). 

The problem is that users might be using modules/packages that contain
hidden pointers to dynamic data.  Without garbage collection, you have
to have a free/dispose/unchecked_deallocation routine available for all
hermetic data types you export, otherwise code will be written that does
not release variables of that type after using them and if at a latter
point you change the implementation of the hidden data type (which you
SHOULD be able to do, that's why you hid it's true contents in the first
place) and stick a pointer/access variable in it, then you're stuck ->
your heap will slowly erode away!

Actually, by not requiring that a user call a "free" routine for all
variables of data types you export (those where implementation is
hidden), you are allowing him/her to make a very important assumption
about the way your data type is implemented (which is bad). 

Of course, one CAN export a "free" routine with *ALL* data types, but
then it becomes a real pain to write code that uses the data type.  For
example, a "dynamic string package" would require that you call
"free(...)" for all of the string variables you declare at the end of
each block that declares such variables -> this is not only notationally
painful (!?), but also very error-prone. 

Anyway, I've been involved in a 75000+ lines Ada project, and every time
I can talk to Ada compiler vendors, I always ask them *when* garbage
collection will finally be available for their compiler.  (Put in a
pragma to turn it off for real-time applications or something...)

(Actually, the two biggest demands that my group had for Ada compilers
 (besides the obvious "fast compile" and "fast execution") where "fast
 tasking" and "garbage collection"!)

Sigh, it felt good getting this off my chest :-)
-- 
Denis Fortin                            | fortin@zap.UUCP
CAE Electronics Ltd                     | philabs!micomvax!zap!fortin
The opinions expressed above are my own | fortin%zap.uucp@uunet.uu.net

Re: From Modula to Oberon

[Lawrence Crowl]

In article <429@zap.UUCP> fortin@zap.UUCP (Denis Fortin) writes:
>... in a language that encourages information-hiding, a good garbage
>collector is almost a must (in my opinion). ... Without garbage collection,
>you have to have a free/dispose/unchecked_deallocation routine available for
>all hermetic data types you export, ... [otherwise you limit subsequent
>implementations] ... but then it becomes a real pain to write code that uses
>the data type.

C++ provides the notion of a *destructor*.  Whenever you define a class
(abstract data type), you may define a destructor.  The destructor is
*implicitly* called when the variable is deleted (e.g. at the end of the
procedure for local variables).  The implementation of the class may change
from static allocation to dynamic allocation, without changing the client
code, without leaking memory, and without explicit client control of
deallocation.

Garbage collection is one approach to reducing the storage management burden
on programmers.  It is not the only approach, nor is it always the best
approach.
-- 
  Lawrence Crowl		716-275-9499	University of Rochester
		      crowl@cs.rochester.edu	Computer Science Department
...!{allegra,decvax,rutgers}!rochester!crowl	Rochester, New York,  14627

Re: From Modula to Oberon

[Hans Boehm]

  It seems to me that the C++ approach to storage management is at best
a partial solution.  Admittedly it succeeds at automatically deallocating
objects in trivial cases.  For some applications this is, no doubt,
sufficient.  But consider a case as simple as implementing a stack type,
whose underlying representation is a linked list.  Assume this type
includes a non-destructive "pop" operation that returns a new stack
one shorter than the old one.  The original stack is left intact.  ("Pop"
can of course be implemented as the "tail" operation on linked lists.)
Should the head of the original linked list be deallocated?  Is it reasonable
to make that the caller's responsibility?  Certainly not, since it's not
supposed to know anything about the representation of stacks.  After all,
I could be copying arrays.  The stack implementation could reference count,
but that's more tedious, error prone, and probably slower than a good
garbage collector.  It also doesn't always work.
  My experience is that any attempt at manipulation of interesting linked
structures in a language that doesn't support real automatic storage
management will either fail, or waste large amounts of debugging time.
(My experience includes a (working) 40,000 line compiler, written in C, that
manipulates a reference counted syntax "tree", or more accurately, a
reference counted syntax graph.)  Normally, it is extremely difficult
to track down bugs created by premature deallocation.  When such bugs are
finally removed, the resulting programs normally include a substantial
number of storage leaks.
  Some recent experiments by Mark Weiser and myself with retrofitting a
garbage collector to existing C programs, verify the latter point.
(The garbage collector should never free anything since that was the
programmers responsibility.  It does.  In other people's code.
Our paper on this should appear in Software P&E shortly.)
Mike Caplinger reported similar results for another application at the last
USENIX conference, I believe.  We have resurrected C code with storage
management bugs by linking it against a garbage collector (which in the case
of C doesn't always work either, but it has a better track record than manual
storage management).
  There are arguably cases in which a garbage collector is undesirable,
notably in the presence of severe real-time constraints.  But even in such
a situation, I would want a garbage collector during debugging to help
me track down storage leaks.

Hans-J. Boehm                       boehm@rice.edu
Computer Science Dept.
Rice University
Houston, TX 77251-1892

Garbage Collection

[Richard Harter]

In article <628@ra.rice.edu> boehm@titan.rice.edu (Hans Boehm) writes:

>  My experience is that any attempt at manipulation of interesting linked
>structures in a language that doesn't support real automatic storage
>management will either fail, or waste large amounts of debugging time.
>(My experience includes a (working) 40,000 line compiler, written in C, that
>manipulates a reference counted syntax "tree", or more accurately, a
>reference counted syntax graph.)  Normally, it is extremely difficult
>to track down bugs created by premature deallocation.  When such bugs are
>finally removed, the resulting programs normally include a substantial
>number of storage leaks.
>  Some recent experiments by Mark Weiser and myself with retrofitting a
>garbage collector to existing C programs, verify the latter point.
>(The garbage collector should never free anything since that was the
>programmers responsibility.  It does.  In other people's code.
>Our paper on this should appear in Software P&E shortly.)
>Mike Caplinger reported similar results for another application at the last
>USENIX conference, I believe.  We have resurrected C code with storage
>management bugs by linking it against a garbage collector (which in the case
>of C doesn't always work either, but it has a better track record than manual
>storage management).

	There is problably something I am missing, but I don't quite see
how you can implement garbage collection in C without collateral assumptions
-- how is the garbage collector supposed to know that that a block is free?

	Your main point is certainly true - manual allocation and deallocation
with the programmer being responsible for ensuring that all comes out right
really doesn't work very well.  This was a critical issue for us -- our
software has to run on systems which do not have pseudo-infinite memory
and it sometimes has to run for very long runs.  We can't afford memory
leaks (or premature deallocation).  What we did was to write our own
storage allocation package.  Salient features:

The allocation routine takes two arguments, a size and an ID.  The latter
is a unique integer specifying that particular call.  (We manage the ID list
manually.)  The allocator creates a node for each request block.  In this
node are sundry links, the ID, and (in effect) a date stamp.  There is also
a hash table that contains the address of every allocated block.  All allocator
control information is stored in a separate space from allocated memory itself.
(This eliminates a large class of mystery bugs associated with overwriting
allocator control data.)

The deallocation routine takes one argument, the address of the block being
returned.  The deallocation routine validates the address as being an
allocated address.  This eliminates another class of bugs caused by passing
an improper or stale address to the deallocation routine.

There is a facility for printing out a complete map of allocated memory
including call ID's and date stamps.  We use this, from time to time, to
check the code for storage leaks.

This scheme is not as good as automatic garbage collection, but we have
found it to be satisfactory.  
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.

Re: Garbage Collection

[Hans Boehm]

In reference to g-rh@cca.CCA.COM (Richard Harter)'s question:
>        There is problably something I am missing, but I don't quite see
>how you can implement garbage collection in C without collateral assumptions
>-- how is the garbage collector supposed to know that that a block is free?

  This is usually, but not always, possible.  The idea is to use a traditional
non-compacting mark-sweep collector.  On a UN*X system, we start by scanning
the registers, stack, data, and (statically allocated) bss segments for
any addresses of valid allocated objects.  We subsequently scan allocated
objects we find in the same way.  For a typical C program, all reachable
objects can be found in this manner.  (Storing exclusive or'ed pointer
values, tagged pointers, and similiar programming tricks, as well as some
rarely used (for C) compiler optimization techniques may break this scheme.)
  In theory, we may end up marking a few unreachable objects as reachable
as well, since integers may be misinterpreted as pointers.  The collector
can be designed so that the only result of this is excess storage retention.
(This does require that we don't compact.)  In my experience, I have never
seen any indication of such unnecessary retention in practice.  There is
an argument to be made that no garbage collector is completely immune
from this phenomenon.
  The fact that the collector has to perform a fairly complicated (but still
O(1)) check for pointer validity does slow it down a little.  On a Sun 3/260,
with a 2 Meg heap, half of which is in use, we normally see collection times of
about 3 seconds.  (This assumes longword aligned pointers and small data and
static bss areas.)  All of this is largely irrelevant if the
collector is used as a debugging tool to detect storage leaks.
  More details can be found in Mark Weiser's and my upcoming Software P&E
article entitled "Garbage Collection in an Uncooperative Environment".

Hans-J. Boehm
boehm@rice.edu

Re: Garbage Collection

[Richard Harter]

In article <632@ra.rice.edu> boehm@titan.rice.edu (Hans Boehm) writes:
>>        There is problably something I am missing, but I don't quite see
>>how you can implement garbage collection in C without collateral assumptions
>>-- how is the garbage collector supposed to know that that a block is free?

>  This is usually, but not always, possible.  The idea is to use a traditional
>non-compacting mark-sweep collector.  On a UN*X system, we start by scanning
>the registers, stack, data, and (statically allocated) bss segments for
>any addresses of valid allocated objects.  We subsequently scan allocated
>objects we find in the same way.  For a typical C program, all reachable
>objects can be found in this manner.  (Storing exclusive or'ed pointer
>values, tagged pointers, and similiar programming tricks, as well as some
>rarely used (for C) compiler optimization techniques may break this scheme.)

I see.  My block was in not thinking of the entire address space of the
program as accessible.  For our purposes it is not (we live in portability
land and are not allowed to do things like that :-)).  That is one reason
we did our own allocator (in C) -- it allows us to track down memory problems
portably.

I still don't see how a garbage collector helps with premature deallocation,
unless you scrap deallocation entirely, and rely entirely on garbage
collection.

The problem with garbage collectors in the old days was that they did
garbage collection when the available space was allocated.  This works
well enough until the actual amount of space allocated starts to approach
the amount of available space, and then the garbage collector starts
thrashing.  Is this a problem?  If not, how do you deal with it?
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.

Re: Garbage Collection

[Hans Boehm]

  Richard Harter writes:
>I still don't see how a garbage collector helps with premature deallocation,
>unless you scrap deallocation entirely, and rely entirely on garbage
>collection.

>The problem with garbage collectors in the old days was that they did
>garbage collection when the available space was allocated.  This works
>well enough until the actual amount of space allocated starts to approach
>the amount of available space, and then the garbage collector starts
>thrashing.  Is this a problem?  If not, how do you deal with it?

  Our current version of the collector doesn't help you with
premature deallocation.  Further instrumenting it might help.  For example,
you could use the marking algorithm to determine whether "free"d objects
really were inaccessible.  (This requires a coding style in which
unused references are explicitly cleared.  Replacing "free" by a
macro that clears its argument takes care of a lot of that and,
by itself, occasionally helps track down bugs.)  I don't have much experience
with this though.
  In non-real-time applications, we tend to use explicit deallocation where
it's easy to do, and let the collector take care of the error-prone cases.
  You are right in that the garbage collector code is not completely portable.
It should really be viewed as part of the run-time library, which is rarely
completely portable anyway.  Actually porting it isn't terribly hard.  There
is only about a screenful of machine dependent code in the collector.
The longest part of that deals with marking from the machine registers.
  Frequent collections in small address spaces can become a problem.
We operate in a virtual memory environment, so we deal with it by expanding
the heap size whenever a collection fails to return enough memory.  This
requires allocating a bit of extra memory.  For debugging, this hardly
matters.  (Memory is supposedly cheap.) In a production environment,
especially without virtual memory, it could be a problem.  On the other hand,
for some existing code, this can be much less significant than memory
otherwise lost to leaks.

Hans-J. Boehm  (boehm@rice.edu)

Re: Garbage Collection

[00704a-Liber]

[followups to comp.lang.misc]

In article <26358@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes:
>	There is problably something I am missing, but I don't quite see
>how you can implement garbage collection in C without collateral assumptions
>-- how is the garbage collector supposed to know that that a block is free?

The only way to do this is to allocate a giant heap with malloc()
and do *all* the memory management on your own.  It is no different
than implementing in C or C++ a language that does automatic garbage
collection.


The problem I found with languages that do automatic garbage collection is
that there is no way for me to modify the implementation of the class (or
the type, for those of you unfamiliar with C++ lingo :-)) to make it better
suit my needs.

For applications where the programmer cost is greater than the run-time
cost (such as prototypes, personal tools, one-shot programs), I tend to use
languages with built in memory management.  For other applications, however,
I would rather use a language like C++ which allows me to change the
implementation of a class without affecting the rest of my code.
-- 
 _ __			NEVIN J. LIBER	..!ihnp4!ihlpf!nevin1	(312) 510-6194
' )  )				"The secret compartment of my ring I fill
 /  / _ , __o  ____		 with an Underdog super-energy pill."
/  (_</_\/ <__/ / <_	These are solely MY opinions, not AT&T's, blah blah blah

Garbage collection

["Alexander L. Wolf"]

I heard a rumor recently that none of the currently existing, production
quality (now we're *really* cutting the field down) Ada compilers does
garbage collection.

We are developing an Ada program that does a lot of string manipulation and
have found that the program requires a surprisingly large amount of memory
in which to run.  We are using DEC's compiler, which in almost every (other)
respect has proven outstanding.

I'd appreciate any insights...

                                                     Alex.

Abstraction In Ada

[Jon Mauney]

Ada is a complicated and rather ponderous language,  and I can 
understand why people might not like it.  But I think that one
of Ada's strengths is a pretty good data abstraction facility.
Therefore I would like to see an elaboration of any complaints
in that area.

Specifically:  (from mit!nessus)

> To do a good job with data abstraction, you really need heap-based
> allocation with automatic garbage collection.  Ada doesn't support this.

I don't see how this follows,  except that lack of a garbage-collected
heap restricts your ability to implement an ADT using a garbage-collected
heap.  There are advantages and disadvantages to heap allocation of
data objects;  I don't see how they relate to abstraction.

> Also, Ada's private type system is completely messed up.  "Private
> types" have their assignment and equality operations provided by the
> system.  This is the wrong thing since two abstract objects may be
> different from the concrete view (the view that Ada's "=" operation
> takes), but equal from the abstract point of view.  And the assignment
> operation is supposed to copy the object being assigned, but the system
> provided operation can't do that right either.  You can do a little
> better with "limiited private types".  You can then provide your own "="
> operation, but you still can't provide your own ":=" operation.  And
> even if you do define your own "=" operation for a limited private type,
> Ada then won't allow you to use "=" on a composite type that contains
> that type.

Ada gives the "package" designer three choices: (A) a type can be
declared right in the package specification, which means everyone can
use the information to write code that is totally dependent on the
particular representation chosen. (B) a type can be declared "private,"
which means that even though everyone knows how the type is
implemented, they can't write code that depends on it.  Two operations,
assignment and equality testing, are provided by the system.  This is
convenient in many cases, because the system-supplied operations are
exactly what you want. (C) a type can be declared "limited private."
In this case the only operations supplied by the system are declaration of
variables (an essential ability) and passing as parameter (also
essential).  This is useful in many cases, because the system-supplied
operations are not appropriate to the particular abstraction or
implementation.  The '=' operator may be overloaded, and definition of
'=' automatically implies definition of '/='.  Sad to say, ':=' is
not an operation that can be overloaded, and assignment of limited
private types must be done using a different syntax.  This system is
not without its defects, but is it really so horrible?

> Basically, Ada is just gross.  Bleah!

The above opinion is frequently heard. Practically every language has been
substituted for Ada at some point.  This prompts me to issue the following
challenge,  pretty much unrelated to the above discussion:
     Can you name a language that will not elicit a "Bleah" from someone
on the net?  Languages so obscure that no one on the net has heard of them
do not qualify.  Mail any suggestions to me; I will collect them and try
to find an objective method of getting a response from the net at large.
The winner will receive a barbeque sandwich from the Blue Mist, Asheboro, NC.

-- 

_Doctor_                           Jon Mauney,    mcnc!ncsu!mauney
\__Mu__/                           North Carolina State University

Re: Abstraction In Ada

[Doug Alan]

>	From: mauney@ncsu.UUCP (Jon Mauney)

>>		To do a good job with data abstraction, you really need
>>		heap-based allocation with automatic garbage collection.
>>		Ada doesn't support this.

>	I don't see how this follows, except that lack of a
>	garbage-collected heap restricts your ability to implement an
>	ADT using a garbage-collected heap.  There are advantages and
>	disadvantages to heap allocation of data objects; I don't see
>	how they relate to abstraction.

If data abstraction is done right, data types that are added to the
languange should look just like data types that are already built into
the language.  Stack-based allocation doesn't work right because you
have to know how much space you will use before you use it.  This is not
very abstract.  You might not know how much space you need.  Heap-based
allocation where explicit deallocation is required doesn't work right
because you can have dangling references.  On object isn't very abstract
if you try to reference it and find out it's been turned to garbage.
Explicit dealocation also violates modularity because one part of a
program has to take responsibilty for deallocating an object and it has
to know when everyone else is no longer using it.  This compromises
modularity.

I will demonstrate by example.  Let's say that you want to implement a
bignum (integer with arbitrary size) abstraction.  In order to be
abstract, the bignum data type should be just as first class as any
other number type.  If you use stack-based allocation, you will have to
worry about reserving the right amount of space in advance.  But gee,
you don't have to do this with number types that are built in.  If you
use heap-based allocation with explicit dealocation, you will have to
worry about dealocating a bignum when you are finished with it.  But
gee, you don't have to do this with number types that are built in.

>	(C) a type can be declared "limited private."  In this case the
>	only operations supplied by the system are declaration of
>	variables (an essential ability) and passing as parameter (also
>	essential).  This is useful in many cases, because the
>	system-supplied operations are not appropriate to the particular
>	abstraction or implementation.  The '=' operator may be
>	overloaded, and definition of '=' automatically implies
>	definition of '/='.  Sad to say, ':=' is not an operation that
>	can be overloaded, and assignment of limited private types must
>	be done using a different syntax.  This system is not without
>	its defects, but is it really so horrible?

Yes, it's gross!  You also forgot to mention that if a composite type
has components of a limited private type "=" is not available for
objects of the composite type.

>	Can you name a language that will not elicit a "Bleah" from
>	someone on the net?  Languages so obscure that no one on the net
>	has heard of them

CLU is my choice.  It is small, simple, clean, powerful, and general.
It is also quite efficient.  It sometimes sacrifices power for the sake
of simplicity.  It doesn't do type inheritance, or run-time type
generics, so it's not suitable for everything.  But for what it tries to
do, it does remarkably well -- it has the best trade off of
power/easy-of-use/efficiency I've ever seen.

Death to Ada!  Long live CLU.
-- 
				-Doug Alan
				 mit-eddie!nessus
				 Nessus@MIT-MC

				"What does 'I' mean"?

 

Re: Abstraction In Ada

[brad]

<peer pressure made me type this>

Let me respond to a few points in the Ada abstraction debate.

>>>		From: nessus@mit-eddie.UUCP
>>>		To do a good job with data abstraction, you really need
>>>		heap-based allocation with automatic garbage collection.
>>>		Ada doesn't support this.

Not true.  The Ada Language Reference Manual (LRM) says the following:
(section 4.8, page 4-25)

	"An implementation must guarantee that any object created by the
	evaluation of an allocator remains allocated for as long as this
	object or one of it's subcomponents is accessable directly or
	indirectly, that is as long as it can be denoted by some name.
	Moreover, if an object or one of its subcomponents belongs to a task
	type, it is considered to be accessible as long as the task is not
	terminated.  An implementation may (but need not) reclaim the
	storage occupied by an object created by an allocator, once this
	object has become inaccessible."

This last sentence gives an implementor the choice of providing garbage
collection.  You see, it's an implementation issue.  You should note that in
some cases (such as real-time systems) it may be a bad thing to have garbage
collection since your system may be effectivly halted for noticable periods
of time.

>From: nessus@mit-eddie.UUCP
>If data abstraction is done right, data types that are added to the
>languange should look just like data types that are already built into
>the language.  Stack-based allocation doesn't work right because you
>have to know how much space you will use before you use it.  This is not
>very abstract.  You might not know how much space you need.  Heap-based
>allocation where explicit deallocation is required doesn't work right
>because you can have dangling references.  On object isn't very abstract
>if you try to reference it and find out it's been turned to garbage.
>Explicit dealocation also violates modularity because one part of a
>program has to take responsibilty for deallocating an object and it has
>to know when everyone else is no longer using it.  This compromises
>modularity.

Ada has been designed so that dangling references are eliminated.  An object
isn't deallocated (and possibly garbage collected) until all references are
elimated.  If you are used to a language like C, where many objects are
unneccessarily global in scope, then you might feel this is a problem, but
in Ada, objects can be declared with an appropriate scope.

>I will demonstrate by example.  Let's say that you want to implement a
>bignum (integer with arbitrary size) abstraction.  In order to be
>abstract, the bignum data type should be just as first class as any
>other number type.  If you use stack-based allocation, you will have to
>worry about reserving the right amount of space in advance.  But gee,
>you don't have to do this with number types that are built in.  If you
>use heap-based allocation with explicit dealocation, you will have to
>worry about dealocating a bignum when you are finished with it.  But
>gee, you don't have to do this with number types that are built in.

Again, in Ada, one can implement the "bignum" using dynamic allocation (i.e.
access types) and you do not have to do explicit deallocation.  Of course
there is the problem of possibly running out of memory, but that is only if
your implementation does not do garbage collection (again, an implementation
issue).  I wonder how much memory your "bignum" scheme would use anyway.  I
won't even mention virtual memory.

>>	From:  mauney@ncsu.UUCP (Jon Mauney)
>>	(C) a type can be declared "limited private."  In this case the
>>	only operations supplied by the system are declaration of
>>	variables (an essential ability) and passing as parameter (also
>>	essential).  This is useful in many cases, because the
>>	system-supplied operations are not appropriate to the particular
>>	abstraction or implementation.  The '=' operator may be
>>	overloaded, and definition of '=' automatically implies
>>	definition of '/='.  Sad to say, ':=' is not an operation that
>>	can be overloaded, and assignment of limited private types must
>>	be done using a different syntax.  This system is not without
>>	its defects, but is it really so horrible?

>Yes, it's gross!  You also forgot to mention that if a composite type
>has components of a limited private type "=" is not available for
>objects of the composite type.

I don't understand why it's so gross.  The lack of overloading for ":=" has
it's trade-offs.  One of the reasons that limited private types may not be
assigned is so that copying of secure or limited resources may be forbidden.

I don't understand under what circumstances that operation "=" for type A
shoud be inherited for objects of type B that contain objects of type A.  If
type B is a record, for example, then the subcomponent of an object of type
B (i.e. one of type A) still has the "=" operation.  Could you give me an
example?

Also, for a discussion of Object Oriented Design and Ada, pick up a copy of
Grady Booch's book, "Software Engineering with Ada".  It is the definite
reference for Object Oriented Design and how it can be used in Ada.

			Brad Balfour
		arpa	brad@maryland
		csnet	brad@umcp-cs
		uucp	{seismo,allegra}!umcp-cs!brad

Re: garbage collection

[Eric Smith]

Who says you can't have your cake and eat it too?

Intel's 432, while it does have other problems, seems to do a d***
good job of heap based allocation *and* PARALLEL garbage collection
using Dijkstra's algorithm (On-the-Fly Garbage Collection: An Exercise
in Cooperation, Communications of the ACM 20: 966-975, November 1978).

There is even some talk of a garbage collection processor... (right now
it's done by the iMAX system process GCOL).

				Eric L. Smith
				...!harpo!utah-cs!e-smith

				B324 Van Cott Hall
				University of Utah
				Salt Lake City, UT  84112
				(801) 584-4276