Queue

Queue

[steve]

Which is the best way to make a queue using head and tail pointers

Many thanks

Re: Queue

[Larry Kilgallen]

In article <yUBM7.7695$4d6.1768979@news11-gui.server.ntli.net>, "steve" <steve_rm@ntlworld.com> writes:
> Which is the best way to make a queue using head and tail pointers

Start by defining your own idea of "best".

To get some hints, look at the last month's posts in this newsgroup
that have the string "List Container" in the title.  Many diverse
opinions have been advanced.

Re: Queue

[Ted Dennison]

In article <BWq3g0s2usk2@eisner.encompasserve.org>, Larry Kilgallen says...
>
>In article <yUBM7.7695$4d6.1768979@news11-gui.server.ntli.net>, "steve" <steve_rm@ntlworld.com> writes:
>> Which is the best way to make a queue using head and tail pointers
>
>Start by defining your own idea of "best".
>
>To get some hints, look at the last month's posts in this newsgroup
>that have the string "List Container" in the title.  Many diverse
>opinions have been advanced.

Yeah. If we knew the answer to that question unanamously, there would have been
about 150 less posts here in the last two weeks. :-)

---
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: Queue

[Marin David Condic]

Or, if we had been able to settle on something and agree that it was going
to be The One, we could have said "Here's a link to the standard Ada data
structure library..." and forced professors everywhere to ban its use in
Data Structures courses. :-)

I'd still be willing to settle on the BC's with some enhancements and
extensions. Anybody else willing to go that route?

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:%QRM7.39743$xS6.65958@www.newsranger.com...
>
> Yeah. If we knew the answer to that question unanamously, there would have
been
> about 150 less posts here in the last two weeks. :-)
>

Re: Queue

[Matthew Heaney]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9u0qhb$pq5$1@nh.pace.co.uk...
> I'd still be willing to settle on the BC's with some enhancements and
> extensions. Anybody else willing to go that route?

No.  The problem with the Booch Components is that they use inheritance,
which is completely unnecessary unless you require dynamic polymorphic
behavior.

The C++ STL doesn't use inheritance.  The use of iterators and algorithms
abstracts away the details of specific containers, and thus treats all
collections as a "sequence."  This is a form of static polymorphism.

If you do need a dynamically polymorphic container (a stack, say), then you
can implement that yourself using an Adapter pattern.

The standard library should provide only the most basic primitives, from
which higher-level abstractions can be constructed.

Re: Queue

[Marin David Condic]

Well, I guess the problem I see is that we could easily keep going back and
forth on what constitutes the best possible solution indefinitely. We'd be
far better off getting something as an answer - even if it is imperfect.

Maybe its hopeless? Is it a little too much like asking "What's the best
kind of car to drive?" or "What's the best shotgun to have?" - Too many
potential uses and personal preferences to come up with a "best" answer and
nobody wants to settle for a sub-optimal answer. Maybe we'd end up with
Lists and Maps if the next standard just has them show up in a sneak attack,
but it seems that this process is not likely to get a consensus strong
enough to get a result.

I think that Ted proposed a package that would make a good start. But that
rather quickly shot off in a few dozen directions with objections on all
sorts of fronts - and it was only one little lonely list package.  I could
still imagine taking it pretty much "as is" and adding to it a map package
that looked similar and declaring that "Version 1.0". Any chance that
proposal would gain any support? Anybody else have a proposed answer?

I think if we don't commit to some direction pretty soon, the stagnation and
deadlock will result in a lack of interest and this will wither on the vine.
Too bad. Its a good idea and a noble goal.

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/


"Matthew Heaney" <mheaney@on2.com> wrote in message
news:u07tltbt28eq1d@corp.supernews.com...
>
> No.  The problem with the Booch Components is that they use inheritance,
> which is completely unnecessary unless you require dynamic polymorphic
> behavior.
>
> The C++ STL doesn't use inheritance.  The use of iterators and algorithms
> abstracts away the details of specific containers, and thus treats all
> collections as a "sequence."  This is a form of static polymorphism.
>
> If you do need a dynamically polymorphic container (a stack, say), then
you
> can implement that yourself using an Adapter pattern.
>
> The standard library should provide only the most basic primitives, from
> which higher-level abstractions can be constructed.
>
>
>
>
>

Re: Queue

[Ehud Lamm]

Marin David Condic <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9u0ujd$rhg$1@nh.pace.co.uk...
> I think if we don't commit to some direction pretty soon, the stagnation
and
> deadlock will result in a lack of interest and this will wither on the
vine.
> Too bad. Its a good idea and a noble goal.

Exactly.
That's why I wanted the central repository to be on AdaPower, and the
discussion to be here.
It all started falling apart when people started posting their favorite
ideas on their own web pages. This is exactly the situation we started with.
We are now trying to work on consolidation, not to show our creativity (not
that I have anything against all the itneresting suggestions, I just don't
think they advance the cause...)

Ehud

Re: Queue

[Marin David Condic]

Well, people posting a variety of ideas is not all bad - but at some point
this has to narrow down to a set of optional courses of action and a
decision needs to be taken as to which option to persue. If a set of three
or four options were posted on AdaPower & a vote taken, we could probably
all ralley around the flag and start arguing about how to
enhance/improve/extend the chosen course of development.

If this were a corporate endeavor - or sponsored by a corporate endeavor,
the product owner/boss would have declared an autocratic and arbitrary
course of action and we'd have all been told to sit down, shut up and get to
work making the game plan successful. :-) I'm sure that once a decision is
taken on this, most of us would be willing to pull together and get some
version of it working. The problem is that this is barely a democracy - if
even close to that. Any one or more of us can pick up our marbles and go
home at any time and if enough of us do that, the whole effort collapses.

IMHO, if we're serious about wanting this, we ought to agree on some set of
choices/design directions/whatever and toss a coin to select a winner. From
there, I'm sure we could collaborate to get any enhancements, extensions or
implementation done.

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


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9u10bt$ake$1@news.huji.ac.il...
>
> Exactly.
> That's why I wanted the central repository to be on AdaPower, and the
> discussion to be here.
> It all started falling apart when people started posting their favorite
> ideas on their own web pages. This is exactly the situation we started
with.
> We are now trying to work on consolidation, not to show our creativity
(not
> that I have anything against all the itneresting suggestions, I just don't
> think they advance the cause...)
>

Re: Queue

[Ehud Lamm]

Marin David Condic <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9u136q$aa$1@nh.pace.co.uk...
> Well, people posting a variety of ideas is not all bad - but at some point
> this has to narrow down to a set of optional courses of action and a
> decision needs to be taken as to which option to persue. If a set of three
> or four options were posted on AdaPower & a vote taken, we could probably
> all ralley around the flag and start arguing about how to
> enhance/improve/extend the chosen course of development.

I think this is what I suggested a while back, but I am not sure this is
what you advocate, if I understand the rest of your message. Are you in
favor of this approach?

>  The problem is that this is barely a democracy - if
> even close to that. Any one or more of us can pick up our marbles and go
> home at any time and if enough of us do that, the whole effort collapses.
>

That's good, in my book. I don't think this is likely to happen, and if it
does it means there are better alternatives - which is good in and of
itself.

> IMHO, if we're serious about wanting this, we ought to agree on some set
of
> choices/design directions/whatever and toss a coin to select a winner.
From
> there, I'm sure we could collaborate to get any enhancements, extensions
or
> implementation done.

This is what I started with. My original message on this was a list of goals
and design criteria. Most poster thought it is better to start with
something more concrete like Ted's strawman. In retrospect I think this was
indeed very useful, and indeed essential. But perhaps the time has come to
revisit the list of goal and try to produce a more polished version.

Ehud

Re: Queue

[Marin David Condic]

I'm in favor of any approach that gets a concensus going about what to
select as a component library for Ada. The danger here is debating the issue
for too long and ending up with *no* component library as a result.

