containers and garbage collections.

containers and garbage collections.

[Martin Krischik]

Hello,

with this article I want to bring two of my discussions together.

On one side I am avocating garbage collection and one argument against it is
that proper container library will make garbage collection unneccesary.

One the other side I am avocating a more complete container librarys and one
argument against it is that one can allways use access types.

In Germany we say that the "cat bites is own tail" here.

Without garbage collection access types are pain in the bud. And when the
container library only stores "type element is private;" than one need to
use access types as element.

I have proven that both options are possible

I have implemented a garbage collected storrage pool for GNAT.

I also have created containers for "type Element (<>) is abstract tagged
private;" and I belive "type Element is array (Index range <>) of Item;" is
possible as well (Enabling collection of Strings). Both can't be done with
C++ templates - so we should not take the all mighty STL as an example.

Any thougts?

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: containers and garbage collections.

[Stephen Leake]

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

> Hello,
> 
> with this article I want to bring two of my discussions together.
> 
> On one side I am avocating garbage collection and one argument against it is
> that proper container library will make garbage collection unneccesary.

I agree; proper containers (and other algorithms) make garbage
collection unnecessary.

> One the other side I am avocating a more complete container librarys
> and one argument against it is that one can allways use access
> types.

Well, one can always use assembly language, too. Containers are an
excellent replacement for access types.

> Without garbage collection access types are pain in the bud. 

Hmm. I guess I can agree with that. But garbage collection is a "pain
in the bud" also; you can't use Finalization for good stuff, you can't
predict when the garbage will be collected. I far prefer containers.

> And when the container library only stores "type element is
> private;" than one need to use access types as element.

Yes.

> I have proven that both options are possible

I'm not sure which options you mean by "both options".

> I have implemented a garbage collected storrage pool for GNAT.

That's nice, and I hope you had fun doing it :).

> I also have created containers for "type Element (<>) is abstract
> tagged private;" 

Good. I'll have to look at it and compare it to SAL
(http://www.toadmail.com/~ada_wizard/), which provides similar
containers. 

> and I belive "type Element is array (Index range <>) of Item;" is
> possible as well (Enabling collection of Strings). 

Yes; SAL containers can hold Ada strings, with appropriate storage
management. 

Do either of your containers rely on the garbage collected storage
pool?

> Both can't be done with C++ templates - so we should not take the
> all mighty STL as an example.

Hmm. I haven't really looked, but I'd be very surprised if an STL
container can't contain STL Strings.

Of course, there is no such thing as "indefinite abstract tagged
private" in C++. The closest thing is a class with only pure virtual
member functions; that leaves out the "indefinite" part (implied by
the (<>)). So to say "STL" can't do that isn't saying much; you're
really just saying "C++ can't do that".

I'm not clear what you mean by "don't take the STL as an example".
Clearly the STL is limited by the expressiveness of C++; Ada is
better. But the STL has proven to be a very useful library, because of
the functionality it provides; it is reasonable to design an Ada
library that has similar functionality, but takes full advantage of
Ada to do it. I think that is your real goal?

-- 
-- Stephe

Re: containers and garbage collections.

[Martin Krischik]

Stephen Leake wrote:

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

> Do either of your containers rely on the garbage collected storage
> pool?

No, AdaCL rely on the garbage collected storage only at two places: The Text
Search and Replace Queues will leak less 16 bytes per File processed when
garbage collection is off.

The extended booch components will not leak memory when garbage collection
has been switched off. At least to my knowlege.
 
>> Both can't be done with C++ templates - so we should not take the
>> all mighty STL as an example.
 
> Hmm. I haven't really looked, but I'd be very surprised if an STL
> container can't contain STL Strings.

Ahh, Yes. but STL strings are like Unbounded_Strings. I was speaking of
fixed strings like char []. Support for open arrays is not the teriffic in
C++.

> Of course, there is no such thing as "indefinite abstract tagged
> private" in C++. The closest thing is a class with only pure virtual
> member functions; that leaves out the "indefinite" part (implied by
> the (<>)). So to say "STL" can't do that isn't saying much; you're
> really just saying "C++ can't do that".

No, you misunderstood. In Ada you can say:

Y: Child_of_Some_Abscract;
X : Some_Abscract_Access := new Some_Abscract'(Child_of_Some_Abscract);

and X will point to a copy of Y. In C++ you will need some form of cloning
facility.

> I'm not clear what you mean by "don't take the STL as an example".
> Clearly the STL is limited by the expressiveness of C++; Ada is
> better. But the STL has proven to be a very useful library, because of
> the functionality it provides; it is reasonable to design an Ada
> library that has similar functionality, but takes full advantage of
> Ada to do it. I think that is your real goal?

Yes, I agree on that. Prehaps I did not make myself clear enough.

With Regards

Martin 

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: containers and garbage collections.

[Matthew Heaney]

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

> Without garbage collection access types are pain in the bud. And when the
> container library only stores "type element is private;" than one need to
> use access types as element.

This statement is not quite correct.  It all depends on your level of
abstraction.  For example, a container for indefinite types can be
declared this way:

generic

   type Element_Type (<>) is private;

package Queues is

   type Queue_Type is limited private;

   procedure Insert
     (Queue : in out Queue_Type;
      Item  : in     Element_Type);

   function Top (Queue : Queue_Type) return Element_Type;

   procedure Pop (Queue : in out Queue_Type);

private

   type Element_Access is access Element_Type;

   type Node_Type;
   type Node_Access is access Node_Type;

   type Node_Type is record
      Element : Element_Access;
      Next    : Node_Access;
   end record;

   type Queue_Type is limited record
      Top : Node_Access;
   end record;

end Queues;


Now Insert can be implemented like this:

   procedure Insert
     (Queue : in out Queue_Type;
      Item  : in     Element_Type) is

      Node : constant Node_Access :=
         new Node_Type'(Element => new Element_Type'(Item),
                        Next    => null);
   begin
      ...
   end;

