Container reqs

Container reqs

[Ehud Lamm]

Let's try to make a list of req the Ada community in general can agree on,
and than see which of the existing libraries is closest and concentrate on
that.

(the following are some suggestions)

* It seems there is a general agreement  to distinguish bouned from
unbounded versions. This can be attributed to a more general
(non-functional) req: the library should be applicable for RT

* I want a library organised around ADT properties (like "sequential
access", "set interface" etc) and not around implementations (doubly linked
lists).
[I think we should think of the best Ada apporach for connecting interfaces
and implementations. I explored many of the possibilities, like signature
packages, class-wide operations etc., and I am still looking for the best
method]

* From my experiens the item type is best accepted as a generic paramter (I
say this, before anyone suggests and "Object" type, and we start fighting
over MI)

* The library should offer Algortihms (in STL-speak): sorting, searching
etc.

* Standard iteration schemes over the various containers (I want both active
and passive versions)

* Since I am thinking about using the library in education, I'd prefer to
make isntantaion as easy as possible (possibly, by supplying
pre-instantiated versiosn). I also prefer to hide the tagged nature of
interface relationships from casual and first time users.

* Memory handling is important, but we don't want to have to do
library-level instantaions beacuse of Controlled types.

This is not ordered by importance, nor is it a complete list. Let's here
more suggestions and critics...
--
Ehud Lamm   mslamm@mscc.huji.ac.il

Re: Container reqs

[Larry Kilgallen]

In article <9qctpn$lil$1@news.huji.ac.il>, "Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:
> Let's try to make a list of req the Ada community in general can agree on,
> and than see which of the existing libraries is closest and concentrate on
> that.
> 
> (the following are some suggestions)

I don't know a lot about this...
...therefore:

I want a well documented set of components.

...badly enough that I would take a lead in writing the documentation
in return for having others review the work with a vengence.

Re: Container reqs

[James Rogers]

Ehud Lamm wrote:
> 
> Let's try to make a list of req the Ada community in general can agree on,
> and than see which of the existing libraries is closest and concentrate on
> that.
> 
> (the following are some suggestions)
> 
> * It seems there is a general agreement  to distinguish bouned from
> unbounded versions. This can be attributed to a more general
> (non-functional) req: the library should be applicable for RT

Bounded and unbounded distinctions are useful. Do we also want to 
specify that bounded versions are allocated on the stack while 
unbounded versions are dynamically allocated from some storage pool?
I believe this is what Dr. Lamm is suggesting. If so, I agree.

For the unbounded containers we may want versions allowing one to
designate the storage pool used.

> 
> * I want a library organised around ADT properties (like "sequential
> access", "set interface" etc) and not around implementations (doubly linked
> lists).
> [I think we should think of the best Ada apporach for connecting interfaces
> and implementations. I explored many of the possibilities, like signature
> packages, class-wide operations etc., and I am still looking for the best
> method]

This corresponds roughly with the approach taken by Java. It has
containers that implement various kinds of lists and sets. They are
organized by ADT properties and not by implementation details.

As far as an Ada approach for connecting interfaces, my first
impulse would be to define a set of abstract types for each 
category (i.e. sets and lists), then inherit from those types to
create the concrete and generic container classes.

> * From my experiens the item type is best accepted as a generic paramter (I
> say this, before anyone suggests and "Object" type, and we start fighting
> over MI)
> 
> * The library should offer Algortihms (in STL-speak): sorting, searching
> etc.

Again, this could be done using abstract types and generic parameters,
allowing a person to define the sorting, searching, etc. algorithm
for a particular instantiation of the container.

> * Standard iteration schemes over the various containers (I want both active
> and passive versions)
> 
> * Since I am thinking about using the library in education, I'd prefer to
> make isntantaion as easy as possible (possibly, by supplying
> pre-instantiated versiosn). I also prefer to hide the tagged nature of
> interface relationships from casual and first time users.
> 
> * Memory handling is important, but we don't want to have to do
> library-level instantaions beacuse of Controlled types.

Memory handling could be made somewhat transparent with the
careful use of storage pools.

Jim Rogers
Colorado Springs, Colorado USA

Re: Container reqs

[Darren New]

James Rogers wrote:
> This corresponds roughly with the approach taken by Java. It has
> containers that implement various kinds of lists and sets. They are
> organized by ADT properties and not by implementation details.

I would also suggest taking to heart lessons learned from the Eiffel
libraries. For example, it's much better to have the top of the stack
and the head of the queue both called "Item" than it is to have the top
of the stack called "Top" and the head of the queue called "Queue". Some
of the design decisions (especially naming conventions) made by the
Eiffel folks (B. Meyer, basically) are very good, making it easy to
learn a library.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
                   Who is this Dr. Ibid anyway, 
                  and how does he know so much?

Re: Container reqs

[Jeffrey Carter]

Ehud Lamm wrote:
> 
> Let's try to make a list of req the Ada community in general can agree on,
> and than see which of the existing libraries is closest and concentrate on
> that.

Can we in general agree on these? The following are PragmAda Software
Engineering's views on these suggestions:

> 
> (the following are some suggestions)
> 
> * It seems there is a general agreement  to distinguish bouned from
> unbounded versions. This can be attributed to a more general
> (non-functional) req: the library should be applicable for RT

OK

> 
> * I want a library organised around ADT properties (like "sequential
> access", "set interface" etc) and not around implementations (doubly linked
> lists).
> [I think we should think of the best Ada apporach for connecting interfaces
> and implementations. I explored many of the possibilities, like signature
> packages, class-wide operations etc., and I am still looking for the best
> method]

Not sure either way. Components are building blocks for problem level
abstractions. A list is sometimes appropriate; other times a queue may
be better. A developer should not have to dig around in the
implementation of various sequential-access containers to find one that
provides the required building block.

> 
> * From my experiens the item type is best accepted as a generic paramter (I
> say this, before anyone suggests and "Object" type, and we start fighting
> over MI)

Agree. The type should be Element so Item may be used as a parameter
name.

> 
> * The library should offer Algortihms (in STL-speak): sorting, searching
> etc.

OK

> 
> * Standard iteration schemes over the various containers (I want both active
> and passive versions)

Agreed. However, we see no advantage to having active iterators (if the
term has the same meaning to both of us). They merely require the
developer to duplicate code that is in the passive iterator.

> 
> * Since I am thinking about using the library in education, I'd prefer to
> make isntantaion as easy as possible (possibly, by supplying
> pre-instantiated versiosn). I also prefer to hide the tagged nature of
> interface relationships from casual and first time users.

Easy instantiation is appropriate for industrial-strength use as well.
However, ease of instantiation should not take precedence over
widespread utility. For example, it should be possible to create
structures of structures.

> 
> * Memory handling is important, but we don't want to have to do
> library-level instantaions beacuse of Controlled types.

Disagree. For industrial-strength use the precision of memory control
using controlled types outweighs the inconvenience of requiring
library-level instantiations.

It will be interesting to see if general agreement can be reached, given
the range of strong opinions on the subject. It may be as difficult as
agreeing on a programming style. While I do not agree completely with
the current Ada standard library, I would rather have it than no
standard library. I think it was designed by a fairly small team; if it
had required general agreement from the community I doubt if it would
exist.

-- 
Jeffrey Carter
PragmAda Software Engineering

Re: Container reqs

[Ted Dennison]

In article <9qctpn$lil$1@news.huji.ac.il>, Ehud Lamm says...
>
>Let's try to make a list of req the Ada community in general can agree on,
>and than see which of the existing libraries is closest and concentrate on
>that.

This sounds a whole lot like the initial charter of the HOLWG. I'm beginning to
be amused at how this is taking on the charactaristics of the early phases of
the history of Ada itself.

>(the following are some suggestions)
(ones I agree with totally left out)

>* It seems there is a general agreement  to distinguish bouned from
>unbounded versions. This can be attributed to a more general
>(non-functional) req: the library should be applicable for RT

I agree, but I'd take it a bit further. The "unbounded" containers should try to
not perform heap operations outside of adding/removing items. That would allow
their use in real-time apps that perform all initializations at startup time.
Any operations that potentially affect the heap should be commented as such.

>* Since I am thinking about using the library in education, I'd prefer to
>make isntantaion as easy as possible (possibly, by supplying
>pre-instantiated versiosn). I also prefer to hide the tagged nature of
>interface relationships from casual and first time users.

I would not be in favor of "dumbing down" the library so that beginners can pick
it up quickly. Making it easy to use properly should be a goal, but not the
primary overriding one (as it is with any facility). If it ends up being a
hierarchy of generics, that's fine. But in that case there should ideally be
some default instantiations (or default generic parameters), to take some of the
work out of it. I realise that an educator's view of this situation is going to
be directly reversed from mine, but there it is. Perhaps we can find something
that works for both goals.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Lutz Donnerhacke]

* Ehud Lamm wrote:
>* From my experiens the item type is best accepted as a generic paramter (I
>say this, before anyone suggests and "Object" type, and we start fighting
>over MI)

   type Item is (<>) tagged abstract limited private;

in order to build collections of tasks and more.

   type Item is exception;

*grin*

Bute seriosly it's necessary, that the same item occurs in several
collections at once. It must be possible to build stacks of lists and hold a
task element in a list and a hash simultaniously. Good luck.

>* The library should offer Algortihms (in STL-speak): sorting, searching
>  etc.

Of course ... provide algorithms with different size/time constraints.
_Prove_ them correctly and derivate the size/time constraints.
Do not assume special derivations for those algorithms, so allow algorithms
over native Ada types.

>* Standard iteration schemes over the various containers (I want both active
>and passive versions)

Keep them threadsafe and multiaccessed, i.e. allow the usage of active
Iterator to create further Iterators which in turn modify the structure.

>* Since I am thinking about using the library in education, I'd prefer to
>  make isntantaion as easy as possible (possibly, by supplying
>  pre-instantiated versiosn).

Exactly.

>  I also prefer to hide the tagged nature of interface relationships

Tagged nature?

Re: Container reqs

[Marin David Condic]

What would be wrong with starting with a simple set of data structures that
got 90% of the work done and then expanding the requirements as experience
demands?

For example: Why not produce a set of packages that supports a) a
homogeneous bi-directional list and b) a homogeneous map? I'll concede to
the need for a static & dynamic version of each. That would be what gets
called in the technical papers "A Good Start"(tm).

It probably should have a handful of sorting & searching algorithms for
arrays as well. (Anything else you want to sort & search on a regular
basis?)

My feeling is that if the scope were kept to something simple and functional
for a large majority of uses, it is more likely to get implemented and used.
Packages with more options, more parameters, different behaviors,
heterogeneous content, sufficient OO-ness, less used structures, etc. can
all be added later.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Lutz Donnerhacke" <lutz@iks-jena.de> wrote in message
news:slrn9slt9m.i2.lutz@taranis.iks-jena.de...
> * Ehud Lamm wrote:
> >* From my experiens the item type is best accepted as a generic paramter
(I
> >say this, before anyone suggests and "Object" type, and we start fighting
> >over MI)
>
>    type Item is (<>) tagged abstract limited private;
>
> in order to build collections of tasks and more.
>
>    type Item is exception;
>
> *grin*
>
> Bute seriosly it's necessary, that the same item occurs in several
> collections at once. It must be possible to build stacks of lists and hold
a
> task element in a list and a hash simultaniously. Good luck.
>
> >* The library should offer Algortihms (in STL-speak): sorting, searching
> >  etc.
>
> Of course ... provide algorithms with different size/time constraints.
> _Prove_ them correctly and derivate the size/time constraints.
> Do not assume special derivations for those algorithms, so allow
algorithms
> over native Ada types.
>
> >* Standard iteration schemes over the various containers (I want both
active
> >and passive versions)
>
> Keep them threadsafe and multiaccessed, i.e. allow the usage of active
> Iterator to create further Iterators which in turn modify the structure.
>
> >* Since I am thinking about using the library in education, I'd prefer to
> >  make isntantaion as easy as possible (possibly, by supplying
> >  pre-instantiated versiosn).
>
> Exactly.
>
> >  I also prefer to hide the tagged nature of interface relationships
>
> Tagged nature?

Re: Container reqs

[Darren New]

> I would not be in favor of "dumbing down" the library so that beginners can pick
> it up quickly. Making it easy to use properly should be a goal, but not the
> primary overriding one (as it is with any facility).

I think if it's complicated to use, excellent documentation will be
necessary. If it takes five instantiations to get a queue of maps
mapping strings to string, a good piece of documentation putting in the
"magic incantation" for the beginner will be extremely helpful. 

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
                   Who is this Dr. Ibid anyway, 
                  and how does he know so much?

Re: Container reqs

[Ehud Lamm]

Larry Kilgallen <Kilgallen@SpamCop.net> wrote in message
news:2Lfc16Vz$Jac@eisner.encompasserve.org...
> In article <9qctpn$lil$1@news.huji.ac.il>, "Ehud Lamm"
<mslamm@mscc.huji.ac.il> writes:
> I want a well documented set of components.
>


One advantage of naming the containers using the STL or Java library names
is to reduce some of this educational effort.
Most interfaces are well known, and we should have differences only when
they really matter.

Ehud

Re: Container reqs

[Ehud Lamm]

James Rogers <jimmaureenrogers@worldnet.att.net> wrote in message
news:3BCA173D.FA305845@worldnet.att.net...
>
>
> For the unbounded containers we may want versions allowing one to
> designate the storage pool used.

What's the best way to do this?
Does this mean that we would have to implement useful storage pools as part
of the effort, and if so - which?

> This corresponds roughly with the approach taken by Java. It has
> containers that implement various kinds of lists and sets. They are
> organized by ADT properties and not by implementation details.

Right. I don't really like Java, and detest its lack of generics, but the
overall structure of the Java containers seems pretty good.

> > * Memory handling is important, but we don't want to have to do
> > library-level instantaions beacuse of Controlled types.
>
> Memory handling could be made somewhat transparent with the
> careful use of storage pools.
>

How about some practical examples? I know the theory, but real life examples
would be interesting.

Ehud

Re: Container reqs

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:3nCy7.29644$ev2.35903@www.newsranger.com...

>
> I agree, but I'd take it a bit further. The "unbounded" containers should
try to
> not perform heap operations outside of adding/removing items. That would
allow
> their use in real-time apps that perform all initializations at startup
time.
> Any operations that potentially affect the heap should be commented as
such.

OK. Esp. the docuemntation part.
As long as unbounded heap allocations versions exist, I don't see any
problem with this.

>
> I would not be in favor of "dumbing down" the library so that beginners
can pick
> it up quickly. Making it easy to use properly should be a goal, but not
the
> primary overriding one (as it is with any facility). If it ends up being a
> hierarchy of generics, that's fine. But in that case there should ideally
be
> some default instantiations (or default generic parameters), to take some
of the
> work out of it. I realise that an educator's view of this situation is
going to
> be directly reversed from mine, but there it is. Perhaps we can find
something
> that works for both goals.

