Re: Garbage Collection

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

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