GC in Ada

GC in Ada

[Stavros Macrakis]

A few weeks ago, there was a query about garbage collection in Ada.
I've assembled a few notes on the subject.

Several Ada systems appear to have garbage collectors (GC) in
development environments (e.g. Rational, Symbolics).  As far as I have
been able to ascertain, no production Ada environment provides garbage
collection in the target computer.

The usual argument is that embedded applications shouldn't GC, because
GC is inefficient and episodic.  This is spurious for several reasons:

 1. Prototypes and early development versions may prefer to sacrifice
    efficiency for simplicity and speed of programming.

 2. Many Ada applications will in fact not be embedded.

 3. If you have GC, it is very easy to add a capability to detect and
    report undeallocated objects and dangling pointers.

 4. Embedded applications may even want GC.  Traditional episodic GC
    will do for some; others will need real-time GC algorithms.

 5. GC may not be as expensive as is thought, especially if currently
    known advanced implementation techniques are used.

 6. Given Ada's typing, scoping, and tasking, much processing can
    continue even during episodic GC.

However, implementing a GC for Ada is not entirely trivial.  Although
Ada's semantics certainly allow GC, some compiler-writers may have
chosen runtime models which make it impractical or impossible.  Not
only must pointers in memory be traceable, but transient `hazards'
must be avoided.  The conditions are even more stringent for
relocating/compacting GC, of course.

The only current compilers I know the internals of, the Intermetrics
Byron Ada compiler family, have their runtime model carefully designed
to in fact make GC practical.  However, no customer so far has
specified GC.  I'm sure Intermetrics would be happy to sell a GC
option as soon as the market demand became sufficient.

	-s

	Stavros Macrakis
	Harvard Univ. and Intermetrics, Inc.

Re: GC in Ada

[Rick Conn]

	There is a simple garbage collector written in Ada in the
repository in PD:<ADA.COMPONENTS>GARBAGE*.*; data:

%4 Garbage_Collection

Author       : Doug Bryan
             : Computer Systems Lab
             : Stanford University

Machine/System Compiled/Run on :
  Data General MV/10000 running the Ada Development Environment 2.2

Keywords     : MEMORY, GARBAGE, GARBAGE COLLECTION

Abstract     :
 This is a generic garbage collector.  It simply maintains an internal
linked list of items which have been freed then reuses these items when more
are needed.

-------

GC in Ada

[Stavros Macrakis]

`Garbage collection' (GC) has been used in more than one sense in
this discussion.  Several contributors equate GC with `storage
reclamation'.  This is misleading.  The essence of GC is finding free
space by determining what access objects remain in use.

GC is a particular type of automatic storage reclamation -- reference
counting, e.g., is another.  And explicit deallocation or deallocation
of stack frames at scope exit time is simply not automatic storage
reclamation.  Neither is deallocating an entire collection at the exit
of the scope declaring the type.  All of these are useful techniques,
but they are not GC.  GC has different advantages and disadvantages
than each of these other methods.

It is not possible to write a garbage collector within Ada (unless, of
course, you have hooks into the implementation).  It is not even
possible to define a private type which reclaims its own space within
Ada.  The essential problem is that there is no way of determining the
``immediately accessible nodes'' in Knuth's ("Art") terminology, i.e.
the variables containing access values.  It would be possible to
define a limited type that used GC or ref counting if there were a
finalization operation (see Schwarz&Melliar-Smith, ``The Finalization
Operation for Abstract Types'' ICSE/5, p273).

For a discussion of issues relating to GC implementation in an
Ada-like environment, see Susan Owicki, ``Making the World Safe for
GC'' in POPL/8, p77.

The term `Garbage collection' has had a precise meaning for over
twenty years.  Here are some citations:

J.McCarthy et al, "Lisp 1.5 Programmer's Manual" (2nd ed, 1965) p105:
   garbage collector: The routine in LISP which identifies all active
   list structure by tracing it from fixed base cells and marking it,
   and then collects all unneeded cells (garbage) into a free-storage
   list so that these words can be used again.

Knuth, "Art" (1st ed, 1968), sec 2.5B p438:
   ...a policy of simply doing nothing until space runs out, then
   searching for all the areas currently in use and fashioning a
   new AVAIL list.

Aho&Ullman, "Principles of Compiler Design" (1st ed, 1977) p44:
   A garbage collection scans all records, determining which are in
   use, and making an <available space list> of those which may be
   reused.

Note that "garbage collection" has been used in many systems other than
Lisp with the same meaning: Snobol, ECL, MIT Teco (!), ....

	-s


ICSE = Intl. Conf. on Software Engineering
POPL = Principles of Programming Languages (Conf.)

Re: GC in Ada

[Rick Conn]

The basic goal of GC is to reclaim space that is no longer needed for
one purpose and allow said space to be used for something else.  For
an application program, this can be done by the opsys, which I believe
is the focus of your message, but it can also be done by the application
itself.  In both cases, the desired effect, viz the utilization of less
space by the application, is achieved.  This is why I feel that the GARBAGE
component is viable ... and it offers a solution now, rather than later.

	Rick
