Re: List Container Strawman 1.4

["Nick Roberts" <nickroberts@adaos.worldonline.co.uk>]

"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