AFAIK, there have been a handful of proposed directions - such as BC's+mods,
PragmAda+mods, Ted's list package strawman, etc. So far, there seems to be
some motion in the direction of building something from scratch based on
Ted's strawman. It seems that this was getting bogged down in a variety of
debates about iterators, sorts, library-level instantiations, etc. I don't
know if we want to take some kind of vote on it or not - but it seems like
it could be a viable direction if we can keep it from getting stalled. I
could get behind Ted's package and would be willing to help get it
implemented if needed - maybe others would do so as well?

Or are there still strong feelings about wanting to make fundamental changes
to Ted's strawman that would preclude using it as-is for a start?
(Superficial changes that can be added or tweaked later are O.K. in my
mind - is the spec good enough that if it were implemented, we'd have an
acceptable approach that might get extended/enhanced at a later point?) Or
is there still some interest in debating alternative approaches?

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


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9u14o2$d61$1@news.huji.ac.il...
>
> I think this is what I suggested a while back, but I am not sure this is
> what you advocate, if I understand the rest of your message. Are you in
> favor of this approach?
>

Standard Library, Again (was: Re: Queue)

[Jeffrey Carter]

Marin David Condic wrote:
> 
> I'm in favor of any approach that gets a concensus going about what to
> select as a component library for Ada. The danger here is debating the issue
> for too long and ending up with *no* component library as a result.
> 
> AFAIK, there have been a handful of proposed directions - such as BC's+mods,
> PragmAda+mods, Ted's list package strawman, etc. So far, there seems to be
> some motion in the direction of building something from scratch based on
> Ted's strawman. It seems that this was getting bogged down in a variety of
> debates about iterators, sorts, library-level instantiations, etc. I don't
> know if we want to take some kind of vote on it or not - but it seems like
> it could be a viable direction if we can keep it from getting stalled. I
> could get behind Ted's package and would be willing to help get it
> implemented if needed - maybe others would do so as well?

Any workable standard library is better than none. TED's recent strawman
specification is certainly workable. While my initial preference is
elsewhere, if there were a consensus for this list package I would
support it.

-- 
Jeffrey Carter

Standard Queue status

[Ted Dennison]

In article <9u0ujd$rhg$1@nh.pace.co.uk>, Marin David Condic says...
>I think that Ted proposed a package that would make a good start. But that
>rather quickly shot off in a few dozen directions with objections on all
>sorts of fronts - and it was only one little lonely list package.  I could
>still imagine taking it pretty much "as is" and adding to it a map package
>that looked similar and declaring that "Version 1.0". Any chance that
>proposal would gain any support? Anybody else have a proposed answer?
>
>I think if we don't commit to some direction pretty soon, the stagnation and
>deadlock will result in a lack of interest and this will wither on the vine.
>Too bad. Its a good idea and a noble goal.

I think I'd best say that I should shoulder a fair bit of the blame for that.
First off, I *asked* for more discussion when some were apparently ready to move
toward implementing what we had. I'd hoped a bit more polishing (particularly
anound the subprogram names and the implementation of the iterator) would
achieve us a broader consensus. 