-------

GC in Ada

[Martin Krischik]

Maciej Sobczak schrieb:

> Yes. Note that scoped lifetime does not preclude GC on some lower level.
> Scoped lifetime provides a hook for deterministic "good bye" action - 
> there is nothing more to it. Even if that "good bye" action calls 
> free/delete/whatever on some memory block, there is nothing that forces 
> the runtime to return the given block of memory right back to the 
> operating system. Actually, none of the self-respecting allocators do 
> this systematically - instead they keep the memory around for a while in 
> anticipation of future allocations.

I believe in most systems memory is never returned.

If I understood Unix file management right only memory at the end of the 
heap can be returned. Without compaction a no go.

And on Windows I know that only the full block allocated with MemAlloc 
can be returned. Blocks are always page sized (multiple of 4kb). A smart 
Memory manager might reserve a full block for large allocations but all 
those tiny 20 byte allocations will never be returned to the OS.

> What I'm against is a GC "paradigm" that prevents me from having 
> deterministic "good bye" hooks for scoped lifetime. The problem is that 
> most GC-oriented languages I'm aware of do have this "issue".

But isn't that exactly what "Unchecked_Deallocation" and "pragma 
Controlled" is all about? Has Ada - by your rationale - not got GC right?

Martin

Re: GC in Ada

[Markus E Leypold]

Martin Krischik <krischik@users.sourceforge.net> writes:

> Maciej Sobczak schrieb:
>
>> Yes. Note that scoped lifetime does not preclude GC on some lower level.
>> Scoped lifetime provides a hook for deterministic "good bye" action
>> -
>> there is nothing more to it. Even if that "good bye" action calls
>> free/delete/whatever on some memory block, there is nothing that
>> forces the runtime to return the given block of memory right back to
>> the operating system. Actually, none of the self-respecting
>> allocators do this systematically - instead they keep the memory
>> around for a while in anticipation of future allocations.
>
> I believe in most systems memory is never returned.
>
> If I understood Unix file management right only memory at the end of
> the heap can be returned. Without compaction a no go.

You're partly right. It depends on the heap implementation. If done
using sbrk() you're right. If done using mmap() you'd have --
theoretically -- the possibility wo return sufficiently large holes to
the OS. 

Regards -- Markus

Re: GC in Ada

[Maciej Sobczak]

Martin Krischik wrote:

>> What I'm against is a GC "paradigm" that prevents me from having 
>> deterministic "good bye" hooks for scoped lifetime. The problem is 
>> that most GC-oriented languages I'm aware of do have this "issue".
> 
> But isn't that exactly what "Unchecked_Deallocation" and "pragma 
> Controlled" is all about? Has Ada - by your rationale - not got GC right?

By my rationale Ada and C++ got it perfectly right ([Limited_]Controlled 
mess aside).

The only difference between them in this regard is that Ada explicitly 
allows GC on the low level without requiring it (so that implementations 
can ignore the whole idea) and that C++ is traditionally silent about 
the concept altogether (so that implementations can provide it). ;-)

(Note that GC will likely be formalized in the upcoming C++ standard.)

My criticism is targeted at those languages which bring GC to the top 
level obstructing the visible part of the object model.

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: GC in Ada

[Martin Krischik]

Maciej Sobczak schrieb:
> Martin Krischik wrote:
> 
>>> What I'm against is a GC "paradigm" that prevents me from having 
>>> deterministic "good bye" hooks for scoped lifetime. The problem is 
>>> that most GC-oriented languages I'm aware of do have this "issue".
>>
>> But isn't that exactly what "Unchecked_Deallocation" and "pragma 
>> Controlled" is all about? Has Ada - by your rationale - not got GC right?
> 
> By my rationale Ada and C++ got it perfectly right ([Limited_]Controlled 
> mess aside).
> 
> The only difference between them in this regard is that Ada explicitly 
> allows GC on the low level without requiring it (so that implementations 
> can ignore the whole idea) and that C++ is traditionally silent about 
> the concept altogether (so that implementations can provide it). ;-)

Only that C++ does not have pragma Controlled to switch the collector 
off. And Unchecked_Deallocation should deallocate even when a collector 
is present.

> (Note that GC will likely be formalized in the upcoming C++ standard.)

Which could solve the above.

> My criticism is targeted at those languages which bring GC to the top 
> level obstructing the visible part of the object model.

On my Weblogic course I could not stop shaking my head about all the 
problems which brings the "all is pointer" concept of Java.

Martin

Re: GC in Ada

[Markus E Leypold]

Maciej Sobczak <no.spam@no.spam.com> writes:

> Martin Krischik wrote:
>
>>> What I'm against is a GC "paradigm" that prevents me from having
>>> deterministic "good bye" hooks for scoped lifetime. The problem is
>>> that most GC-oriented languages I'm aware of do have this "issue".
>> But isn't that exactly what "Unchecked_Deallocation" and "pragma
>> Controlled" is all about? Has Ada - by your rationale - not got GC
>> right?
>
> By my rationale Ada and C++ got it perfectly right
> ([Limited_]Controlled mess aside).
>
> The only difference between them in this regard is that Ada explicitly
> allows GC on the low level without requiring it (so that
> implementations can ignore the whole idea) and that C++ is
> traditionally silent about the concept altogether (so that
> implementations can provide it). ;-)
>
> (Note that GC will likely be formalized in the upcoming C++ standard.)
>
> My criticism is targeted at those languages which bring GC to the top
> level obstructing the visible part of the object model.

You mean like Smalltalk -- a language which carries the label OO
wrongly, because it's GC obstructs the object model.

Hm.

Actually I think, real OO (as opposed to tagged types) need GC and
unbounded life time of objects. That's indeed all OO is about.

Regards -- Markus

Re: GC in Ada

[Markus E Leypold]

Martin Krischik <krischik@users.sourceforge.net> writes:

> Maciej Sobczak schrieb:
>> Martin Krischik wrote:
>>
>>>> What I'm against is a GC "paradigm" that prevents me from having
>>>> deterministic "good bye" hooks for scoped lifetime. The problem is
>>>> that most GC-oriented languages I'm aware of do have this "issue".
>>>
>>> But isn't that exactly what "Unchecked_Deallocation" and "pragma
>>> Controlled" is all about? Has Ada - by your rationale - not got GC
>>> right?
>> By my rationale Ada and C++ got it perfectly right
>> ([Limited_]Controlled mess aside).
>> The only difference between them in this regard is that Ada
>> explicitly allows GC on the low level without requiring it (so that
>> implementations can ignore the whole idea) and that C++ is
>> traditionally silent about the concept altogether (so that
>> implementations can provide it). ;-)
>
> Only that C++ does not have pragma Controlled to switch the collector
> off. And Unchecked_Deallocation should deallocate even when a
> collector is present.
>
>> (Note that GC will likely be formalized in the upcoming C++ standard.)
>
> Which could solve the above.
>
>> My criticism is targeted at those languages which bring GC to the
>> top level obstructing the visible part of the object model.
>
> On my Weblogic course I could not stop shaking my head about all the
> problems which brings the "all is pointer" concept of Java.

Fortunately you can ignore this "all is pointer" by exposing only a
read-only interface to the client and leaving the rest to the GC. That
feels exactly like passing records around with in, out and in/out.  I
don't see the problem. Not to doubt your experience on this, but just
because I'm curious: Can you provide a hint or example what the
problems are?

Regards -- Markus

Re: GC in Ada

[Martin Krischik]

Markus E Leypold schrieb:

> Martin Krischik <krischik@users.sourceforge.net> writes:

>> Maciej Sobczak schrieb:

>> On my Weblogic course I could not stop shaking my head about all the
>> problems which brings the "all is pointer" concept of Java.

> Fortunately you can ignore this "all is pointer" by exposing only a
> read-only interface to the client and leaving the rest to the GC

Only Java has no const keyword. It is supposed to get one but how long 
until it is actually used?

> That
> feels exactly like passing records around with in, out and in/out.  I
> don't see the problem. Not to doubt your experience on this, but just
> because I'm curious: Can you provide a hint or example what the
> problems are?

I can give you the solution, which is not used all that widely because 
of the performance impact:

class X
   {
   Date date = new Date;

   Date
   get_Date ()
      {
      return new Date (date);
      }

   void
   set_Date (Date new_Date)
      {
      date = new Date (new_Date);
      }
   }

Got it? If get_Date would just return date it would return a modifiable 
pointer - which could be used and - well - modified almost everywhere.

As said the solution above is not used all that often and so the 
interesting part in the weblogic course was that the hard core java 
programmers had to learn that for remote call object those object might 
be copied behind the scenes and not passes by (non const) reference. And 
so to those objects modifications might be lost!

This was the moment where a hole horror scenario unfolded to me: 
programmers which actually modified objects returned by a geta function 
instead of using the appropriate seta function!

Martin

Re: GC in Ada

[Maciej Sobczak]

Martin Krischik wrote:

> And Unchecked_Deallocation should deallocate even when a collector 
> is present.

I don't understand. There is no legal way for the program to verify that 
anything was indeed deallocated, so it doesn't make much sense to say 
that this behaviour is required.

As far as I understand it, Unchecked_Deallocation is allowed to do 
nothing. That wouldn't be a very competitive language implementation, 
but AARM does not require it either. :-)

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: GC in Ada

[Maciej Sobczak]

Markus E Leypold wrote:

> Actually I think, real OO (as opposed to tagged types) need GC and
> unbounded life time of objects. That's indeed all OO is about.

That is quite novel definition of OO. Any references?

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: GC in Ada

[Martin Krischik]

Maciej Sobczak schrieb:

> Martin Krischik wrote:

>> And Unchecked_Deallocation should deallocate even when a collector is 
>> present.

