List Container Strawman 1.4

List Container Strawman 1.4

[Ted Dennison]

I have posted a strawman version 1.4 of the standard Ada List container at
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . 

Changes for this version:

o  The direction enumeration values have been changed to "Head" and "Tail".
o  Direction enumeration parameters have been added to a couple of routines that
were missing them. Most notably, there is now a Direction generic parameter for
the Sorting sub-package.


We seem to be reaching a fair level of maturity with this version. Accordingly,
I'd like to ask if we feel comfortable enough with it to actually progress to
the next step of developing a reference implementation. Does anyone have
problems with taking this step?

---
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: List Container Strawman 1.4

[Brian Hanson]

Ted Dennison<dennison@telepath.com> wrote in message news:<GaVR7.59636$xS6.97761@www.newsranger.com>...
> I have posted a strawman version 1.4 of the standard Ada List container at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . 
> 
> Changes for this version:
> 
> o  The direction enumeration values have been changed to "Head" and "Tail".

How about "At_End" insead of "List_End"

   Procedure Insert (Target : in out List;
      New_Element : in Element;
      At_End : in Direction);
   procedure Remove (Target : in out List;
      Old_Element :    out Element;
      At_End : in Direction)

   Insert(Target => My_List, New_Element => Item, At_End => Tail);

Re: List Container Strawman 1.4

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:GaVR7.59636$xS6.97761@www.newsranger.com...

> I have posted a strawman version 1.4 of the standard Ada List container at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .

This is quite nice in many ways.

> We seem to be reaching a fair level of maturity with this version.
> Accordingly, I'd like to ask if we feel comfortable enough with it
> to actually progress to the next step of developing a reference
> implementation. Does anyone have problems with taking this step?

I'm not convinced that we have quite reached this stage yet.

Ted, what is your opinion of my proposal, please?

--
Best wishes,
Nick Roberts

Re: List Container Strawman 1.4

[Ted Dennison]

In article <9vbc89$eb6li$2@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>Ted, what is your opinion of my proposal, please?

I think that, for the most part, the concerns I expressed in my post about it a
little over 2 weeks ago on the "Standard Queue status thread still hold. I'm
sorry I can't give a link to it, but my newsreader barfs whenever I try. Google
groups's message ID for it is <z9aN7.41127$xS6.69040@www.newsranger.com>. Go to
their advanced group search and enter that in the message ID field.

However, there are some very good ideas in there, most notably the unconstrained
array conversions and the Direction type, that have made their way into the
Strawman.

Excepting the stuff I have raised issues about, is there anything else in there
that you think really needs to be in the Strawman before we proceed?

---
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: List Container Strawman 1.4

[Ted Dennison]

Ted Dennison wrote:

> In article <9vbc89$eb6li$2@ID-25716.news.dfncis.de>, Nick Roberts says...
> 
>>Ted, what is your opinion of my proposal, please?
>>
> 
> I think that, for the most part, the concerns I expressed in my post about it a
> little over 2 weeks ago on the "Standard Queue status thread still hold. I'm
> sorry I can't give a link to it, but my newsreader barfs whenever I try. Google
> groups's message ID for it is <z9aN7.41127$xS6.69040@www.newsranger.com>. Go to


Now that I'm back where I have a real newsreader, a URL for this message 
is 
http://groups.google.com/groups?selm=z9aN7.41127%24xS6.69040%40www.newsranger.com

Re: List Container Strawman 1.4

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:pMoS7.61491$xS6.100531@www.newsranger.com...

> However, there are some very good ideas in there, most notably the
unconstrained
> array conversions and the Direction type, that have made their way into
the
> Strawman.

Ironically, I want to remove the Forward parameters (of type Direction) from
all the operations (and replace the functionality with a 'smart reverse'
operation).

"Ted Dennison" <dennison@telepath.com> wrote in message
news:z9aN7.41127$xS6.69040@www.newsranger.com...

> On the other hand, I'm not a big fan of the iterator approach used. In an
> "unbounded" package, I don't think the user should have to worry about
running
> out of resources like iterators. That sort of breaks the whole "unbounded"
> philosophy.

I've fixed that. For unbounded lists, the user can have up to 255 cursors
(iterators), dynamically allocated, which can be dynamically varied. The
limit of 255 is arbitrary, and could be increased if you think it necessary.

> Also I think there are too many operations in there. The package spec is
huge.
> It has (by my count) 79 subprograms. The current strawman has 34, which to
some
> people it seems is annoyingly small, as we keep seeing suggestions for
> additions. Perhaps in between there somewhere the truth lies.

Ada.Strings.Unbounded has 62. Ada.Text_IO has 113. I would submit that 79 is
not huge, and (like lines or semicolons) is not a very good measure (of
complexity?) anyway. The number of really conceptually different operations
is around 20-30, and most of the concepts not too difficult.

> A large culprit here seems to be the unbounded-array support, which is
probably
> taken a bit too far. Its OK to convert between them, but anything much
more
> should probably be accomplished by first converting the array to a list.
If we
> take Ada.Strings.Unbounded as a model, only the infix operators should
have
> unbounded array equivalents.

The fact that an array version is included for each operation that has a
secondary data parameter is not just nice, it is necessary for the sake of
efficiency. Consider the extra work done by converting the array to a list,
and then applying that list.

"Ted Dennison" <dennison@telepath.com> wrote in message
news:pMoS7.61491$xS6.100531@www.newsranger.com...

> Excepting the stuff I have raised issues about, is there anything else in
there
> that you think really needs to be in the Strawman before we proceed?

I'm afraid I've got quite a few comments on your straw man as it is
currently. Here goes.

[1] I would prefer the name 'Element_Type' to 'Element' for the generic
parameter, since 'Element_Type' is what Ada.Sequential_IO and Ada.Direct_IO
use.

[2] I would prefer a name other than 'List' for the list type, since 'List'
seems to be such a natural name for parameters and objects of a list type
(not necessarily in the list package spec, but elsewhere). If the unbounded
list package is going to be named 'x.Lists.Unbounded', it would seem natural
to use the name 'Unbounded_List' (by analogy to
Ada.Strings.Unbounded.Unbounded_List). I do feel that the need for
consistency outweighs any complaint of wordiness.

[3] Why is Element_Array declared with a Natural index subtype? Wouldn't
Positive be more appropriate?

[4] If you consider their usage, the functions 'To' and 'From' are surely
confusingly named. What is wrong with 'To_List' and 'To_Array' (or similar)?

[5] Analogous to the Ada.Strings.Maps.To_Set function, the function
'Singleton' should be named more like 'To_List' with a parameter named
'Singleton'.

[6] I think it would probably (but not necessarily) be better to have the
list exceptions gathered into the x.Lists parent package, so that there is
only one of each exception (rather than one for each instantiation of
x.Lists.[Unb|B]ounded).

[7] As mentioned, I actually want to remove directional parameters. Instead,
all that is required is a 'smart reverse' operation. This merely switches an
'effective forwardness' flip-flop between actually forward and actually
backward. All the operations must be programmed to behave according to the
effective forwardness (not difficult).

[8] I would much prefer the 'Size' function to be named 'Length'. This would
be much more consistent with the use of the term size in the RM95 (and the
Size attribute), as well as the use of the term length, the Length attribute
of arrays, and the Length functions for Bounded and Unbounded strings.

[9] It would also be more consistent with Ada.Strings.* to use the parameter
name 'Source' rather than 'Subject'. [10] Similarly 'New_Item' rather than
'New_Element' (or 'New_Items'), and [11] 'Is_Null' for the function
'Is_Empty'.

[12] I like the Remove procedure combining retrieval and deletion. This is
an omission from my own proposal. [13] Maybe 'Old_Element' should be
'Old_Item'. ([14] Also, I would prefer the name 'Extract' for the
subprogram.)

Now we come to the vexed issue of iterators.

[13] I have a problem with passive iterators. Texts say that they should be
provided in addition to active iterators, but I rather feel this is like
providing cars with propellors and sails. Passive iterators have various
limitations that active iterators do not: an algorithm that has multiple
(significantly different) behaviour paths between iterations is much easier
to program with an active iterator; an algorithm that works with two or more
read-iterators is in general impossible to program with a passive iterator;
passive iterators do not permit arbitrary restarting; a passive iterator
cannot be a write-iterator. Passive iterators tend to break up the source
code associated with a particular algorithm or work chunk. Finally, a
passive iterator generic procedure can always be (very easily) constructed
from an active iterator. In computer science generally, arguments still rage
about this issue, but I'd give it the chop.

[14] I feel that the term 'iterator' should be reserved for a construct that
is applicable to all container types (and which is therefore monodirectional
and not repositionable, since reverse movement or repositioning would not be
appropriate to most containers), as this is the general use of the term (for
both Ada and other languages). This is why I chose the term 'cursor' (taken
from SQL) instead.

[15] The reason why I made cursors internal to list objects (rather than
providing a separate cursor type) is because an operation on one cursor
(active on a certain list object) must be able to interrogate and possibly
update any other cursors (also active on the same list object). With
separate cursor objects, the only way to do this is for each cursor to
contain a pointer to the list it is active on, and for each list to contain
pointers (perhaps in a linked list) to all the cursors active on it. This
would require the user to declare all list and cursor objects aliased, and
to somehow make the connection between cursor object and list object before
using a cursor. By having its cursors internal to the list object, all of
these inconveniences are removed.

[16] By making my cursors point inbetween items in the list, rather than at
items, various conceptual complications are clarified regarding deletion and
positioning at the end of the list. You do not appear to have adopted this
approach.

[17] My proposal provides a complete set of cursor operations. These include
element and array secondary data parameters. As mentioned, it is necessary
to provide all these operations, since they could not in general (depending
on the details of the implementation) be efficiently implemented otherwise.
[18] I also provide a complete set of absolute operations; I had thought
that it was agreed these were justified (if only just) on the grounds of
convenience. [19] I don't think it would be desirable for any of these
operations to be put into an inner package, because then they wouldn't be
inherited on derivatation of the list type (which is admittedly an unlikely
requirement, but possible).

[18] I have not published it yet, but I am going to add a child package
which provides an active iterator for lists. This iterator is of a type
derived from a container-wide iterator class, and forms part of an iteration
scheme that permits container-independent algorithms. This
container-independence is (according to texts on the subject) supposed to be
an essential aspect of (the advantage of using) iterators (and I agree).

[19] I'm also going to add a child package for sorting. The advantage (not
necessaily overwhelming) of using one of the predefined relative comparison
operators ("<", "<=", ">", ">=") for the ordering function is that you can
declare it "is <>" and save the instantiator having to specify this function
every time.

[20] What does Splice do? Is it useful?

[21] Why do you provide list serialisation (stream read and write)
procedures in public, rather than overriding the Read and Write attributes
of the list type in private?

Your proposal apparently omits the following vital operations: [22] testing
lists for equality; [23] exchanging lists; [24] exchanging two slices of a
list; [25] exchanging two elements of a list; [26] retrieval of a slice;
[27] deletion of a slice; [28] splitting a list into two (especially
destructively for a linked-list implementation).

[29] Although you have put some documentation into the spec as comments, it
is not quite as clear or complete as would be ideal. I think it might be
helpful if this documentation were separated out into a text (or HTML) file.
I must admit, the documentation file (HTML) that I cooked up for my own
proposal needs revision, simplification, and examples.

These points doubtless vary in importance, between 'not at all' to (I think)
'very'. Also, it has been demonstrated that I am not infallible :-) on
numerous occasions :-o ;-) However, I do feel that we are not quite yet at
the stage of going to a sample implementation.

I'm not concerned about whose proposal is developed, and I concede that
consensus means compromise, but I do feel that there are good reasons behind
the design of my proposal. What am I missing? (Apart, that is of course,
from charm, wit, courage, physique, generosity, humour, artistic
sensitivity, any kind of social grace whatsoever, ... ;-)

I really mean it when I say that I feel your input, as well as that of Jeff,
Mark, Stephe, and others, has prevented me from making an almighty cock-up
of the library I was going to (attempt to) build for AdaOS. For that I owe
you immense gratitude anyway. But I'm hoping that we can continue to make
progress together, Ted. After lists, I think we have sets, contars (or
whatever you want to call them), and probably many other things, to tackle.
I'd rather not do this alone.

Any more thoughts on a (better) name for the project? (Does 'Tenet' tickle
you at all?)

--
Best wishes,
Nick Roberts

Server - tasking and long lived connections

[Eric Merritt]

Hello All,

I am in the process of designing a server that will
need to accept long lived (up to several hours) client
connections. The processes themselves will be fairly
I/O bound (database accesses), and at most the number
of processors will be in the range of 2 - 4. The
obvious choice (in my mind) for this is to use a
single task per connection. In this senario, context
switching will not be a major issues due to the length
of the connections. There will be little or no
performance gains by using tasking, but it handles the
long connection times well. 