My second crime was that I went and purchased Civ3, which has proceeded to suck
up all my computer time for the last couple of weeks, along with a good chunk of
my sleep time as well. :-(

To get things back on track, I'd like to ask if there is anything in Nick's
proposal that there is general consensus on putting in the strawman (or we could
take it the other way, if that's what folks want). If you want to look at it,
the package in question is at
http://www.adaos.ukf.net/njr05/scl-lists-unbounded.ads.html .

Personally, I like his use of the "Direction" type to specify which end to start
from in his operations. I also like the ability to convert between lists and
unbounded arrays. I think those may merit putting in the final version. There
are also a number of operations in there that the strawman doesn't have which
some folks may find useful.

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. 

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. 

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.

---
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: Standard Queue status

[Marin David Condic]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:z9aN7.41127$xS6.69040@www.newsranger.com...
>
> I think I'd best say that I should shoulder a fair bit of the blame for
that.
> First off, I *asked* for more discussion when some were apparently ready
to move
> toward implementing what we had. I'd hoped a bit more polishing
(particularly
> anound the subprogram names and the implementation of the iterator) would
> achieve us a broader consensus.
>
The names can always be changed before a final release - the important thing
is that the concepts be acceptable because you can't change those once its
started. The iterator scheme is something that has to be lived with once
started. I'd favor "simple" since it is always possible to tack on a child
package that provides more fancy schemes if it seems desirable.

>
> To get things back on track, I'd like to ask if there is anything in
Nick's
> proposal that there is general consensus on putting in the strawman (or we
could
> take it the other way, if that's what folks want). If you want to look at
it,
> the package in question is at
> http://www.adaos.ukf.net/njr05/scl-lists-unbounded.ads.html .
>
I'll take a look but the page is not coming up at the moment.


> Personally, I like his use of the "Direction" type to specify which end to
start
> from in his operations. I also like the ability to convert between lists
and
> unbounded arrays. I think those may merit putting in the final version.
There
> are also a number of operations in there that the strawman doesn't have
which
> some folks may find useful.
>
I wouldn't try to make the lists be all things to all people. KISS - then
come up with fancier varieties that are variations on a theme. Extra
operations can always exist in a child package.


> 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.
>
Then keep the basic iterator you have in the Mark 1, Mod 0 package spec -
alternative iterators can be added in a child package. Keep the scope small
and simple enough that it is doable in some rational span of time and
effort. Ada is nice in allowing extensions and enhancements as we go without
upsetting the apple cart.


> 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.
>
If the subprograms can be broken into groups and the basic ones kept in the
parent, then one or more child packages that provide enhanced capabilities
is the way to go. Just because it is useful doesn't mean it needs to be in
v1.0 or the parent package. Don't discard the ideas - just stall them off
until we have something basic working and acceptable to the general public.


> 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.
>
Make an Unbounded Array a separate data type. Sure, its similar to a list,
but maybe it should be its own specialized data type because its usage will
be different and ultimately it may be better off with a different
implementation. Conversions can be handled by child packages at a later time
if it seems that they are needed.

Just my $0.02 - I think this would make a good start.

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: Standard Queue status

[Ehud Lamm]

Marin David Condic <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9u3jdb$2i9$1@nh.pace.co.uk...
> Make an Unbounded Array a separate data type.

Right.

Re: Standard Queue status

[Ted Dennison]

In article <9u3lth$uic$1@news.huji.ac.il>, Ehud Lamm says...
>
>Marin David Condic <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
>message news:9u3jdb$2i9$1@nh.pace.co.uk...
>> Make an Unbounded Array a separate data type.
>
>Right.

Well, obviously its a separate data type. :-)

The issue is wheather to provide for converting between them and lists. Note
that Ada.Strings.Unbounded does this exact same thing for Strings and
Unbounded_String's. The only real difference is that the String type already
exists, whereas the unbounded array type would have to be declared in the
package. 

---
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: Standard Queue status

[Marin David Condic]

What about this:

package Unbounded_Arrays is
    type Array_Type is private ; --etc...
end Unbounded_Arrays ;

package Unbounded_Lists is
    type List_Type is private ; -- etc...
end Unbounded_Lists ;

with Unbounded_Arrays ;
package Unbounded_Lists.Lesser_Used_Operations is
    function To_Unbounded_List (
        Item : in Unbounded_Arrays.Array_Type) return List_Type ;
end Unbounded_Lists.Less_Used_Operations ;

This has a variety of advantages. The package Unbounded_Lists supplies just
the basic plain-vanilla operations one needs for a list, so it isn't a
burden for the simple cases. There might be a whole variety of other similar
conversions one might want to perform - such as changing Maps into Lists or
Trees into Lists - we don't yet know what all of the possible abstract types
are that we might want to build or what sort of conversions would be
desirable. We are also likely to discover a large variety of
lesser-used-yet-still-useful operations that we might want to bundle up
somehwere and have available - a child package seems like the proper place
for all this potential baggage.

Want a simple list? Use Unbounded_Lists. Want to perform conversions between
all of our standard components? Grab Unbounded_Lists.Conversions and go
through a few complicated gyrations to get it to work. Want to compute
statistics on your list data? Bring in Unbounded_Lists.Statistics. Want some
clever-but-obscure list operations? Bring in Unbounded_Lists.Tenebrous.
Defering to child packages lets us initially concentrate on the really
fundamental stuff first & leave the rest for later.

I have not given much thought as to how to deal with the instantiations - it
does look like a kind of double-inheritance. However, we could probably come
up with something that stalled the operations off to a child package.
(Unbounded arrays become a descendent of unbounded lists? Gen-Spec
relationship?)

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:IPrN7.42250$xS6.70888@www.newsranger.com...
>
> The issue is wheather to provide for converting between them and lists.
Note
> that Ada.Strings.Unbounded does this exact same thing for Strings and
> Unbounded_String's. The only real difference is that the String type
already
> exists, whereas the unbounded array type would have to be declared in the
> package.
>

Re: Standard Queue status

[Ted Dennison]

In article <9u5jtj$r1d$1@nh.pace.co.uk>, Marin David Condic says...
>
>What about this:
>
>package Unbounded_Arrays is
>    type Array_Type is private ; --etc...
>end Unbounded_Arrays ;

You could do something like that. I'm just not sure it really *needs* it own
package. All I would plan on doing with them is convert them to List.

Then again, I suppose it would be consistent with the Strings packages if we had
a Lists.Fixed package. Still, other packages can wait until we have the first
one.

---
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: Standard Queue status

[Mats Karlssohn]

Ted Dennison wrote:
%<
> Personally, I like his use of the "Direction" type to specify which end to start
> from in his operations. I also like the ability to convert between lists and
> unbounded arrays. I think those may merit putting in the final version. There
> are also a number of operations in there that the strawman doesn't have which
> some folks may find useful.

Yes, the use of "Direction" is elegant, and converting to and from
unbounded arrays seems useful.

%<
> 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.

I almost started in this direction the other day...
Even 34 subprogram seems a bit bulky to me, would it be possible to
subdivide the package further (of course it would, but would it be
useful)? Would doing so nessecarily (spl ?) make instansiation that
much more complicated ?

After all one of my general rules is:
"Don't bring in more than you need"
That is, as much as I like nifty features, I want to be able to
pinpoint exactly what facets of an object/alorithm-collection that I
want to bring in for use when solving a problem. Even if
instansiations becomes numerous or _somewhat_ more complicated.

Is it just me ?


-- 
Mats Karlssohn, developer                         mailto:mats@mida.se  
Mida Systemutveckling AB                          http://www.mida.se
Box 64, S-732 22 ARBOGA, SWEDEN
Phone: +46-(0)589-89808   Fax: +46-(0)589-89809

Re: Standard Queue status

[Ted Dennison]

In article <3C05E289.C254DA29@mida.se>, Mats Karlssohn says...
>
>Ted Dennison wrote:
>%<
>> Personally, I like his use of the "Direction" type to specify which end to 

>Yes, the use of "Direction" is elegant, and converting to and from
>unbounded arrays seems useful.

I think it may also be the way to resolve some of our naming issues, although
that could just be wishful thinking on my part. :-)

>> Also I think there are too many operations in there. The package spec is 
>I almost started in this direction the other day...
>Even 34 subprogram seems a bit bulky to me, would it be possible to
>subdivide the package further (of course it would, but would it be
>useful)? Would doing so nessecarily (spl ?) make instansiation that
>much more complicated ?

Any time you make a child package of a generic, it has to be generic as well. It
also must be instantiated from the parent package's *instantiation*, not from
the parent generic unit. This is fairly confusing to most people when they first
run into it. It certianly was for me anyway. Remember that students are one of
the intended user bases of this facility. So I'd say that this is definitely
something we'd like to aviod, if possible.

As for the strawman's current size, I think it is definitely getting up near the
point where I like to split my own packages apart, but it isn't quite there yet.
That's part of the reason I've been fighting fairly hard against adding lots of
stuff that isn't a common need for a general list, or that can be just as
efficiently done by the user using the routines already provided as a base.

---
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: Standard Queue status

[Jeffrey Carter]

Mats Karlssohn wrote:
> 
> Ted Dennison wrote:
> %<
> > Personally, I like his use of the "Direction" type to specify which end to start
> > from in his operations. I also like the ability to convert between lists and
> > unbounded arrays. I think those may merit putting in the final version. There
> > are also a number of operations in there that the strawman doesn't have which
> > some folks may find useful.
> 
> Yes, the use of "Direction" is elegant, and converting to and from
> unbounded arrays seems useful.

I don't know. Specifying the direction seems like control coupling.

I don't recall an "unbounded array" in his spec. I recall unconstrained
arrays, but that's a different animal. Converting to and from
unconstrained arrays is trivial to implement with the standard features
of a list, so I'm not sure it should be in the basic package; on the
other hand, I'm not sure it shouldn't be there if it's going to be
defined at all.

> After all one of my general rules is:
> "Don't bring in more than you need"
> That is, as much as I like nifty features, I want to be able to
> pinpoint exactly what facets of an object/alorithm-collection that I
> want to bring in for use when solving a problem. Even if
> instansiations becomes numerous or _somewhat_ more complicated.

There needs to be a balance. After all, the minimum features one needs
to build and use an unbounded list are provided by Ada, but I hope no
one thinks this is an argument for not having a list ADT. On the other
hand, the operations one can think of doing with lists are limited
mainly by one's imagination. So the general rule should be something
like: include the basic operations, operations that cannot be
efficiently implemented without directly manipulating the
implementation, and extremely common operations; exclude everything
else.

The problem is agreeing on "extremely common operations".

-- 
Jeffrey Carter

Re: Standard Queue status

[Marin David Condic]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3C065B15.5CA7D10B@boeing.com...
>
> The problem is agreeing on "extremely common operations".
>

How about: Anything that we can't agree is either absolutely necessary or a
fundamental operation of an ADT goes into a child package for the ADT. For
example, one might imagine an operation that returned a list consisting of
only the odd elements of the input list. It might be useful in some
settings, but certainly isn't fundamental to the notion of what a list is.
Hence, defer it to a child package. That ought to help keep us focused and
probably won't result in too much disagreement. When in doubt, it goes in a
child package so the advocates have not lost the feature and the detractors
don't need to be burdened with it if they don't want 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: Standard Queue status

[Ted Dennison]

In article <3C065B15.5CA7D10B@boeing.com>, Jeffrey Carter says...
>
>Mats Karlssohn wrote:
>> Yes, the use of "Direction" is elegant, and converting to and from
>> unbounded arrays seems useful.
>
>I don't know. Specifying the direction seems like control coupling.

That's my problem with it exactly. Its nice to see I'm not the only classicly
trained software engineer here. :-)

I can usually get over such reservations if there is either some common code
inside, or if it makes the interface more useful (eg: can use it in a loop). I
don't think the latter will apply here, but the former might.

>unconstrained arrays is trivial to implement with the standard features
>of a list, so I'm not sure it should be in the basic package; on the
>other hand, I'm not sure it shouldn't be there if it's going to be
>defined at all.

What I was thinking was just simple to- and from-list conversion routines, and
some extra "&" functions using them as operands (but not products). Anything
more sophisticated than that should probably go into a Lists.Fixed package,
should we choose to make one.

>mainly by one's imagination. So the general rule should be something
>like: include the basic operations, operations that cannot be
>efficiently implemented without directly manipulating the
>implementation, and extremely common operations; exclude everything
>else.

Exactly.

---
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: Standard Queue status

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3C065B15.5CA7D10B@boeing.com>, Jeffrey Carter says...
> >
> >I don't know. Specifying the direction seems like control coupling.
> 
> That's my problem with it exactly. Its nice to see I'm not the only classicly
> trained software engineer here. :-)

There may be a couple of us around. On the other hand, how many of us
can also spell "classically"? :)

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail

Re: Standard Queue status

[Ted Dennison]