> I don't understand. There is no legal way for the program to verify that 
> anything was indeed deallocated, so it doesn't make much sense to say 
> that this behaviour is required.

should /= must

> As far as I understand it, Unchecked_Deallocation is allowed to do 
> nothing. That wouldn't be a very competitive language implementation, 
> but AARM does not require it either. :-)

Just read it up [1] and Unchecked_Deallocation may not be a no-op - you 
forgot finalization. Apart from that:

---------------------
Implementation Advice

For a standard storage pool, Free should actually reclaim the storage.
---------------------

Again "Should /= must" and - you are right - there are no references as 
to when reclaim should happen.

Martin

[1] http://www.adaic.com/standards/05rm/html/RM-13-11-2.html

Re: GC in Ada

[Markus E Leypold]

Maciej Sobczak <no.spam@no.spam.com> writes:

> Martin Krischik wrote:
>
>> And Unchecked_Deallocation should deallocate even when a collector
>> is present.
>
> I don't understand. There is no legal way for the program to verify
> that anything was indeed deallocated, so it doesn't make much sense to
> say that this behaviour is required.

Oh yes. Deallocating immeditately and deallocating later makes a
difference in time and space behaviour -- which IS measurable outside
the program (BTW: Exactly what you've been harping upon in you
opposition against GC :-)) )

Regards -- Markus

Re: GC in Ada

[Markus E Leypold]

Martin Krischik <krischik@users.sourceforge.net> writes:

> Markus E Leypold schrieb:
>
>> Martin Krischik <krischik@users.sourceforge.net> writes:
>
>>> Maciej Sobczak schrieb:
>
>>> On my Weblogic course I could not stop shaking my head about all the
>>> problems which brings the "all is pointer" concept of Java.
>
>> Fortunately you can ignore this "all is pointer" by exposing only a
>> read-only interface to the client and leaving the rest to the GC

> Only Java has no const keyword. It is supposed to get one but how long
> until it is actually used?


Excuse me, but ... "a read only interface" means:

   (a) make all field of objects private 
   (b) allow access only my methods
   (c) provide only Get_*-methods, no Set_*-methods

(a+b) is actually standard good practice in software engineering,
since it allows to hide representation and allows for maintaining
cached attributes/data (which direct access to fields won't allow).

Regards -- Markus

Re: GC in Ada

[Markus E Leypold]

Maciej Sobczak <no.spam@no.spam.com> writes:

> Markus E Leypold wrote:

>> Actually I think, real OO (as opposed to tagged types) need GC and
>> unbounded life time of objects. That's indeed all OO is about.

> That is quite novel definition of OO. Any references?

Ian Graham: "Object-Oriented Methods: Principles & Practice". 

Footnotes and general comments there make that quite clear I
think. (But I can't quote chapter and verse here, since I DON'T intend
to spent the rest of the morning with researching literature). I
remeber that this was not the first source which noted that a delete
operator is quite contrary to the spirit of stateful OOP (as opposed
to the functional OO models proposed by Abadi and others (Cardelli?).

And then of course there is me, myself, as a source :-). The reasoning
fo the assertion above is basically that OO is about having
(projected) views of a total system. In no view you can say that an
object leaves the view -- you can only say that it becomes unimportant
for the view (goes into the kernel of the projection). And that is so
for all views -- whose sum only gives the complete system. Then (when
viewing the whole system) you can decide where to delete. Object
deletion is a global property/function. Rooting it in any subsystem
will destroy modularity in the OO sense (which is different from
modularity in the modula2 or Ada-sense, which is derived from the
ideas of structured programming).

But note that I'm not really interested in discussing these
propositions. Either you profit from it or you don't -- I don't think
that it is easy to see what I mean and it was hard for me to get that
insights at the beginning (since there is really lots of bad
literature on OO (mostly the ad-hoc approach) and few usable formal or
semi-formal approaches). Discussing those on a serious level would take
lots of time. So I have just to assert my guru status here for lack of
more time :-).

Regards -- Markus

Re: GC in Ada

[Jeffrey R. Carter]

Maciej Sobczak wrote:
> 
> As far as I understand it, Unchecked_Deallocation is allowed to do 
> nothing. That wouldn't be a very competitive language implementation, 
> but AARM does not require it either. :-)

Unchecked_Deallocation has to set its parameter to null.

The Rolm-Data General compiler, the 1st validated Ada-83 compiler, did 
only that. The argument was that every program had a 4 GB virtual memory 
space, so there was no need to actually reclaim memory.

In reality, I think it was skipped to save time so they could have the 
1st validated compiler.

-- 
Jeff Carter
"What I wouldn't give for a large sock with horse manure in it."
Annie Hall
42

Re: GC in Ada

[Dmitry A. Kazakov]

On Wed, 07 Feb 2007 12:53:27 +0100, Martin Krischik wrote:

> On my Weblogic course I could not stop shaking my head about all the 
> problems which brings the "all is pointer" concept of Java.

Which is the same sort of rubbish as "all is object."