I do, however, have a few reservations about
scalablity due to OS limitations on the number of
threads per machine and the number of open file
descriptors. Although at first the number of
connections will not be high, it is possible that it
could rapidly need to scale up to a fairly high
number, several hundred or more. This may mean that I
will just have to distribute the app across several
boxs and do some type of mirroring on the databases,
but I want to put that off as long as possible. 

I have quit a bit of experience in code this type of
application but usually with short lived connections
or a low number of total connections. 

Anyway, I am just looking for some one to either point
me in a different direction or confirm my current
approach (one thread per connection).

Thank you for your input.


__________________________________________________
Do You Yahoo!?
Check out Yahoo! Shopping and Yahoo! Auctions for all of
your unique holiday gifts! Buy at http://shopping.yahoo.com
or bid at http://auctions.yahoo.com

Re: Server - tasking and long lived connections

[James Rogers]

Hi Eric.

Which operating system are you targeting for this application?

WinNT easily handles about 2000 of tasks. I do not know the
limits on open file descriptors.

The tasking approach is somewhat more efficient than the traditional
Unix approach of creating a separate process to handle each 
connection. The tasking approach will require the same number
of file descriptors and data base connections. Context switching will
be faster with tasks than with processes.

Which other design approaches would you consider if your operating
system resources are too limited? Would you be able to expand the
system by creating a set of application servers all accessing
a central database through a network? Would you need a system that
performed automatic load balancing across a network?

One advantage of the tasking approach is that you will be able to
create the tasking code as a task type, then create as many 
instances of that task type as you need. From the Ada point of
view this solution is highly scalable.

Jim Rogers

Eric Merritt wrote:
> 
> Hello All,
> 
> I am in the process of designing a server that will
> need to accept long lived (up to several hours) client
> connections. The processes themselves will be fairly
> I/O bound (database accesses), and at most the number
> of processors will be in the range of 2 - 4. The
> obvious choice (in my mind) for this is to use a
> single task per connection. In this senario, context
> switching will not be a major issues due to the length
> of the connections. There will be little or no
> performance gains by using tasking, but it handles the
> long connection times well.
> 
> I do, however, have a few reservations about
> scalablity due to OS limitations on the number of
> threads per machine and the number of open file
> descriptors. Although at first the number of
> connections will not be high, it is possible that it
> could rapidly need to scale up to a fairly high
> number, several hundred or more. This may mean that I
> will just have to distribute the app across several
> boxs and do some type of mirroring on the databases,
> but I want to put that off as long as possible.
> 
> I have quit a bit of experience in code this type of
> application but usually with short lived connections
> or a low number of total connections.
> 
> Anyway, I am just looking for some one to either point
> me in a different direction or confirm my current
> approach (one thread per connection).
> 
> Thank you for your input.
> 
> __________________________________________________
> Do You Yahoo!?
> Check out Yahoo! Shopping and Yahoo! Auctions for all of
> your unique holiday gifts! Buy at http://shopping.yahoo.com
> or bid at http://auctions.yahoo.com

Re: Server - tasking and long lived connections

[Florian Weimer]

James Rogers <jimmaureenrogers@worldnet.att.net> writes:

> The tasking approach is somewhat more efficient than the traditional
> Unix approach of creating a separate process to handle each 
> connection.

For long-living connections, this might not be the case.  It depends
on several factors.  For example, if there isn't much communication
required between the theads of control handling separate connections,
and each thread of control performs many memory allocations and
deallocations, the separate process implementation is probably faster.

> Context switching will be faster with tasks than with processes.

This depends on the OS and Ada implementation.

Re: Server - tasking and long lived connections

[Larry Kilgallen]

In article <mailman.1008382022.25904.comp.lang.ada@ada.eu.org>, Eric Merritt <cyberlync@yahoo.com> writes:

> I do, however, have a few reservations about
> scalablity due to OS limitations on the number of
> threads per machine and the number of open file
> descriptors.

This must enter into your choice of operating system, but I don't
think of the term "file descriptors" as being an Ada phrase.  If
you are limiting your choice to operating systems that use such
a construct, consider whether that is an artificial limit on the
available implementations.

The operating system with which I am most familiar had to increase
the number of simultaneous IO channels available, in recent years.
So not only the operating system but also the version may be important.

In that case, there are also multiple network implementations
available for each of two protocol sets.  These also have different
limitations.

Re: Server - tasking and long lived connections

[Steve Doiel]

I certainly wouldn't rule out a tasking arrangement using one task per N
file descriptors,  where the number of file descriptors handled for each
task is target specific.  I know that the "select" function on some targets
have a limit on the number of file descriptors, while other targets have a
limit on the number of tasks that may be used.

Our applications run on Winows NT 4.0.  We use more than one task for each
connection (input, output and connection maintainence).  We typically have a
few dozen connections.  This implementation proves to be very simple and
easy to maintain.  But you're talking about a lot more connections.

SteveD

"Eric Merritt" <cyberlync@yahoo.com> wrote in message
news:mailman.1008382022.25904.comp.lang.ada@ada.eu.org...
> Hello All,
>
> I am in the process of designing a server that will
> need to accept long lived (up to several hours) client
> connections. The processes themselves will be fairly
> I/O bound (database accesses), and at most the number
> of processors will be in the range of 2 - 4. The
> obvious choice (in my mind) for this is to use a
> single task per connection. In this senario, context
> switching will not be a major issues due to the length
> of the connections. There will be little or no
> performance gains by using tasking, but it handles the
> long connection times well.
>
> I do, however, have a few reservations about
> scalablity due to OS limitations on the number of
> threads per machine and the number of open file
> descriptors. Although at first the number of
> connections will not be high, it is possible that it
> could rapidly need to scale up to a fairly high
> number, several hundred or more. This may mean that I
> will just have to distribute the app across several
> boxs and do some type of mirroring on the databases,
> but I want to put that off as long as possible.
>
> I have quit a bit of experience in code this type of
> application but usually with short lived connections
> or a low number of total connections.
>
> Anyway, I am just looking for some one to either point
> me in a different direction or confirm my current
> approach (one thread per connection).
>
> Thank you for your input.
>
>
> __________________________________________________
> Do You Yahoo!?
> Check out Yahoo! Shopping and Yahoo! Auctions for all of
> your unique holiday gifts! Buy at http://shopping.yahoo.com
> or bid at http://auctions.yahoo.com

Re: List Container Strawman 1.4

[Ted Dennison]

In article <9ve8jn$esilp$1@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>"Ted Dennison" <dennison@telepath.com> wrote in message
>news:z9aN7.41127$xS6.69040@www.newsranger.com...
>
>> "unbounded" package, I don't think the user should have to worry about
>running
>> out of resources like iterators. That sort of breaks the whole "unbounded"
>> philosophy.
>
>I've fixed that. For unbounded lists, the user can have up to 255 cursors
>(iterators), dynamically allocated, which can be dynamically varied. The
>limit of 255 is arbitrary, and could be increased if you think it necessary.

I don't think that really addresses the concern, which is that this isn't really
an "unbounded" approach. Not that I'm a huge fan of the approach the current
strawman uses either. If you've been reading a while, you know I'd lean towards
making the users responsible for iterator safety. But the current approach is
the only one that we have been able to get general agreement on. If you could
convince folks that your (hugely) bounded approach was the way to go, I'd
certianly put that in instead. But so far I see absolutely no sign of that
happening. Not a single other person has come out in support of it in two weeks,
and I see no evidence that this situation would change if we were to delay
things another two weeks.


>The fact that an array version is included for each operation that has a
>secondary data parameter is not just nice, it is necessary for the sake of
>efficiency. Consider the extra work done by converting the array to a list,
>and then applying that list.

That's only an issue if you don't have the Strawman's "Splice" routine.

>I'm afraid I've got quite a few comments on your straw man as it is
>currently. Here goes.
>
>[1] I would prefer the name 'Element_Type' to 'Element' for the generic
>parameter, since 'Element_Type' is what Ada.Sequential_IO and Ada.Direct_IO
>use.

My opinion on the stupidity of "_Type" is probably well known by now. If we were
trying to emulate either of those packages in other ways, or there was a good
case for it possibly causing confusion, then it might be worth using "_Type"
regardless. But I don't believe either is the case here.

>[2] I would prefer a name other than 'List' for the list type, since 'List'
>seems to be such a natural name for parameters and objects of a list type

That issue (type vs. object naming guidelines) has been thouroughly discussed
already a week and a half ago. General names like "List" are for types, while
objects (and parameters) should be named something more specific that designates
either exactly what the object is, or what its role in the system is (eg:
"Target"). This isn't just some rule I made up. The Ada Quality and Style guide
phrases it this way:

* Use singular, general nouns as subtype identifiers. (3.2.2 - Subtype Names)
* Choose identifiers that describe the object's value during execution. (3.2.3 -
Object Names)

You seem to worry that this will cause problems, but we already have a package
spec and it hasn't caused problems that I can see. I'm thinking we can get by
just fine in the body too. Those are the only places it should be an issue, as
everywhere else dot notation can be used to disambiguate.  

>(not necessarily in the list package spec, but elsewhere). If the unbounded
>list package is going to be named 'x.Lists.Unbounded', it would seem natural
>to use the name 'Unbounded_List' (by analogy to
>Ada.Strings.Unbounded.Unbounded_List). I do feel that the need for
>consistency outweighs any complaint of wordiness.

If folks *really* want that, we can do it. But the current difference is quite
conscious. All things being equal, I'm in favor of keeping things consistent as
well. But in this case, all things aren't even close to equal. That naming
system (repeating the package name in the type name) was a tragic mistake, and I
for one am not in favor of spreading the cancer further throughout the standard
libraries in the name of consistency. 

>[3] Why is Element_Array declared with a Natural index subtype? Wouldn't
>Positive be more appropriate?

An oversight. You are quite correct. I'll fix it.

>[4] If you consider their usage, the functions 'To' and 'From' are surely
>confusingly named. What is wrong with 'To_List' and 'To_Array' (or similar)?

That may be a bit of an issue. I general I think things should be named relative
to the package name. If one uses full dot notation, things look great this way.
However, in this case it might be a bit obscure without it:

Foo_List := To (Foo_Items);

and

Foo_Items := From (Foo_List)

The flip answer to this it to use the package names anyway if it doesn't look
clear without them. However, it would perhaps be nice if things aren't quite so
obtuse without them.

>[5] Analogous to the Ada.Strings.Maps.To_Set function, the function
>'Singleton' should be named more like 'To_List' with a parameter named
>'Singleton'.

I could see it as an overload of the "To" function, or whatever we end up naming
it. But its not that big of a deal either way.

>[6] I think it would probably (but not necessarily) be better to have the
>list exceptions gathered into the x.Lists parent package, so that there is
>only one of each exception (rather than one for each instantiation of
>x.Lists.[Unb|B]ounded).

That's most likely true. When we have more than one package we can do that.

>[7] As mentioned, I actually want to remove directional parameters. Instead,
>all that is required is a 'smart reverse' operation. This merely switches an
>'effective forwardness' flip-flop between actually forward and actually
>backward. All the operations must be programmed to behave according to the
>effective forwardness (not difficult).

I'd like to see this, but I should note that the less state-full calls are, the
easier they will be to parralelize. I also get worried whenever I hear anyone
use the word "smart" in the context of a computer program. :-)

(several other parameter naming issues removed)
I'll look into the merits of all these. I don't think we should let parameter
names hold up the works at this point though. We'll never get everyone to agree
that they are all perfect.

>[12] I like the Remove procedure combining retrieval and deletion. This is
>an omission from my own proposal. [13] Maybe 'Old_Element' should be
>'Old_Item'. ([14] Also, I would prefer the name 'Extract' for the
>subprogram.)

I think I like that better too.

>
>Now we come to the vexed issue of iterators.
>
>[13] I have a problem with passive iterators. Texts say that they should be
>provided in addition to active iterators, but I rather feel this is like

Frankly I totally agree with you here. I don't like to use them either. But
several people here do, and were quite insistent that they need to be in there.
Since it doesn't seriously hurt anything to put one in (its not like it has
cascading effects throughout the whole package), I can't really see keeping them
out just because the two of us don't like to use them.