In article <3C06E885.B50FD00F@acm.org>, Jeffrey Carter says...
>
>Ted Dennison wrote:
>> That's my problem with it exactly. Its nice to see I'm not the only classicly
>> trained software engineer here. :-)
>
>There may be a couple of us around. On the other hand, how many of us
>can also spell "classically"? :)

I object. There's probably some English-speaking country around for which I used
the correct spelling.

That's my story, and I'm sticking to it. :-)

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

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

Re: Standard Queue status

[Mark Lundquist]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3C065B15.5CA7D10B@boeing.com...
> Mats Karlssohn wrote:
> >
> > Yes, the use of "Direction" is elegant, and converting to and from
> > unbounded arrays seems useful.
>
> I don't know. Specifying the direction seems like control coupling.

I don't think it really is control coupling.  The semantics of Direction are
defined independently from any implementation issues.  Direction is a
legitimate part of the abstraction in this case (I'm not saying I think it's
necessarily the best design).

The litmus test is, "What dependencies does it set up that you don't like?"
If it doesn't create any dependencies, then it's not coupling.  Another way
to look at it: if the approach gives you no more and no less than having two
variants (forward and reverse) for each operation, then how is one approach
any more "control coupled" than the other?

-- mark

Re: Standard Queue status

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> To get things back on track, I'd like to ask if there is anything in Nick's
> proposal that there is general consensus on putting in the strawman (or we could
> take it the other way, if that's what folks want). If you want to look at it,
> the package in question is at
> http://www.adaos.ukf.net/njr05/scl-lists-unbounded.ads.html .

I'd like to suggest a slightly different approach. 

I would find it useful to have a list of criteria, so that we can
judge each candidate by that criteria. For example, one criterium is
that the user be able to get a list package with a single
instantiation. Other criteria have been proposed, such as "lists must
be safe (ie no dangling pointers, etc) against _any_ iterator
operation". That criteria separates Ted's strawman from Nick's.

If we can all agree on what the criteria are, it will be easier to
agree on the package design. The criteria list should mention all of
the criteria that have been proposed, and say whether the consensus is
to keep it or not.

Here are some criteria I remember from this discussion:

user must be able to get a list package with a single
instantiation. 

lists must be safe (ie no dangling pointers, etc) against _any_ list
or iterator operation

lists must be efficient enough for hard real-time use

lists must be safe in a multitasking environment

lists must not be a tagged type

lists must be safe for assignment (always do deep copy, or don't allow
assignment).

list elements must not be private

lists must support elements of any Ada type (private, limited, tagged,
indefinite)

Ted (or Nick); can you post this list on your web page, and try to
keep track of votes for and against each one?

-- 
-- Stephe

Re: Standard Queue status

[Marin David Condic]

"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:ubshlheoj.fsf@gsfc.nasa.gov...
>
> lists must be efficient enough for hard real-time use
>
I don't think this was a requirement and would be hard to meet if any sort
of dynamic allocation is being done. It isn't so much an efficiency issue as
it is a determinism issue. IIRC, there seemed to be some consensus that a
v1.0 implementation could be sort of "general purpose computing" and that
other variations of the structures could be designed to meet things like
realtime requirements.

> lists must be safe in a multitasking environment
>
It would be nice to have a flavor of lists that met this requirement, but I
think the general feeling was that a) it wasn't needed for v1.0 and b) the
user could do this for themselves by encasing the list in a protected type.

>
> list elements must not be private
>
Why not? Are you saying they need to be limited private? What would you
expect them to be if they were not private?


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: Standard Queue status

[Stephen Leake]

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

> "Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
> news:ubshlheoj.fsf@gsfc.nasa.gov...
> <snip>
> >
> > list elements must not be private
> >
> Why not? Are you saying they need to be limited private? What would you
> expect them to be if they were not private?

I was not actually stating an opinion on any of these criteria; I was
simply listing them, so others could state their opinions on each one.

I guess I should reply to my message, and state my opinions on each.

> 
> 
> 
> 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/
> 
> 

-- 
-- Stephe

Re: Standard Queue status

[Marin David Condic]

Sorry. I didn't mean to sound critical. More a case of my not understanding
why list elements shouldn't be private - I don't get the requirement. Is the
idea that they should be limited private rather than private? ("Limited" is
still "private"). I'd restate the requirement as "list elements should be
limited" if that is the case.

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


"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:uy9kpfnxl.fsf@gsfc.nasa.gov...
> "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:
>
> > "Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
> > news:ubshlheoj.fsf@gsfc.nasa.gov...
> > <snip>
> > >
> > > list elements must not be private
> > >
> > Why not? Are you saying they need to be limited private? What would you
> > expect them to be if they were not private?
>
> I was not actually stating an opinion on any of these criteria; I was
> simply listing them, so others could state their opinions on each one.
>
> I guess I should reply to my message, and state my opinions on each.
>

Re: Standard Queue status

[Ted Dennison]

In article <9u5ll7$ron$1@nh.pace.co.uk>, Marin David Condic says...
>
>"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
>news:ubshlheoj.fsf@gsfc.nasa.gov...
>>
>> lists must be efficient enough for hard real-time use
>>
>I don't think this was a requirement and would be hard to meet if any sort
>of dynamic allocation is being done. It isn't so much an efficiency issue as
>it is a determinism issue. IIRC, there seemed to be some consensus that a

I believe it was more of a "should" than a "shall" requirement. You clearly
can't entirely get rid of dynamic allocation for an "unbounded" structure. But
what you can do is try to fix it so that once the structure is "set" (no more
deletions, additions, or moves), it can be used without any heap allocations
occuring. If its feasable to do this without violating a "shall" requirement,
there is no good reason to not design it that way.

>> lists must be safe in a multitasking environment
>>
>It would be nice to have a flavor of lists that met this requirement, but I
>think the general feeling was that a) it wasn't needed for v1.0 and b) the
>user could do this for themselves by encasing the list in a protected type.

I believe that is what we got to. However, I do think that at least the routines
themselves should be re-entrant. It should be possible for a user to make things
task-safe by synchronizing all accesses to the same list object. That would give
us the level of safety folks have come to expect from the standard Ada library.

---
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: Standard Queue status

[Marin David Condic]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:p0vN7.42577$xS6.71670@www.newsranger.com...
>
> I believe it was more of a "should" than a "shall" requirement. You
clearly
> can't entirely get rid of dynamic allocation for an "unbounded" structure.
But
> what you can do is try to fix it so that once the structure is "set" (no
more
> deletions, additions, or moves), it can be used without any heap
allocations
> occuring. If its feasable to do this without violating a "shall"
requirement,
> there is no good reason to not design it that way.
>
I get your point. I'd agree to reentrancy and efficiency and lack of dynamic
allocation once the list is built - all of which just on general principle.
Even non-realtime stuff shouldn't suffer with needless inefficiency or
unpredictable behavior without good reason.

Obviously, a data structure of indeterminate size has real problems for
"hard" real time systems. Behavior of the code now depends on the number of
elements that are there at any given run. So really, anything other than a
fixed (at *compile* time) sized structure would probably be unsuitable for
hard realtime. Hence, I think the requirement should be restated:

The list should do allocation/deallocation of memory only to add or remove
elements - not to access its contents.

The list should be made as efficient and predictable as is practical for a
dynamic data structure.

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: Standard Queue status

[Ted Dennison]

In article <9u61b8$3o9$1@nh.pace.co.uk>, Marin David Condic says...
>
>Obviously, a data structure of indeterminate size has real problems for
>"hard" real time systems. Behavior of the code now depends on the number of
>elements that are there at any given run. So really, anything other than a
>fixed (at *compile* time) sized structure would probably be unsuitable for
>hard realtime. Hence, I think the requirement should be restated:

You are right that there needs to be some kind of assurance up front that the
sheer size of the list won't make schedulability a problem. But it doesn't
always have to come from the compiler.

Often times our systems have lists whose size is set by the number of items put
in a configuration file somewhere. We do this so that we don't have to resort to
a compiler to make trivial changes. For a mass-produced simulator, the end units
that you need to debug are often quite far away from any compiler. 

