Re: From Modula to Oberon

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