>[14] I feel that the term 'iterator' should be reserved for a construct that
>is applicable to all container types (and which is therefore monodirectional

Since we don't and won't have such a thing, I don't see the sense in reserving
the term for that. 

>[15] The reason why I made cursors internal to list objects (rather than
>providing a separate cursor type) is because an operation on one cursor
>(active on a certain list object) must be able to interrogate and possibly
>update any other cursors (also active on the same list object). With
>separate cursor objects, the only way to do this is for each cursor to
>contain a pointer to the list it is active on, and for each list to contain
>pointers (perhaps in a linked list) to all the cursors active on it. This

That's correct, but what it ultimately requires is that both lists and active
iterators be controlled. I can show the implementation in detail, but the work
required is roughly equivalent to providing a body for this package, which is
what we were discussing doing in the first place.

Fine rationale aside, it appears we have already reached a consensus on using
the controlled iterator approach. The issue under consideration isn't if someone
has another approach which they can argue is better. Clearly you feel you do.
The issue is what we can move forward with. The approach you describe is not
substantially different from the one you presented 2 weeks ago, and the fact of
the matter is that people, for whatever reason, have not been rallying around
it. I don't see any hope in the tide turning in its favor if we wait another 2-4
weeks. 

The strawman has presented 3 different active iterator approaches (each
progressively further from my "ideal" btw). The final one seems to be the one
people want. I'm not nessecarily any happier about that than you are, but that's
the way it has worked out.


>[20] What does Splice do? Is it useful?

See *waaay* previously. I cribbed it from the STL. Its essential for efficiently
putting two lists together.

>
>[21] Why do you provide list serialisation (stream read and write)
>procedures in public, rather than overriding the Read and Write attributes
>of the list type in private?

I've had problems (of an exact nature that I forget) when they were private. So
that's just become my idiom. It could be that the routines could be moved to
just inside of the private section without hurting anything. I'll check it out
when I get a chance.

>Your proposal apparently omits the following vital operations: [22] testing
..
I don't personally consider any of this "vital", and much of it can be done just
fine with an iterator, along with loads of other stuff you haven't thought of
but someone somewhere else considers vital. :-)

The exception is "=", which clearly needs to be redefined or removed. The
default is going to be nonsense.

>[29] Although you have put some documentation into the spec as comments, it
>is not quite as clear or complete as would be ideal. I think it might be
>helpful if this documentation were separated out into a text (or HTML) file.

I agree with this wholeheartedly. I already have one volunteer to work up some
documentation. Unfortunately, he prefers to work in Word instead of HTML(yuk).
But word is (arguably) better than nothing. :-)

You do point out some issues which I think need to be addressed. But the only
ones I'd consider major are issues where it appears we already have a fair
amount of consensus on. The rest is just naming issues.


>Any more thoughts on a (better) name for the project? (Does 'Tenet' tickle
>you at all?)
Perhaps my tonsils a bit. :-)

I'm still stuck on the palindrome issue. Unfortunately, palindromes are one of
the tougher word tricks to work out, so there aren't that many to choose from.
Since Anna is taken, I'd kind of like "ANA" (if someone can get a decent acronym
for it), or "Elle" or "Ele" for personal reasons.

---
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: List Container Strawman 1.4

[Ted Dennison]

In article <3C1D17F5.C980E0E9@otelco.net>, Larry Hazel says...
>
>I thought you could save a Word document as HTML.

You can, but its generally not compliant HTML. Also, I don't think you'd get the
hyperlinks you'd have if you used HTML as the master.

Anyway, that's just one of my pet issues. I don't think its appropriate to use
proprietary file formats for documents meant for public issue. Its fine if you
are just going to use it internally somewhere where you can be sure everyone is
using the right version of the right software. But that's another issue for
another time. I don't want to discourage a volunteer from doing work just to
feed my biases.

---
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: List Container Strawman 1.4

[Florian Weimer]

Ted Dennison<dennison@telepath.com> writes:

> I have posted a strawman version 1.4 of the standard Ada List container at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . 


   -- List <---> Unconstrained array conversions.

   type Element_Array is array (Natural range <>) of Element;

   function To   (Source : Element_Array) return List;
   function From (Source : List) return Element_Array;

What about a generic version of To and From which can handle arrays
with different index types?

   -- Passive iterator. Operation will be applied on each element on the list
   -- Opertion can terminate this process early by setting Quit to True.

   generic
      with procedure Operation (Target : in out Element; Quit : out Boolean);
   procedure Passive_Iterator (Target : in out List);


I'd like to suggest to make Quit mode "in out", with a default of
False.

   -- Sorting sub-package.
   -- To sort in increasing order, use the ">" routine for the Reverse_Order
   -- parameter. To sort in decreasing order, substitute your "<" routine for
   -- the Reverse_Order parameter. :-)

I think the Reverse_Order predicate should be named differently, so
that it's clear from its name that it's a predicate.  "Reverse_Order"
could also mean "Reverse the order of the elments.", not just "Are
these elements in reversed order?".

Re: List Container Strawman 1.4

[Darren New]

Ted Dennison wrote:
> Anyway, that's just one of my pet issues. I don't think its appropriate to use
> proprietary file formats for documents meant for public issue. Its fine if you
> are just going to use it internally somewhere where you can be sure everyone is
> using the right version of the right software. But that's another issue for
> another time. I don't want to discourage a volunteer from doing work just to
> feed my biases.

Actually, I find it easiest to do the initial documentation using an
actual word processor, then cut-and-paste into a more primitive format.
I suggest the RFC2196 XML format, with processors available at
xml.resource.org (or maybe beepcore.org) for translation to plain text,
html, nroff, etc.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List Container Strawman 1.4

[Ted Dennison]

In article <87heqs5awc.fsf@deneb.enyo.de>, Florian Weimer says...
>
>   type Element_Array is array (Natural range <>) of Element;
>
>   function To   (Source : Element_Array) return List;
>   function From (Source : List) return Element_Array;
>
>What about a generic version of To and From which can handle arrays
>with different index types?

I think the proper way to give that level of flexability would be to make the
array itself a generic parameter to the package. In my opinion, that's just one
bridge too far.

>   generic
>      with procedure Operation (Target : in out Element; Quit : out Boolean);
>   procedure Passive_Iterator (Target : in out List);
>
>
>I'd like to suggest to make Quit mode "in out", with a default of
>False.

Arrg! That had already been agreed to. I just forgot to put it in. Good catch.

>I think the Reverse_Order predicate should be named differently, so
>that it's clear from its name that it's a predicate.  "Reverse_Order"
>could also mean "Reverse the order of the elments.", not just "Are
>these elements in reversed order?".

That's a good point. The only other thing I can think of at the moment though
is "Out_Of_Order", which has other unfortunate connotations. :-)

---
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: List Container Strawman 1.4

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:koOS7.73$XC5.37@www.newsranger.com...

> >I've fixed that. For unbounded lists, the user can have up to 255 cursors
> >(iterators), dynamically allocated, which can be dynamically varied. The
> >limit of 255 is arbitrary, and could be increased if you think it
necessary.
>
> I don't think that really addresses the concern, which is that this isn't
really
> an "unbounded" approach.

Ted, what are you getting at, really? I don't give a flying Dan Quail
whether it is or isn't, in some higher Zen way, an unbounded approach. Isn't
the point simply that the user can have as many cursors (iterators) as she
requires?

> Not that I'm a huge fan of the approach the current
> strawman uses either. If you've been reading a while, you know I'd lean
towards
> making the users responsible for iterator safety. But the current approach
is
> the only one that we have been able to get general agreement on.

Frankly, I'm more interested in getting your agreement than anyone else's
(at this point). Are you saying you personally favour my approach? Since it
looks like we two are going to be producing this facility, who else has a
more important opinion? If other people don't like it, it's up to them to
make a noise.

> If you could
> convince folks that your (hugely) bounded approach was the way to go, I'd
> certianly put that in instead. But so far I see absolutely no sign of that
> happening. Not a single other person has come out in support of it in two
weeks,
> and I see no evidence that this situation would change if we were to delay
> things another two weeks.

On the other hand, why don't we do it my way, and see how many people
complain? I don't think anyone actually would.

> >The fact that an array version is included for each operation that has a
> >secondary data parameter is not just nice, it is necessary for the sake
of
> >efficiency. Consider the extra work done by converting the array to a
list,
> >and then applying that list.
>
> That's only an issue if you don't have the Strawman's "Splice" routine.

I don't think so. I can see it helps for insertion, but not for replacement.
Besides which, you seem to be advocating making a user do this:

   declare
      Temp: x.List := To(("Alice","Jenny","Frida"));
      It: Iterator := Side(Invitees,Back);
   begin
      Splice(Temp,It);
   end;

when my package would permit:

   Append(Invitees,("Alice","Jenny","Frida"));

You've got to admit, the latter is a bit easier, huh?

> >[1] I would prefer the name 'Element_Type' to 'Element' for the generic
> >parameter, since 'Element_Type' is what Ada.Sequential_IO and
Ada.Direct_IO
> >use.
>
> My opinion on the stupidity of "_Type" is probably well known by now. If
we were
> trying to emulate either of those packages in other ways, or there was a
good
> case for it possibly causing confusion, then it might be worth using
"_Type"
> regardless. But I don't believe either is the case here.

I agree it's stupid, but if we start trying to correct all the stupid things
in Ada, we might just as well start inventing a new language. I really think
most users are not going to say "Oh goody, how great that they changed all
the naming conventions to something better!". I think most would say "Oh
******* ****, they've changed all the ******* naming conventions to
something different to the rest of Ada!" Specifically, if the name 'Element'
is used for the data type (instead of 'Element_Type') that means the
function which retrieves an element cannot be named 'Element', which is the
name of the analogous function in Ada.Strings.*ounded.

> >[2] I would prefer a name other than 'List' for the list type, since
'List'
> >seems to be such a natural name for parameters and objects of a list type
>
> That issue (type vs. object naming guidelines) has been thouroughly
discussed
> already a week and a half ago. General names like "List" are for types,
while
> objects (and parameters) should be named something more specific that
designates
> either exactly what the object is, or what its role in the system is (eg:
> "Target"). This isn't just some rule I made up. The Ada Quality and Style
guide
> phrases it this way:
>
> * Use singular, general nouns as subtype identifiers. (3.2.2 - Subtype
Names)
> * Choose identifiers that describe the object's value during execution.
(3.2.3 -
> Object Names)
>
> You seem to worry that this will cause problems, but we already have a
package
> spec and it hasn't caused problems that I can see. I'm thinking we can get
by
> just fine in the body too. Those are the only places it should be an
issue, as
> everywhere else dot notation can be used to disambiguate.

Nicely argued, and I concede. Type names such as 'List', 'Set', and 'Contar'
(or 'Lookup'?) are reasonably appropriate in a generic package, since they
will indeed tend to be either qualified or renamed (by a subtype
declaration).

> >[4] If you consider their usage, the functions 'To' and 'From' are surely
> >confusingly named. What is wrong with 'To_List' and 'To_Array' (or
similar)?
>
> That may be a bit of an issue. I general I think things should be named
relative
> to the package name. If one uses full dot notation, things look great this
way.
> However, in this case it might be a bit obscure without it:
>
> Foo_List := To (Foo_Items);
>
> and
>
> Foo_Items := From (Foo_List)
>
> The flip answer to this it to use the package names anyway if it doesn't
look
> clear without them. However, it would perhaps be nice if things aren't
quite so
> obtuse without them.

   Foo_List  := To_List  (Foo_Items);
   Foo_Items := To_Array (Foo_List);

This seems a lot better to me.

   Foo_List  := Foo_Lists.To_List  (Foo_Items);
   Foo_Items := Foo_Lists.To_Array (Foo_List);

And this is perfectly okay, isn't it?

> >[5] Analogous to the Ada.Strings.Maps.To_Set function, the function
> >'Singleton' should be named more like 'To_List' with a parameter named
> >'Singleton'.
>
> I could see it as an overload of the "To" function, or whatever we end up
naming
> it. But its not that big of a deal either way.

So is that a "yes" then? ;-)

> >[6] I think it would probably (but not necessarily) be better to have the
> >list exceptions gathered into the x.Lists parent package, so that there
is
> >only one of each exception (rather than one for each instantiation of
> >x.Lists.[Unb|B]ounded).
>
> That's most likely true. When we have more than one package we can do
that.

No time like the present. Let's do it now.

> >[7] As mentioned, I actually want to remove directional parameters.
Instead,
> >all that is required is a 'smart reverse' operation. This merely switches
an
> >'effective forwardness' flip-flop between actually forward and actually
> >backward. All the operations must be programmed to behave according to
the
> >effective forwardness (not difficult).
>
> I'd like to see this,

All that is required is that the pair of pointers in each node, cursor, and
the base, are made into a duple (array):

   type Direction is (Forward, Backward);
   type Ref_Pair is array (Direction) of Node_Ref;

Then the base has a component that indicates the current 'sense' of the
list:

   EF: Direction; -- Effective Forward

All operations then simply refer to L.Ref(L.EF) to get the 'current forward'
node pointer, and L.Ref(Opposite(L.EF)) to get the 'current backward' one.
(of course, one might have two components, EF and EB.) To apparently reverse
the list, all you do is reverse (set to its opposite) EF (and EB).

> but I should note that the less state-full calls are, the
> easier they will be to parralelize.

Fair point in general, but I think you will find that it is very rare, in
practice, for a list to be operated on in parallel (conversely, a slightly
different idiom, the queue, is used almost exclusively in parallel). By
contrast, sets and contars (and others) are often used in parallel. It's one
of those little oddities.

> I also get worried whenever I hear anyone
> use the word "smart" in the context of a computer program. :-)

You're quite right there, of course! It's only one short step away from
artificial intelligence, and we all know where that leads to. :-)

> (several other parameter naming issues removed)
> I'll look into the merits of all these. I don't think we should let
parameter
> names hold up the works at this point though. We'll never get everyone to
agree
> that they are all perfect.