For example, each scheduled "item" that our RT scheduler has to schedule is put
in a configuration file (along with stuff like what frequency it runs at, and
whether its disabled or not). This is obviously going to end up in a list. It
would be tough to concieve of a RT scheduler that *doesn't* use some kind of
list. The issue for us isn't how it handles additions, since those happen at
startup, or deletions, since those only occur when there's a fatal error. But we
do have to iterate through the list and access the items in real time. 

What this means is that there really is no reason why we can't use a dynamic
list, as long as its authors can restrain themselves from performing heap
operations during iterations and element fetches.

This is just one example. We actually have several lists like this that get
accessed in real time, based upon the information in some kind of configuration
file. At one point we had some engineers (ab)using our interpolation table files
for this purpose by making a bunch of single-row tables with a column for each
configuration item. They'd then try to avoid the interpolation logic by only
requesting data for columns which they knew to be in the table file. %-(

>The list should do allocation/deallocation of memory only to add or remove
>elements - not to access its contents.

Exactly. :-)

---
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: Standard Queue status

[Marin David Condic]

Well, not exactly from the compiler. More like this:

If I build a program with 100 elements in an array, then test the program
with all 100 elements in use, I now know if it can meet its performance
requirements as built. I can't possibly get 101 elements into it and have
that be the camel that breaks its straw back. I'd have to rebuild the
software tweaking that size upwards - presumably I'd be smart enough to test
the *new* worst case. For sure I know I've got a different set of bits now
and the verification of the original bits is null and void.

If its a dynamic list, I can have it allocate 100 elements and feel
confident that my accessing of those 100 elements is time-wise consistent if
I understand my design, etc. But what if the next execution of the program
ends up with 101 elements - oh, say, because a user tweaked something or an
unusual condition came up or something in the environment changed, or
whatever. If that 101'st element is the one-too-many camels, the house of
straw gets blown away by the big bad wolf.

I'm not saying you can't build hard real time with dynamic lists - it just
means you've got to be real careful about your design and understand its
limitations, etc. Asking "Did I design it to behave deterministically and
have a worst case scenario that I can test?" is a good idea. If you're
there, then O.K. I just think it is simpler with a fixed allocation.

It also depends on your relative level of paranoia. :-)

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:KQwN7.42765$xS6.72463@www.newsranger.com...
>
> You are right that there needs to be some kind of assurance up front that
the
> sheer size of the list won't make schedulability a problem. But it doesn't
> always have to come from the compiler.
>

Re: Standard Queue status

[Ted Dennison]

In article <9u6e1d$903$1@nh.pace.co.uk>, Marin David Condic says...
>requirements as built. I can't possibly get 101 elements into it and have
>that be the camel that breaks its straw back. I'd have to rebuild the
>software tweaking that size upwards - presumably I'd be smart enough to test
>the *new* worst case. For sure I know I've got a different set of bits now
>and the verification of the original bits is null and void.

Stuff like that can happen in our system quite easily. For example, a user who
knows just enough about the system to be dangerous could theoriticaly decide
that the navigational model is behaving too sluggishly for them, and go into our
configuration file and bump its iteration rate up to 30Hz where it doesn't even
have time to complete before the next iteration. Then they will start to get
overrun messages all over the place. Our answer to this is: "Don't do that". The
configuration stuff is there for diagnotic purposes, not for casual twiddling. 

---
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: Standard Queue status

[Marin David Condic]

Well, like I said, it depends a lot on your relative level of paranoia. :-)

When I used to do flight-critical software, we wouldn't have done anything
with dynamic storage out of fear that somehow, some way, a corner case might
arise that threw the timing off (or something similar) and the box might
crash - or worse. Its also much harder to verify dynamic memory stuff if
you're doing real rigorous testing.

Now that I'm working on programming digital TV boxes in C (with a *real*
crappy, unstable OS! :-) with the only true realtime requirement being
"Don't annoy the user too much" the thought of dynamic memory is a lot less
scary. (Indeed, its being used all over the place and I think its one of the
chief causes of our little box crashing a lot at the moment.) Worst case -
the box crashes & reboots and maybe someone is annoyed that you messed up
their attempt to record a rerun of "Gilligans Island".

Mind you, there's always a variety of product warranty and liability issues.
Not to mention corporate reputation, etc. Hence you still don't want any
instability if at all possible. But its easier to tolerate a potential
source of software errors in some environments than in others.

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:1oNN7.43862$xS6.73757@www.newsranger.com...
>
> Stuff like that can happen in our system quite easily. For example, a user
who
> knows just enough about the system to be dangerous could theoriticaly
decide
> that the navigational model is behaving too sluggishly for them, and go
into our
> configuration file and bump its iteration rate up to 30Hz where it doesn't
even
> have time to complete before the next iteration. Then they will start to
get
> overrun messages all over the place. Our answer to this is: "Don't do
that". The
> configuration stuff is there for diagnotic purposes, not for casual
twiddling.
>
> ---
> 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: Standard Queue status

[tmoran]

>Worst case - the box crashes & reboots and maybe someone is annoyed
>that you messed up their attempt to record a rerun of "Gilligans Island".
  People assume "I did something wrong" or "all software is buggy" when
their PC crashes.  It seems unlikely they will think the former, or
accept the latter, when the device fails to record that favorite episode.

Re: Standard Queue status

[Stephen Leake]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> I'd like to suggest a slightly different approach. 

And here are my votes on these criteria.

> user must be able to get a list package with a single
> instantiation. 

yes.

> lists must be safe (ie no dangling pointers, etc) against _any_ list
> or iterator operation

No. There should be an "Unchecked_Lists" package that is _fast_, and
perhaps another "Checked" version built on top of it.

> lists must be efficient enough for hard real-time use

No. Hard real-time doesn't do dynamic allocation.

> lists must be safe in a multitasking environment

No. Similar to "Unchecked" above.

> lists must not be a tagged type

I could go either way. Making it tagged allows deep copy on a
non-limited list, so I lean that way.

> lists must be safe for assignment (always do deep copy, or don't
> allow assignment).

Yes.

> list elements must not be private

Hmm, I meant "limited private", not "private". And all my others are
stated positively. So let's replace this with:

"List elements must be limited private".

Yes. They force the user to provide a Copy routine, allowing
multi-layered deep copies.

> lists must support elements of any Ada type (private, limited,
> tagged, indefinite)

Yes. But I could relax this one if it really is a hassle.

-- 
-- Stephe

Re: Standard Queue status

[Marin David Condic]

"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:uu1vdfn1c.fsf@gsfc.nasa.gov...
>
> > lists must not be a tagged type
>
> I could go either way. Making it tagged allows deep copy on a
> non-limited list, so I lean that way.
>
I'd kind of favor tagged and inheriting from Controlled.


>
> "List elements must be limited private".
>
O.K. I can live with that.

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: Standard Queue status

[Ted Dennison]

In article <9u627b$42t$1@nh.pace.co.uk>, Marin David Condic says...
>
>"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
>news:uu1vdfn1c.fsf@gsfc.nasa.gov...
>>
>> > lists must not be a tagged type
>>
>> I could go either way. Making it tagged allows deep copy on a
>> non-limited list, so I lean that way.
>>
>I'd kind of favor tagged and inheriting from Controlled.

That's actually kind of required, I'm afraid. Any other option is going to run
horribly afowl of the transparent storage management fans (and probably require
removal of all the funtional calls).

>> "List elements must be limited private".
>>
>O.K. I can live with that.

Perhaps, but I'm pretty sure we already argued that one and decided against it.
It would require some kind of "copy" routine be supplied as a generic, which
would require even the 90% who *don't* want to deal with limited types to go
create themselves a copy routine that performs vanilla assignment just to make
the generic happy. Some suggested that we could create limited and non-limited
versions, but the general agreement we arrived at was to just drop the whole
thing and not deal with limited types. If it ends up being a huge problem,
someone can always create a parallel "Containers.Lists.Limited_Unbounded package
later.