Right.
The way I see it, if it is impossible - or just very hard - to provide
default instantiaions, it is likely that the design is bad anyway.

Ehud

Re: Container reqs

[Ehud Lamm]

Lutz Donnerhacke <lutz@iks-jena.de> wrote in message
news:slrn9slt9m.i2.lutz@taranis.iks-jena.de...
> * Ehud Lamm wrote:
> >* From my experiens the item type is best accepted as a generic paramter
(I
> >say this, before anyone suggests and "Object" type, and we start fighting
> >over MI)
>
>    type Item is (<>) tagged abstract limited private;
>
> in order to build collections of tasks and more.
>
>    type Item is exception;
>
> *grin*
>
> Bute seriosly it's necessary, that the same item occurs in several
> collections at once. It must be possible to build stacks of lists and hold
a
> task element in a list and a hash simultaniously. Good luck.
>

So we need defaults. "take a private type and supply default named
operations like Assign"

But, I think we should decide on the semantics. If you can use by-reference
semantics, you can solv emany of these simply by instantiating with access
types. This can be problematic, but where applicable cansave us a  lot of
trouble..


> Of course ... provide algorithms with different size/time constraints.
> _Prove_ them correctly and derivate the size/time constraints.
> Do not assume special derivations for those algorithms, so allow
algorithms
> over native Ada types.

Ok.
<aside>Now when will we have speicalization of generics...</aside>

> Keep them threadsafe and multiaccessed, i.e. allow the usage of active
> Iterator to create further Iterators which in turn modify the structure.

I don't see any problem with this.

Re: Container reqs

[Ehud Lamm]

James Rogers <jimmaureenrogers@worldnet.att.net> wrote in message
news:3BCA173D.FA305845@worldnet.att.net...
> As far as an Ada approach for connecting interfaces, my first
> impulse would be to define a set of abstract types for each
> category (i.e. sets and lists), then inherit from those types to
> create the concrete and generic container classes.
>


Two options.
1. Make the parent package (where the abstract "interface" types are
decalred) generic.
2. Add the Element generic later on (but how are the interface operations
defined in this scheme?)

I like the first option. It is also quite nice that you can have child units
that are class-wide procedures (searching over a sequential type etc.), that
automatically get the Element.

Ehud

Re: Container reqs

[Lutz Donnerhacke]

* Ehud Lamm wrote:
>Lutz Donnerhacke <lutz@iks-jena.de> wrote in message
>> Bute seriosly it's necessary, that the same item occurs in several
>> collections at once. It must be possible to build stacks of lists and hold
>> a task element in a list and a hash simultaniously. Good luck.
>
>So we need defaults. "take a private type and supply default named
>operations like Assign"

No. You can't get Assign on most interesting types. There is none possible.
My lib was designed to deal with this problem, but it is a first study.

>But, I think we should decide on the semantics. If you can use
>by-reference semantics, you can solv emany of these simply by
>instantiating with access types. This can be problematic, but where
>applicable cansave us a lot of trouble..

Access types are inherently dangerous. Furthermore it's not necessary to use
access types.

>> Keep them threadsafe and multiaccessed, i.e. allow the usage of active
>> Iterator to create further Iterators which in turn modify the structure.
>
>I don't see any problem with this.

  declare
     i : Iterator'Class := Get_Iterator (collection);
     j : Iterator'Class := Get_Iterator (collection);
  begin
     while not Is_Finished (i) loop
        if something then j:=i; end if;
	if foobar then callmerecursivly_in_other_task; end if;
	if someother then Delete (j); end if;
	Advance (i);
     end loop;
  end;

Do this for hashes, btrees in a multitasking enviroment without deadlocks.

Re: Container reqs

[Ehud Lamm]

The problems you raise are not knew. Can you tell us about the solutions and
design you propose? (Specific to the issues at hand)

Ehud

Re: Container reqs

[Jean-Marc Bourguet]

Lutz Donnerhacke wrote:
> >* Standard iteration schemes over the various containers (I want both active
> >and passive versions)
> 
> Keep them threadsafe and multiaccessed, i.e. allow the usage of active
> Iterator to create further Iterators which in turn modify the structure.

I'm not for making a container "threadsafe"  to the point where
several tasks may modify the container without providing their
synchronisation.
In my experience
   * most containers are accessed only by one task
   * for those who are not, an explicit synchronisation is needed for
other
     purpose as the container is not the only part member of the
datastructure
     which has to be modified atomically.

-- Jean-Marc

Re: Container reqs

[Lutz Donnerhacke]

* Ehud Lamm wrote:
>The problems you raise are not knew. Can you tell us about the solutions and
>design you propose? (Specific to the issues at hand)

I do not propose anything. I did a study for my own education:
  ftp://ftp.iks-jena.de/pub/mitarb/lutz/ada/types/
 http://www.iks-jena.de/mitarb/lutz/ada/types/
 

Re: Container reqs

[Jean-Marc Bourguet]

Ehud Lamm wrote:
> 
> Let's try to make a list of req the Ada community in general can agree on,
> and than see which of the existing libraries is closest and concentrate on
> that.

* the library should have an organisation which make it extensible;

* for one ADT, it should be possible to choose between several
  implementations (say an hash table or a red black tree for the
  ADT dictionnary);

* if several ADT are using the same implementation (say a stack and a
  queue provided over singly linked lists), it should be possible to
  share the implementation package;

* I prefer the STL way over the Booch components one, ie all iterators
  provide the same interface but are not overwise related (the same
  would hold for the dictionnary packages). 

* the container types should be limited (one can always provides
  a clone function if needed).

* the contained types should not be limited (one can always provides
  a standard wrapper for limited types)

* the save iterators should be provided (that is iterator not silently
  invalidated like in the STL) and be the default if unsave iterators
  are also provided;

* I prefer using a single iterators instead of the double iterators
  of the STL;

A possible organisation which provides the first two points is to have
the packages providing abstract data type be childs of packages
providing
concrete data type. 

Yours,

-- Jean-Marc

Re: Container reqs

[Ehud Lamm]

Jean-Marc Bourguet <jbourguet@free.fr> wrote in message
news:3BCC01B1.18C18C98@free.fr...
> I'm not for making a container "threadsafe"  to the point where
> several tasks may modify the container without providing their
> synchronisation.
> In my experience
>    * most containers are accessed only by one task
>    * for those who are not, an explicit synchronisation is needed for
> other
>      purpose as the container is not the only part member of the
> datastructure
>      which has to be modified atomically.
>

I agree, that we should not attempt to  make everything protected.

Ehud

Re: Container reqs

[Ehud Lamm]

Jean-Marc Bourguet <jbourguet@free.fr> wrote in message
news:3BCC1BEE.99169F8B@free.fr...
> * the library should have an organisation which make it extensible;

Ok.

>
> * for one ADT, it should be possible to choose between several
>   implementations (say an hash table or a red black tree for the
>   ADT dictionnary);

Ok. Crucial.

>
> * if several ADT are using the same implementation (say a stack and a
>   queue provided over singly linked lists), it should be possible to
>   share the implementation package;

Ok.

>
> * the container types should be limited (one can always provides
>   a clone function if needed).

Right.

>
> * the contained types should not be limited (one can always provides
>   a standard wrapper for limited types)
>

I also like this design. But others seem to disagree (maps of maps of maps
of ...), and I understand their pov. We should try to find the best
solution/compromise on this important issue.

Ehud

Re: Container reqs

[Jean-Marc Bourguet]

Ehud Lamm wrote:
> 
> Jean-Marc Bourguet <jbourguet@free.fr> wrote in message
> news:3BCC1BEE.99169F8B@free.fr...
[...]
> >
> > * the container types should be limited (one can always provides
> >   a clone function if needed).
> 
> Right.
> 
> >
> > * the contained types should not be limited (one can always provides
> >   a standard wrapper for limited types)
> >
> 
> I also like this design. But others seem to disagree (maps of maps of maps
> of ...), and I understand their pov. We should try to find the best
> solution/compromise on this important issue.

Of these two requirements, the one which is the less important for me
est the first.  I'd far prefer to have the container non limited.

-- Jean-Marc

Re: Container reqs

[Ted Dennison]

In article <9qfgl7$7sb$1@news.huji.ac.il>, Ehud Lamm says...
>
>One advantage of naming the containers using the STL or Java library names
>is to reduce some of this educational effort.
>Most interfaces are well known, and we should have differences only when
>they really matter.

I'd argue that. They are only well-known to C++ and Java users. In fact, even
all C++ users aren't familiar with the STL. Many use the MFC instead, and many
many more use C++-- and have never seen the libaray. Certianly I'd think a lot
of your students would be unfamiliar with any language. Or perhaps things have
changed a great deal since I went to school.

I'd say it would be more important that things are simply intelligently named.
That's what's going to help reduce the educational effort the most. If that
happens to match up with some stuff in the STL, MFC, or Java library, so be it.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Ted Dennison]

In article <3BCA86C7.BB252751@acm.org>, Jeffrey Carter says...
>
>Ehud Lamm wrote:
>> * Memory handling is important, but we don't want to have to do
>> library-level instantaions beacuse of Controlled types.
>
>Disagree. For industrial-strength use the precision of memory control
>using controlled types outweighs the inconvenience of requiring
>library-level instantiations.

I don't think this one is worth arguing, because its probabaly unattainable
anyway. The problem isn't controlled types per se. The problem is that you can't
derive from a type at a lower level than the parent is declared. If you
implement your components with tagged types, you will almost certinaly bump into
this limitation whether controlled types are used or not.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Ted Dennison]

In article <9qhcd2$amt$1@news.huji.ac.il>, Ehud Lamm says...
>
>Jean-Marc Bourguet <jbourguet@free.fr> wrote in message
>news:3BCC01B1.18C18C98@free.fr...
>> I'm not for making a container "threadsafe"  to the point where
>> several tasks may modify the container without providing their
>> synchronisation.
>> In my experience
>>    * most containers are accessed only by one task
>>    * for those who are not, an explicit synchronisation is needed for
>> other
>>      purpose as the container is not the only part member of the
>> datastructure
>>      which has to be modified atomically.
>>
>
>I agree, that we should not attempt to  make everything protected.

I find myself having to implement small queues with controlled types a lot. :-(

This issue is why Booch also has tasksafe and non-tasksafe versions of
everything.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Vincent Marciante]

The Original Booch Components available at AdaPower
(along with the newer Ada95 version) seem to me
to meet most of these requirements.  What is the
main objection to the original ones?

Vincent Marciante


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9qhcj0$anv$1@news.huji.ac.il...
> Jean-Marc Bourguet <jbourguet@free.fr> wrote in message
> news:3BCC1BEE.99169F8B@free.fr...
> > * the library should have an organisation which make it extensible;
>
> Ok.
>
> >
> > * for one ADT, it should be possible to choose between several
> >   implementations (say an hash table or a red black tree for the
> >   ADT dictionnary);
>
> Ok. Crucial.
>
> >
> > * if several ADT are using the same implementation (say a stack and a
> >   queue provided over singly linked lists), it should be possible to
> >   share the implementation package;
>
> Ok.
>
> >
> > * the container types should be limited (one can always provides
> >   a clone function if needed).
>
> Right.
>
> >
> > * the contained types should not be limited (one can always provides
> >   a standard wrapper for limited types)
> >
>
> I also like this design. But others seem to disagree (maps of maps of maps
> of ...), and I understand their pov. We should try to find the best
> solution/compromise on this important issue.
>
> Ehud
>
>

Re: Container reqs

[Ted Dennison]

In article <3BCC1BEE.99169F8B@free.fr>, Jean-Marc Bourguet says...
>
>* the contained types should not be limited (one can always provides
>  a standard wrapper for limited types)

That almost goes without saying. The only way to allow limited types would be to
contain unchecked accesses to them, which would make for highly unsafe
containers.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> In article <3BCC1BEE.99169F8B@free.fr>, Jean-Marc Bourguet says...
> >
> >* the contained types should not be limited (one can always provides
> >  a standard wrapper for limited types)
> 
> That almost goes without saying. The only way to allow limited types would be to
> contain unchecked accesses to them, which would make for highly unsafe
> containers.

When I was searching for a container library for Ada, I remember having
seen
one which required a clone procedure to be provided, so that it was
possible
to have contained limited types.  It is not something I want for a
standardized
library.

A+

-- Jean-Marc

Re: Container reqs

[Pat Rogers]

"Vincent Marciante" <marciant_remove@li.net> wrote in message
news:4tYy7.9380$ym4.408459@iad-read.news.verio.net...
> The Original Booch Components available at AdaPower
> (along with the newer Ada95 version) seem to me
> to meet most of these requirements.  What is the
> main objection to the original ones?

Indeed.

Re: Container reqs

[Jeffrey Carter]

Jean-Marc Bourguet wrote:
> 
> I'm not for making a container "threadsafe"  to the point where
> several tasks may modify the container without providing their
> synchronisation.
> In my experience
>    * most containers are accessed only by one task
>    * for those who are not, an explicit synchronisation is needed for
> other
>      purpose as the container is not the only part member of the
> datastructure
>      which has to be modified atomically.

This is an interesting assertion, considering that a protected queue is
a useful and common form of intertask communication.

-- 
Jeffrey Carter

Re: Container reqs

[Stephen Leake]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> James Rogers <jimmaureenrogers@worldnet.att.net> wrote in message
> news:3BCA173D.FA305845@worldnet.att.net...
> >
> > <snip> 
> > Memory handling could be made somewhat transparent with the
> > careful use of storage pools.
> >
> 
> How about some practical examples? I know the theory, but real life examples
> would be interesting.

My Ada library provides a storage pool parameter. See
http://users.erols.com/leakstan/Stephe/Ada/sal.html 

-- 
-- Stephe

Re: Container reqs

[Stephen Leake]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

> What would be wrong with starting with a simple set of data structures that
> got 90% of the work done and then expanding the requirements as experience
> demands?
> 
> For example: Why not produce a set of packages that supports a) a
> homogeneous bi-directional list and b) a homogeneous map? I'll concede to
> the need for a static & dynamic version of each. That would be what gets
> called in the technical papers "A Good Start"(tm).

I agree. My set of components does not currently provide a "homogenous
map". At least, I don't think it does - I'm not sure you define that
the same way I do. 

So, how about you download my components, add a homogeneous map, and
then somebody else can add what they want.

I know, someone will chime in with "Why start with Stephe's instead of
the Booch Components?". Well, that is exactly the question we need to
be discussing now.

Several people have put together what they consider "A Good Start".
The question is, is there enough consensus for any one of these to
convince the rest of us to jump on board, and integrate our stuff into
it (instead of the other way around).

> It probably should have a handful of sorting & searching algorithms
> for arrays as well. (Anything else you want to sort & search on a
> regular basis?)
> 
> My feeling is that if the scope were kept to something simple and functional
> for a large majority of uses, it is more likely to get implemented and used.
> Packages with more options, more parameters, different behaviors,
> heterogeneous content, sufficient OO-ness, less used structures, etc. can
> all be added later.