As I say, never mind anyone else. Let's agree between ourselves, and let's
do it now (it's easier that way).

> >[13] I have a problem with passive iterators. Texts say that they should
be
> >provided in addition to active iterators, but I rather feel this is like
>
> Frankly I totally agree with you here. I don't like to use them either.
But
> several people here do, and were quite insistent that they need to be in
there.
> Since it doesn't seriously hurt anything to put one in (its not like it
has
> cascading effects throughout the whole package), I can't really see
keeping them
> out just because the two of us don't like to use them.

Reluctuantly accepted.

> >[14] I feel that the term 'iterator' should be reserved for a construct
that
> >is applicable to all container types (and which is therefore
monodirectional
>
> Since we don't and won't have such a thing, I don't see the sense in
reserving
> the term for that.

This is extremely important, to me. Could you explain why you don't want
container-wide iterators? It seems like a bizarre attitude, to be frank.
Remember, the STL iterators are all container-wide, and I believe this was a
fundamental design decision.

> >[15] The reason why I made cursors internal to list objects (rather than
> >providing a separate cursor type) is because an operation on one cursor
> >(active on a certain list object) must be able to interrogate and
possibly
> >update any other cursors (also active on the same list object). With
> >separate cursor objects, the only way to do this is for each cursor to
> >contain a pointer to the list it is active on, and for each list to
contain
> >pointers (perhaps in a linked list) to all the cursors active on it. This
>
> That's correct, but what it ultimately requires is that both lists and
active
> iterators be controlled. I can show the implementation in detail, but the
work
> required is roughly equivalent to providing a body for this package, which
is
> what we were discussing doing in the first place.

I don't think this issue really has anything to do with controlledness
(although the two issues do touch upon one another, they do so only
incidentally). Again, it sounds like you are actually agreeing with me. Are
you?

> Fine rationale aside, it appears we have already reached a consensus on
using
> the controlled iterator approach. The issue under consideration isn't if
someone
> has another approach which they can argue is better. Clearly you feel you
do.
> The issue is what we can move forward with. The approach you describe is
not
> substantially different from the one you presented 2 weeks ago, and the
fact of
> the matter is that people, for whatever reason, have not been rallying
around
> it. I don't see any hope in the tide turning in its favor if we wait
another 2-4
> weeks.

Again, why don't we do it my way, and see how many other people complain?

> The strawman has presented 3 different active iterator approaches (each
> progressively further from my "ideal" btw). The final one seems to be the
one
> people want. I'm not nessecarily any happier about that than you are, but
that's
> the way it has worked out.

So, go for a design you are happier about! :-)

> >[20] What does Splice do? Is it useful?
>
> See *waaay* previously. I cribbed it from the STL. Its essential for
efficiently
> putting two lists together.

Aha! A destructive insert. Handy. (Added to my package ;-)

> >[21] Why do you provide list serialisation (stream read and write)
> >procedures in public, rather than overriding the Read and Write
attributes
> >of the list type in private?
>
> I've had problems (of an exact nature that I forget) when they were
private. So
> that's just become my idiom. It could be that the routines could be moved
to
> just inside of the private section without hurting anything. I'll check it
out
> when I get a chance.

All you have to do is declare in the private part:

   type List is new Ada.Finalization.Controlled with
      record
         ...
      end record;

   procedure Read_List (
         Stream : access Ada.Streams.Root_Stream_Type'Class;
         Item   :    out List );

   procedure Write_List (
         Stream : access Ada.Streams.Root_Stream_Type'Class;
         Item   : in     List );

   for List'Read  use Read_List;
   for List'Write use Write_List;

and then provide bodies for Read_List and Write_List in the package body.
Job done and dusted.

> >Your proposal apparently omits the following vital operations: [22]
testing
> ..
> I don't personally consider any of this "vital", and much of it can be
done just
> fine with an iterator, along with loads of other stuff you haven't thought
of
> but someone somewhere else considers vital. :-)

I readily agree with the point that one could indeed go on and on forever
adding useful operations. But you are wrong that the operations I mentioned
can be done "perfectly well" with an iterator. They cannot: the equivalent
operations done with an iterator would be significantly less efficient (as
well as less convenient).

> >[29] Although you have put some documentation into the spec as comments,
it
> >is not quite as clear or complete as would be ideal. I think it might be
> >helpful if this documentation were separated out into a text (or HTML)
file.
>
> I agree with this wholeheartedly. I already have one volunteer to work up
some
> documentation. Unfortunately, he prefers to work in Word instead of
HTML(yuk).
> But word is (arguably) better than nothing. :-)

Splendid.

> You do point out some issues which I think need to be addressed. But the
only
> ones I'd consider major are issues where it appears we already have a fair
> amount of consensus on. The rest is just naming issues.

Well, to recap: I think the most important consensus is between us two (at
the moment); I think naming issues are pretty important (but true everything
is relative); I think it's important to pin down the spec as best we can
early on, so as not to give the documentor a moving target, and so as not to
give ourselves a moving target writing the sample implementation.

> >Any more thoughts on a (better) name for the project? (Does 'Tenet'
tickle
> >you at all?)
> Perhaps my tonsils a bit. :-)
>
> I'm still stuck on the palindrome issue. Unfortunately, palindromes are
one of
> the tougher word tricks to work out, so there aren't that many to choose
from.
> Since Anna is taken, I'd kind of like "ANA" (if someone can get a decent
acronym
> for it), or "Elle" or "Ele" for personal reasons.

Extended Language Library Endeavour (ELLE) would be fine by me (base package
name 'Elle'). Pretty good, really.

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

--
Best wishes,
Nick Roberts

Re: List Container Strawman 1.4

[Larry Hazel]

Ted Dennison wrote:
> 
> I agree with this wholeheartedly. I already have one volunteer to work up some
> documentation. Unfortunately, he prefers to work in Word instead of HTML(yuk).
> But word is (arguably) better than nothing. :-)

I thought you could save a Word document as HTML.

> >Any more thoughts on a (better) name for the project? (Does 'Tenet' tickle
> >you at all?)
> Perhaps my tonsils a bit. :-)
> 
> I'm still stuck on the palindrome issue. Unfortunately, palindromes are one of
> the tougher word tricks to work out, so there aren't that many to choose from.
> Since Anna is taken, I'd kind of like "ANA" (if someone can get a decent acronym
> for it), or "Elle" or "Ele" for personal reasons.

Ada's Next Annes :-)

Larry

Re: List Container Strawman 1.4

[Mark Lundquist]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message
news:87heqs5awc.fsf@deneb.enyo.de...
> Ted Dennison<dennison@telepath.com> writes:
>
> > I have posted a strawman version 1.4 of the standard Ada List container
at
> > http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
.
>
>
>    -- List <---> Unconstrained array conversions.
>
>    type Element_Array is array (Natural range <>) of Element;
>
>    function To   (Source : Element_Array) return List;
>    function From (Source : List) return Element_Array;
>
> What about a generic version of To and From which can handle arrays
> with different index types?

Interesting idea, but I doubt if it would be useful enough to be justified.
A list abstraction of this sort is unbounded, and since the only reason you
would convert To it from one of these things with a non-integer index type
would be to convert From the list back to it again, you're not going to be
adding or deleting elements... using a list this way (e.g. to find or sort)
is quite roundabout, it would be much better to have a Fixed variant of the
sequence abstraction.

'To' is probably much more useful than 'From', in any case (you can use an
aggregate notation to initialize your list).

>
>    -- Passive iterator. Operation will be applied on each element on the
list
>    -- Opertion can terminate this process early by setting Quit to True.
>
>    generic
>       with procedure Operation (Target : in out Element; Quit : out
Boolean);
>    procedure Passive_Iterator (Target : in out List);
>
>
> I'd like to suggest to make Quit mode "in out", with a default of
> False.

There are no defaults for anything other than an "in" mode parameter.

>
>    -- Sorting sub-package.
>    -- To sort in increasing order, use the ">" routine for the
Reverse_Order
>    -- parameter. To sort in decreasing order, substitute your "<" routine
for
>    -- the Reverse_Order parameter. :-)
>
> I think the Reverse_Order predicate should be named differently, so
> that it's clear from its name that it's a predicate.  "Reverse_Order"
> could also mean "Reverse the order of the elments.", not just "Are
> these elements in reversed order?".

I must say I don't care much for these attempts to avoid using a relational
operator for the predicate ("Swap", "Reverse_Order").  They are a case of
the cure being worse than the disease.  Besides being obtuse and
bletcherous, they lack the notational convenience provided by a relational
operator with a box (<>) default.

-- mark

Re: Server - tasking and long lived connections

[Thierry Lelegard]

We have applications that we successfully tested with up to 6000 tasks.
That was on OpenVMS with the DEC Ada compiler. We now use GNAT on
VMS/UNIX/WNT. We haven't yet made such load testing but several hundredths
of tasks run fine.

On most operating systems, though, this requires some tuning (memory
management, I/O, etc).

I think that the trap in this kind of applications (servers with one
or more tasks per client connection) is the fate of the tasks when
the client disconnects. If you let the tasks die and recreate new
tasks for new client connections, you will most certainly face some
slow memory leak. We have seen that, although the stack itself is
deallocated when a task dies, there aer a few bytes which remain
allocated (some kind of TCB I suppose).

So, the trick is to never let the service tasks die. When a client
disconnects, just queue the service task for future usage by a new
client connection. When a new connection comes in, reuse an idle
service task. Create a new one only when there is no available
idle task.

Of course, if you connection are long lived (several hours) and your
application is relatively short lived (a few weeks), this may not
be an issue. But if you want your application to potentially run
forever, you should take care.

In the (long) past, I have seen a Minitel server (French ancestor
of the WWW) crashing every 3 months, due to virtual memory exhaustion,
just because the Ada tasks died when the clients disconnected.

-Thierry
____________________________________________________________________________

Thierry Lelegard, "The Jazzing Troll", Email: thierry.lelegard@canal-plus.fr
CANAL+ Technologies, 34 place Raoul Dautry, 75906 Paris Cedex 15, France
Tel: +33 1 71 71 54 30   Fax: +33 1 71 71 52 08   Mobile: +33 6 03 00 65 75
____________________________________________________________________________

Re: Server - tasking and long lived connections

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 879 bytes --]


"Thierry Lelegard" <thierry.lelegard@canal-plus.fr> a �crit dans le message news: 3C1DB7B7.DF767F9@canal-plus.fr...
> I think that the trap in this kind of applications (servers with one
> or more tasks per client connection) is the fate of the tasks when
> the client disconnects. If you let the tasks die and recreate new
> tasks for new client connections, you will most certainly face some
> slow memory leak. We have seen that, although the stack itself is
> deallocated when a task dies, there aer a few bytes which remain
> allocated (some kind of TCB I suppose).
>
This was due to the (in)famous Rosen's pathology ;-)
It has been (fortunately) exterminated in in Ada 95, so the problem should not appear any more.

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

Re: Server - tasking and long lived connections

[Thierry Lelegard]

Jean-Pierre Rosen wrote :
> 
> "Thierry Lelegard" <thierry.lelegard@canal-plus.fr> a �crit dans le message news: 3C1DB7B7.DF767F9@canal-plus.fr...
> > I think that the trap in this kind of applications (servers with one
> > or more tasks per client connection) is the fate of the tasks when
> > the client disconnects. If you let the tasks die and recreate new
> > tasks for new client connections, you will most certainly face some
> > slow memory leak. We have seen that, although the stack itself is
> > deallocated when a task dies, there aer a few bytes which remain
> > allocated (some kind of TCB I suppose).
> >
> This was due to the (in)famous Rosen's pathology ;-)
> It has been (fortunately) exterminated in in Ada 95, so the problem should not appear any more.

Quite interesting. Could you elaborate on this? What kind of change was
introduced in Ada95 to eliminate this?

-Thierry
____________________________________________________________________________

Thierry Lelegard, "The Jazzing Troll", Email: thierry.lelegard@canal-plus.fr
CANAL+ Technologies, 34 place Raoul Dautry, 75906 Paris Cedex 15, France
Tel: +33 1 71 71 54 30   Fax: +33 1 71 71 52 08   Mobile: +33 6 03 00 65 75
____________________________________________________________________________

Re: Server - tasking and long lived connections

[Larry Kilgallen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 966 bytes --]

In article <9vkecb$a6v$1@s1.read.news.oleane.net>, "Jean-Pierre Rosen" <rosen@adalog.fr> writes:
> 
> "Thierry Lelegard" <thierry.lelegard@canal-plus.fr> a �crit dans le message news: 3C1DB7B7.DF767F9@canal-plus.fr...
>> I think that the trap in this kind of applications (servers with one
>> or more tasks per client connection) is the fate of the tasks when
>> the client disconnects. If you let the tasks die and recreate new
>> tasks for new client connections, you will most certainly face some
>> slow memory leak. We have seen that, although the stack itself is
>> deallocated when a task dies, there aer a few bytes which remain
>> allocated (some kind of TCB I suppose).
>>
> This was due to the (in)famous Rosen's pathology ;-)
> It has been (fortunately) exterminated in in Ada 95, so the problem should not appear any more.