---
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: Standard Queue status

[Marin David Condic]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:%ZwN7.42782$xS6.72544@www.newsranger.com...
>
> Perhaps, but I'm pretty sure we already argued that one and decided
against it.
> It would require some kind of "copy" routine be supplied as a generic,
which
> would require even the 90% who *don't* want to deal with limited types to
go
> create themselves a copy routine that performs vanilla assignment just to
make
> the generic happy. Some suggested that we could create limited and
non-limited
> versions, but the general agreement we arrived at was to just drop the
whole
> thing and not deal with limited types. If it ends up being a huge problem,
> someone can always create a parallel "Containers.Lists.Limited_Unbounded
package
> later.
>

O.K., I can live with that too! :-)

Either way, you get a list structure that isn't too horribly complicated to
use. I don't find that many uses for limited private types now that we've
got finalization, so I'd be happier with a private formal. (No extra work).
But if we have really strong feelings on the other side of it, I can get
over having to define an Assign procedure. Lets shoot for private and see if
any serious limited fans come out of the woodwork.

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: Standard Queue status

[Jeffrey Carter]

Marin David Condic wrote:
> 
> Lets shoot for private and see if
> any serious limited fans come out of the woodwork.

I guess I'm already on record as being a serious limited fan, but a
standard with unlimited is better than no standard.

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail

Re: Standard Queue status

[Ted Dennison]

In article <ubshlheoj.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>I would find it useful to have a list of criteria, so that we can
>judge each candidate by that criteria. For example, one criterium is
.
>If we can all agree on what the criteria are, it will be easier to
>agree on the package design. The criteria list should mention all of

I initially produced the strawman because it looked like we had pretty much
arrived at a consensus on requirements. Building some kind of reference
implementation so that we could proceede to discuss design issues seemed the
next logical step. Of course if you subscribe to the "spiral method" of software
design, it should come as no suprise that this activity generated a new
requirement or two as well. That has happened, but for the most part I thinkg
discussions have been centered on design issues (eg: do we include an "insert
list" operation, or let the user do it themselves with the primitives).

.
>Ted (or Nick); can you post this list on your web page, and try to
>keep track of votes for and against each one?

I can certianly see the merit of posting for the record the requirements to
which the strawman has been designed on my web page. But if you want something
more complicated, like some kind of line-item votable list, then I'd have to
agree with Ehud that AdaPower would be a much better place for it. For one
thing, its just a more logical place. For another, I sort of envisoned the
strawman as the community's design, coded up by me (of course I'm in the
community too though :-) ). If it instead becomes some kind of candidate upon
which folks are voting, it really wouldn't be appropriate for the author of one
of the candidates to also tabulate the votes. That's just a recipe for acrimony.
I get enough of that at home. :-)

---
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: Standard Queue status

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <ubshlheoj.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >Ted (or Nick); can you post this list on your web page, and try to
> >keep track of votes for and against each one?
> 
> I can certianly see the merit of posting for the record the requirements to
> which the strawman has been designed on my web page. But if you want something
> more complicated, like some kind of line-item votable list, then I'd have to
> agree with Ehud that AdaPower would be a much better place for it. 

Ok, I accept your rationale for not putting this on your web site. But
who is actually going to put it on AdaPower? I don't want to spend
more time on this if it isn't going to become a real project.

-- 
-- Stephe

Re: Standard Queue status

[Ted Dennison]

In article <uofledawz.fsf@gsfc.nasa.gov>, Stephen Leake says...
>Ok, I accept your rationale for not putting this on your web site. But
>who is actually going to put it on AdaPower? I don't want to spend
>more time on this if it isn't going to become a real project.

Personally, I don't think we have anything that has needed something as formal
as a vote yet. In fact, I think it would be a bit of a failure if we actually
did make a decision on an issue by a slim majority, which is the only time a
show of hands would truly be needed. I'd much rather see decisions reached by
general consensus than by majority rule.

In the interests of pushing this forward, I will post a new (perhaps final?)
Strawman spec rev this evening. I'll ask you to reserve judgement on the
futility of this process until then. Previously I had asked that we *not* move
forward with the strawman until it had matured some (been beaten a bit more),
even though there were calls to do so. That is part of why we are still where we
are. My opinion with the new version is that it is now about ready for the next
step.

If we do achieve consensus to move forward with the strawman (or with something
else), It will indeed be put up on AdaPower, hopefully with all the appropriate
fanfare and party favors. :-)

---
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: Standard Queue status

[Jeffrey Carter]

Stephen Leake wrote:
> 
> Here are some criteria I remember from this discussion:

I thought we had reached a sort of rough consensus on these kinds of
things. I'll try to express that consensus.

> 
> user must be able to get a list package with a single
> instantiation.

Consensus: Yes.
Me: Yes.

> 
> lists must be safe (ie no dangling pointers, etc) against _any_ list
> or iterator operation

Consensus: Undecided.
Me: 99% safe is good enough.

> 
> lists must be efficient enough for hard real-time use

Consensus: No.
Me: No.

> 
> lists must be safe in a multitasking environment

Consensus: No.
Me: Basic list should be unprotected, and a protected version built on
top of it should also be provided (this comes under the heading of
"common enough" to supply, even though the client can do it himself).

> 
> lists must not be a tagged type

Consensus: No. Must be controlled.
Me: Should not be visibly tagged, but must be controlled.

> 
> lists must be safe for assignment (always do deep copy, or don't allow
> assignment).

Consensus: Yes.
Me: Should be limited.

> 
> list elements must not be [limited] private

Consensus: Yes.
Me: No.

> 
> lists must support elements of any Ada type (private, limited, tagged,
> indefinite)

Consensus: No.
Me: Needn't support indefinite types.

-- 
Jeffrey Carter

Re: Standard Queue status

[Nick Roberts]

To repeat myself, I've attempted to track these requirements and comments:

http://www.adaos.ukf.net

I've added a couple of requirements for moot.

--
Best wishes,
Nick Roberts

Re: Standard Queue status

[Stephen Leake]

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

> To repeat myself, I've attempted to track these requirements and comments:
> 
> http://www.adaos.ukf.net

Excellent. Sorry if I missed this first time around.

-- 
-- Stephe

Re: Standard Queue status

[Ted Dennison]

In article <3C06B6B8.F739A3B0@boeing.com>, Jeffrey Carter says...
>
>Stephen Leake wrote:
>> 
>> Here are some criteria I remember from this discussion:
>
>I thought we had reached a sort of rough consensus on these kinds of
>things. I'll try to express that consensus.

That pretty much matches my reading of the consensus as well.

---
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: Standard Queue status

[Simon Wright]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> Here are some criteria I remember from this discussion:
> 
> user must be able to get a list package with a single
> instantiation. 

don't care

> lists must be safe (ie no dangling pointers, etc) against _any_ list
> or iterator operation

I need to know what operations are safe and what operations aren't

> lists must be efficient enough for hard real-time use

yes

> lists must be safe in a multitasking environment

I'm prepared to supervise access myself, I think

> lists must not be a tagged type

don't care

> lists must be safe for assignment (always do deep copy, or don't allow
> assignment).

yes

> list elements must not be private

?

> lists must support elements of any Ada type (private, limited, tagged,
> indefinite)

I'm pretty sure I want this, how expensive is it going to be?



Should the list work under JGNAT? (or OA or .. other JVM-tageted
compiler). The BCs don't, because of nasty tricks to do with avoiding
aliasing and converting an "in" by-reference parameter to a variable.

Re: Queue

[Brian Rogoff]

On Tue, 27 Nov 2001, Matthew Heaney wrote:
> "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
> message news:9u0qhb$pq5$1@nh.pace.co.uk...
> > I'd still be willing to settle on the BC's with some enhancements and
> > extensions. Anybody else willing to go that route?
> 
> No.  The problem with the Booch Components is that they use inheritance,
> which is completely unnecessary unless you require dynamic polymorphic
> behavior.
> 
> The C++ STL doesn't use inheritance.  The use of iterators and algorithms
> abstracts away the details of specific containers, and thus treats all
> collections as a "sequence."  This is a form of static polymorphism.