Perhaps you could vote on the several that are out there, indicating
which one most closely fits _your_ needs. Then everyone else could do
the same. Some data would be useful here.

-- 
-- Stephe

Re: Container reqs

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> I find myself having to implement small queues with controlled types a lot. :-(
> 
> This issue is why Booch also has tasksafe and non-tasksafe versions of
> everything.

Yep, yet another reason why an Ada library will be more complex than
the not-so-equivalent C++ library.

-- 
-- Stephe

Re: Container reqs

[Ted Dennison]

In article <3BCC6CB7.20BAA30D@boeing.com>, Jeffrey Carter says...
>
>Jean-Marc Bourguet wrote:
>> 
>> I'm not for making a container "threadsafe"  to the point where
>> several tasks may modify the container without providing their
>> synchronisation.
..
>This is an interesting assertion, considering that a protected queue is
>a useful and common form of intertask communication.

More like "nessecary". Its one of the only safe ways to gender-bender two
"server" tasks together. You could put the queue in one of the servers, then
create a new client task to do nothing but ask for queue entries and pass them
to the other server. However, that creates servers that have two completely
different services (generally a bad idea), adds a task/thread to the system, and
is just all-around ugly.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Stephen Leake]

Jeffrey Carter <jeffrey.carter@boeing.com> writes:

> Jean-Marc Bourguet wrote:
> > 
> > I'm not for making a container "threadsafe"  to the point where
> > several tasks may modify the container without providing their
> > synchronisation.
> > In my experience
> >    * most containers are accessed only by one task
> >    * for those who are not, an explicit synchronisation is needed for
> > other
> >      purpose as the container is not the only part member of the
> > datastructure
> >      which has to be modified atomically.
> 
> This is an interesting assertion, considering that a protected queue is
> a useful and common form of intertask communication.

Ok, let me play mediator. 

Jean-Marc is saying "In my (perhaps somewhat limited) experience, most
data structures that need to be protected from multi-tasking are
actually part of a larger structure".

And Jeffrey is saying "In my (perhaps somewhat limited) experience, a
simple protected queue is often useful".

No conflict here, just different experience. Apparently, the library
should have both task safe and non-task safe components, as the Booch
library has (and my library does not; my experience matches
Jean-Marc's, so far).

We hope to get the union of all useful components, not the
intersection of components _everyone_ finds useful, which would be the
null set.

-- 
-- Stephe

Re: Container reqs

[Stephen Leake]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> >
> > * the container types should be limited (one can always provides
> >   a clone function if needed).
> 
> Right.
> 
> >
> > * the contained types should not be limited (one can always provides
> >   a standard wrapper for limited types)
> >
> 
> I also like this design. But others seem to disagree (maps of maps of maps
> of ...), and I understand their pov. We should try to find the best
> solution/compromise on this important issue.

It is possible to write generic packages than can accept item types
that are either limited or non-limited. See
http://users.erols.com/leakstan/Stephe/Ada/Sal_Packages/index.htm, 
package sal-gen-lists-double.ads for example. Here's the critical
part:

generic
   type Item_Type (<>) is limited private;
   type Item_Node_Type is private;
   with function To_Item_Node (Item : in Item_Type) return Item_Node_Type;
   with procedure Free_Item (Item : in out Item_Node_Type);
-- If Item_Type is definite non-limited, Item_Node_Type should just be
-- Item_Type. Then To_Item_Node should just return Item, and Free_Item
-- should be null (and both should be inlined). See
-- SAL.Aux.Definite_Private_Items.
--
-- If Item_Type is indefinite, Item_Node_Type should be 'access
-- Item_Type'. Then To_Item_Node should allocate Item and return a
-- pointer to it, and Free_Item should be Unchecked_Deallocation. See
-- SAL.Aux.Indefinite_Private_Items.
--
-- To create a list of limited objects (say of type Limited_Type),
-- Item_Type can be a non-limited type holding the parameters needed to
-- create an object (non-limited to allow the user to create aggregates
-- of creation parameters), and Item_Node_Type can be 'access
-- Limited_Type'. Then To_Item_Node must allocate an object of type
-- Limited_Type and initialize it using the parameters in Item_Type. See
-- SAL.Aux.Indefinite_Limited_Items.
--
-- Other usages may be possible.

-- 
-- Stephe

Re: Container reqs

[Darren New]

Ehud Lamm wrote:
> One advantage of naming the containers using the STL or Java library names
> is to reduce some of this educational effort.

Which Java names? Vector/Hash/Etc? Or the Java 1.2 names, like List and
Map?

(Note: This is a rhetorical question, pointout out the futility of
trying to match someone else's galloping standard.)

If anything, I'd use the Eiffel library notations. Indeed, Eiffel was
almost created in order to write data structure libraries in, to a large
extent.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
                   Who is this Dr. Ibid anyway, 
                  and how does he know so much?

Re: Container reqs

[Marin David Condic]

"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:ug08jtoa9.fsf@gsfc.nasa.gov...
> "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:
> > For example: Why not produce a set of packages that supports a) a
> > homogeneous bi-directional list and b) a homogeneous map? I'll concede
to
> > the need for a static & dynamic version of each. That would be what gets
> > called in the technical papers "A Good Start"(tm).
>
> I agree. My set of components does not currently provide a "homogenous
> map". At least, I don't think it does - I'm not sure you define that
> the same way I do.
>
By a "homogenous map" I mean something that roughly approximates an indexed
file. (See the MFC for what they call a "Map") Basically, there is a need
for some kind of in-memory data structure that might hold, for example,
employee names as a string associated to employee records such that
retrieval out of the map is based on the employee name.

Homogeneous in the sense that the bulk of standard issue applications for a
Map need not hold some kind of heterogenous data based on some "root
object". No need to have pointers to some 'class - although that might be
"Nice To Have"(tm). (I'd avoid making it a requirement - but if you support
it, cool!)


> So, how about you download my components, add a homogeneous map, and
> then somebody else can add what they want.
>
> I know, someone will chime in with "Why start with Stephe's instead of
> the Booch Components?". Well, that is exactly the question we need to
> be discussing now.
>
I'm willing to start from anywhere provided there is some modicum of
concensus that "anywhere" is the right thing to adopt. (I didn't much like
the Ada.Strings... packages because they weren't what I would have built,
but I dropped my own string tools when the basic services were available in
a standard package. Better to be in-sync and consistent even if it isn't
what I might view as the ultimate answer.)

As for consensus, I reiterate that the key players will be one or more of
the compiler vendors. If you're willing to have your components distributed
by the vendors and they're willing to accept/distribute some version of
them, I'd get behind it and be willing to help out. If you really want to
get your stuff adopted as the "standard" you might consider trying to enlist
a vendor or two. This is one of those "Time To Market" thingies wherein the
first guy to get adopted and out there wins the debate. What everyone else
thinks won't matter so long as your code is at minimum "sufficient".


> Several people have put together what they consider "A Good Start".
> The question is, is there enough consensus for any one of these to
> convince the rest of us to jump on board, and integrate our stuff into
> it (instead of the other way around).
>

I don't think you'll ever get a consensus debating it here. Get a vendor to
back it and it will likely win. I think it was Charles Colson of the Nixon
Whitehouse who once said "When you've got them by the balls, their hearts
and minds will follow..." Whatever gets distributed widely and integrated
into a number of projects will end up becoming too hard to resist.


>
> Perhaps you could vote on the several that are out there, indicating
> which one most closely fits _your_ needs. Then everyone else could do
> the same. Some data would be useful here.
>
My preferences aren't that strong provided there is some minimal, simple way
to get a handful of the most commonly used structures. (That, and having it
under a license that isn't infectious.) Mostly, I want to use whatever is
going to have some acceptance by the vendors.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

Re: Container reqs

[Marin David Condic]

A wise proposition.

If you wish to keep the realtime/embedded crowd happy, you need to have
task-safe versions. You also need to have static allocation versions. Nice
To Have are versions that may do dynamic allocation, but don't impose that
for read access so you can load them up at startup and be sure they won't
kill you after that.

For non-realtime/embedded, non-multitasking, plain vanilla applications you
can have non-task-safe and dynamic implementations.

That leaves us with four versions of any given structure. Any other
variants? Like Object Oriented versus Generic Instantiated implementations?
That would mean 8 variants of every structure. (Starts making it harder to
find or make a library that fits.)

If you presume a need for Lists and Maps, that means 8 packages that need to
be implemented to constitute A Good Start. If those already exist and some
consensus emerges to adopt some existing thing, great. If not, 8 packages
could probably be built from nothing in a reasonable time.

Is it possible that we could have a consensus that what I have outlined here
might work for a *minimal* set of requirements? We can presume that
fancy-schmancy optional data structrues are allowed to exist or be
implemented - they just need not be *required* for adoption criteria. I
think getting just this far would mean that there is a usable component
library that probably exceeds the capabilities of things available as
"standard" for other languages. (IOW, If compilers shipped with
*just*this*much*more* they are likely exceeding what compilers for other
languages give you for data structures.)

We could argue about what else to add to it *after* this much got adopted.
:-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:u3d4jtnq6.fsf@gsfc.nasa.gov...
> No conflict here, just different experience. Apparently, the library
> should have both task safe and non-task safe components, as the Booch
> library has (and my library does not; my experience matches
> Jean-Marc's, so far).
>
> We hope to get the union of all useful components, not the
> intersection of components _everyone_ finds useful, which would be the
> null set.

Re: Container reqs

[Larry Kilgallen]

In article <9qi2c8$gpb$1@nh.pace.co.uk>, "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

> If you wish to keep the realtime/embedded crowd happy, you need to have
> task-safe versions.

I think that is a rather narrow subset of the audience for task-safe
versions.

Re: Container reqs

[Marin David Condic]

True, but it doesn't really negate the statement, eh? :-)

I think I mentioned further down something about
multi-tasking/non-multi-tasking and I'll readily concede that there are
workstation/PC/server/mainframe apps that need task safety because they use
tasks.

Non-task-safety is also of interest from the perspective of performance and
might also be of serious interest to the realtime/embedded crowd for that
reason. Ironically, the non-realtime/embedded crowd might not care. Whatever
overhead might be imposed by task safety might be small enough to go
unnoticed in apps that aren't realtime.

Curiously, if the library were to exist in some kind of compiled and
C-callable form, it might even be of interest to the non-Ada crowd if it
provided task-safe operations. We're not the only ones who build
multi-threaded apps, but we'd be one of the few that had data structures
that were *safe* for multithreaded apps! (Could this be one of the big
reasons I can't keep things like Netscape from crashing? :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Larry Kilgallen" <Kilgallen@SpamCop.net> wrote in message
news:UXf5fGM0Vx5L@eisner.encompasserve.org...
> In article <9qi2c8$gpb$1@nh.pace.co.uk>, "Marin David Condic"
<dont.bother.mcondic.auntie.spam@[acm.org> writes:
>
> > If you wish to keep the realtime/embedded crowd happy, you need to have
> > task-safe versions.
>
> I think that is a rather narrow subset of the audience for task-safe
> versions.

Re: Container reqs

[Robert*]

In article <u3d4jtnq6.fsf@gsfc.nasa.gov>, Stephen says...
>
 
>
>No conflict here, just different experience. Apparently, the library
>should have both task safe and non-task safe components, as the Booch
>library has (and my library does not; my experience matches
>Jean-Marc's, so far).
>
 
In java, you can create a synchronized version of any java standard 
collection . Same collection name, same interface, etc...

see

http://developer.java.sun.com/developer/qow/archive/60/index.html

This is from the above

"The synchronization wrappers add automatic synchronization (thread-safety) 
to an arbitrary collection. There is one static factory method for 
each of the six core collection interfaces:

 public static Collection synchronizedCollection(
                                      Collection c); 
 public static Set synchronizedSet(Set s); 
 public static List synchronizedList(List list); 
 public static Map synchronizedMap(Map m); 
 public static SortedSet synchronizedSortedSet(
                                       SortedSet s); 
 public static SortedMap synchronizedSortedMap(
                                       SortedMap m); 


Each of these methods returns a synchronized (thread-safe) Collection 
backed by the specified collection."


If you like to see a list of java collection, see

http://java.sun.com/j2se/1.3/docs/guide/collections/reference.html

Re: Container reqs

[Simon Wright]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> James Rogers <jimmaureenrogers@worldnet.att.net> wrote in message
> news:3BCA173D.FA305845@worldnet.att.net...
> >
> >
> > For the unbounded containers we may want versions allowing one to
> > designate the storage pool used.
> 
> What's the best way to do this?

The BCs now say eg

  with System.Storage_Pools;

  generic
     Storage : in out System.Storage_Pools.Root_Storage_Pool'Class;
  package BC.Containers.Collections.Unbounded is

> Does this mean that we would have to implement useful storage pools as part
> of the effort, and if so - which?

and it seems you can get away with

  with System.Storage_Pools;

  package BC.Support.Standard_Storage is

     type T is access Integer; -- arbitrary subtype

     Pool : System.Storage_Pools.Root_Storage_Pool'Class renames T'Storage_Pool;

  end BC.Support.Standard_Storage;

(ObjectAda & GNAT)


It would be Quite Nice if there were standardised access to the
system's default Storage_Pool, though I can see that if different
types had to be allocated from different pools this might be hard.

Re: Container reqs

[Simon Wright]

Ted Dennison<dennison@telepath.com> writes:

> In article <9qhcd2$amt$1@news.huji.ac.il>, Ehud Lamm says...
> >
> >Jean-Marc Bourguet <jbourguet@free.fr> wrote in message
> >news:3BCC01B1.18C18C98@free.fr...
> >> I'm not for making a container "threadsafe"  to the point where
> >> several tasks may modify the container without providing their
> >> synchronisation.
> >> In my experience
> >>    * most containers are accessed only by one task
> >>    * for those who are not, an explicit synchronisation is needed for
> >> other
> >>      purpose as the container is not the only part member of the
> >> datastructure
> >>      which has to be modified atomically.
> >>
> >
> >I agree, that we should not attempt to  make everything protected.
> 
> I find myself having to implement small queues with controlled types a lot. :-(
> 
> This issue is why Booch also has tasksafe and non-tasksafe versions of
> everything.

This is still an open area. You can easily create Guarded versions of
things (well, those that don't have structural sharing), where the
user gets to Seize and Release. But Synchronized versions (where the
locking is internal) are more work, and also semantically challenging
for Iterators I think.

Re: Container reqs

[Simon Wright]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> The way I see it, if it is impossible - or just very hard - to
> provide default instantiaions, it is likely that the design is bad
> anyway.

I don't see how you can provide containers that can contain anything
at all in Ada.

You could have containers that were capable of handling anything in
Containable_Object'Class, I guess (but you'd need access types, 'Class
is unconstrained).

Re: Container reqs

[Jean-Marc Bourguet]

Jeffrey Carter wrote:
> 
> Jean-Marc Bourguet wrote:
> >
> > I'm not for making a container "threadsafe"  to the point where
> > several tasks may modify the container without providing their
> > synchronisation.
> > In my experience
> >    * most containers are accessed only by one task
> >    * for those who are not, an explicit synchronisation is needed for
> > other
> >      purpose as the container is not the only part member of the
> > datastructure
> >      which has to be modified atomically.
> 
> This is an interesting assertion, considering that a protected queue is
> a useful and common form of intertask communication.

I was probably not clear enough.  Tasks savety is not something binary,
it's something for which there is at least five levels.

0) the whole library can't be used by two tasks without explicit
synchronisation because there is use of some features (global variables,
COW datastructure build without considering tasking, ...) which make 
it totally unfit for that use.

1) you can work savely on different objects in different tasks but not
access the same object in different tasks without synchronisation.

2) you can savely have read access to one object from different tasks
but modifying accesses must be protected explicitly from other accesses.

3) there is a limited set of modifying accesses which can be issued
simultaneously from different tasks.

4) whatever you do -- trying to modify the datastructure simultaneously
via iterators from different tasks -- is save.

From my experience,
  * level 4 is useless because you still need synchronisation
    for other reasons when its whole generality is needed.  Achieving it
    has a major performance impact (every operation has to be
protected).

  * level 3 is usefull but the set of modifying access which make sense
    depend very much on the application.  Your example is probably the
    only widely applicable one. Achieving this level has a important
    performance impact.

  * level 2 can be achieved with a small performance impact: there is no
    need for explicit synchronisation, one need simply to pay attention
    to the datastructure used and the way it is accessed.

I think that one should aim for level 2 because:
   - this simplify the library (no need to have tasks save and tasks
unsave
     version)
   - aiming level 3 whould imply major discussion about the set of
operations
     needed with the risks of compromising to level 4.
   - I whould probably still encapsulate the ADT in an other
type/package which
     export only the operations needed for the application with names
related
     to the application.

If one want to provide level 3, I'm for having separate tasks save and
tasks
unsave version and that the "task unsave" still provide level 2
saveness.

Yours,

-- Jean-Marc

Re: Container reqs

[John English]

Ted Dennison wrote:
> 
> In article <3BCA86C7.BB252751@acm.org>, Jeffrey Carter says...
> >
> >Ehud Lamm wrote:
> >> * Memory handling is important, but we don't want to have to do
> >> library-level instantaions beacuse of Controlled types.
> >
> >Disagree. For industrial-strength use the precision of memory control
> >using controlled types outweighs the inconvenience of requiring
> >library-level instantiations.
> 
> I don't think this one is worth arguing, because its probabaly unattainable
> anyway. The problem isn't controlled types per se. The problem is that you can't
> derive from a type at a lower level than the parent is declared. If you
> implement your components with tagged types, you will almost certinaly bump into
> this limitation whether controlled types are used or not.

Hmm, the STL doesn't use inheritance, it's all done with templates.
Tagged types probably aren't needed at all (other than as derivations
of controlled). And you can use tricks to get around the library-level
problem, e.g. have a library-level parent package which defines a private
controlled type and generic children which make use of those controlled
objects as components in other composite types... 