Does the standard mandate that such a problem not happen,
or simply avoid mandating something that would force it to happen?

Re: Server - tasking and long lived connections

[Pat Rogers]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1535 bytes --]


"Larry Kilgallen" <Kilgallen@SpamCop.net> wrote in message
news:YaH+t3eYcXsB@eisner.encompasserve.org...
> In article <9vkecb$a6v$1@s1.read.news.oleane.net>, "Jean-Pierre Rosen"
<rosen@adalog.fr> writes:
> >
> > "Thierry Lelegard" <thierry.lelegard@canal-plus.fr> a �crit dans le
message news: 3C1DB7B7.DF767F9@canal-plus.fr...
> >> I think that the trap in this kind of applications (servers with one
> >> or more tasks per client connection) is the fate of the tasks when
> >> the client disconnects. If you let the tasks die and recreate new
> >> tasks for new client connections, you will most certainly face some
> >> slow memory leak. We have seen that, although the stack itself is
> >> deallocated when a task dies, there aer a few bytes which remain
> >> allocated (some kind of TCB I suppose).
> >>
> > This was due to the (in)famous Rosen's pathology ;-)
> > It has been (fortunately) exterminated in in Ada 95, so the problem
should not appear any more.
>
> Does the standard mandate that such a problem not happen,
> or simply avoid mandating something that would force it to happen?

It is solved indirectly because functions can no longer return limited types
(eg task types) by-value.  (A nice simple rule that solves a number of
issues.)

---
Patrick Rogers                       Consulting and Training in:
http://www.classwide.com          Real-Time/OO Languages
progers@classwide.com               Hard Deadline Schedulability Analysis
(281)648-3165                                 Software Fault Tolerance

Re: Server - tasking and long lived connections

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1931 bytes --]


"Thierry Lelegard" <thierry.lelegard@canal-plus.fr> a �crit dans le message news: 3C1DC5ED.9E9F11F1@canal-plus.fr...
> Jean-Pierre Rosen wrote :
> >
> > "Thierry Lelegard" <thierry.lelegard@canal-plus.fr> a �crit dans le message news: 3C1DB7B7.DF767F9@canal-plus.fr...
> > > I think that the trap in this kind of applications (servers with one
> > > or more tasks per client connection) is the fate of the tasks when
> > > the client disconnects. If you let the tasks die and recreate new
> > > tasks for new client connections, you will most certainly face some
> > > slow memory leak. We have seen that, although the stack itself is
> > > deallocated when a task dies, there aer a few bytes which remain
> > > allocated (some kind of TCB I suppose).
> > >
> > This was due to the (in)famous Rosen's pathology ;-)
> > It has been (fortunately) exterminated in in Ada 95, so the problem should not appear any more.
>
> Quite interesting. Could you elaborate on this? What kind of change was
> introduced in Ada95 to eliminate this?
>
Here is (was) the problem:

task type TT is....

function F return TT is
   Local : tt;
begin
   return Local;
end F;

....

if F'Terminated then..... -- Allways true

The master of Local is function F; but since it is returned by the function, it is still possible to access the task object after
the scope of its master has been left (although the task will allways be terminated); hence the need to keep a minimum information,
and since the master is left, there is no logical place where that information can be reclaimed.

In Ada 95, a task type is a by-reference type (6.2(6)), and a function is not allowed to return a local object of a by-reference
type (6.5(18)). Therefore, the above program will raise Program_Error (6.5(20)).

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

Re: List Container Strawman 1.4

[Larry Kilgallen]

In article <87k7vkxkdw.fsf@deneb.enyo.de>, Florian Weimer <fw@deneb.enyo.de> writes:
> "Mark Lundquist" <no.spam@getalife.com> writes:
> 
>>> What about a generic version of To and From which can handle arrays
>>> with different index types?
>>
>> Interesting idea, but I doubt if it would be useful enough to be justified.
>> A list abstraction of this sort is unbounded, and since the only reason you
>> would convert To it from one of these things with a non-integer index type
>> would be to convert From the list back to it again, you're not going to be
>> adding or deleting elements...
> 
> Some people like to have different integer types for different things.

Absolutely !!!

Re: List Container Strawman 1.4

[Florian Weimer]

"Mark Lundquist" <no.spam@getalife.com> writes:

>> What about a generic version of To and From which can handle arrays
>> with different index types?
>
> Interesting idea, but I doubt if it would be useful enough to be justified.
> A list abstraction of this sort is unbounded, and since the only reason you
> would convert To it from one of these things with a non-integer index type
> would be to convert From the list back to it again, you're not going to be
> adding or deleting elements...

Some people like to have different integer types for different things.

I think the simple way of introducing new integer types is one of the
nice benefits of Ada, and packages for general use should not remove
this benifit.

>> I'd like to suggest to make Quit mode "in out", with a default of
>> False.
>
> There are no defaults for anything other than an "in" mode parameter.

You can supply defaults even without default_expressions.  In this
case, simply assign the variable in the caller, before the call.

Re: List Container Strawman 1.4

[Mark Lundquist]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message
news:87k7vkxkdw.fsf@deneb.enyo.de...
> "Mark Lundquist" <no.spam@getalife.com> writes:
>
> >> What about a generic version of To and From which can handle arrays
> >> with different index types?
> >
> > Interesting idea, but I doubt if it would be useful enough to be
justified.
> > A list abstraction of this sort is unbounded, and since the only reason
you
> > would convert To it from one of these things with a non-integer index
type
> > would be to convert From the list back to it again, you're not going to
be
> > adding or deleting elements...
>
> Some people like to have different integer types for different things.

Whups, my bad... I was thinking just of enumeration types...

> >
> > There are no defaults for anything other than an "in" mode parameter.
>
> You can supply defaults even without default_expressions.  In this
> case, simply assign the variable in the caller, before the call.

Oh, I see what you mean.

-- mark

Re: List Container Strawman 1.4

[Nick Roberts]

I think this requirement can be solved by adding a generic child.


   generic
      type Alternate_Index is (<>);
      type Alternate_Array is array (Alternate_Index range <>) of
Element_Type;

   package x.Lists.Unbounded.Array_Conversion is

      function To_Alternate (Item:  in Element_Array;
                             First: in Alternate_Index :=
Alternate_Index'First)
        return Alternate_Array;

      function From_Alternate (Item:  in Alternate_Array;
                               First: in Positive := 1)
        return Element_Array;
   end;


and the same for Bounded.

--
Best wishes,
Nick Roberts

Re: Server - tasking and long lived connections

[Matthew Heaney]

"Eric Merritt" <cyberlync@yahoo.com> wrote in message
news:mailman.1008382022.25904.comp.lang.ada@ada.eu.org...
> Anyway, I am just looking for some one to either point
> me in a different direction or confirm my current
> approach (one thread per connection).

One thread per connection cannot possibly scale well.  It is the *wrong* way
to implement a server.

Our RTSP video server uses WinNT I/O completion ports, so that a small
number of tasks (threads) can service hundreds (or even thousands) of client
connections.

Re: Server - tasking and long lived connections

[Eric Merritt]

> One thread per connection cannot possibly scale
> well.  It is the *wrong* way
> to implement a server.
> 
> Our RTSP video server uses WinNT I/O completion
> ports, so that a small
> number of tasks (threads) can service hundreds (or
> even thousands) of client
> connections.

Actually after thinking about it I agree with you.
Though the connections are long lived (on the order of
several hours) that doesn't really remove the
usefulness of a thread pool, it just makes it less
valuable. It makes it less valuable because context
switching takes up a much smaller percentage of
overall run time. Even in this case a thread pool is
still a good idea.


__________________________________________________
Do You Yahoo!?
Check out Yahoo! Shopping and Yahoo! Auctions for all of
your unique holiday gifts! Buy at http://shopping.yahoo.com
or bid at http://auctions.yahoo.com

Re: List Container Strawman 1.4

[Ted Dennison]

I'm sorry I'm so tardy in replying to this. I got busy doing XMas stuff.

In article <9viq4m$fjbkr$1@ID-25716.news.dfncis.de>, Nick Roberts says...
>On the other hand, why don't we do it my way, and see how many people
>complain? I don't think anyone actually would.

The current iterator implementation is the way that was requested by several
people. I'm not going to change it again unless I get a feel that the consensus
is for it to be changed.

So far I've bascily got one "yes" vote for moving on, and one emphatic "no". So
I'll do a bit more work on it and try again...

---
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: List Container Strawman 1.4

[Marin David Condic]

You've got my (emphatic) "Yes" vote.

BTW: I'm looking at the code & hacking some little demos just to understand
how it will work. What I seem to be missing is some kind of destructor. Some
version of "procedure Destroy (Target : in out List) ;" seems like it would
be in order. Or do you have some other preferred method of clearing out a
list? (I'd rather not iterate over the list and remove the elements
individually just to clear a list prior to its next usage...)

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:UVIU7.6899$XC5.8894@www.newsranger.com...
>
> The current iterator implementation is the way that was requested by
several
> people. I'm not going to change it again unless I get a feel that the
consensus
> is for it to be changed.
>
> So far I've bascily got one "yes" vote for moving on, and one emphatic
"no". So
> I'll do a bit more work on it and try again...
>

Re: List Container Strawman 1.4

[Marin David Condic]

One other thing: If we are moving towards a first-cut implementation, I
think we need to pick some kind of acronym to be the "Root" package from
which all this stuff will emanate. I'd go for ACL - Ada Component Library -
as being short & sweet and to the point. Hence, we'd have
ACL.Containers.Lists.Unbounded as our first component.

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:UVIU7.6899$XC5.8894@www.newsranger.com...
>
> So far I've bascily got one "yes" vote for moving on, and one emphatic
"no". So
> I'll do a bit more work on it and try again...
>

Re: List Container Strawman 1.4

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> So far I've bascily got one "yes" vote for moving on, and one emphatic "no". So
> I'll do a bit more work on it and try again...

I think it's time for an implementation. I'll be off the next couple
of weeks; I'll see if I can implement the strawman as a wrapper around
SAL lists.


-- 
-- Stephe

Re: List Container Strawman 1.4

[Ted Dennison]

In article <9vvopp$gm2$1@nh.pace.co.uk>, Marin David Condic says...
>BTW: I'm looking at the code & hacking some little demos just to understand
>how it will work. What I seem to be missing is some kind of destructor. Some
>version of "procedure Destroy (Target : in out List) ;" seems like it would
>be in order. Or do you have some other preferred method of clearing out a
>list? (I'd rather not iterate over the list and remove the elements
>individually just to clear a list prior to its next usage...)

When do you need to actually deal with a null list? If its just a matter of
reusing the list object for a new set of values, then you can do that by using
one of the constructor functions.

---
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: List Container Strawman 1.4

[Ted Dennison]

In article <9vvpc9$gud$1@nh.pace.co.uk>, Marin David Condic says...
>
>One other thing: If we are moving towards a first-cut implementation, I
>think we need to pick some kind of acronym to be the "Root" package from
>which all this stuff will emanate. I'd go for ACL - Ada Component Library -
>as being short & sweet and to the point. Hence, we'd have
>ACL.Containers.Lists.Unbounded as our first component.

A point of order: The ACL would actually replace the "Containers" part.
"Containers" was my placeholder root name.

As for the name itself, ACL is one of the better ones I've seen from the acronym
approach. I'd still like something with a bit of pizzaz. Java has "Beans", which
I don't believe stands for anything.

Hmmm. How about "Grace"? It could be considered a homage to Adm. Grace Hopper.
Alternatively, it could stand for something like "General Reusable Ada Container
Environment". :-)

---
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: List Container Strawman 1.4

[Ted Dennison]

In article <uy9jwtqnh.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>I think it's time for an implementation. I'll be off the next couple
>of weeks; I'll see if I can implement the strawman as a wrapper around
>SAL lists.

That would indeed be interesting. Perhaps I'll try a scratch implementation if I
get some time this XMAS. I'm taking a couple of days off, but I'll have a house
full of inlaws and new games & gadgets to deal with.

---
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: List Container Strawman 1.4

[Marin David Condic]

Yeah, I suppose you could just start adding new elements to the list with
the Singleton subprogram. I guess I'm one of those guys who likes to
explicitly clear things out - especially dynamic data structures when I'm
done with them. Presumably, that would make the storage available for some
other dynamic data structure, if its implemented right. Assuming
finalization and handling things properly with scope, I realize this may not
be strictly necessary - but I like to know I can clear the structure and
reclaim the storage any time I just get that uncontrollable urge to do so.

This might be more of an embedded thing than a workstation-app thing. I know
that in my current domain, the OS may request the app minimize itself to
gain back storage needed for some other app. Here, you want to be able to
say "Hey, here's this collection of stuff I was saving, but I suppose I
could go reload it when I need it, so here you go - have my storage and I'll
get it back later..."

An alternative might be to define a constant called Null_List that could be
assigned to a List and force it to get cleared out. This is not unlike
Null_Unbounded_String and would be keeping in the flavor of mirroring
Ada.Strings.Unbounded wherever possible.

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:kbLU7.7081$XC5.9293@www.newsranger.com...
>
> When do you need to actually deal with a null list? If its just a matter
of
> reusing the list object for a new set of values, then you can do that by
using
> one of the constructor functions.
>

Re: List Container Strawman 1.4

[Marin David Condic]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:mnLU7.7098$XC5.9248@www.newsranger.com...
>
> A point of order: The ACL would actually replace the "Containers" part.
> "Containers" was my placeholder root name.
>
That kind of presumes that the only thing this library of stuff will ever
have in it is containers. What if some other collection of packages or
classes gets identified as useful? (I have my favorites, but even without
them, I'd still see some desirability to enable future expansion.)

"Components" need not all be "Containers". Maybe we could lose the whole
"Containers" part and make a flatter tree? Something like
ACL.Lists.Unbounded?

> As for the name itself, ACL is one of the better ones I've seen from the
acronym
> approach. I'd still like something with a bit of pizzaz. Java has "Beans",
which
> I don't believe stands for anything.
>
It could also be over-used - Access Control Lists? I like it for being
simple and short, like STL or MFC. Pizzaz? For that, you kind of need a
theme - Java has the whole coffee thing locked up and Ada traditionally has
used things like Byron and Lovelace and Diana - names that may have
something or nothing to do with Ada. Agusta?

One of my compatriots in another existence liked to name all the company
laptops and computers after Tequilas. Trademark infringements aside, I'd go
for that. Especially when it came time to do some "research" to find a name
for a new machine. :-)

> Hmmm. How about "Grace"? It could be considered a homage to Adm. Grace
Hopper.
> Alternatively, it could stand for something like "General Reusable Ada
Container
> Environment". :-)
>
Grace? Hmmmmm....... "Amazing Grace"? "Grace-land"? "Princess Grace"? "Grace
Jones"? "GrrrrrrACE!!!"? Hmmmmm...... (I'd say "Ko-Ko-Kosherrific!" if I
thought there was anybody out there who would get the reference... :-)