Interestingly enough, there was a proposal to do something like this
(very much like the C++ STL) in Ada circa 1990. I mentioned it loooong 
ago, maybe in 1997 when there was some discussion of the STL here. I
forget the author's name, but she was a prof at some South African
university. What's interesting to me is that this was completely
independent of the STL line of work. I can dig up the ref if anyone is
interested. 

Doing an STL like library in Ada is certainly possible, but it will never
fit as snugly with Ada as the STL does with C++, for a number of reasons. 

> The standard library should provide only the most basic primitives, from
> which higher-level abstractions can be constructed.

I agree completely. To do otherwise would be an abstraction inversion. You 
can build a safe library on top of a fast one, but not vice-versa. 

-- Brian

Re: Queue

[Mats Karlssohn]

Brian Rogoff wrote:
%<
> Interestingly enough, there was a proposal to do something like this
> (very much like the C++ STL) in Ada circa 1990. I mentioned it loooong
> ago, maybe in 1997 when there was some discussion of the STL here. I
> forget the author's name, but she was a prof at some South African
> university. What's interesting to me is that this was completely
> independent of the STL line of work. I can dig up the ref if anyone is
> interested.

Please do! I'd like to read that.

> Doing an STL like library in Ada is certainly possible, but it will never
> fit as snugly with Ada as the STL does with C++, for a number of reasons.

I haven't really dug into this subject, would you care to expand on
this issue and perhaps suggest ways to make it fit better with Ada.


-- 
Mats Karlssohn, developer                         mailto:mats@mida.se  
Mida Systemutveckling AB                          http://www.mida.se
Box 64, S-732 22 ARBOGA, SWEDEN
Phone: +46-(0)589-89808   Fax: +46-(0)589-89809

Re: Queue

[Brian Rogoff]

I thought I replied, but my reply didn't even show up on Google groups.
&@#$ing computers!

On Wed, 28 Nov 2001, Mats Karlssohn wrote:
> Brian Rogoff wrote:
> %<
> > Interestingly enough, there was a proposal to do something like this
> > (very much like the C++ STL) in Ada circa 1990. I mentioned it loooong
> > ago, maybe in 1997 when there was some discussion of the STL here. I
> > forget the author's name, but she was a prof at some South African
> > university. What's interesting to me is that this was completely
> > independent of the STL line of work. I can dig up the ref if anyone is
> > interested.
>
> Please do! I'd like to read that.


@article{ bishop90effect,
    author = "J. M. Bishop",
    title = "The Effect of Data Abstraction on Loop Programming
Techniques",
    journal = "IEEE Transactions on Software Engineering",
    volume = "16",
    number = "4",
    publisher = "IEEE Computer Society",
    address = "Washington, DC",
    pages = "389--402",
    year = "1990"
}

> > Doing an STL like library in Ada is certainly possible, but it will never
> > fit as snugly with Ada as the STL does with C++, for a number of reasons.
>
> I haven't really dug into this subject, would you care to expand on
> this issue and perhaps suggest ways to make it fit better with Ada.

Well, for one thing pointer traversal using ++, --, etc is a common idiom
in C and C++, and since those operators, and [], are overloadable in C++,
STL code for traversing an ADT looks like low level pointer bumbing code.
C also has that ability to refer just beyond the end of an array and that
notion maps well to the one off the end iterator value.

The excessive instantiations that you need in an Ada version of the STL
become ponderous IMO. I believe this is a fundamental problem with Ada
generics, and perhaps even a fundamental issue in statically typed
languages, namely, when do we prefer explicit (manifest?) types and when
do we prefer implicit types. My own opinion is that I'd like a language
with both. Ada has only the first, and while modern high level languages
(think ML and Haskell here) provide both I'm a bit unsatisfied with the
way it all fits together (not to drift too far, but I'd like something
like Haskell's type classes and not just ML's universal style of
polymorphism, *and* I want a decent module system). I guess I'm not meant
to be happy with any programming language :-).

One of the things that annoys me about Ada is the fact that there is a lot
of nice notation that I, the programmer, can't change. It would be nice if
there were a more generalized notion of 'First and 'Last, since that's
what Ada programmers would like to use in an Ada "STL". If you just map
the STL concepts onto Ada directly, using, say, Incr, Decr, Pred, Succ
Get_Value, Set_Value, etc., instead of the C shorthand, Ada programmers
will still complain that the resulting library doesn't "look like" Ada.
Sorry, nothing can be done about that.

Just so I don't sound entirely negative, generic formal package
parameters, and the signature trick, really make something like the STL,
or Bishop's approach, a lot cleaner in Ada 95 than was possible in Ada 83.
It also makes the STL easier to understand, since you can express the
notion of "iterator category" (I think that's what Alex Stepanov called
it, I can't remember since it was a few years ago) pretty directly with
a few signatures (Forward_Iterator_Sig, Bidirectional_Iterator_Sig, etc.).

Sorry for rambling, I guess I'll ramble off now...

-- Brian

Re: Queue

[Ted Dennison]

In article <Pine.BSF.4.40.0111300447310.89131-100000@bpr.best.vwh.net>, Brian
Rogoff says...
>One of the things that annoys me about Ada is the fact that there is a lot
>of nice notation that I, the programmer, can't change. It would be nice if
>there were a more generalized notion of 'First and 'Last, since that's
>what Ada programmers would like to use in an Ada "STL". If you just map
>the STL concepts onto Ada directly, using, say, Incr, Decr, Pred, Succ
>Get_Value, Set_Value, etc., instead of the C shorthand, Ada programmers
>will still complain that the resulting library doesn't "look like" Ada.
>Sorry, nothing can be done about that.

I like that idea. Hopefully redefining of more attributes will make its way into
Ada 20XX. I'd add 'Image to the list.

---
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: Queue

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:LCNN7.43879$xS6.73853@www.newsranger.com...

> I like that idea. Hopefully redefining of more attributes will make its
way into
> Ada 20XX. I'd add 'Image to the list.
>


I remember being so sure this must be possible, I spent tons of time trying
and looking in the RM for the way to overload (common) attributes. After
that I made rationalization about why this is not possible in most cases...

Ehud

Re: Queue

[Ehud Lamm]

Brian Rogoff <bpr@bpr.best.vwh.net> wrote in message
news:Pine.BSF.4.40.0111300447310.89131-100000@bpr.best.vwh.net...
>
> The excessive instantiations that you need in an Ada version of the STL
> become ponderous IMO. I believe this is a fundamental problem with Ada
> generics, and perhaps even a fundamental issue in statically typed
> languages, namely, when do we prefer explicit (manifest?) types and when
> do we prefer implicit types. My own opinion is that I'd like a language
> with both. Ada has only the first, and while modern high level languages
> (think ML and Haskell here) provide both I'm a bit unsatisfied with the
> way it all fits together (not to drift too far, but I'd like something
> like Haskell's type classes and not just ML's universal style of
> polymorphism, *and* I want a decent module system). I guess I'm not meant
> to be happy with any programming language :-).
>

I am with you on this.
In a sense this is a language engineering issue. We want to safety brought
by explicit instanations etc., but we don't want to have to use it all the
time.
I am still not sure what's the best way of combining these features, but it
seems to me there shouldn't be a theoretical problem here, just a need for
smart language design.