Maybe the STL approach, with an optional "allocator" parameter, is the
way to go for memory allocation issues?

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Container reqs

[Ted Dennison]

In article <3BCD7C50.647ADBD0@brighton.ac.uk>, John English says...
>
>of controlled). And you can use tricks to get around the library-level
>problem, e.g. have a library-level parent package which defines a private
>controlled type and generic children which make use of those controlled
>objects as components in other composite types... 

This sounds a bit like the trick Dr. Dewar keeps referring to. I know this is
off the thread's topic, but could you give a specific example of how this works?
I could never see how one could use a controlled-type record field to manage
anything in its parent object, about which it theoreticly knows nothing.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Ted Dennison]

In article <3BCD2EC3.3B3C4498@free.fr>, Jean-Marc Bourguet says...
>
>4) whatever you do -- trying to modify the datastructure simultaneously
>via iterators from different tasks -- is save.
>
>From my experience,
>  * level 4 is useless because you still need synchronisation
>    for other reasons when its whole generality is needed.  Achieving it
>    has a major performance impact (every operation has to be
>protected).

But your "level 4" is exactly what is needed for the "gender-bender"
server-to-server queue we were referring to. This is a *quite* common need. Its
come up in every multitasking Ada app I've ever written of at least moderate
complexity. Your assertion is quite wrong too. When used as I described, it is
the *only* communication the two server tasks need. In fact, it is the only safe
communication method they can have. 

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> In article <3BCD2EC3.3B3C4498@free.fr>, Jean-Marc Bourguet says...
> >
> >4) whatever you do -- trying to modify the datastructure simultaneously
> >via iterators from different tasks -- is save.
> >
> >From my experience,
> >  * level 4 is useless because you still need synchronisation
> >    for other reasons when its whole generality is needed.  Achieving it
> >    has a major performance impact (every operation has to be
> >protected).
> 
> But your "level 4" is exactly what is needed for the "gender-bender"
> server-to-server queue we were referring to. This is a *quite* common need. Its
> come up in every multitasking Ada app I've ever written of at least moderate
> complexity. Your assertion is quite wrong too. When used as I described, it is
> the *only* communication the two server tasks need. In fact, it is the only safe
> communication method they can have.

There is a possibility I don't understand what you are refering to -- so
if you
think it is the case, please explain it more thorougly.

For a queue defined by three operations (is_empty, enqueue, dequeue) out
of
which two are modifying, the difference between level 3 and level 4 is
so
small that it has only a signification if you are also looking at the
other
containers.

I'm arguing that level 4 (where it is substantially different than level
3)
is not usefull and that level 3 is usefull but quite application
specific
so one is better providing it on a tailored way in each application
(I don't remember having ever needed concurrent modifications via
iterators
for exemple which is the requirement I reacted to initially.).

Yours,

-- Jean-Marc

Re: Container reqs

[Ehud Lamm]

John English <je@brighton.ac.uk> wrote in message
news:3BCD7C50.647ADBD0@brighton.ac.uk...
> Hmm, the STL doesn't use inheritance, it's all done with templates.
> Tagged types probably aren't needed at all (other than as derivations
> of controlled). And you can use tricks to get around the library-level
> problem, e.g. have a library-level parent package which defines a private
> controlled type and generic children which make use of those controlled
> objects as components in other composite types...
>

Don't you like using inheritance as for interface reuse?
I like the ability to have all sequential structures support the same
iteration mechanisms. I like the ability to write class-wide opertations
("Exists", "For_All", "Filter" etc.)

Ehud

Re: Container reqs

[Ted Dennison]

In article <3BCD91D9.C77668AA@free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison wrote:
>> 
>> But your "level 4" is exactly what is needed for the "gender-bender"
>> server-to-server queue we were referring to. This is a *quite* common need. 
>> Its come up in every multitasking Ada app I've ever written of at least 
>> moderate complexity. Your assertion is quite wrong too. When used as I 
>> described, it is the *only* communication the two server tasks need. In 
>> fact, it is the only safe communication method they can have.
>
>There is a possibility I don't understand what you are refering to -- so
>if you think it is the case, please explain it more thorougly.

The way this has to work is that server task 1 enqueues events/info/whatever and
server task 2 goes and dequeues that stuff whenever it finds some there. There
clearly may be times when server task 1 is enqueing while server task 2 is
dequeueing from the same queue.

You can't just have them rendezvous, because you would then be using one of them
as both a client and a server, which can cause real problems. In particular, you
could have the hybrid client/server task blocking for long periods (not
servicing requests) while the other server is busy servicing its other requests.
This also makes problems with priority inversions really sticky. At best, you
are needlessly slowing your system down due to unneeded client waiting. You
might release a client as soon as the server receives a request, but if the
server has to wait for another server, any new clients will be waiting too). If
you have multiple hybrids you could even run into deadlock situations.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> In article <3BCD91D9.C77668AA@free.fr>, Jean-Marc Bourguet says...
> >
> >Ted Dennison wrote:
> >>
> >> But your "level 4" is exactly what is needed for the "gender-bender"
> >> server-to-server queue we were referring to. This is a *quite* common need.
> >> Its come up in every multitasking Ada app I've ever written of at least
> >> moderate complexity. Your assertion is quite wrong too. When used as I
> >> described, it is the *only* communication the two server tasks need. In
> >> fact, it is the only safe communication method they can have.
> >
> >There is a possibility I don't understand what you are refering to -- so
> >if you think it is the case, please explain it more thorougly.
> 
> The way this has to work is that server task 1 enqueues events/info/whatever and
> server task 2 goes and dequeues that stuff whenever it finds some there. There
> clearly may be times when server task 1 is enqueing while server task 2 is
> dequeueing from the same queue.
[...]

That's what I had understood.  I put this in level 3 (but as I wrote in
my
previous post, for a queue the difference between level 3 and level 4 is
tiny).

But I don't think it is a good argument in favor of working hard and
complexifying the library in order to be able to modify a tree from
several 
tasks using shared iterators.

-- Jean-Marc

Re: Container reqs

[Ted Dennison]

In article <3BCDB29B.EBD01D8C@free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison wrote:
>> The way this has to work is that server task 1 enqueues events/info/whatever 
>> and server task 2 goes and dequeues that stuff whenever it finds some there. 

>But I don't think it is a good argument in favor of working hard and
>complexifying the library in order to be able to modify a tree from
>several tasks using shared iterators.

Well, as long as some kind of task-safe queue/stack is available, that's
probably fair enough.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:QEiz7.32911$ev2.39789@www.newsranger.com...
>
> Well, as long as some kind of task-safe queue/stack is available, that's
> probably fair enough.
>

I see two things that are of interest:
1. Synchronisation Abstractions (like barriers, blackboards etc.). These are
interesting, but are more involved than simply being protected versions of
containers. Burns's book has interesting stuff (I think someone (Pascal?)
has it online somewhere).
These are important, but are not in the mainstream for the container
library. They should be considered seperately.

2. Protected versions of regular containers.
I am not sure how crucial this is to anyone.
I can survive without this being part of the library.

(Notice that it is possible to write wrappers that can take something that
supports a give  interface, and create a protected version. This is nice,
and can be done seperately. Manage complexity!)

Ehud

Re: Container reqs

[Jeffrey Carter]

Jean-Marc Bourguet wrote:
> 
> I was probably not clear enough.  Tasks savety is not something binary,
> it's something for which there is at least five levels.
> 
> 0) the whole library can't be used by two tasks without explicit
> synchronisation because there is use of some features (global variables,
> COW datastructure build without considering tasking, ...) which make
> it totally unfit for that use.
> 
> 1) you can work savely on different objects in different tasks but not
> access the same object in different tasks without synchronisation.
> 
> 2) you can savely have read access to one object from different tasks
> but modifying accesses must be protected explicitly from other accesses.
> 
> 3) there is a limited set of modifying accesses which can be issued
> simultaneously from different tasks.
> 
> 4) whatever you do -- trying to modify the datastructure simultaneously
> via iterators from different tasks -- is save.
> 
> From my experience,
>   * level 4 is useless because you still need synchronisation
>     for other reasons when its whole generality is needed.  Achieving it
>     has a major performance impact (every operation has to be
> protected).

Your level 0 is clearly a faulty design. The protected data structures
in the PragmAda Reusable Components achieve level 4, no additional
synchronization is needed, and the performance has yet to be found
unsatisfactory. Even the unprotected structures achieve level 2.

FYI, the word you should be using is "safe".

-- 
Jeffrey Carter

Re: Container reqs

[Lutz Donnerhacke]

* Jean-Marc Bourguet wrote:
>But I don't think it is a good argument in favor of working hard and
>complexifying the library in order to be able to modify a tree from
>several tasks using shared iterators.

Multiple tasks modifying the same data structure simultanously is a common
requirement for any larger application.

Re: Container reqs

[Jean-Marc Bourguet]

Jeffrey Carter wrote:

> Your level 0 is clearly a faulty design.

For a general purpose library in Ada, I agree.   But people are often
surprised
that using reference counts, copy on write data structure, sharing
special
values, ... leads to this result.  There are some non threadsafe
versions of
the C++ STL which are at this level.

> FYI, the word you should be using is "safe".

Thanks.

-- Jean-Marc

Re: Container reqs

[Jean-Marc Bourguet]

Lutz Donnerhacke wrote:
> 
> * Jean-Marc Bourguet wrote:
> >But I don't think it is a good argument in favor of working hard and
> >complexifying the library in order to be able to modify a tree from
> >several tasks using shared iterators.
> 
> Multiple tasks modifying the same data structure simultanously is a common
> requirement for any larger application.

Yes  but in my experience
   * the data structure is often more complex than a simple container,
     so you need synchronization from outside the container and you need
     to encapsulate the whole data structure to provide the wanted
     interface 
   * the set of modifying operations allowed is often restricted so
     you need encapsulate the data structure not to expose
implementation
     details.

My conclusion was that it is not needed to complexify the library to
provide a synchronization which will often be also provided from the
user.
The only exception I've met where none of these two points did hold is a
queue.

-- Jean-Marc

Re: Container reqs

[John English]

Ted Dennison wrote:
> 
> In article <3BCD7C50.647ADBD0@brighton.ac.uk>, John English says...
> >
> >of controlled). And you can use tricks to get around the library-level
> >problem, e.g. have a library-level parent package which defines a private
> >controlled type and generic children which make use of those controlled
> >objects as components in other composite types...
> 
> This sounds a bit like the trick Dr. Dewar keeps referring to. I know this is
> off the thread's topic, but could you give a specific example of how this works?

I do something like this in JEWL. There's a reference-counted tagged
type in package JEWL (non-generic parent):

  type Reference_Counted_Type is tagged limited
    record
      Count : Natural := 1;
    end record;

  procedure Cleanup (Object : in out Reference_Counted_Type);

  type Reference_Counted_Ptr is access all Reference_Counted_Type'Class;

  type Controlled_Type is new Ada.Finalization.Controlled with
    record
      Pointer : Reference_Counted_Ptr;
    end record;

  procedure Finalize (Object : in out Controlled_Type);
  procedure Adjust   (Object : in out Controlled_Type);

and then JEWL.Windows (which is generic) uses this Controlled_Type as
a component (actually *the* component) in all the window types, so that
all windows are implemented as pointers to reference-counted types.
The actual object that a particular type of window points to is one
of a variety of possible derivations which are defined in a private
child and produced by constructor (factory) functions.

> I could never see how one could use a controlled-type record field to manage
> anything in its parent object, about which it theoreticly knows nothing.

You can also use access discriminants to get at the containing record,
but I didn't need to in this case... This is presumably what you're
after? There's a description of the technique near the end of section
4.6 in part 2 of the Rationale:
  http://burks.bton.ac.uk/burks/language/ada/rat95/rat2_4.htm#6

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Container reqs