I like how it honors Adm. Hopper - any objections to having Ada be even more
associated with the DoD?

If it alternately stood for General Reusable Ada Component Environment, and
honored Grace Hopper as well, I could go for it. I don't know if we'd get
any really good marketing slogans or pizzaz out of it.

What about just ACE? Ada Component Environment? Then you've got Deuce, Jack,
Heart, Diamond, Full_House, Flush, etc. as new directions.

I'm not fussy as long as it is relatively short and doesn't limit the
library strictly to containers. Pick one and lets see if anybody hates it so
much they threaten to leave the newsgroup and program in Cobol if we use it.

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: List Container Strawman 1.4

[Ted Dennison]

In article <a0004p$jnc$1@nh.pace.co.uk>, Marin David Condic says...
>An alternative might be to define a constant called Null_List that could be
>assigned to a List and force it to get cleared out. This is not unlike
>Null_Unbounded_String and would be keeping in the flavor of mirroring
>Ada.Strings.Unbounded wherever possible.

It could be done. I think the only reason there isn't a Null_List there now is
that no one else thought of a reason why it would be needed. You could still get
by in the current scheme by assigning a new list to the existing one, or by
performing "To" on a null element array, but those solutions are a bit awkward.

---
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: List Container Strawman 1.4

[Marin David Condic]

Well then, count this as my personal request that we have a Null_List
constant in keeping with Ada.Strings.Unbounded.

BTW: Merry Christmas to all y'all! I'll be back at it next year.

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:TdMU7.7179$XC5.9446@www.newsranger.com...
>
> It could be done. I think the only reason there isn't a Null_List there
now is
> that no one else thought of a reason why it would be needed. You could
still get
> by in the current scheme by assigning a new list to the existing one, or
by
> performing "To" on a null element array, but those solutions are a bit
awkward.
>

Re: List Container Strawman 1.4

[Nick Roberts]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:a0004p$jnc$1@nh.pace.co.uk...

> ...
> This might be more of an embedded thing than a workstation-app thing. I
know
> that in my current domain, the OS may request the app minimize itself to
> gain back storage needed for some other app. Here, you want to be able to
> say "Hey, here's this collection of stuff I was saving, but I suppose I
> could go reload it when I need it, so here you go - have my storage and
I'll
> get it back later..."

I think it's called virtual memory ;-)

> An alternative might be to define a constant called Null_List that could
be
> assigned to a List and force it to get cleared out. This is not unlike
> Null_Unbounded_String and would be keeping in the flavor of mirroring
> Ada.Strings.Unbounded wherever possible.

You mean, exactly like my proposal provides? (The Clear procedure and
Null_List function, to be specific. Has anyone actually *looked* at my
proposal? :-)

Does anyone object if I rename the ASCL project on AdaPower.net to "Tenet",
and use 'Tenet' as the root package name for a hierarchy of packages based
on my own proposal?

Understood that people are especially busy this time of year (myself
included). Over the holiday period I'll try to produce: a (more) complete
specification, that includes sets, associative arrays, and maybe other
stuff; documentation for these; sample implementations. Maybe someone will
find it useful.

My ulterior motive has always been to produce a utility base for AdaOS (and
Tenet will therefore be aimed specifically at that). Maybe this objective
has always been a bit (too) different to what other people are aiming for.
There can always be room for cross-fertilisation.

--
Best wishes,
Nick Roberts

Re: List Container Strawman 1.4

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> Hmmm. How about "Grace"? It could be considered a homage to Adm. Grace Hopper.
> Alternatively, it could stand for something like "General Reusable Ada Container
> Environment". :-)

Excelent. Much better than "Hopper", which something that everything
gets thrown in :).

-- 
-- Stephe

Re: List Container Strawman 1.4

[Ted Dennison]

In article <a001n2$kbt$1@nh.pace.co.uk>, Marin David Condic says...
>
>"Ted Dennison" <dennison@telepath.com> wrote in message
>news:mnLU7.7098$XC5.9248@www.newsranger.com...
>>
>> A point of order: The ACL would actually replace the "Containers" part.
>> "Containers" was my placeholder root name.
>>
>That kind of presumes that the only thing this library of stuff will ever
>have in it is containers. What if some other collection of packages or
>classes gets identified as useful? (I have my favorites, but even without
>them, I'd still see some desirability to enable future expansion.)

Personally I think this effort should be restricted to containers, so that
everything is logically related. If it is successful, then perhaps we can
perform a similar effort for other useful stuff like GUI's. While it might just
be possible to get a container facility in the next Ada standard, I don't think
we'd have much chance if it were combined with something as contraversial as a
GUI. At best, the namespace would have to be rearranged. We might as well just
not put unrelated stuff together in the first place.

>"Components" need not all be "Containers". Maybe we could lose the whole
>"Containers" part and make a flatter tree? Something like
>ACL.Lists.Unbounded?

Yes, that's what I was talking about (minus the adding of unrelated stuff, of
course).

>It could also be over-used - Access Control Lists? I like it for being

I keep thinking "Anterior Cruia Ligament"(sp?), which is a really nasty sports
injury.

>One of my compatriots in another existence liked to name all the company
>laptops and computers after Tequilas. Trademark infringements aside, I'd go
>for that. Especially when it came time to do some "research" to find a name
>for a new machine. :-)

If we make it scotch instead, we could start with Dewar. :-)

---
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: List Container Strawman 1.4

[Ted Dennison]

In article <upu58tjgp.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>> Hmmm. How about "Grace"? It could be considered a homage to Adm. Grace 
>> Hopper. Alternatively, it could stand for something like "General Reusable 
>> Ada Container Environment". :-)
>
>Excelent. Much better than "Hopper", which something that everything
>gets thrown in :).

I thought "Hopper" was taken (as a language), but I can't find it now. 

Disadvantages that I see:
Its 5 characters, which is a bit longer than most of the alternatives so far.
It could further associate the language with the DoD.
It could associate the language with Cobol (Grace Hopper helped invent it).
Its not a palindrome. :-)

Advantages:
At 5 characters, its not undully long.
It honors one of the greats in the history of CS.
As a first name instead of a last name, it fits the same scheme used for "Ada".
There is also a sensible acronym for it.
The word itself has positive connotations that we would all like to see signs of
in our source code.

---
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: List Container Strawman 1.4

[John B. Matthews]

In article <aCNU7.7298$XC5.9741@www.newsranger.com>, Ted
Dennison<dennison@telepath.com> wrote:

> In article <a001n2$kbt$1@nh.pace.co.uk>, Marin David Condic says...
> >
> >"Ted Dennison" <dennison@telepath.com> wrote in message
> >news:mnLU7.7098$XC5.9248@www.newsranger.com...
..
> >"Components" need not all be "Containers". Maybe we could lose the whole
> >"Containers" part and make a flatter tree? Something like
> >ACL.Lists.Unbounded?
> 
> Yes, that's what I was talking about (minus the adding of unrelated stuff, of
> course).
> 
> >It could also be over-used - Access Control Lists? I like it for being
> 
> I keep thinking "Anterior Cruia Ligament"(sp?), which is a really nasty sports
> injury.

Anterior cruciate ligament: one of a pair of ligaments that
form a cross in the knee joint to provide front/back stability.

> >One of my compatriots in another existence liked to name all the company
> >laptops and computers after Tequilas. Trademark infringements aside, I'd go
> >for that. Especially when it came time to do some "research" to find a name
> >for a new machine. :-)
> 
> If we make it scotch instead, we could start with Dewar. :-)

I'll drink to that! (Oh dear, now I'm off topic _and_ drunk:-)

John
----
http://homepage.mac.com/johnmatthews

> ---
> 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: List Container Strawman 1.4

[Simon Wright]

Ted Dennison<dennison@telepath.com> writes:

> It could be done. I think the only reason there isn't a Null_List
> there now is that no one else thought of a reason why it would be
> needed.

The reason this was added to the BCs was so that it would be possible
to create aggregates of types with Container elements.

Re: List Container Strawman 1.4

[Florian Weimer]

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

> One other thing: If we are moving towards a first-cut implementation, I
> think we need to pick some kind of acronym to be the "Root" package from
> which all this stuff will emanate. I'd go for ACL - Ada Component Library -
> as being short & sweet and to the point. Hence, we'd have
> ACL.Containers.Lists.Unbounded as our first component.

We could use "GNU" as well, I think, in the code is released under a
suitable license.

Re: List Container Strawman 1.4

[Florian Weimer]

Darren New <dnew@san.rr.com> writes:

> Actually, I find it easiest to do the initial documentation using an
> actual word processor, then cut-and-paste into a more primitive
> format.

Note that any documentation which is not tied to the source code will
almost inevitably become outdated over time.

IMHO, one should generate documentation from the Ada spec files, using
special markup comments.  At least that's what I'm doing. ;-)

Re: List Container Strawman 1.4

[Florian Weimer]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:

> I think this requirement can be solved by adding a generic child.
>
>
>    generic
>       type Alternate_Index is (<>);
>       type Alternate_Array is array (Alternate_Index range <>) of
> Element_Type;
>
>    package x.Lists.Unbounded.Array_Conversion is
>
>       function To_Alternate (Item:  in Element_Array;
>                              First: in Alternate_Index :=
> Alternate_Index'First)
>         return Alternate_Array;

It seems that this hasn't got to do much with the list package (except
for the implicit array formal parameter), so it should go to a
separate package.

Re: List Container Strawman 1.4

[Florian Weimer]

Ted Dennison<dennison@telepath.com> writes:

> In article <87heqs5awc.fsf@deneb.enyo.de>, Florian Weimer says...
>>
>>   type Element_Array is array (Natural range <>) of Element;
>>
>>   function To   (Source : Element_Array) return List;
>>   function From (Source : List) return Element_Array;
>>
>>What about a generic version of To and From which can handle arrays
>>with different index types?
>
> I think the proper way to give that level of flexability would be to
> make the array itself a generic parameter to the package. In my
> opinion, that's just one bridge too far.

I agree because in this case, you would have to declare an array type
to use the list package, which seems inappropriate.  Maybe there
should be a child package "Array_Conversions" or something like that
(which is tied to the list, and not the quite generic array conversion
package suggested by Nick).

> That's a good point. The only other thing I can think of at the
> moment though is "Out_Of_Order", which has other unfortunate
> connotations. :-)

What about "Is_Reversed", "Must_Reorder", "Is_In_Order", or just
"In_Order"?

Re: List Container Strawman 1.4

[Eric Merritt]

> 
> We could use "GNU" as well, I think, in the code is
> released under a
> suitable license.
Not to be a problem, but the term GNU carries alot of
negative political overtones that may not be a good
idea for this project.

__________________________________________________
Do You Yahoo!?
Send your FREE holiday greetings online!
http://greetings.yahoo.com

Re: List Container Strawman 1.4

[Ted Dennison]