Clearly it is impossible to have all types referents. I don't mean here
small fundamental types like Boolean etc, but the pointers themselves. To
incorporate then one needs to introduce pointers-to-pointers, then
pointers-to-pointers-to-pointers ad infinitum, which is impossible. The
"concept" leaks. 

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: GC in Ada

[Maciej Sobczak]

Dmitry A. Kazakov wrote:

>> On my Weblogic course I could not stop shaking my head about all the 
>> problems which brings the "all is pointer" concept of Java.
> 
> Which is the same sort of rubbish as "all is object."
> 
> Clearly it is impossible to have all types referents. I don't mean here
> small fundamental types like Boolean etc, but the pointers themselves. To
> incorporate then one needs to introduce pointers-to-pointers, then
> pointers-to-pointers-to-pointers ad infinitum, which is impossible. The
> "concept" leaks. 

Not only it leaks, but combined with other defficiencies often leads to 
"consciusness split".

Consider: int, Integer, IntHolder.
That gives three types for the same logical domain.

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: GC in Ada

[Jean-Pierre Rosen]

Jeffrey R. Carter a �crit :

> The Rolm-Data General compiler, the 1st validated Ada-83 compiler
Although DG claimed that, their certificate shows #2.
#1 was Ada-ED, from NYU, as everybody should know.


-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: GC in Ada

[Martin Krischik]

Dmitry A. Kazakov schrieb:
> On Wed, 07 Feb 2007 12:53:27 +0100, Martin Krischik wrote:
> 
>> On my Weblogic course I could not stop shaking my head about all the 
>> problems which brings the "all is pointer" concept of Java.
> 
> Which is the same sort of rubbish as "all is object."
> 
> Clearly it is impossible to have all types referents. I don't mean here
> small fundamental types like Boolean etc, but the pointers themselves. To
> incorporate then one needs to introduce pointers-to-pointers, then
> pointers-to-pointers-to-pointers ad infinitum, which is impossible. The
> "concept" leaks. 

Well, really it is "all objects and arrays handled by reference". But 
still a silly concept.

Martin

Re: GC in Ada

[Robert A Duff]

Jean-Pierre Rosen <rosen@adalog.fr> writes:

> Jeffrey R. Carter a �crit :
>
>> The Rolm-Data General compiler, the 1st validated Ada-83 compiler
> Although DG claimed that, their certificate shows #2.
> #1 was Ada-ED, from NYU, as everybody should know.

I think it's fair to say that Ada-ED was the first validated
implementation of Ada 83, and that the Rolm-Data General implementation
was the first validated Ada compiler for Ada 83.

- Bob

Re: GC in Ada

[Martin Krischik]

Markus E Leypold schrieb:

>> Only Java has no const keyword. It is supposed to get one but how long
>> until it is actually used?
> 
> Excuse me, but ... "a read only interface" means:
> 
>    (a) make all field of objects private 
>    (b) allow access only my methods
>    (c) provide only Get_*-methods, no Set_*-methods

you mean as in:

java.lang.Date
get_Date ()
   {
   return this.date;
   }

True enough, with a Get_*-method like this you never need a Set_*-method 
;-).

Martin

Re: GC in Ada

[Georg Bauhaus]

On Thu, 2007-02-08 at 10:33 +0100, Markus E Leypold wrote:
> 
> Martin Krischik <krischik@users.sourceforge.net> writes:

> > Only Java has no const keyword. It is supposed to get one but how long
> > until it is actually used?
> 
> 
> Excuse me, but ... "a read only interface" means:
> 
>    (a) make all field of objects private 
>    (b) allow access only my methods

What Eiffel does by design.

>    (c) provide only Get_*-methods, no Set_*-methods

This lets programmers design type interfaces and wrappers so that
objects are effectively read-only.
Wouldn't it be nice to just export a constant view where
needed? Like C++'s const& or Ada's access-to-constant?
Or to have C++ const view and Ada in mode parameters
that extend to the referred object?

procedure a is

    type J is
        record
            x: Integer;
        end record;

    procedure nope(this: in J; new_x: Integer) is
    begin
        this.x := new_x; -- compile time error
    end nope;

begin
    nope(42);
end a;


struct J
{
  int x;
};

int main()
{
  J wj;
  const J rj = wj;

  wj.x = 42;
  rj.x = 42;  // compile time error
  return 0;
}

Re: GC in Ada

[Dmitry A. Kazakov]

On Fri, 09 Feb 2007 11:07:44 +0100, Martin Krischik wrote:

> Dmitry A. Kazakov schrieb:
>> On Wed, 07 Feb 2007 12:53:27 +0100, Martin Krischik wrote:
>> 
>>> On my Weblogic course I could not stop shaking my head about all the 
>>> problems which brings the "all is pointer" concept of Java.
>> 
>> Which is the same sort of rubbish as "all is object."
>> 
>> Clearly it is impossible to have all types referents. I don't mean here
>> small fundamental types like Boolean etc, but the pointers themselves. To
>> incorporate then one needs to introduce pointers-to-pointers, then
>> pointers-to-pointers-to-pointers ad infinitum, which is impossible. The
>> "concept" leaks. 
> 
> Well, really it is "all objects and arrays handled by reference". But 
> still a silly concept.