[Ted Dennison]

In article <3BCEF4B8.B1AC6965@brighton.ac.uk>, John English says...
>
>I do something like this in JEWL. There's a reference-counted tagged
>type in package JEWL (non-generic parent):
>
>  type Reference_Counted_Type is tagged limited
>    record
>      Count : Natural := 1;
>    end record;
>
>  procedure Cleanup (Object : in out Reference_Counted_Type);
>
>  type Reference_Counted_Ptr is access all Reference_Counted_Type'Class;
>
>  type Controlled_Type is new Ada.Finalization.Controlled with
>    record
>      Pointer : Reference_Counted_Ptr;
>    end record;
>
>  procedure Finalize (Object : in out Controlled_Type);
>  procedure Adjust   (Object : in out Controlled_Type);
>
>and then JEWL.Windows (which is generic) uses this Controlled_Type as
>a component (actually *the* component) in all the window types, so that
>all windows are implemented as pointers to reference-counted types.
>The actual object that a particular type of window points to is one
>of a variety of possible derivations which are defined in a private
>child and produced by constructor (factory) functions.

I still don't see how that allows you to declare something in the generic that
can be managed by the controlled object. You can manage the
"reference_counted_type", but if I declare some new type that needs to be
managed in my generic, the only way to get Controlled_Type to manage it is to
derive it from "reference_counted_type". If I do that, I'm back to the situation
where my generic can only be instantiated at the library level.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Jeffrey Carter]

Jean-Marc Bourguet wrote:
> 
> Lutz Donnerhacke wrote:
> >
> > * Jean-Marc Bourguet wrote:
> > >But I don't think it is a good argument in favor of working hard and
> > >complexifying the library in order to be able to modify a tree from
> > >several tasks using shared iterators.
> >
> > Multiple tasks modifying the same data structure simultanously is a common
> > requirement for any larger application.

Modifying an ordered structure such as a tree while iterating seems like
a recipe for disaster, even from a single thread. By "ordered" I mean a
structure where the position of an Element within the structure is
determined by the value of the Element. What is the next Element in the
structure if the current Element has moved?

-- 
Jeffrey Carter

Re: Container reqs

[Simon Wright]

Jean-Marc Bourguet <jbourguet@free.fr> writes:

> I was probably not clear enough.  Tasks savety is not something binary,
> it's something for which there is at least five levels.
> 
> 0) the whole library can't be used by two tasks without explicit
> synchronisation because there is use of some features (global variables,
> COW datastructure build without considering tasking, ...) which make 
> it totally unfit for that use.
> 
> 1) you can work savely on different objects in different tasks but not
> access the same object in different tasks without synchronisation.
> 
> 2) you can savely have read access to one object from different tasks
> but modifying accesses must be protected explicitly from other accesses.
> 
> 3) there is a limited set of modifying accesses which can be issued
> simultaneously from different tasks.
> 
> 4) whatever you do -- trying to modify the datastructure simultaneously
> via iterators from different tasks -- is save.
> 
> From my experience,
>   * level 4 is useless because you still need synchronisation
>     for other reasons when its whole generality is needed.  Achieving it
>     has a major performance impact (every operation has to be
> protected).
> 
>   * level 3 is usefull but the set of modifying access which make sense
>     depend very much on the application.  Your example is probably the
>     only widely applicable one. Achieving this level has a important
>     performance impact.
> 
>   * level 2 can be achieved with a small performance impact: there is no
>     need for explicit synchronisation, one need simply to pay attention
>     to the datastructure used and the way it is accessed.
> 
> I think that one should aim for level 2 because:
>    - this simplify the library (no need to have tasks save and tasks
> unsave
>      version)
>    - aiming level 3 whould imply major discussion about the set of
> operations
>      needed with the risks of compromising to level 4.
>    - I whould probably still encapsulate the ADT in an other
> type/package which
>      export only the operations needed for the application with names
> related
>      to the application.

The BCs' design has two sorts of Container, called monolithic and
polylithic. The monolithic containers (eg, Queue) are self-contained
memory structures, and if I say

  Queue_2 := Queue_1;

I get a deep copy. Polylithic (Grady's word!) containers are
implemented as in-memory structures with multiple viewports, for want
of a better word, so that if I say

  List_2 := List_1;

I still have only one List; if I say

  Tail (List_2);

then List_2 points one element along from List_1. Very complicated,
and the reason I recommend people not to use BC Lists unless they
really really need that functionality.

The polylithic containers (Lists, Graphs, Binary and Multiway Trees)
can't be protected, so they're at your Level 1.

The monolithic containers can be protected using BC.Containers.Guarded:

  generic
     type Base_Container is new BC.Containers.Container with private;
     type Semaphore
     is new BC.Support.Synchronization.Semaphore_Base with private;
  package BC.Containers.Guarded is

which basically adds Seize and Release operations, so that the user
has control over where synchronization is applied. This can be applied
as an add-in to any style of container (bounded or unbounded with
storage allocator). I supply two sorts of Semaphore:

   --  A Semaphore is like a standard POSIX mutex.
   type Semaphore is new Semaphore_Base with private;

   --  A Recursive_Semaphore is like a POSIX recursive mutex; once
   --  Seized by a task, that task can Seize again; other tasks are
   --  blocked until the owning task has Released the semaphore as
   --  many times as it Seized it.
   type Recursive_Semaphore is new Semaphore_Base with private;

If your task happens to die while holding the Semaphore, tough!

The other sort of concurrency control, Synchronized, requires a lot
more work since one has to wrap the protocol of the class
concerned. So far I've done it for Queues and Maps. For Queues,

  generic
     type Queue_Base is new Abstract_Queue with private;
     type Monitor is new BC.Support.Synchronization.Monitor_Base with private;
  package BC.Containers.Queues.Synchronized is

and I supply two sorts of Monitor:

   --  Single_Monitors allow one task at a time to have access, be it
   --  for reading or writing.
   type Single_Monitor is new Monitor_Base with private;

   --  Multiple_Monitors allow multiple readers; however, when a
   --  writer owns the monitor it has exclusive access.
   type Multiple_Monitor is new Monitor_Base with private;

Again, this can wrap any style of memory management. (By the way, I
should add that this generic doesn't work with ObjectAda 7.2 (free
download). I have no idea whether it works with Apex or AdaMulti or
.., no complaints received).

The normal Queue protocol includes

   procedure Pop_Value (Q : in out Queue; Elem : out Item);
   --  Remove and return the item from the front of the queue.

which is atomic (and blocking) for the Synchronized queue; I see that
for the unsynchronized Queue a call of Pop_Value on an empty queue
will in fact raise an exception (but what else can I do?!)


What really bugs me is how to provide a multiple reader/single writer
Monitor for use with iterators.


I fully agree with Jean-Marc that containers are for implementing
things, not for inheriting from!


-S

Re: Container reqs

[Lutz Donnerhacke]

* Jeffrey Carter wrote:
>> Lutz Donnerhacke wrote:
>>> Multiple tasks modifying the same data structure simultanously is a
>>> common requirement for any larger application.
>
>Modifying an ordered structure such as a tree while iterating seems like a
>recipe for disaster, even from a single thread.

But it is a very common problem. Normally databases are involved to solve
this problem on larger collections.

>By "ordered" I mean a structure where the position of an Element within
>the structure is determined by the value of the Element. What is the next
>Element in the structure if the current Element has moved?

Wrong preconditions. You talk about arrays, but even those needs not to be
counted continously. Example:
  type offset is (one, two, four, five);
  for offset use (one => 1, two => 2, four => 4, five => 5);
  type example is array (offset) of Item;

Re: Container reqs

[Ehud Lamm]

Simon Wright <simon@pushface.org> wrote in message
news:x7v4royhk79.fsf@smaug.pushface.org...
> "Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:
>
> > The way I see it, if it is impossible - or just very hard - to
> > provide default instantiaions, it is likely that the design is bad
> > anyway.
>
> I don't see how you can provide containers that can contain anything
> at all in Ada.
>
> You could have containers that were capable of handling anything in
> Containable_Object'Class, I guess (but you'd need access types, 'Class
> is unconstrained).

I guess we are talking different things here.

I have no problem with a Queue package paraemtrized by an Element type
(specified as private). Even novice Ada programmer must know how to
instantiate such packages if he uses Text_IO.
What I dodn't like is the need for several, possibly nested, instantiations
simply to get a simple queue or hash table.

Ehud

Re: Container reqs

[Ehud Lamm]

Simon Wright <simon@pushface.org> wrote in message
news:x7vadyo68g0.fsf@smaug.pushface.org...

> I fully agree with Jean-Marc that containers are for implementing
> things, not for inheriting from!
>


Obviously.
The inheritance I was talking about, at least, was between various kinds of
container interfaces (in order to allow class-wide algorithms that depend of
container interfaces).
The user works with specific containers.

Ehud

Re: Container reqs

[Jeffrey Carter]

Ehud Lamm wrote:
> 
> I have no problem with a Queue package paraemtrized by an Element type
> (specified as private). Even novice Ada programmer must know how to
> instantiate such packages if he uses Text_IO.

How the Element type is specified in the generic formal part should
reflect how the generic uses the type. A generic formal part is a
specification of what the generic must be given to perform its service.
A generic formal private type specifies that the generic will use ":="
and "=" for the type. If the generic doesn't use both, then the generic
is incorrectly specified.

If the generic only uses assignment, then the only way to specify this
in Ada is

   type Element is limited private;
   with procedure Assign (To : in out Element; From : in Element);

This is a failing in Ada, IMO. It might have been better to have
something like

type T is private; -- No operations defined, like Ada's limited private
type T is private with ":="; -- Only assignment defined; no analog in
Ada

and allow the definition (in package specifications) or import (in
generic formal parts) of "=".

> What I dodn't like is the need for several, possibly nested, instantiations
> simply to get a simple queue or hash table.

I wholeheartedly agree. Wright's posting here a few days ago of the
sequence of instantiations needed to obtain a simple structure with the
Booch components clearly indicates that they fail this requirement.

-- 
Jeffrey Carter

Re: Container reqs

[Jeffrey Carter]

Lutz Donnerhacke wrote:
> 
> * Jeffrey Carter wrote:
> >Modifying an ordered structure such as a tree while iterating seems like a
> >recipe for disaster, even from a single thread.
> 
> But it is a very common problem. Normally databases are involved to solve
> this problem on larger collections.

It's not something I have ever wanted to do.

> >By "ordered" I mean a structure where the position of an Element within
> >the structure is determined by the value of the Element. What is the next
> >Element in the structure if the current Element has moved?
> 
> Wrong preconditions. You talk about arrays, but even those needs not to be
> counted continously. Example:

No, I didn't mention arrays. I'm talking about iterating over an ordered
data structure. Some action is applied to the current Element, then to
the next Element, where "next" is defined by the structure.

-- 
Jeffrey Carter

Re: Container reqs

[Lutz Donnerhacke]

* Jeffrey Carter wrote:
>Lutz Donnerhacke wrote:
>> >By "ordered" I mean a structure where the position of an Element within
>> >the structure is determined by the value of the Element. What is the next
>> >Element in the structure if the current Element has moved?
>> 
>> Wrong preconditions. You talk about arrays, but even those needs not to be
>> counted continously. Example:
>
>No, I didn't mention arrays. I'm talking about iterating over an ordered
>data structure. Some action is applied to the current Element, then to
>the next Element, where "next" is defined by the structure.

Exactly. Where is the problem with changing the underlying structure while
iterating? Databases offer serveral isolation levels for this.

Re: Container reqs

[Georg Bauhaus]

Jeffrey Carter <jeffrey.carter@boeing.com> wrote:
 
: I wholeheartedly agree. Wright's posting here a few days ago of the
: sequence of instantiations needed to obtain a simple structure with the
: Booch components clearly indicates that they fail this requirement.
 
I can't see why in _Ada_ this is a problem. You have to
laboriously write things up in all sorts of unexpected places,
unexpected to the newcommers at least. Like certain arrays in a
record: you need to declare a type first.  That is, multilevel
instantiation, considered an _implementation detail_, is quite
in the Ada spirit from that point of view. At least to me.

(If I wanted nice data structures almost for free, I might as well chose
a language that has them :-)

Georg

Re: Container reqs

[Ehud Lamm]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:un12nod47.fsf@gsfc.nasa.gov...
> Jeffrey Carter <jeffrey.carter@boeing.com> writes:
>
> > Ehud Lamm wrote:
> > > <snip>
> > > What I dodn't like is the need for several, possibly nested,
instantiations
> > > simply to get a simple queue or hash table.
> >
> > I wholeheartedly agree. Wright's posting here a few days ago of the
> > sequence of instantiations needed to obtain a simple structure with the
> > Booch components clearly indicates that they fail this requirement.
>
> This is easy to say. But can you provide an alternative, that still
> allows the container to handle all reasonable Ada types?
>
> People have made the same complaint about my library. But that
> complexity is simply a reflection of the complexity that Ada supports.
> I don't see a simple alternative that is not so restrictive as to be
> useless. Well, you could maintain several copies of the code, each
> accepting slightly different generic formal types. But _I'm_ not going
> to do that!
>


Yep. I agree entirely.<p>
But since I find this point to be important for using the library in
education, I wanted to hear ideas and possible solutions.<p>
What I was thinking about was having wrapper packages, for the most
important cases. I don't think this will turn out to be a mjor overhead. And
it should ease the learning curve, even for experts, since these packages
will be, in essence, example code...

Ehud

Re: Container reqs

[Stephen Leake]

Jeffrey Carter <jeffrey.carter@boeing.com> writes:

> Ehud Lamm wrote:
> > <snip> 
> > What I dodn't like is the need for several, possibly nested, instantiations
> > simply to get a simple queue or hash table.
> 
> I wholeheartedly agree. Wright's posting here a few days ago of the
> sequence of instantiations needed to obtain a simple structure with the
> Booch components clearly indicates that they fail this requirement.

This is easy to say. But can you provide an alternative, that still
allows the container to handle all reasonable Ada types? 

People have made the same complaint about my library. But that
complexity is simply a reflection of the complexity that Ada supports.
I don't see a simple alternative that is not so restrictive as to be
useless. Well, you could maintain several copies of the code, each
accepting slightly different generic formal types. But _I'm_ not going
to do that!

Life isn't simple, as well as not being fair!

-- 
-- Stephe

Re: Container reqs

[Jeffrey Carter]

Stephen Leake wrote:
> 
> Jeffrey Carter <jeffrey.carter@boeing.com> writes:
> 
> > Ehud Lamm wrote:
> > > <snip>
> > > What I dodn't like is the need for several, possibly nested, instantiations
> > > simply to get a simple queue or hash table.
> >
> > I wholeheartedly agree. Wright's posting here a few days ago of the
> > sequence of instantiations needed to obtain a simple structure with the
> > Booch components clearly indicates that they fail this requirement.
> 
> This is easy to say. But can you provide an alternative, that still
> allows the container to handle all reasonable Ada types?