In article <877krcomm6.fsf@deneb.enyo.de>, Florian Weimer says...
>
>"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:
>
>> One other thing: If we are moving towards a first-cut implementation, I
>> think we need to pick some kind of acronym to be the "Root" package from
>> which all this stuff will emanate. I'd go for ACL - Ada Component Library -
>> as being short & sweet and to the point. Hence, we'd have
>> ACL.Containers.Lists.Unbounded as our first component.
>
>We could use "GNU" as well, I think, in the code is released under a
>suitable license.

My current leaning (unless someone has a good objection) is to release it Public
Domain. Gnu implies a certian license, and licenses imply it isn't Public
Domain.

---
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: List Container Strawman 1.4

[Florian Weimer]

Ted Dennison<dennison@telepath.com> writes:

>>We could use "GNU" as well, I think, in the code is released under a
>>suitable license.
>
> My current leaning (unless someone has a good objection) is to
> release it Public Domain. Gnu implies a certian license, and
> licenses imply it isn't Public Domain.

Okay.  This means interested parties are free to make a GNU.Containers
version of it. ;-)

Re: List Container Strawman 1.4

[Ted Dennison]

In article <871yhjvtd6.fsf@deneb.enyo.de>, Florian Weimer says...
>
>Ted Dennison<dennison@telepath.com> writes:
>> My current leaning (unless someone has a good objection) is to
>> release it Public Domain. Gnu implies a certian license, and

>Okay.  This means interested parties are free to make a GNU.Containers
>version of it. ;-)

Quite true. 

---
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: List Container Strawman 1.4

[Ted Dennison]

In article <87lmfsn2jj.fsf@deneb.enyo.de>, Florian Weimer says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>> In article <87heqs5awc.fsf@deneb.enyo.de>, Florian Weimer says...
>>>
>>>   type Element_Array is array (Natural range <>) of Element;
>>>
>>>   function To   (Source : Element_Array) return List;
>>>   function From (Source : List) return Element_Array;
>>>
>>>What about a generic version of To and From which can handle arrays
>>>with different index types?
>>
>> I think the proper way to give that level of flexability would be to
>> make the array itself a generic parameter to the package. In my
>> opinion, that's just one bridge too far.
>
>I agree because in this case, you would have to declare an array type
>to use the list package, which seems inappropriate.  Maybe there
>should be a child package "Array_Conversions" or something like that
>(which is tied to the list, and not the quite generic array conversion
>package suggested by Nick).

Actually, I was thinking along the lines of an Containers.Lists.Fixed package
that works with arrays.

---
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: List Container Strawman 1.4

[Hyman Rosen]

Ted Dennison wrote:

> Actually, I was thinking along the lines of an Containers.Lists.Fixed

 > package that works with arrays.

I think this kind of thing is where C++'s iterators and algorithms
approach shows its superiority. Why should a List have any notion
of other data structures to which its elements can be copied?

In the STL, creating or copying one structure from another can be
done just using the std::copy algorithm, a pair of iterators giving
the source range, and a target iterator which receives the copies.
If you want to copy to a fixed-size array, the target iterator can
simply be a pointer to the first element. If you are creating a more
complicated target (such as another list, or a vector), then it is
the iterator that holds the semantics of where the data goes, for
example std::inserter or std::back_inserter.

Re: List Container Strawman 1.4

[Nick Roberts]

"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:3C2CA143.6030006@mail.com...

> Ted Dennison wrote:
>
> > Actually, I was thinking along the lines of an Containers.Lists.Fixed
>
>  > package that works with arrays.
>
> I think this kind of thing is where C++'s iterators and algorithms
> approach shows its superiority. Why should a List have any notion
> of other data structures to which its elements can be copied?
>
> In the STL, creating or copying one structure from another can be
> done just using the std::copy algorithm, a pair of iterators giving
> the source range, and a target iterator which receives the copies.
> If you want to copy to a fixed-size array, the target iterator can
> simply be a pointer to the first element. If you are creating a more
> complicated target (such as another list, or a vector), then it is
> the iterator that holds the semantics of where the data goes, for
> example std::inserter or std::back_inserter.