But what is so special in Boolean which makes it non-object? Such
irregularities are always language design faults.

[ As for Ada there should be Boolean'Class. ]

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: GC in Ada

[Maciej Sobczak]

Markus E Leypold wrote:

>>> And Unchecked_Deallocation should deallocate even when a collector
>>> is present.
>> I don't understand. There is no legal way for the program to verify
>> that anything was indeed deallocated, so it doesn't make much sense to
>> say that this behaviour is required.
> 
> Oh yes. Deallocating immeditately and deallocating later makes a
> difference in time and space behaviour -- which IS measurable outside
> the program

With a small issues that this possibility is not formalized by the 
language standard (please read carefully my sentence above: "there is no 
*legal* way *for the program*").

And that is why it is *not* measurable, because there is no sensible way 
to define at which level of memory management it should be measured.

As was already pointed out in this thread, with some operating systems 
memory reclamation might not be meaningful at all unless the whole 
program is terminated.

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: GC in Ada

[Jean-Pierre Rosen]

Robert A Duff a �crit :
> Jean-Pierre Rosen <rosen@adalog.fr> writes:
> I think it's fair to say that Ada-ED was the first validated
> implementation of Ada 83, and that the Rolm-Data General implementation
> was the first validated Ada compiler for Ada 83.
> 
I fail to see why Ada-ED does not deserve the name "compiler". I may 
admit that Rolm was the first /industrial/ compiler, i.e. usable for 
real programs...

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: GC in Ada

[Maciej Sobczak]

Georg Bauhaus wrote:

> Or to have C++ const view and Ada in mode parameters
> that extend to the referred object?

>   J wj;
>   const J rj = wj;
            ^

const J &rj = wj;
         ^

I guess you wanted to use const reference. This is closer to the concept 
of "view".

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: GC in Ada

[Markus E Leypold]

Maciej Sobczak <no.spam@no.spam.com> writes:

>> Oh yes. Deallocating immeditately and deallocating later makes a
>> difference in time and space behaviour -- which IS measurable outside
>> the program
>
> With a small issues that this possibility is not formalized by the
> language standard (please read carefully my sentence above: "there is
> no *legal* way *for the program*").
>
> And that is why it is *not* measurable, because there is no sensible
> way to define at which level of memory management it should be
> measured.

You said:

>>> I don't understand. There is no legal way for the program to verify
>>> that anything was indeed deallocated, so it doesn't make much sense to
>>> say that this behaviour is required.

This is a 'non sequitur', since it makes sense to say the behaviour is
required to fix certain real time properties. Regardless of wether it
can be detected in the program (and it could, by observing the wall
clock).

> As was already pointed out in this thread, with some operating systems
> memory reclamation might not be meaningful at all unless the whole
> program is terminated.

I don't even ask to be shown such an operating system...

Regards -- Markus

Re: GC in Ada

[Jeffrey R. Carter]

Jean-Pierre Rosen wrote:
> 
> Although DG claimed that, their certificate shows #2.
> #1 was Ada-ED, from NYU, as everybody should know.

Ada-ED was an interpreter, not a compiler, as everybody should know.

-- 
Jeff Carter
"Sheriff murdered, crops burned, stores looted,
people stampeded, and cattle raped."
Blazing Saddles
35

Re: GC in Ada

[Georg Bauhaus]

On Fri, 2007-02-09 at 16:29 +0100, Maciej Sobczak wrote:
> Georg Bauhaus wrote:

> >   J wj;
> >   const J rj = wj;
>             ^
> 
> const J &rj = wj;
>          ^
> 
> I guess you wanted to use const reference. This is closer to the concept 
> of "view".

Yes, thanks for the patch.

Re: GC in Ada

[Robert A Duff]

Jean-Pierre Rosen <rosen@adalog.fr> writes:

> Robert A Duff a �crit :
>> Jean-Pierre Rosen <rosen@adalog.fr> writes:
>> I think it's fair to say that Ada-ED was the first validated
>> implementation of Ada 83, and that the Rolm-Data General implementation
>> was the first validated Ada compiler for Ada 83.
>>
> I fail to see why Ada-ED does not deserve the name "compiler". 

Because the Ada-ED implementation was highly interpretive.

>...I may
> admit that Rolm was the first /industrial/ compiler, i.e. usable for
> real programs...

- Bob

Re: GC in Ada

[Martin Krischik]

Jeffrey R. Carter wrote:

> Jean-Pierre Rosen wrote:
>> 
>> Although DG claimed that, their certificate shows #2.
>> #1 was Ada-ED, from NYU, as everybody should know.
> 
> Ada-ED was an interpreter, not a compiler, as everybody should know.

Ada interpreter, cool.

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: GC in Ada

[Pascal Obry]

Jeffrey R. Carter a �crit :
> Jean-Pierre Rosen wrote:
>>
>> Although DG claimed that, their certificate shows #2.
>> #1 was Ada-ED, from NYU, as everybody should know.
> 
> Ada-ED was an interpreter, not a compiler, as everybody should know.

Well one could argue that Ada-ED was a compiler to a virtual machine.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GC in Ada

[Jeffrey R. Carter]

Pascal Obry wrote:
> 
> Well one could argue that Ada-ED was a compiler to a virtual machine.

I never used it, but my understanding is that that isn't an accurate 
description.

-- 
Jeff Carter
"Many times we're given rhymes that are quite unsingable."
Monty Python and the Holy Grail
57

Re: GC in Ada

[Jean-Pierre Rosen]

Robert A Duff a �crit :
>> I fail to see why Ada-ED does not deserve the name "compiler". 
> 
> Because the Ada-ED implementation was highly interpretive.
> 
So what? You still have to transform source text into another 
representation, and do numerous checks at the same time. That's what I 
call "compiling".

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: GC in Ada

[Maciej Sobczak]

Markus E Leypold wrote:

>>>> I don't understand. There is no legal way for the program to verify
>>>> that anything was indeed deallocated, so it doesn't make much sense to
>>>> say that this behaviour is required.
> 
> This is a 'non sequitur', since it makes sense to say the behaviour is
> required to fix certain real time properties. Regardless of wether it
> can be detected in the program (and it could, by observing the wall
> clock).

Observing the wall clock does not help much in a language where even 
null; can raise exceptions. Standard does not even guarantee that any 
given sequence of instructions will give consistent timings when run twice.

Definitely, observice the wall clock is of no use to verify memory 
deallocation, since deallocation might have positive effect on the 
timing as well as negative or none at all.

>> As was already pointed out in this thread, with some operating systems
>> memory reclamation might not be meaningful at all unless the whole
>> program is terminated.
> 
> I don't even ask to be shown such an operating system...

On systems with virtual memory, deallocations that don't span at least 
one full page (that condition can be met after joining with other free 
blocks, though) will certainly not deallocate anything to the operating 
system.


-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: GC in Ada

[Markus E Leypold]

Maciej Sobczak <no.spam@no.spam.com> writes:

> Markus E Leypold wrote:
>
>>>>> I don't understand. There is no legal way for the program to verify
>>>>> that anything was indeed deallocated, so it doesn't make much sense to
>>>>> say that this behaviour is required.
>> This is a 'non sequitur', since it makes sense to say the behaviour
>> is
>> required to fix certain real time properties. Regardless of wether it
>> can be detected in the program (and it could, by observing the wall
>> clock).
>
> Observing the wall clock does not help much in a language where even
> null; can raise exceptions. Standard does not even guarantee that any
> given sequence of instructions will give consistent timings when run
> twice.
>
> Definitely, observice the wall clock is of no use to verify memory
> deallocation, since deallocation might have positive effect on the
> timing as well as negative or none at all.

If you don't deallocate memory "really" in Unchecked_Deallocation then
you aither run out of memory sooner or later (verifiable and it makes
sense to require that this doesn't occur) or you have a garbage
collector and intermittend garbage collection runs which are visible
in the real time behaviour. So it makes sense to say the behaviour
(real deallocation to return memory to the free list) is required and
checkable, regardless of the question wether _the program_ can verify this. 

And as I said, from "no legal way for the program to verify" to
"doesn't make much sense to say that this behaviour is required" is a
non sequitur since behaviour might entail aspects that cannot only be
described in the production of data.

>>> As was already pointed out in this thread, with some operating systems
>>> memory reclamation might not be meaningful at all unless the whole
>>> program is terminated.
>> I don't even ask to be shown such an operating system...
>
> On systems with virtual memory, deallocations that don't span at least
> one full page (that condition can be met after joining with other free
> blocks, though) will certainly not deallocate anything to the
> operating system.

Excuse me: I misread "memory reclamation might not be meaningful at
all unless the whole program is terminated" as: No memory is ever
deallocated. Which is still the only meaningful reading of your
sentence since deallocation to the internal free block list is still
meaningful and not a no-op.

Regards -- Markus

Re: GC in Ada

[Jeffrey R. Carter]

Jean-Pierre Rosen wrote:
>
> So what? You still have to transform source text into another 
> representation, and do numerous checks at the same time. That's what I 
> call "compiling".

Then your definition differs from mine, Duff's, and numerous other people's.

-- 
Jeff Carter
"So if I understand 'The Matrix Reloaded' correctly, the Matrix is
basically a Microsoft operating system--it runs for a while and
then crashes and reboots. By design, no less. Neo is just a
memory leak that's too hard to fix, so they left him in ... The
users don't complain because they're packed in slush and kept
sedated."
Marin D. Condic
65

Re: GC in Ada

[Pascal Obry]

Jeffrey R. Carter a �crit :
> Pascal Obry wrote:
>>
>> Well one could argue that Ada-ED was a compiler to a virtual machine.
> 
> I never used it, but my understanding is that that isn't an accurate
> description.

I've used it... log time ago and IIRC it was using a kind of p-code a-la
Pascal. This is just a kind of virtual machine to me...

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GC in Ada

[Jeffrey R. Carter]

Pascal Obry wrote:
> 
> I've used it... log time ago and IIRC it was using a kind of p-code a-la
> Pascal. This is just a kind of virtual machine to me...

I guess it's a matter of semantics. If the program reads the source and 
performs the actions required by it, I consider it an interpreter. What 
activities it uses internally to perform that interpretation are an 
elephant.

If the program converts the source into another form which can later be 
executed by appropriate HW or an emulator, then I call it a compiler. 
UCSD Pascal had a Pascal-to-P-code compiler. The P-code could be 
executed later, on a P-code machine or, more commonly, through an 
emulator. (I'm not aware of there ever being a P-code machine, which is 
why it's often referred to as a virtual machine. But there's no reason 
there couldn't have been one.) Java works similarly.

My understanding is that Ada-Ed was in the former category.

-- 
Jeff Carter
"C++ is like giving an AK-47 to a monk, shooting him
full of crack and letting him loose in a mall and
expecting him to balance your checking account
'when he has the time.'"
Drew Olbrich
52

Re: GC in Ada

[Jean-Pierre Rosen]

Pascal Obry a �crit :
> Jeffrey R. Carter a �crit :
>> Pascal Obry wrote:
>>> Well one could argue that Ada-ED was a compiler to a virtual machine.
>> I never used it, but my understanding is that that isn't an accurate
>> description.
> 
> I've used it... log time ago and IIRC it was using a kind of p-code a-la
> Pascal. This is just a kind of virtual machine to me...
> 
Since we are in historical mode...

The first version of Ada-ED was interpreting directly SETL structures. 
The second one generated code for a virtual machine.

If you are really interested, the description of the virtual machine can 
be found in the PhD thesis of P. Kruchten and J-P. Rosen ;-). Only 
available on paper, though (this was in 1985).
-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: GC in Ada

[Jean-Pierre Rosen]

Jeffrey R. Carter a �crit :
> The P-code could be 
> executed later, on a P-code machine or, more commonly, through an 
> emulator. (I'm not aware of there ever being a P-code machine, which is 
> why it's often referred to as a virtual machine. But there's no reason 
> there couldn't have been one.) 
There was one, by Western-Digital:
http://en.wikipedia.org/wiki/Pascal_MicroEngine

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: GC in Ada

[Jeffrey R. Carter]

Jean-Pierre Rosen wrote:
> 
> The first version of Ada-ED was interpreting directly SETL structures. 
> The second one generated code for a virtual machine.

I guess the question, then, is which version received certificate #1?

-- 
Jeff Carter
"I blow my nose on you."
Monty Python & the Holy Grail
03

Re: GC in Ada

[Jeffrey R. Carter]

Jean-Pierre Rosen wrote:
> There was one [P-code machine], by Western-Digital:
> http://en.wikipedia.org/wiki/Pascal_MicroEngine

Cool.

-- 
Jeff Carter
"I blow my nose on you."
Monty Python & the Holy Grail
03

Re: GC in Ada

[Robert A Duff]

"Jeffrey R. Carter" <jrcarter@acm.org> writes:

> If the program converts the source into another form which can later be
> executed by appropriate HW or an emulator, then I call it a
> compiler.

Well, Ada requires certain errors to be detected at compile time,
so it is impossible to write a _pure_ interpreter for Ada -- something
like a Unix shell, which executes the first line before even looking
at the second line.  An Ada implementation has to look at the entire
program before running it.

But still, the part of Ada-Ed that runs the SETL structures or the bytes
or whatever, is an interpreter.  I claim Ada-Ed is a hybrid
implementation of Ada -- neither pure interpreter nor pure compiler.

- Bob

Re: GC in Ada

[Jean-Pierre Rosen]

Jeffrey R. Carter a �crit :
> Jean-Pierre Rosen wrote:
>>
>> The first version of Ada-ED was interpreting directly SETL structures. 
>> The second one generated code for a virtual machine.
> 
> I guess the question, then, is which version received certificate #1?
> 
It was the full SETL version. I don't argue that it was interpreted. I 
just mean that a "compiler" is any tool that processes a programming 
language (which term would you use instead?).

The difference between HW code generation or "interpretation" is a very 
thin implementation detail. As mentionned before, is P-Code 
interpretation? What if P-Code is cast in hardware? And isn't a "true" 
processor something that interprets its own code with micro-instructions?

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: GC in Ada

[Jeffrey R. Carter]

Jean-Pierre Rosen wrote:
>>
> It was the full SETL version. I don't argue that it was interpreted. I 
> just mean that a "compiler" is any tool that processes a programming 
> language (which term would you use instead?).

That's a pretty broad definition. It covers pretty printers and 
AdaSubst, for example.

I don't have a term for any tool that processes a programming language.

-- 
Jeff Carter
"Go and boil your bottoms."
Monty Python & the Holy Grail
01