I refer you to the PragmAda Reusable Components as an example of a
component library that provides single instantiations for simple
structures that handle all reasonable Ada types.

http://home.earthlink.net/~jrcarter010/pragmarc.htm

-- 
Jeffrey R. Carter
PragmAda Software Engineering

Re: Container reqs

[Simon Wright]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> What I was thinking about was having wrapper packages, for the most
> important cases. I don't think this will turn out to be a mjor
> overhead. And it should ease the learning curve, even for experts,
> since these packages will be, in essence, example code...

It turns out that they would be quite hard to write for the BCs,
particularly because of Iterators; and I'm not sure how useful an
example a set of renamings of operations would be ..

Re: Container reqs

[Simon Wright]

lutz@iks-jena.de (Lutz Donnerhacke) writes:

> * Jeffrey Carter wrote:
> >Lutz Donnerhacke wrote:
> >> >By "ordered" I mean a structure where the position of an Element within
> >> >the structure is determined by the value of the Element. What is the next
> >> >Element in the structure if the current Element has moved?
> >> 
> >> Wrong preconditions. You talk about arrays, but even those needs not to be
> >> counted continously. Example:
> >
> >No, I didn't mention arrays. I'm talking about iterating over an ordered
> >data structure. Some action is applied to the current Element, then to
> >the next Element, where "next" is defined by the structure.
> 
> Exactly. Where is the problem with changing the underlying structure while
> iterating? Databases offer serveral isolation levels for this.

If you need a database, use a database! All the component libraries
I'm aware of are intended to be used for in-memory data structures and
are fairly light-weight.

What would the Java collections classes do under such circumstances?

Re: Container reqs

[Paul Duquennoy]

Simon Wright <simon@pushface.org> wrote:

> lutz@iks-jena.de (Lutz Donnerhacke) writes:
> 
> > * Jeffrey Carter wrote:
> > >Lutz Donnerhacke wrote:
> > >> >By "ordered" I mean a structure where the position of an Element within
> > >> >the structure is determined by the value of the Element. What is
> > >> >the next Element in the structure if the current Element has moved?
> 
> What would the Java collections classes do under such circumstances?

Assume that you have (in Java) : 

   Collection c = new ArrayList (10);
   Iterator   i = c.iterator();

If you do c.remove (...); and try i.next(), you get an exception. But
the iterator has a remove() method that removes the last element fetched
object from the collection while keeping the integrity of the iterator.

If you add a new element to the collection, you will get an exception at
the next call of an iterator method.

So do not use any updating method of the collection itself while you are
iterating over it. Use only the "remove" method of the iterator.

Re: Container reqs

[Stephen Leake]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
> news:un12nod47.fsf@gsfc.nasa.gov...
> > Jeffrey Carter <jeffrey.carter@boeing.com> writes:
> >
> > > Ehud Lamm wrote:
> > > > <snip>
> > > > What I dodn't like is the need for several, possibly nested,
> instantiations
> > > > simply to get a simple queue or hash table.
> > >
> > > I wholeheartedly agree. Wright's posting here a few days ago of the
> > > sequence of instantiations needed to obtain a simple structure with the
> > > Booch components clearly indicates that they fail this requirement.
> >
> > This is easy to say. But can you provide an alternative, that still
> > allows the container to handle all reasonable Ada types?
> >
> > People have made the same complaint about my library. But that
> > complexity is simply a reflection of the complexity that Ada supports.
> > I don't see a simple alternative that is not so restrictive as to be
> > useless. Well, you could maintain several copies of the code, each
> > accepting slightly different generic formal types. But _I'm_ not going
> > to do that!
> >
> 
> 
> Yep. I agree entirely.<p>
> But since I find this point to be important for using the library in
> education, I wanted to hear ideas and possible solutions.<p>
> What I was thinking about was having wrapper packages, for the most
> important cases. I don't think this will turn out to be a mjor overhead. And
> it should ease the learning curve, even for experts, since these packages
> will be, in essence, example code...

Well, examples are always useful. And I have helper packages to make
things simpler in the "simple" cases. There is test code that serves
as examples for my library; other examples would probably be helpful.

Perhaps you could volunteer to define the "typical most important
cases", and I'll write example code for them, for my library. If it
seems reasonable, I'll also try to write a "simple wrapper" package.
Then someone else can try to do the same with each of the other
candidate libraries. That should be a good learning exercise. It might
also make it easier for potential users to compare the libraries:

"Let's see. It takes 42 lines and 5 packages to get a list of integers
with SAL, and 52 lines in 3 packages with BC. Which should I use?"

Hopefully it won't be that simplistic :).

Hmm. I suppose more learning would occur if we each did the examples
for someone _else's_ library. But I don't have the time ...

-- 
-- Stephe

Re: Container reqs

[Stephen Leake]

Jeffrey Carter <jrcarter@acm.org> writes:

> Stephen Leake wrote:
> > 
> > Jeffrey Carter <jeffrey.carter@boeing.com> writes:
> > 
> > > Ehud Lamm wrote:
> > > > <snip>
> > > > What I dodn't like is the need for several, possibly nested, instantiations
> > > > simply to get a simple queue or hash table.
> > >
> > > I wholeheartedly agree. Wright's posting here a few days ago of the
> > > sequence of instantiations needed to obtain a simple structure with the
> > > Booch components clearly indicates that they fail this requirement.
> > 
> > This is easy to say. But can you provide an alternative, that still
> > allows the container to handle all reasonable Ada types?
> 
> I refer you to the PragmAda Reusable Components as an example of a
> component library that provides single instantiations for simple
> structures that handle all reasonable Ada types.
> 
> http://home.earthlink.net/~jrcarter010/pragmarc.htm

Ok, I'll take a look at it.


-- 
-- Stephe

Re: Container reqs

[Kenneth Almquist]

Jeffrey Carter <jeffrey.carter@boeing.com> wrote:
> Jean-Marc Bourguet wrote:
>> 
>> I'm not for making a container "threadsafe"  to the point where
>> several tasks may modify the container without providing their
>> synchronisation.
>> In my experience
>>    * most containers are accessed only by one task
>>    * for those who are not, an explicit synchronisation is needed for
>>      other purpose as the container is not the only part member of the
>>      datastructure which has to be modified atomically.
>
> This is an interesting assertion, considering that a protected queue is
> a useful and common form of intertask communication.

When using a queue for interprocess communication, you normally want a
reader task to block when the queue is empty.  You probably want the
writer to block when the queue is full, though it is easier to imagine
exceptions to this.  The natural way to accomplish this in Ada is to
wrap the queue in a protected type with appropriate entry barriers, as
is shown in the code at the end of this posting.  If you do this, the
semantics for protected types mean that the queue will never be
accessed by two tasks simultaneously, so there is no need for the
queue type to be "threadsafe."

I'm not saying that intertask communication mechanisms should not be
part of the library.  I just don't think that "threadsafe" containers
are a particularly useful intertask communication mechanism.
				Kenneth Almquist


generic
   type Element is private;
package Channel is

   package Element_Queue is new Queue(Element);

   protected type T is
      entry Put(Item : Element);
      entry Get(Item : out Element);
   private
      Q : Element_Queue.T;
   end T;

end Channel;


package body Channel is
   protected body T is

      entry Put(Item : Element) when not Element_Queue.Is_Full(Q) is
      begin
         Element_Queue.Insert(Q, Item);
      end Put;

      entry Get(Item : out Element) when not Element_Queue.Is_Empty(Q) is
      begin
         Element_Queue.Remove(Q, Item);
      end Get;

   end T;
end Channel;

Re: Container reqs

[mike]

In article <9r0fbp$l5t$1@shell.monmouth.com>, ka@sorry.no.email says...
>
 
> The natural way to accomplish this in Ada is to
>wrap the queue in a protected type with appropriate entry barriers, as
>is shown in the code at the end of this posting. 

 
I assume given a type that is not wrapped by a protected type (i.e. a type
in a 3rd party package), one could wrap a protected type around it to
make it thread safe?

i.e. if I have nice Queue package and I want to use with tasks, but I do not
have the code for that package, can one still use protected types with it?

Re: Container reqs

[Lutz Donnerhacke]

* mike@nospam wrote:
>I assume given a type that is not wrapped by a protected type (i.e. a type
>in a 3rd party package), one could wrap a protected type around it to
>make it thread safe?

Yes.

>i.e. if I have nice Queue package and I want to use with tasks, but I do not
>have the code for that package, can one still use protected types with it?

Yes, of course.

Re: Container reqs

[Jeffrey Carter]

Kenneth Almquist wrote:
> 
> When using a queue for interprocess communication, you normally want a
> reader task to block when the queue is empty.  You probably want the
> writer to block when the queue is full, though it is easier to imagine
> exceptions to this.  The natural way to accomplish this in Ada is to
> wrap the queue in a protected type with appropriate entry barriers, as
> is shown in the code at the end of this posting.  If you do this, the
> semantics for protected types mean that the queue will never be
> accessed by two tasks simultaneously, so there is no need for the
> queue type to be "threadsafe."

Yes, the protected queue component will normally be implemented using an
unprotected queue component. This is such a common idiom that any
library that doesn't supply such components will not help much in
providing standardization (instead of everyone having to provide his own
component, everyone will have to provide his own protected component).
Indeed, I rarely use unprotected components except when constructing
more complex data structures, even when developing sequential systems.
The overhead of the protected object is generally not an issue.

-- 
Jeffrey Carter

Re: Container reqs

[Ehud Lamm]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:uadyk5045.fsf@gsfc.nasa.gov...
> Perhaps you could volunteer to define the "typical most important
> cases", and I'll write example code for them, for my library. If it
> seems reasonable, I'll also try to write a "simple wrapper" package.
> Then someone else can try to do the same with each of the other
> candidate libraries. That should be a good learning exercise. It might
> also make it easier for potential users to compare the libraries:
>

I don't have the time right now to make sure something really is "typical",
or "most important", but I'll describe one the things I needed for one of my
recent examples.

1) Vector (unbounded, indexed collection) or strings (possibly Unbounded)
2) Array of Hash tables, keys into the hash are strings (we can assume,
fixed size), and the values are Sets of integers (in fact, indexes into the
vector, in (1))

(in (2), it was also an option to change "Array of.." to "hash of...")

Notice that the hash tables must be an ADT, since we need many. Most simple
packages implement hash ADOs.

I didn't need iterators. I did need to be able to update the sets, after
they are inserted to the hash tables, though it is possible to extract a
set, update it, and insert it back into the hash.

Ehud

Re: Container reqs

[Ehud Lamm]

Jeffrey Carter <jeffrey.carter@boeing.com> wrote in message
news:3BD449A4.B3D44645@boeing.com...
>The overhead of the protected object is generally not an issue.

Do you have some numbers?

From what I remember the overhead I experienced on Win/Gnat 3.11 was quite
significant. For my needs this wasn't a problem, but I could understand why
others regarded it as unaaceptable.

Ehud

Re: Container reqs

[David Botton]

Take a look at the original_booch components, I think you will find what you
need. http://www.adapower.com/original_booch and in the form you are looking
for.

David Botton

"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9r1jlr$5of$1@news.huji.ac.il...
> 1) Vector (unbounded, indexed collection) or strings (possibly Unbounded)
> 2) Array of Hash tables, keys into the hash are strings (we can assume,
> fixed size), and the values are Sets of integers (in fact, indexes into
the
> vector, in (1))
>
> (in (2), it was also an option to change "Array of.." to "hash of...")
>
> Notice that the hash tables must be an ADT, since we need many. Most
simple
> packages implement hash ADOs.
>
> I didn't need iterators. I did need to be able to update the sets, after
> they are inserted to the hash tables, though it is possible to extract a
> set, update it, and insert it back into the hash.
>
> Ehud

Re: Container reqs

[Ehud Lamm]

David Botton <David@Botton.com> wrote in message
news:tt8m5isqsjma2f@corp.supernews.com...
> Take a look at the original_booch components, I think you will find what
you
> need. http://www.adapower.com/original_booch and in the form you are
looking
> for.


I am quite familiar with these. I like their Ada-83 falvor (no inheritance).
Troubleis, I also like the interface ineheritance you can have using tagged
types...

Ehud

Re: Container reqs

[Stephen Leake]

Jeffrey Carter <jrcarter@acm.org> writes:

> Stephen Leake wrote:
> > 
> > Jeffrey Carter <jeffrey.carter@boeing.com> writes:
> > 
> > > Ehud Lamm wrote:
> > > > <snip>
> > > > What I dodn't like is the need for several, possibly nested, instantiations
> > > > simply to get a simple queue or hash table.
> > >
> > > I wholeheartedly agree. Wright's posting here a few days ago of the
> > > sequence of instantiations needed to obtain a simple structure with the
> > > Booch components clearly indicates that they fail this requirement.
> > 
> > This is easy to say. But can you provide an alternative, that still
> > allows the container to handle all reasonable Ada types?
> 
> I refer you to the PragmAda Reusable Components as an example of a
> component library that provides single instantiations for simple
> structures that handle all reasonable Ada types.
> 
> http://home.earthlink.net/~jrcarter010/pragmarc.htm

Well, I've looked at it (briefly). Here's the relevant part of the
unbounded list package:

generic -- PragmARC.List_Unbounded
   type Element is limited private; -- Do not instantiate with a scalar

   with procedure Assign (To : in out Element; From : in Element) is <>;
package PragmARC.List_Unbounded is

And the equivalent from my library:
generic
   type Item_Type (<>) is limited private;
   type Item_Node_Type is private;
   with function To_Item_Node (Item : in Item_Type) return Item_Node_Type;
   with procedure Free_Item (Item : in out Item_Node_Type);
   -- If Item_Type is definite non-limited, Item_Node_Type should just be
   -- Item_Type. Then To_Item_Node should just return Item, and Free_Item
   -- should be null (and both should be inlined). See
   -- SAL.Aux.Definite_Private_Items.
   --
   -- If Item_Type is indefinite, Item_Node_Type should be 'access
   -- Item_Type'. Then To_Item_Node should allocate Item and return a
   -- pointer to it, and Free_Item should be Unchecked_Deallocation. See
   -- SAL.Aux.Indefinite_Private_Items.
   --
   -- To create a list of limited objects (say of type Limited_Type),
   -- Item_Type can be a non-limited type holding the parameters needed to
   -- create an object (non-limited to allow the user to create aggregates
   -- of creation parameters), and Item_Node_Type can be 'access
   -- Limited_Type'. Then To_Item_Node must allocate an object of type
   -- Limited_Type and initialize it using the parameters in Item_Type. See
   -- SAL.Aux.Indefinite_Limited_Items.
   --
   -- Other usages may be possible.
   --

   with function Copy (Source : in Item_Node_Type) return Item_Node_Type is <>;
   -- Deep copy of Source, for use in allocators in Copy (List).

   Node_Storage_Pool : in out System.Storage_Pools.Root_Storage_Pool'Class;
   -- Root_Storage_Pool is limited, which does not allow defaults. Default
   -- for a global list type should be <some_global_access_type>'Storage_Pool.
   -- Default for a local list type, which should be reclaimed when the
   -- list type goes out of scope, is implementation defined (sigh).