Well, speaking for what my own library (which I'm calling Tenet) will
provide, I am supplying a set of container-wide iterator types, which come
with a Copy_All procedure. So if I have, say, a lookup and a list, I can
copy from one to the other thus:


   package Widget_Lookups is new Tenet.Lookups.Unbounded(Widget);
   package Widget_Lists is new Tenet.Lists.Unbounded(Widget);

   M: Widget_Lookups.Lookup;
   L: Widget_Lists.List;

   package Widget_Iteration is Tenet.Iteration(Widget);
   package Widget_Lookup_Iteration is new
Widget_Lookups.Iteration(Widget_Iteration);
   package Widget_List_Iteration is new
Widget_Lists.Iteration(Widget_Iteration);

   R: Widget_Lookup_Iteration.Reader;
   W: Widget_List_Iteration.Writer;

   ...

   Open(R,M);
   Open(W,L);
   Copy_All(R,W);
   Close(W);
   Close(R);


It is all very wordy. The C++ equivalent is no doubt more concise. But, of
course, this is only a tiny example. Realler software would show (IMHO ;-)
the expressiveness of this design. In a hurry; must go.

--
Best wishes,
Nick Roberts

Re: List Container Strawman 1.4

[Matthew Heaney]

"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:3C2CA143.6030006@mail.com...
> Ted Dennison wrote:
>
> > Actually, I was thinking along the lines of an Containers.Lists.Fixed
>
>  > package that works with arrays.
>
> I think this kind of thing is where C++'s iterators and algorithms
> approach shows its superiority. Why should a List have any notion
> of other data structures to which its elements can be copied?

You're right, it shouldn't.  Iterators allow you to abstract away the
differences among different containers.  That's the whole point.

The app I will be submitting to the Ada-Belgium competition includes a list
container type that allows you to copy its items using iterators, like this:

List : Integer_Lists.List_Type;
...
declare
   Items : array (1 .. Length (List)) of Integer;
   Iter : Iterator_Type := First (List);
begin
   for I in Items'Range loop
      Items (I) := Item (Iter);
      Next (Iter);
   end loop;
end;

(My list type has selectors that return iterators designating First, Last,
Front, and Back.  The latter two are sentinals.)

It would be easy to generalize this algorithm to copy items from any
container type with an iterator:

generic
   type Iterator_Type (<>) is private;
   type Item_Type is private;
   type Item_Array is array (Positive range <>) of Item_Type;
   with function "=" (L, R : Iterator_Type) return Boolean is <>;
procedure Generic_Copy
  (First  : in      Iterator_Type;
   Back : in      Iterator_Type;
   Items : in out Items_Type);

procedure Generic_Copy (...) is
   Iter : Iterator_Type := First;
   I : Positive := Items'First;
begin
   while Iter /= Back loop
      Items (I) := Item (Iter);
      Next (Iter);
      I := I + 1;
   end loop;
end Generic_Copy;

If you wanted, you could generalize this further (as the STL does) to
abstract away the target type (in the example above we've hard-coded an
array type as the target type).  To do this for arrays you'd need an
appropriate iterator type; maybe Interfaces.C.Pointers would work.

Re: List Container Strawman 1.4

[Matthew Heaney]

"Matthew Heaney" <mheaney@on2.com> wrote in message
news:u2pitjhps1bp07@corp.supernews.com...
> If you wanted, you could generalize this further (as the STL does) to
> abstract away the target type (in the example above we've hard-coded an
> array type as the target type).  To do this for arrays you'd need an
> appropriate iterator type; maybe Interfaces.C.Pointers would work.

In the example below I wrote an array iterator and a Generic_Copy algorithm
that works for any target type.  The basic idea is:

declare
   ...
    procedure Copy is
         new Generic_Copy
           (Integer_Lists.Iterator_Type,
            Integer_Arrays.Iterator_Type);

      Items : aliased Integer_Array (1 .. Length (List));
      Iter : Integer_Arrays.Iterator_Type := Items
(Items'First)'Unchecked_Access;
   begin
      Copy (First (List), Back (List), Iter);
  end;

This is exactly how the STL does things.

The code below is suitable for use with gnatchop.

--STX
with System.Storage_Elements;
with Ada.Unchecked_Conversion;

package body Array_Iterators is

   use type System.Storage_Elements.Storage_Offset;


   function To_Iterator is
      new Ada.Unchecked_Conversion (System.Address, Iterator_Type);

   function First (Items : access Array_Type) return Iterator_Type is
   begin
      return Items (Items'First)'Access;
   end;


   function Back (Items : access Array_Type) return Iterator_Type is

      First_Address : constant System.Address := Items
(Items'First)'Address;

      Length : constant System.Storage_Elements.Storage_Count :=
Items'Length;

      Offset : constant System.Storage_Elements.Storage_Count :=
         Length * Array_Type'Component_Size / System.Storage_Unit;

      Back_Address : constant System.Address := First_Address + Offset;

   begin

      return To_Iterator (Back_Address);

   end;


   function Item (Iterator : Iterator_Type) return Item_Type is
   begin
      return Iterator.all;
   end;


   procedure Next (Iterator : in out Iterator_Type) is

      Curr_Address : constant System.Address := Iterator.all'Address;

      Offset : constant System.Storage_Elements.Storage_Count :=
         Array_Type'Component_Size / System.Storage_Unit;

      Next_Address : constant System.Address := Curr_Address + Offset;

   begin

      Iterator := To_Iterator (Next_Address);

   end;


end Array_Iterators;
generic

   type Item_Type is limited private;

   type Index_Type is range <>;

   type Array_Type is array (Index_Type range <>) of aliased Item_Type;

package Array_Iterators is

   type Iterator_Type is access all Item_Type;
   for Iterator_Type'Storage_Size use 0;

   function First (Items : access Array_Type) return Iterator_Type;

   function Back (Items : access Array_Type) return Iterator_Type;

   function Item (Iterator : Iterator_Type) return Item_Type;

   procedure Next (Iterator : in out Iterator_Type);

end Array_Iterators;

      procedure Generic_Copy
  (First  : in     Source_Iterator_Type;
   Back   : in     Source_Iterator_Type;
   Target : in out Target_Iterator_Type) is

   Source : Source_Iterator_Type := First;
begin
   while Source /= Back loop
      Set_Item (Source, Target);
      Next (Source);
      Next (Target);
   end loop;
end Generic_Copy;

generic

   type Source_Iterator_Type (<>) is private;

   type Target_Iterator_Type (<>) is private;

   with procedure Set_Item
     (Source : Source_Iterator_Type;
      Target : Target_Iterator_Type) is <>;

   with procedure Next (Iterator : in out Source_Iterator_Type) is <>;

   with procedure Next (Iterator : in out Target_Iterator_Type) is <>;

   with function "=" (L, R : Source_Iterator_Type) return Boolean is <>;

procedure Generic_Copy
  (First  : in     Source_Iterator_Type;
   Back   : in     Source_Iterator_Type;
   Target : in out Target_Iterator_Type);
   with Array_Iterators;
pragma Elaborate_All (Array_Iterators);

package Integer_Arrays is

   type Integer_Array is array (Positive range <>) of aliased Integer;

   package Integer_Array_Iterators is
      new Array_Iterators (Integer, Positive, Integer_Array);

   type Iterator_Type is new Integer_Array_Iterators.Iterator_Type;

end Integer_Arrays;
with Unbounded_Lists;
pragma Elaborate_All (Unbounded_Lists);

package Integer_Lists is
   new Unbounded_Lists (Integer);

with Integer_Lists;  use Integer_Lists;
with Integer_Arrays;  use Integer_Arrays;
with Generic_Copy;
with Ada.Text_IO;  use Ada.Text_IO;
with Ada.Integer_Text_IO;  use Ada.Integer_Text_IO;

procedure Test_Copy is

   List : List_Type;

begin

   for I in 1 .. 5 loop
      Push_Back (List, I);
   end loop;

   declare
      Iter : Integer_Lists.Iterator_Type := First (List);
      Back : constant Integer_Lists.Iterator_Type := Integer_Lists.Back
(List);
   begin
      Put ("source:");

      while Iter /= Back loop
         Put (' ');
         Put (Item (Iter), Width => 0);
         Next (Iter);
      end loop;

      New_Line;
   end;

   declare
      procedure Set_Item
        (Source : Integer_Lists.Iterator_Type;
         Target : Integer_Arrays.Iterator_Type) is
      begin
         Target.all := Item (Source);
      end;

      pragma Warnings (Off, Set_Item);

      procedure Copy is
         new Generic_Copy
           (Integer_Lists.Iterator_Type,
            Integer_Arrays.Iterator_Type);

      Items : aliased Integer_Array (1 .. Length (List));
      Iter : Integer_Arrays.Iterator_Type := Items
(Items'First)'Unchecked_Access;
   begin
      Copy (First (List), Back (List), Iter);

      Put ("target:");

      for I in Items'Range loop
         Put (' ');
         Put (Items (I), Width => 0);
      end loop;

      New_Line;
   end;


end Test_Copy;

with Ada.Unchecked_Deallocation;  --should pass in storage_pool

package body Unbounded_Lists is

   procedure Free is
      new Ada.Unchecked_Deallocation (Node_Type, Node_Access);


   procedure Initialize (List : in out List_Type) is
   begin

      List.Front := new Node_Type;
      List.Back := new Node_Type;

      List.Front.Next := List.Back;
      List.Back.Prev := List.Front;

      List.Length := 0;

   end Initialize;


   procedure Finalize (List : in out List_Type) is
   begin
      Clear (List);
      Free (List.Front);
      Free (List.Back);
   end;


   procedure Push_Front
     (List : in out List_Type;
      Item : in     Item_Type) is

      Node : constant Node_Access :=
         new Node_Type'(Item => Item,
                        Next => List.Front.Next,
                        Prev => List.Front);
   begin
      Node.Next.Prev := Node;
      List.Front.Next := Node;
      List.Length := List.Length + 1;
   end;


   procedure Push_Front
     (List : access List_Type;
      Item : in     Item_Type) is
   begin
      Push_Front (List.all, Item);
   end;


   procedure Push_Back
     (List : in out List_Type;
      Item : in     Item_Type) is

      Node : constant Node_Access :=
         new Node_Type'(Item => Item,
                        Next => List.Back,
                        Prev => List.Back.Prev);
   begin
      Node.Prev.Next := Node;
      List.Back.Prev := Node;
      List.Length := List.Length + 1;
   end;


   procedure Push_Back
     (List : access List_Type;
      Item : in     Item_Type) is
   begin
      Push_Back (List.all, Item);
   end;


   procedure Push_Front (List : in out List_Type) is
      Node : constant Node_Access := new Node_Type;
   begin
      Node.Next := List.Front.Next;
      Node.Prev := List.Front;
      Node.Next.Prev := Node;
      List.Front.Next := Node;
      List.Length := List.Length + 1;
   end;


   procedure Push_Back (List : in out List_Type) is
      Node : constant Node_Access := new Node_Type;
   begin
      Node.Next := List.Back;
      Node.Prev := List.Back.Prev;
      Node.Prev.Next := Node;
      List.Back.Prev := Node;
      List.Length := List.Length + 1;
   end;


   procedure Pop_Front (List : in out List_Type) is
      pragma Assert (List.Length > 0);

      Node : Node_Access := List.Front.Next;
   begin
      List.Front.Next := Node.Next;
      Node.Next.Prev := List.Front;
      List.Length := List.Length - 1;
      Free (Node);
   end;

   procedure Pop_Back (List : in out List_Type) is
      pragma Assert (List.Length > 0);

      Node : Node_Access := List.Back.Prev;
   begin
      List.Back.Prev := Node.Prev;
      Node.Prev.Next := List.Back;
      List.Length := List.Length - 1;
      Free (Node);
   end;


   function Length (List : List_Type) return Natural is
   begin
      return List.Length;
   end;


   procedure Clear (List : in out List_Type) is
      Node : Node_Access := List.Front.Next;
      Next : Node_Access;
   begin
      while Node /= List.Back loop
         Next := Node.Next;
         Free (Node);
         Node := Next;
      end loop;

      List.Front.Next := List.Back;
      List.Back.Prev := List.Front;
      List.Length := 0;
   end;


   function First (List : List_Type) return Item_Type is
      pragma Assert (List.Length > 0);
   begin
      return List.Front.Next.Item;
   end;

   function Last (List : List_Type) return Item_Type is
      pragma Assert (List.Length > 0);
   begin
      return List.Back.Prev.Item;
   end;

   procedure Swap (L, R : in out List_Type) is
      Front : constant Node_Access := L.Front;
      Back  : constant Node_Access := L.Back;
      Length : constant Natural := L.Length;
   begin
      L.Front := R.Front;
      L.Back := R.Back;
      L.Length := R.Length;

      R.Front := Front;
      R.Back := Back;
      R.Length := Length;
   end;



   function First (List : List_Type) return Iterator_Type is
      pragma Assert (List.Length > 0);
   begin
      return Iterator_Type'(Node => List.Front.Next);
   end;

   function Last (List : List_Type) return Iterator_Type is
      pragma Assert (List.Length > 0);
   begin
      return Iterator_Type'(Node => List.Back.Prev);
   end;

   function Front (List : List_Type) return Iterator_Type is
   begin
      return Iterator_Type'(Node => List.Front);
   end;

   function Back (List : List_Type) return Iterator_Type is
   begin
      return Iterator_Type'(Node => List.Back);
   end;

   procedure Next (Iterator : in out Iterator_Type) is
   begin
      Iterator.Node := Iterator.Node.Next;
   end;

   procedure Previous (Iterator : in out Iterator_Type) is
   begin
      Iterator.Node := Iterator.Node.Prev;
   end;

   function Item (Iterator : Iterator_Type) return Item_Type is
   begin
      return Iterator.Node.Item;
   end;


end Unbounded_Lists;
with Ada.Finalization;

generic

   type Item_Type is private;

package Unbounded_Lists is

   type List_Type is limited private;


   procedure Push_Front
     (List : in out List_Type;
      Item : in     Item_Type);

   procedure Push_Front
     (List : access List_Type;
      Item : in     Item_Type);

   procedure Push_Front (List : in out List_Type);

   procedure Pop_Front (List : in out List_Type);


   procedure Push_Back
     (List : in out List_Type;
      Item : in     Item_Type);

   procedure Push_Back
     (List : access List_Type;
      Item : in     Item_Type);

   procedure Push_Back (List : in out List_Type);

   procedure Pop_Back (List : in out List_Type);



   function Length (List : List_Type) return Natural;

   procedure Clear (List : in out List_Type);

   function First (List : List_Type) return Item_Type;

   function Last (List : List_Type) return Item_Type;

   procedure Swap (L, R : in out List_Type);


   type Iterator_Type is private;

   function First (List : List_Type) return Iterator_Type;

   function Last (List : List_Type) return Iterator_Type;

   function Front (List : List_Type) return Iterator_Type;

   function Back (List : List_Type) return Iterator_Type;

   procedure Next (Iterator : in out Iterator_Type);

   procedure Previous (Iterator : in out Iterator_Type);

   function Item (Iterator : Iterator_Type) return Item_Type;


private

   type Node_Type;
   type Node_Access is access Node_Type;

   type Node_Type is
      record
         Item : aliased Item_Type;
         Next : Node_Access;
         Prev : Node_Access;
      end record;

   type Handle_Type (L : access List_Type) is limited null record;

   type List_Type is
      new Ada.Finalization.Limited_Controlled with record
         H      : Handle_Type (List_Type'Access);
         Front  : Node_Access;
         Back   : Node_Access;
         Length : Natural;
      end record;

   procedure Initialize (List : in out List_Type);
   procedure Finalize (List : in out List_Type);

   type Iterator_Type is
      record
         Node : Node_Access;
      end record;

end Unbounded_Lists;

Re: List Container Strawman 1.4

[Hyman Rosen]

Matthew Heaney wrote:

> In the example below I wrote an array iterator and a Generic_Copy algorithm
> that works for any target type.

...
>    use type System.Storage_Elements.Storage_Offset;
>    function To_Iterator is
>       new Ada.Unchecked_Conversion (System.Address, Iterator_Type);


The generic copy seems good, but all of that address manipulation seems
ver un-Adalike to me (and I'm not an Ada programmer!)

Re: List Container Strawman 1.4

[Matthew Heaney]

"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:3C2EB518.5040805@mail.com...
> The generic copy seems good, but all of that address manipulation seems
> very un-Adalike to me (and I'm not an Ada programmer!).

Yes, that's true, although the address manipulation is confined to a single
module.

However, I thought about the problem some more and realized that you can
generalize the copy algorithm to work for any kind of array (so that the
elements don't have to be aliased) and to any container type.

Here's the spec for Generic_Copy:
generic

   type Source_Type (<>) is private;


   type Target_Type (<>) is limited private;


   with function Succ

      (Source : Source_Type) return Source_Type is <>;

   with procedure Copy

      (Source : in Source_Type;

      Target : in out Target_Type) is <>;

procedure Generic_Copy

  (First : in Source_Type;

   Back : in Source_Type;

   Target : in out Target_Type);

The idiom for copying an array to a list would look like:

declare

   Items : constant Integer_Array := (1, 2, 3, 4, 5);

   List : List_Type;

   procedure Copy
     (Source : in     Positive;
      Target : in out Iterator_Type) is
      pragma Warnings (Off, Target);
   begin
      Push_Back (List, Items (Source));
   end;

   procedure Copy is
      new Generic_Copy
            (Positive,
             Iterator_Type,
             Integer'Succ);

   Iter : Iterator_Type;

begin

   Copy (Items'First, Items'First + Items'Length, Iter);

end;



The idiom for copying a list to an array is:

   declare
      Items : array (1 .. Length (List)) of Integer;

      procedure Copy
        (Source : in     Iterator_Type;
         Target : in out Positive) is
      begin
         Items (Target) := Item (Source);
         Target := Target + 1;
      end;

      procedure Copy is
         new Generic_Copy
               (Iterator_Type,
                Positive);

      Index : Positive := Items'First;
   begin
      Copy (First (List), Back (List), Index);
   end;



The fact that you can declare subprograms locally means you don't need
STL-style insert iterators, because you can just refer to the container
object directly.  And using the index subtype as the array iterator means
you can use any kind of array, irrespective of whether it is constrained, or
its items aliased.

If you're curious, the body of Generic_Copy is:

procedure Generic_Copy
  (First  : in     Source_Type;
   Back   : in     Source_Type;
   Target : in out Target_Type) is

   Source : Source_Type := First;

begin

   while Source /= Back loop
      Copy (Source, Target);
      Source := Succ (Source);
   end loop;

end Generic_Copy;

Re: List Container Strawman 1.4

[Brian Rogoff]

Very nice Matthew! I think I'll dust off my old attempt at STL in Ada and
incorporate these fragments.

FWIW, I didn't even find the first version too bad, though I guess I'm
thoroughly polluted by C, C++, and other non-Ada languages. Ummm, insert
a smiley after "polluted" if you're a hypersensitive C++ programmer...

-- Brian

On Wed, 2 Jan 2002, Matthew Heaney wrote:

>
> "Hyman Rosen" <hyrosen@mail.com> wrote in message
> news:3C2EB518.5040805@mail.com...
> > The generic copy seems good, but all of that address manipulation seems
> > very un-Adalike to me (and I'm not an Ada programmer!).
>
> Yes, that's true, although the address manipulation is confined to a single
> module.
>
> However, I thought about the problem some more and realized that you can
> generalize the copy algorithm to work for any kind of array (so that the
> elements don't have to be aliased) and to any container type.
>
> Here's the spec for Generic_Copy:
> generic
>
>    type Source_Type (<>) is private;
>
>
>    type Target_Type (<>) is limited private;
>
>
>    with function Succ
>
>       (Source : Source_Type) return Source_Type is <>;
>
>    with procedure Copy
>
>       (Source : in Source_Type;
>
>       Target : in out Target_Type) is <>;
>
> procedure Generic_Copy
>
>   (First : in Source_Type;
>
>    Back : in Source_Type;
>
>    Target : in out Target_Type);
>
> The idiom for copying an array to a list would look like:
>
> declare
>
>    Items : constant Integer_Array := (1, 2, 3, 4, 5);
>
>    List : List_Type;
>
>    procedure Copy
>      (Source : in     Positive;
>       Target : in out Iterator_Type) is
>       pragma Warnings (Off, Target);
>    begin
>       Push_Back (List, Items (Source));
>    end;
>
>    procedure Copy is
>       new Generic_Copy
>             (Positive,
>              Iterator_Type,
>              Integer'Succ);
>
>    Iter : Iterator_Type;
>
> begin
>
>    Copy (Items'First, Items'First + Items'Length, Iter);
>
> end;
>
>
>
> The idiom for copying a list to an array is:
>
>    declare
>       Items : array (1 .. Length (List)) of Integer;
>
>       procedure Copy
>         (Source : in     Iterator_Type;
>          Target : in out Positive) is
>       begin
>          Items (Target) := Item (Source);
>          Target := Target + 1;
>       end;
>
>       procedure Copy is
>          new Generic_Copy
>                (Iterator_Type,
>                 Positive);
>
>       Index : Positive := Items'First;
>    begin
>       Copy (First (List), Back (List), Index);
>    end;
>
>
>
> The fact that you can declare subprograms locally means you don't need
> STL-style insert iterators, because you can just refer to the container
> object directly.  And using the index subtype as the array iterator means
> you can use any kind of array, irrespective of whether it is constrained, or
> its items aliased.
>
> If you're curious, the body of Generic_Copy is:
>
> procedure Generic_Copy
>   (First  : in     Source_Type;
>    Back   : in     Source_Type;
>    Target : in out Target_Type) is
>
>    Source : Source_Type := First;
>
> begin
>
>    while Source /= Back loop
>       Copy (Source, Target);
>       Source := Succ (Source);
>    end loop;
>
> end Generic_Copy;
>
>
>
>
>
>