To extract an item, you just do this:

   procedure Op (Q : in out QT) is
      E : ET := Top (Q);
   begin
      Pop (Q);
   end;

From the point of view of a user of the queue, the queue contains
elements, of indefinite type Element_Type.  Clearly, inside the queue,
access types are used, but that is an implementation detail hidden from
client.


> I have proven that both options are possible
> 
> I have implemented a garbage collected storrage pool for GNAT.
> 
> I also have created containers for "type Element (<>) is abstract tagged
> private;" and I belive "type Element is array (Index range <>) of Item;" is
> possible as well (Enabling collection of Strings). Both can't be done with
> C++ templates - so we should not take the all mighty STL as an example.

Both of these containers are possible using the single declaration:

generic
   type Element_Type (<>) is private;
package GP is ...;

You can instantiate GP using either of the types in your example.  It's
not clear why you made two separate containers, one for tagged types
vs. another for array types, as a single container seems adequate.

Re: containers and garbage collections.

[Martin Krischik]

Matthew Heaney wrote:

> Martin Krischik <krischik@users.sourceforge.net> writes:
 
> From the point of view of a user of the queue, the queue contains
> elements, of indefinite type Element_Type.  Clearly, inside the queue,
> access types are used, but that is an implementation detail hidden from
> client.

Yes, and this is what I am advocating. And more.

>> I also have created containers for "type Element (<>) is abstract tagged
>> private;" and I belive "type Element is array (Index range <>) of Item;"
>>is
>> possible as well (Enabling collection of Strings). Both can't be done
>>with
>> C++ templates - so we should not take the all mighty STL as an example.

> Both of these containers are possible using the single declaration:
> 
> generic
>    type Element_Type (<>) is private;
> package GP is ...;
> 
> You can instantiate GP using either of the types in your example.  It's
> not clear why you made two separate containers, one for tagged types
> vs. another for array types, as a single container seems adequate.

Will it work with any combination of tagged types incl. controled types any
derived types of Element_Type? If so I stay corrected and will rething my
design.

With Rwegards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: containers and garbage collections.

[Matthew Heaney]

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

> Matthew Heaney wrote:
> 
> > Both of these containers are possible using the single declaration:
> > 
> > generic
> >    type Element_Type (<>) is private;
> > package GP is ...;
> > 
> > You can instantiate GP using either of the types in your example.  It's
> > not clear why you made two separate containers, one for tagged types
> > vs. another for array types, as a single container seems adequate.
> 
> Will it work with any combination of tagged types incl. controled types any
> derived types of Element_Type? If so I stay corrected and will rething my
> design.

Yes, it will work for any combination of tagged type.  All you need to
do is specify T'Class as the generic actual:

package P is new GP (T'Class);

This works becuase of Ada's built-in cloning facility.  So when you say

  X : Element_Access := new Element_Type'(Item);

this means

  X : T_Class_Access := new T'Class'(Item);

and now X designates a copy of Item, having the same type tag as Item.

When you query the item, just do this:

  E : T'Class := Top (Q);

This makes a copy of the (indefinite) element at the front of the queue.

If you want to be able to dispatch on the tag of an item in the
container, without having to make a copy of item, then you can expose
the internal pointer:

   E : constant Element_Access := Top_Access (Q);
begin
   Op (E.all);  --dispatch

Re: containers and garbage collections.

[Dmitry A. Kazakov]

On Sat, 13 Sep 2003 11:45:14 +0200, Martin Krischik
<krischik@users.sourceforge.net> wrote:

>Will it work with any combination of tagged types incl. controled types any
>derived types of Element_Type? If so I stay corrected and will rething my
>design.

Yes it will, as Matthew Heaney wrote. What you will lose with it, and
there is always something to lose, is that the type operations will
not be considered dispatching. So if the actual of Element_Type is
class-wide, and you want to dispatch somewhere in a generic body, you
will need to pass a [class-wide] wrapper subprogram around a primitive
operation instead of the primitive operation itself.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: containers and garbage collections.

[Matthew Heaney]

Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> writes:

> What you will lose with it, and there is always something to lose, is
> that the type operations will not be considered dispatching. So if the
> actual of Element_Type is class-wide, and you want to dispatch
> somewhere in a generic body, you will need to pass a [class-wide]
> wrapper subprogram around a primitive operation instead of the
> primitive operation itself.

That wasn't required for his problem.  All the dispatching is done
outside of the generic.

Re: containers and garbage collections.

[Martin Krischik]

Matthew Heaney wrote:

> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> writes:
 
>> What you will lose with it, and there is always something to lose, is
>> that the type operations will not be considered dispatching. So if the
>> actual of Element_Type is class-wide, and you want to dispatch
>> somewhere in a generic body, you will need to pass a [class-wide]
>> wrapper subprogram around a primitive operation instead of the
>> primitive operation itself.

> That wasn't required for his problem.  All the dispatching is done
> outside of the generic.

Initialize, Adjust, and Finalize are dispatching and will implicitly be
called (on GNAT by the hidden procedures Deep_Initialize, Deep_Adjust, and
Deep_Finalize which are also dispatching).

Still, I found you suggestion very interesting and I have started to work on
it.

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com