package SAL.Gen.Lists.Double is

PragmARC does _not_ support indefinite types, which are a large part
of Ada (strings, unconstrained variant records, tagged types with
unconstrained discriminants). In addition, the comment says "no
scalars"; I'm not clear why.

So I don't think PragmARC meets the criteria of "simple instantiation
for all reasonable Ada types".

Perhaps we disagree on the meaning of "reasonable" here.

-- 
-- Stephe

Re: Container reqs

[Jeffrey Carter]

Stephen Leake wrote:
> 
> PragmARC does _not_ support indefinite types, which are a large part
> of Ada (strings, unconstrained variant records, tagged types with
> unconstrained discriminants). In addition, the comment says "no
> scalars"; I'm not clear why.

That is correct. Raw indefinite types are not reasonable types to store
in a data structure. If you need to store strings, you should be using
an abstraction such as (Un)Bounded_String. Similar abstractions should
be used for other indefinite types.

The problem with scalars is that there is a range check required on copy
in for a scalar parameter of mode in out. The PragmARCs pass
uninitialized objects of type Element to the To parameter of Assign. If
Element is a scalar subtype (such as Positive) and an object's
uninitialized value is out of the subtype's range (-7), Constraint_Error
would be raised. For scalar types that cannot have an out of range value
(Integer), this is not an issue, but for a simple-minded rule, no
scalars is easily stated. It is a simple matter to wrap a scalar in a
record if it's really needed, but experience shows that data structures
are almost always used for more complex types. It's a reasonable trade
off for being able to handle limited types without access types.

> So I don't think PragmARC meets the criteria of "simple instantiation
> for all reasonable Ada types".
> 
> Perhaps we disagree on the meaning of "reasonable" here.

So it would seem. I think SAL doesn't provide simple instantiation for
any Ada type.

-- 
Jeffrey R. Carter
PragmAda Software Engineering

Re: Container reqs

[John English]

Ehud Lamm wrote:
> 
> John English <je@brighton.ac.uk> wrote in message
> news:3BCD7C50.647ADBD0@brighton.ac.uk...
> > Hmm, the STL doesn't use inheritance, it's all done with templates.
> > Tagged types probably aren't needed at all (other than as derivations
> > of controlled). And you can use tricks to get around the library-level
> > problem, e.g. have a library-level parent package which defines a private
> > controlled type and generic children which make use of those controlled
> > objects as components in other composite types...
> 
> Don't you like using inheritance as for interface reuse?
> I like the ability to have all sequential structures support the same
> iteration mechanisms. I like the ability to write class-wide opertations
> ("Exists", "For_All", "Filter" etc.)

Yes; but if you *want* to avoid inheritance, the STL is an existence
proof for a possible solution... :-)

OTOH, if you do want to use inheritance here, some trickery is probably
needed to avoid the library-level problem (since you'll presumably want
generic packages but don't want to force library-level instantiation).

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Container reqs

[Ted Dennison]

In article <3BD4D157.C96BBAAD@acm.org>, Jeffrey Carter says...
>
>So it would seem. I think SAL doesn't provide simple instantiation for
>any Ada type.

I'm curious about this "requirement"; Does it hold for limited types too? If so,
you are limiting the implementations in certian ways.

As a checkpoint, the STL relies on making copies of objects, so it doesn't work
with C++'s equivalent of limited types. This isn't really too much of a
hardship, as you can use it with pointers to such types.

It probably wouldn't prove too much of a hardship in Ada to limit the component
library to non-limited definite types.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Ehud Lamm]

<je@brighton.ac.uk> wrote in message
news:3BD527A8.93C1F68B@brighton.ac.uk...
> Yes; but if you *want* to avoid inheritance, the STL is an existence
> proof for a possible solution... :-)
>
> OTOH, if you do want to use inheritance here, some trickery is probably
> needed to avoid the library-level problem (since you'll presumably want
> generic packages but don't want to force library-level instantiation).
>

Life isn't simple, is it?

I outlined a basic approach that works for me, a few days a go (the abstract
types package is parametreized by item. Inheritance, providing
implementation, is done in child units).

Others presented their apporaches.

Let me say a few words concerning my point of view, from a teaching
perspective. Since you teach too, I'd be happy to hear your views on these
issues.

- I want to teach the concept of ADTs, without talking about inheritance,
tagged types etc.

- I want to be able to show how ADTs can help reuse, by utilizing the
container library.

- Following the above, I want to be able to explore the concept of
"interfaces" in the most general sense: what is sometimes called interface
oriented programming. I want to show how a Set ADT defines an interface, and
how this interface can have multiple implementations. This, in Ada, means
inheritance, and tagged types. However, the situation right now, means you
can only directly support one interface (MI idioms are going to be too
confusing, I'm afraid).

- Interface leads us to class-wide programming, or to the use of signature
packages.

- The interface relations are best explored using inheritance, and that's
fine. Inheritance however can easily be used for other purposes, and I want
to minimize the possbility for confusion.

- I want to utilize Ada's strong typing, and detest access to Object'class
solutions.

And all this, before getting into issues of guarded, bounded and other
design dimensions. These are also worth considering...

Ehud

Re: Container reqs

[Stephen Leake]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> <je@brighton.ac.uk> wrote in message
> news:3BD527A8.93C1F68B@brighton.ac.uk...
> > Yes; but if you *want* to avoid inheritance, the STL is an existence
> > proof for a possible solution... :-)
> >
> > OTOH, if you do want to use inheritance here, some trickery is probably
> > needed to avoid the library-level problem (since you'll presumably want
> > generic packages but don't want to force library-level instantiation).
> >
> 
> Life isn't simple, is it?
> 
> I outlined a basic approach that works for me, a few days a go (the abstract
> types package is parametreized by item. Inheritance, providing
> implementation, is done in child units).
> 
> Others presented their apporaches.
> 
> Let me say a few words concerning my point of view, from a teaching
> perspective. Since you teach too, I'd be happy to hear your views on these
> issues.

I think we can all agree that a library intended to be used as a
teaching example might be simpler than a library intended to be used
in general.

-- 
-- Stephe

Re: Container reqs

[Ehud Lamm]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:uu1wqf7d8.fsf@gsfc.nasa.gov...
> I think we can all agree that a library intended to be used as a
> teaching example might be simpler than a library intended to be used
> in general.
>


Well, yes and no.
If you look at the current situation, people are saying to themselves (and
some say it out loud), that by using Java, you can teach students how to use
libraries and APIs. APIs even appear as a standard subject in the draft ACM
CS syllabus.

Notice that all this started from thinkin about a STANDARD container library
for Ada. IHaving such a thing will in turn help produce common examples,
text books etc.
This is much better than each teacher building his own set of tools, and
having several Ada text books teaching you how to solve problems you'd most
probably use a standard  library for in Java or C++.

So, yes - if build only for education a libraty can be made very much
simpler, and no - a well desgined  standard library would be one of my
criteria for choosing a language with which to teach design. (Notice that
this is obviously not the only factor, and more important that I am NOT
talking about choosing a first programming language. This is a totally
different issue of course, and one we shouldn't debate in this thread..)

Ehud

Re: Container reqs

[Ted Dennison]

In article <uu1wqf7d8.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>I think we can all agree that a library intended to be used as a
>teaching example might be simpler than a library intended to be used
>in general.

Yes, but now we are talking about having multiple different libraries. That is
the exact situation we have now that everyone is decrying.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Marin David Condic]

I've been hoping to find in this discussion some kind of "Least Common
Denominator" that would outline requirements for some minimal collection of
data structures & algorithms for a standard library. Slicing the scope down
to some minimal set of containers that might address - say - 80%? of the
garden variety usages would constitute A Good Start. (Personally, I think a
plain vanilla double ended list and map would take care of the bulk of
needs.) It can *always* get expanded into different variations and flavors -
not unlike what you see under Ada.Strings.

Getting overly ambitious about what should be required for a standard Ada
library is just going to guarantee that this discussion remains just a
discussion.

If you had:

generic
    type Item is private ;
package Lists is .....

and...

generic
    type Index is private ;
    type Item is private ;
    with function "<" (Left, Right : Index) return Boolean is <> ;
package Maps is.....

would this *maybe* take care of some really large percentage of the usages
of data structures? Yeah, it wouldn't necessarily handle all the more
interesting cases and it might not be task safe and it might not be useful
for realtime and a whole bunch of other objections. But for a *whole lot* of
uses, this might just be enough and it leaves plenty of room for things like
"package Realtime_Lists is" and "package Object_Oriented_Maps is" and so on.

If it isn't kept reasonably simple, it won't get done and/or it won't find
widespread acceptance. I'm thinking that a tree containing just the two
packages I outlined above (or some reasonable variant on that theme) might
just be simple enough, reliable enough and useful enough to make a start. If
that much got accepted, other variations could be added with time.

And we still don't know if any vendors would include it in their
distributions...

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:IKkB7.40160$ev2.47839@www.newsranger.com...
>
> Yes, but now we are talking about having multiple different libraries.
That is
> the exact situation we have now that everyone is decrying.
>
.

Re: Container reqs

[Larry Hazel]

Ted Dennison wrote:
> 
> In article <uu1wqf7d8.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >
> >I think we can all agree that a library intended to be used as a
> >teaching example might be simpler than a library intended to be used
> >in general.
> 
> Yes, but now we are talking about having multiple different libraries. That is
> the exact situation we have now that everyone is decrying.
> 
So, we can have a general purpose library and just expose the students to parts
of it (or pre-instantiated parts of it).

Larry

Re: Container reqs

[Ehud Lamm]

Larry Hazel <lhhazel@otelco.net> wrote in message
news:3BD5E0CC.306FB227@otelco.net...
> So, we can have a general purpose library and just expose the students to
parts
> of it (or pre-instantiated parts of it).
>

This is indeed the goal. The problem is that some designs make this harder
than others, and I am not sure this is always justified. Hence my original
list of reqs.

Ehud

Re: Container reqs

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BD4D157.C96BBAAD@acm.org>, Jeffrey Carter says...
> >
> >So it would seem. I think SAL doesn't provide simple instantiation for
> >any Ada type.
> 
> I'm curious about this "requirement"; Does it hold for limited types too? If so,
> you are limiting the implementations in certian ways.
> 
> As a checkpoint, the STL relies on making copies of objects, so it doesn't work
> with C++'s equivalent of limited types. This isn't really too much of a
> hardship, as you can use it with pointers to such types.
> 
> It probably wouldn't prove too much of a hardship in Ada to limit the component
> library to non-limited definite types.

I'm not sure what "requirement" you're talking about. Most of the data
structures in the PragmAda Reusable Components can handle any type the
client can define an Assign procedure for. That includes many useful
limited types, such as most of the data structures.

-- 
Jeff Carter
"We burst our pimples at you."
Monty Python & the Holy Grail

Re: Container reqs

[Ehud Lamm]

Marin David Condic <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9r4mr9$os0$1@nh.pace.co.uk...
> I've been hoping to find in this discussion some kind of "Least Common
> Denominator" that would outline requirements for some minimal collection
of
> data structures & algorithms for a standard library.

Right!

> It can *always* get expanded into different variations and flavors -
> not unlike what you see under Ada.Strings.

Right. But only if the original design is extendable. Hence the reason for
this discussion.

Ehud

Re: Container reqs

[Ted Dennison]

In article <3BD626BF.4CAEAF69@acm.org>, Jeffrey Carter says...
>
>Ted Dennison wrote:
>> 
>> It probably wouldn't prove too much of a hardship in Ada to limit the 
>> component library to non-limited definite types.
>
>Most of the data structures in the PragmAda Reusable Components can 
>handle any type the client can define an Assign procedure for. That 
>includes many useful limited types, such as most of the data structures.

True. But when you take that approach you have to do one of two things:

1) Force *every* user, including the >90% using only non-limited definite types,
to create an "assign" procedure so that they can instantiate the container
package. One of my personal no-no's of design is forcing extra work of this
magnitude on every user to support an exceptional case.

2) Create separate versions of the same component for use with
limited/indefinite types. 


I see that you chose 1, and tried to mitigate the effort with another helper
generic. But again, all this is complicating things significantly for the
benifit of a small percentage of users.

Is there anyone out there who really thinks that being able to handle such types
is a requirement, given that you can still handle pointers to them, and doing so
would complicate the facility for everyone?

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Container reqs

[Lutz Donnerhacke]

* Ted Dennison wrote:
>Is there anyone out there who really thinks that being able to handle such
>types is a requirement, given that you can still handle pointers to them,
>and doing so would complicate the facility for everyone?

*Raising a hand* I prefer mixins in order to prevent unnecessary pointers.

Re: Container reqs

[Marin David Condic]

I grok that, but it still seems to me that it would be possible to start
with:

package ASCL.Basic_Containers.Lists is
package ASCL.Basic_Containers.Maps is

(Throw in a very small handful of other things if you like and make these
generic to take private, limited private, tagged private, or
whatever-you-like, generic data and I'll bet this would cover some really
huge amount of realestate in your garden variety Workstation/PC apps.)

...And from there branch out into all sorts of variants - some that might
support an OO-Inheritance style, some that would have dozens of generic
parameters that let you cinfigure it eighteen ways from Tuesday, some that
provide static storage & protected access for realtime, etc. The point is
that this original branch will serve lots of needs and doesn't really hamper
extension. No reason that there can't be added:

ASCL.OO_Containers.Lists
ASCL.Realtime_Containers.Lists
ASCL.Booch_Containers...
...etc...

Or even extending it to:

ASCL.Mathematics...
ASCL.Sort_Search...
ASCL.OS_Interface...
ASCL.Graphics...
ASCL.GUI...

I think if we had those two (or some small, single digit number) packages
and got some kind of consensus that the compiler vendors would distribute
that much with their compilers, we'd be WELL on our way to forming up a more
sophisticated Ada Standard Component Library. If the vendors would accept
ASCL.Basic_Containers as a branch, they could opt in/out on any additional
branches that got dreamed up. But you'd have A Good Start(tm) and one-up on
numerous other languages out there.

I'm thinking that if the discussion surrounds itself around adopting
this-or-that particular existing library, it will go on forever because it
is too hard to build a consensus on the dozens of components all at once and
too many people have a vested interest in getting this-or-that library
adopted. Getting a consensus on only two or three things is much more
likely. Starting from some bottom-dead-center position means everybody is
disadvantaged equally. Starting small keeps the objectives achievable.