> Just so I don't sound entirely negative, generic formal package
> parameters, and the signature trick, really make something like the STL,
> or Bishop's approach, a lot cleaner in Ada 95 than was possible in Ada 83.
> It also makes the STL easier to understand, since you can express the
> notion of "iterator category" (I think that's what Alex Stepanov called
> it, I can't remember since it was a few years ago) pretty directly with
> a few signatures (Forward_Iterator_Sig, Bidirectional_Iterator_Sig, etc.).
>

Signature packages are a very important concept, and add expressive power
that I like.
Indeed, formal packages were a great addition to the language. But they can
be improved upon (for example, I'd like to be able to elegantly require that
 two formal packages share some parameters, etc.)

Ehud

Re: Queue

[Thomas Wolf]

Brian Rogoff wrote:

> Interestingly enough, there was a proposal to do something like this
> (very much like the C++ STL) in Ada circa 1990. I mentioned it loooong
> ago, maybe in 1997 when there was some discussion of the STL here. I
> forget the author's name, but she was a prof at some South African
> university. What's interesting to me is that this was completely
> independent of the STL line of work. I can dig up the ref if anyone is
> interested.
> 
> Doing an STL like library in Ada is certainly possible, but it will never
> fit as snugly with Ada as the STL does with C++, for a number of reasons.

Don't know if this has already been mentioned or is generally known.
But...

The C++ STL started out as an Ada 83 generic library. Only in 1990 the
authors changed from Ada 83 to C++ as their implementation language.

There is an Ada 95 version of the STL called SGL done by Dave Musser and
Alexander Konstantinou available at the URL
<http://www.cs.rpi.edu/pub/stl/SGL-2.0a3.tar.gz>.

--
---------------------------------------------------------------------
Dr. Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: Queue

[Ted Dennison]

In article <Pine.BSF.4.10.10111272129470.93360-100000@bpr.best.vwh.net>, Brian
Rogoff says...
>
>Doing an STL like library in Ada is certainly possible, but it will never
>fit as snugly with Ada as the STL does with C++, for a number of reasons. 

I was actually hoping to end up with something like that. Not an Ada version of
the STL, but rather something on the STL's level of ease of use and power, but
fitting in "snugly" with Ada and its libraries. That's why I kept pointing back
to the STL as a point of comarison in the discussions.

---
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: Queue

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:u89N7.40977$xS6.68933@www.newsranger.com...
> I was actually hoping to end up with something like that. Not an Ada
version of
> the STL, but rather something on the STL's level of ease of use and power,
but
> fitting in "snugly" with Ada and its libraries. That's why I kept pointing
back
> to the STL as a point of comarison in the discussions.
>

I think it is fair to ask whether Ada makes this goal too hard to achieve.
I think some things we came across (like the need of nested instnatiations,
when using an OO design; or the library level instnation needed if we want
to use Controlled) can't be solved nicely with Ada95. Maybe this can guide
some language changes.
In fact, the STL influenced the C++ design process too.

Ehud

Re: Queue

[Mats Karlssohn]

Matthew Heaney wrote:
> 
> "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
> message news:9u0qhb$pq5$1@nh.pace.co.uk...
> > I'd still be willing to settle on the BC's with some enhancements and
> > extensions. Anybody else willing to go that route?
> 
> No.  The problem with the Booch Components is that they use inheritance,
> which is completely unnecessary unless you require dynamic polymorphic
> behavior.

I have vorried about this and actually I think it is this property that I
like most (dislike least ? :-) about STL. I havn't actually had any
problems arising from BC's using inheritance during my (admittedly small)
use of them.

%<
> The standard library should provide only the most basic primitives, from
> which higher-level abstractions can be constructed.

Yes, AND much of the 'standard' higher-level stuff should probably be
availible in standard add-on pakages (at least after version 1.1).


-- 
Mats Karlssohn, developer                         mailto:mats@mida.se  
Mida Systemutveckling AB                          http://www.mida.se
Box 64, S-732 22 ARBOGA, SWEDEN
Phone: +46-(0)589-89808   Fax: +46-(0)589-89809

Re: Queue

[Mats Karlssohn]

Marin David Condic wrote:
%<
> I'd still be willing to settle on the BC's with some enhancements and
> extensions. Anybody else willing to go that route?

Yes, I'd be willing to support the BC's. They DO exist and they have
worked quite fine in the projects where I have used them. Although
I have to admit that I have not made any esoteric use of them. I also
find them somewhat bulky, but I can't say that I've made any real
measurements on neither code size nor execution time, so that may
just be my imagination.

What enhancements (spl ?) are we talking about ?

-- 
Mats Karlssohn, developer                         mailto:mats@mida.se  
Mida Systemutveckling AB                          http://www.mida.se
Box 64, S-732 22 ARBOGA, SWEDEN
Phone: +46-(0)589-89808   Fax: +46-(0)589-89809

Re: Queue

[Marin David Condic]

The weaknesses of the BC's have been discussed in other threads here quite a
bit. My personal favorite is that they don't have persistence & would need
some version of 'Read and 'Write implemented for them so that structures
could be loaded/stored from/to files/streams. The other objections seem to
center around the excessive complexity of the BC's making them too hard to
use for more simple situations. No real fix for that except to add on some
extension to the library that provides for the more simple cases in a manner
that wouldn't be at all in keeping with the flavor of the BC's. Hence, there
is resistance to the idea of using the BC's as the basis and possibly more
support for the idea of building a library from the ground up.

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/


"Mats Karlssohn" <mats@mida.se> wrote in message
news:3C0496B9.813D5667@mida.se...
>
> What enhancements (spl ?) are we talking about ?
>

Re: Queue

[Mats Karlssohn]

Marin David Condic wrote:
> 
> The weaknesses of the BC's have been discussed in other threads here quite a
> bit. My personal favorite is that they don't have persistence & would need
> some version of 'Read and 'Write implemented for them so that structures
> could be loaded/stored from/to files/streams. The other objections seem to
> center around the excessive complexity of the BC's making them too hard to
> use for more simple situations. No real fix for that except to add on some
> extension to the library that provides for the more simple cases in a manner
> that wouldn't be at all in keeping with the flavor of the BC's. Hence, there
> is resistance to the idea of using the BC's as the basis and possibly more
> support for the idea of building a library from the ground up.

OK, I'm back on track...
The persistance/streams stuff havn't really been a concern of mine, so
I will not comment on that.
As for the instansiation complexity, Yes, it can be complex, but
somehow I've always managed. I guess that it took an hour or so the
first time with a lot of digging around in the source. But once one
get the feel for it the biggest problem is IMHO to com up with
sensible names for the 'intermediate' packages/types. Sometimes I
really whish that Ada would provide anonymous types.

*smacks my fingers with the ruler and tell myself to stop ranting*

-- 
Mats Karlssohn, developer                         mailto:mats@mida.se  
Mida Systemutveckling AB                          http://www.mida.se
Box 64, S-732 22 ARBOGA, SWEDEN
Phone: +46-(0)589-89808   Fax: +46-(0)589-89809

Queue

[steve]

i have sent up a queue package using head and tail pointers, and have
procedures for adding, removing and nodes. But l am haveing trouble writing
a procedure for displaying the nodes. Can anyone send me a procedure where
you can display all the nodes.

Thanks in advance.

Steve

Re: Queue

[Jeffrey Carter]

steve wrote:
> 
> i have sent up a queue package using head and tail pointers, and have
> procedures for adding, removing and nodes. But l am haveing trouble writing
> a procedure for displaying the nodes. Can anyone send me a procedure where
> you can display all the nodes.

That's quite simple:

generic -- Display_Nodes
   with function End_Of_Nodes return Boolean;
   with function Get (Q : Queue) return Node;
   with procedure Next (Q : in out Queue);
   with procedure Display (N : in Node);
procedure Display_Nodes (Q : in out Queue);

procedure Display_Nodes (Q : in out Queue) is
   -- null;
begin -- Display_Nodes
   All_Nodes : loop
      exit All_Nodes when End_Of_Nodes (Q);

      Display (N => Get (Q) );
      Next (Q => Q);
   end loop All_Nodes;
end Display_Nodes;

Seriously, since we have no idea what your queue package looks like,
what a node looks like, or what you mean by "display", how can you
expect anyone here to be able to do this? If, as seems likely, this is a
homework assignment, no one here will do your homework for you. Your
first place to go for help should be your instructor. If you have
specific problems and your instructor can't help you, then we might be
able to help with a clearly stated and narrowly focused question.

-- 
Jeff Carter
"We call your door-opening request a silly thing."
Monty Python & the Holy Grail