Just a thought - its better to get *something* done than to endlessly
discuss the "Perfect Component Library"

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9r5ues$ns6$1@news.huji.ac.il...
>
> > It can *always* get expanded into different variations and flavors -
> > not unlike what you see under Ada.Strings.
>
> Right. But only if the original design is extendable. Hence the reason for
> this discussion.
>

Re: Container reqs

[Marin David Condic]

I'd rather see a plain-vanilla initial case that let me make lists of
Integers, Floats, Strings and Records (no tags, no discriminants, no
pointers, no nothing but plain vanilla records). That would probably handle
75% of the things that I would normally do.

From there, a variant of the same packages could be created that dealt with
limited private or other unusual generic parameter requirements. (Like
requiring "<" and "=" operators for sorting limited private stuff...) The
other variants can provide a nearly identical package spec, just offer
different advantages. Document the reasons for different variants so that
the user can choose the best variant for the job at hand and you've got
something there. (Why do we have Ada.Strings.Fixed, Ada.Strings.Bounded,
Ada.Strings.Unbounded otherwise? I'm lobbying to get the equivalent of
Ada.Strings.Fixed accepted and we can worry about the rest later.)

Give me the plain vanilla case and leave a branch open for more
sophisticated cases and I'll have infinitely more standard components than I
have right now.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:lKzB7.41007$ev2.48168@www.newsranger.com...
>
> True. But when you take that approach you have to do one of two things:
>
> 1) Force *every* user, including the >90% using only non-limited definite
types,
> to create an "assign" procedure so that they can instantiate the container
> package. One of my personal no-no's of design is forcing extra work of
this
> magnitude on every user to support an exceptional case.
>
> 2) Create separate versions of the same component for use with
> limited/indefinite types.
>
>
> I see that you chose 1, and tried to mitigate the effort with another
helper
> generic. But again, all this is complicating things significantly for the

> benifit of a small percentage of users.
>
> Is there anyone out there who really thinks that being able to handle such
types
> is a requirement, given that you can still handle pointers to them, and
doing so
> would complicate the facility for everyone?
>

Re: Container reqs

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <3BD626BF.4CAEAF69@acm.org>, Jeffrey Carter says...
> >
> >Ted Dennison wrote:
> >> 
> >> It probably wouldn't prove too much of a hardship in Ada to limit the 
> >> component library to non-limited definite types.
> >
> >Most of the data structures in the PragmAda Reusable Components can 
> >handle any type the client can define an Assign procedure for. That 
> >includes many useful limited types, such as most of the data structures.
> 
> True. But when you take that approach you have to do one of two things:
> 
> 1) Force *every* user, including the >90% using only non-limited definite types,
> to create an "assign" procedure so that they can instantiate the container
> package. One of my personal no-no's of design is forcing extra work of this
> magnitude on every user to support an exceptional case.
> 
> 2) Create separate versions of the same component for use with
> limited/indefinite types. 

Correct.

Although another option, that I mention without really supporting, is
to use gnatprep to provide the two packages above, from a single
source. That eases the maintenance burden. But it won't be standard
Ada. 

> I see that you chose 1, and tried to mitigate the effort with
> another helper generic. But again, all this is complicating things
> significantly for the benifit of a small percentage of users.

How do you know it is a "small" percentage?

> Is there anyone out there who really thinks that being able to
> handle such types is a requirement, given that you can still handle
> pointers to them, and doing so would complicate the facility for
> everyone?

The packages in SAL were built precisely because I needed them in one
or another project I was working on. I don't know how many others
would use the full feature set, but I will in future projects. I use
limited indefinite types a lot!

Maybe this weekend I'll find time to sift thru my project code for
some real examples.

-- 
-- Stephe

Re: Container reqs

[Jeffrey Carter]

Ted Dennison wrote:
> 
> True. But when you take that approach you have to do one of two things:
> 
> 1) Force *every* user, including the >90% using only non-limited definite types,
> to create an "assign" procedure so that they can instantiate the container
> package. One of my personal no-no's of design is forcing extra work of this
> magnitude on every user to support an exceptional case.
> 
> 2) Create separate versions of the same component for use with
> limited/indefinite types.
> 
> I see that you chose 1, and tried to mitigate the effort with another helper
> generic. But again, all this is complicating things significantly for the
> benifit of a small percentage of users.

There is also the issue of precision of specification that I mentioned
in an earlier post. This is the only way in Ada to specify that the
generic only uses assignment. This is, I think, a failing of Ada, but
considering that in 1980 no mainstream languages had any equivalent of
limited types, I can't fault it very much.

-- 
Jeff Carter
"Your mother was a hamster and your father smelt of elderberries."
Monty Python & the Holy Grail

Re: Container reqs

[Ehud Lamm]

I agree with almost all your points.

Indeed we can start with some minimal number of conponents, and build on
from there. I also agree that endless debates, are - well - endless...

My only concern is that without some overall design, you'll end up with a
pile of packages, and not one consistent library.
I want things to compose nicely, and be extendable.

That's also why I agree that debating the various existing libraries, though
educational is not "good for the cause".

Still, I'd feel better with something organised by ADT properties. Thus MAPS
are fine, where as I'd like clarification about Lists. Are we talking
sequential structures, or about the implementation as linked sturctures?

I prefer maps, queues, dequeues etc.

Ehud

Re: Container reqs

[Marin David Condic]

We're probably not far off in terms of goals and objectives. I'd just like
to actually see something emerge from this process that has a concrete
result and a significant benefit to Ada. My fear is that with an informal
sort of process like this, it will drift in too many directions for too long
until eventually interest wanes and we don't see anything come of it. Its a
problem for volunteer projects. If there were a dozen of us getting paid to
do it and we had a deadline, I have every confidence that we'd hammer out
something. As it is (and without some indication of support/endorsement from
vendors) its hard to see a concrete result emerging any time soon.

By "Lists" I have in mind a dynamically allocated, doubly linked list. In my
experience, things like stacks and queues (at least dynamic ones) are just a
subset of calls to a doubly-linked list and so they don't get used much in
practice. (We could debate for hours the relative merits and usefulness of
static/dynamic stacks/queues/lists/double-lists/etc. All that is "nice" and
"interesting" but I think that just getting a doubly-linked-list package
available would probably handle enough practical conditions that it would
get beat to death in normal usage.)

I would note that the MFC basically provides some version of Lists and Maps
and no other particular data structures. (Depending on what arguments one
wants to have about what constitutes a "Data Structure". I'm thinking about
just a general container kind of thing.) Hence getting just that far would
bring us up to par with MSVC++ in that area. Not that I want to duplicate
everything in the MFC, but lots of people write lots of code using it and
they get lots of mileage out of Lists and Maps available to them there. It
isn't *everything* but it is, as I have observed, A Good Start.

Now I can see the point about wanting to get the right concepts together so
that extensions don't start becoming a problem. Should these be generic or
some form of OO Inheritance? (I'm thinking generic for a "basic" set) Should
they have private, limited and/or tagged parameters? (I'd start with "Basic"
as the rule and create variants - make a set with private parameters and
clone them off for limited/tagged usage.)

I'm still hoping to see some support for a basic set of data structures.
Take a look at the standard/semi-standard libraries that come with other
languages or products and you can see signs that they did not start out in
life with "The Grand, Unified, Theory Of Code Libraries" guiding their every
development. Most of them look like they started out small and had branches
and wings added on to them over time. So long as the initial development
doesn't hopelessly hamstring future add-ons, and the initial cut at it
provides some useful, core tools, I'd think we had something O.K. to adopt
and build on.

Heck! I'd get on board with one of the existing packages if there was some
emerging consensus from the users and some buy-in from the compiler writers.
So far, there seems to be neither, so I think it would be better to come up
with some small core of things that *could* be agreed upon as being
generally useful and *might* get some buy-in from the compiler vendors. I
don't know if I'm a lone voice crying out in the wilderness over this or
not. I'd suspect that most Ada users would be happy to see their compiler
come with a library full of stuff they could use with some confidence that
it would be portable to other compilers and didn't require a masters degree
in CS to figure out how to use. I hope we can get that far.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9r9rqj$5dh$1@news.huji.ac.il...
> I agree with almost all your points.
>
> Indeed we can start with some minimal number of conponents, and build on
> from there. I also agree that endless debates, are - well - endless...
>
> My only concern is that without some overall design, you'll end up with a
> pile of packages, and not one consistent library.
> I want things to compose nicely, and be extendable.
>
> That's also why I agree that debating the various existing libraries,
though
> educational is not "good for the cause".
>
> Still, I'd feel better with something organised by ADT properties. Thus
MAPS
> are fine, where as I'd like clarification about Lists. Are we talking
> sequential structures, or about the implementation as linked sturctures?
>
> I prefer maps, queues, dequeues etc.
>
> Ehud
>
>

Re: Container reqs

[Marin David Condic]

One other thought: Perhaps you could lay out a few package-spec-skeletons
that illustrate what you think might make a framework for a consistent
library that could be extended without becoming a pile of packages? I'm
curious to see what you think this might be.

I agree that to the extent possible one package ought to look very similar
to the next so that they all had a consistent flavor. However we also have
to accept the fact that others would come along later with extensions and,
perhaps, better notions of what it should look like & that the library would
grow in somewhat inconsistent directions. Maybe the most we could hope for
would be that each major branch would at least be internally consistent.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9r9rqj$5dh$1@news.huji.ac.il...
> My only concern is that without some overall design, you'll end up with a
> pile of packages, and not one consistent library.
> I want things to compose nicely, and be extendable.

Re: Container reqs

[Barry Kelly]

In article <9qi2c8$gpb$1@nh.pace.co.uk>
	"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>
wrote:

> If you wish to keep the realtime/embedded crowd happy, you need to have
> task-safe versions.

C++ can implement task safety using the RAII (resource aquisition is
initialization) idiom, which eliminates the need for creating a whole
new type for task-safe access to structures.

Why can't Ada do this?

-- Barry

Re: Container reqs

[Marin David Condic]

Well, it can. The thing is you have to ask "What do you mean by task
safety?" For relatively simple subprograms and data, you might get by with
reentrancy and atomic access to global data. For more complex data
structures, you have to protect updates more thoroughly within protected
types. You have to understand the issues surrounding the particular data you
are accessing and the algorithms you are using to access the data. You
either have, or can create mechanisms for handling it - but you need to
understand tasks and protected types.

I am afraid I don't know what the RAII idiom is all about so I don't know if
there is a direct parallel in Ada. But I don't know of any C++ construct
that does a) Tasking and/or b) Protected types so I imagine if you want true
thread safety, you've got to implement some kind of semaphore or locking
mechanism - which can become butt-ugly and lead to some interesting mutex
bugs.

Can you elaborate?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Barry Kelly" <dynagen@eircom.net> wrote in message
news:m7jsttod28l58b9betgcm8n6q5lue6oo5o@4ax.com...
> In article <9qi2c8$gpb$1@nh.pace.co.uk>
> "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>
> wrote:
>
> > If you wish to keep the realtime/embedded crowd happy, you need to have
> > task-safe versions.
>
> C++ can implement task safety using the RAII (resource aquisition is
> initialization) idiom, which eliminates the need for creating a whole
> new type for task-safe access to structures.
>
> Why can't Ada do this?
>
> -- Barry

Re: Container reqs

[Jean-Marc Bourguet]

Barry Kelly <dynagen@eircom.net> writes:

> In article <9qi2c8$gpb$1@nh.pace.co.uk>
> 	"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>
> wrote:
> 
> > If you wish to keep the realtime/embedded crowd happy, you need to have
> > task-safe versions.
> 
> C++ can implement task safety using the RAII (resource aquisition is
> initialization) idiom, which eliminates the need for creating a whole
> new type for task-safe access to structures.
> 
> Why can't Ada do this?

Ada can do it as well as C++ -- see controlled types.  (For cla people
unused to RAII, it is the idiom where the constructor acquire a
ressource and the destructor free it).

But if you want to use it, you have to rely on the user to acquire the
lock, so instead you define a new type providing only protected
operation, like in Ada.

-- 
Jean-Marc

Re: Container reqs

[Marin David Condic]

Seems like that might unreasonably lock up access to some object. Also, it
isn't clear to me how this would make the object task safe? Assume you have
a class that the constructor/destructor acquire some semaphore. It gets
globally declared such that two threads can access its functions. Does each
thread have to check/acquire the semaphore before write operations? Or do
you code a check of the semaphore into all the critical paths? It isn't
clear to me how this is supposed to work....

You could obviously do some sort of acquisition with controlled types - they
provide the same sort of capabilities of constructors/destructors - but why
would you want to if you have protected types?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Jean-Marc Bourguet" <jbourguet@free.fr> wrote in message
news:3bded21b$0$32589$626a54ce@news.free.fr...
>
> Ada can do it as well as C++ -- see controlled types.  (For cla people
> unused to RAII, it is the idiom where the constructor acquire a
> ressource and the destructor free it).
>
> But if you want to use it, you have to rely on the user to acquire the
> lock, so instead you define a new type providing only protected
> operation, like in Ada.
>

Re: Container reqs

[Stephen Leake]

Barry Kelly <dynagen@eircom.net> writes:

> In article <9qi2c8$gpb$1@nh.pace.co.uk>
> 	"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>
> wrote:
> 
> > If you wish to keep the realtime/embedded crowd happy, you need to have
> > task-safe versions.
> 
> C++ can implement task safety using the RAII (resource aquisition is
> initialization) idiom, which eliminates the need for creating a whole
> new type for task-safe access to structures.

It does not "eliminate the need". If _all_ types in the library use
initialization to acquire an appropriate lock, then _all_ types in the
library suffer from that overhead, which can be significant.

The point is to provide types that are as fast as possible, and only
add the task lock overhead if absolutely necessary. Only the user can
tell whether they need the task lock

-- 
-- Stephe

Re: Container reqs

[Simon Wright]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

> Seems like that might unreasonably lock up access to some
> object. Also, it isn't clear to me how this would make the object
> task safe? Assume you have a class that the constructor/destructor
> acquire some semaphore. It gets globally declared such that two
> threads can access its functions. Does each thread have to
> check/acquire the semaphore before write operations? Or do you code
> a check of the semaphore into all the critical paths? It isn't clear
> to me how this is supposed to work....

The BCs use this scheme for the "synchronized" components.

Start with a Monitor, probably but not necessarily one per Container
to be locked. It's probably implemented using a protected type with
Seize and Release.

Now create a (Limited_)Controlled Lock type, constrained by an access
to this Monitor. Its Initialize Seizes the Monitor, and its Finalize
releases it.

  declare
    L : Lock (The_Monitor'access);
  begin
    -- do stuff
  end;

so L's Finalize _will_ get called on exit, and release the Monitor,
even if there's an exception.

With GNAT, you need to add a pragma Warnings (Off, L) because of
course it's not referenced.

Also, you hope that the compiler doesn't optimize L away -- I think
there is an AI which says not to if the type Lock is limited.

And I'm not sure what'll happen with ATC .. deep stuff here.