Thoughts about Collections

[jeshaw2]

Also, did I understand you correctly as agreeing with me that a collection need not be Iterable?
 
If so, that means that Deque, Stack and Queue are not Iterable by default.  One may provide an Iterator (or do you believe you shouldn't be able to); but if you don't, you can only use their default Interface which doesn't include one - thus confirming our restricted access Policy.

I think I agree with you, however I'm arriving at this position from a different direction.  My logic starts with real-world observations.

We've agreed that without Tags the isOrdered property is not applicable.  Thur, the only order possible in an unTagged collection is the implicit Ordinal order established by the relative, temporal order in which Items are entered into the collection.  We have also agreed that Iterators operate on the collection's Ordinal Order.  Now, if I can find just one real-world case where a default iteration does not work properly (i.e., return Items in their Ordinal Order, or some function based thereon) then I can say that the collection is not inherently iterable "out of the box".

On Saturdays, everyone in our village goes grocery shopping and the queue at the meat counter becomes quite crowded.  The butcher attempts to remember our Ordinal order and iterate across the customers in a fair and orderly fashion, but (to the butcher) the customers in the queue appear to exhibit Brownian Motion as they socialize with each other during their wait.  As a consequence, I have noted with dismay that customers arriving after me are occasionally served before me.

Now, at the PIM level, we design our queues with a memory device to keep track of a queue's Ordinal Order.  In fact, using a computer built with today's technology, forces that upon us. thus all collections are iterable in a PIM.  But, at the CIM level not all collections come with a memory device (such as rope enclosed isles)  to retain the Ordinal Order of its Parts.

After much grumbling by the customers, the butcher installed one of those machines that dispenses sequential number tags as a surrogate memory device.  But that converted the queue to a Tag Ordered Set.  

Thus I arrive at the conclusion that collections, at the CIM level, have faulty or non-existent memories and therefore need Iterators defined for them.

I'll go on to say that, in addition to providing access to parts in a collection, iterators enforce access rights to the collection.

[mikewhit]

Excuse me parachuting in, I may have missed most of the context (and therefore be talking rubbish), but

Thus, the only order possible in an unTagged collection is the implicit Ordinal order established by the relative, temporal order in which Items are entered into the collection

What about some implementation-dependent order such as you might find if 'internally' examining a hash table in index order ?

All that matters in this case is whether you get to see every item uniquely, and the iterator could at least guarantee to do that.

[jeshaw2]

Hi Mike;  Glad you jumped in.  Reviews are always good.  

You quoted me as saying

Thus, the only order possible in an unTagged collection is the implicit Ordinal order established by the relative, temporal order in which Items are entered into the collection

I took this position because I accepted Paolo's following definition (which I took by everyone's silence as being, if not correct, at least acceptable for the time being).

Iterator: Retrieves one item at a time by applying a function over the ordinal position of the current Item.

You also said:

What about some implementation-dependent order such as you might find if 'internally' examining a hash table in index order ?

At the PIM or PSM level, I would agree with this statement, however, we being at the CIM level, do not have an implementation to speak of yet.    In any event, to do that, the Iterator would need to be nested in the collector to have special access to the Item's attributes.  I agree that such a nesting could take place.
Paolo's definition:

Iterate: To say or perform again; repeat Thus Iterator: Something we use to repeatedly access the collection. In particular, the process of moving from one item to the next is repeatable.

tends to support your assertion.


Then you suggested:

All that matters in this case is whether you get to see every item uniquely, and the iterator could at least guarantee to do that.

I feel good about that, but I remain unconvinced.  Earlier I made the assertion that an Iterator, being called repeatedly by its client, needs to remember its state in the iteration; and, to do that each client needs to have its own copy of an Iterator object. I'm not sure how to provide each client with their own copy of a nested Iterator.   :-/

I'm also concerned about this in a multi-threaded environment where it is possible for a second process to modify the contents of the collection while in mid-iteration by the first process.  In that context, I don't even know how to define "every item in the list"!  Its a moving target...

Perhaps Paolo can shed some light on this?

[Paolo F Cantoni]

Like I said before, let's keep mutability out of this until we've sorted out the other things.

I'm near to republishing an updated Unified Theory when we finalise the outstanding issues (apart from mutability) raised so far.

We can then say: for immutable lists this is a valid theory.  Then look at how mutability affects it.  Hopefully, mutability will be just a Policy like many others...

My AU$ 2c (about US$ 1.5c)

Paolo

[mikewhit]

where it is possible for a second process to modify the contents of the collection while in mid-iteration

I guess that your model either doesn't care about such an eventuality, in which case it doesn't matter, or it does care, in which case you'd better define the semantics within your model, too !

(Or insist on mutually-exclusive access.)

[Paolo F Cantoni]

Hi,
some thoughts that came into my mind while reading this interesting discussion.
[size=13][SNIP][/size]
Regards Martin

Welcome also, Martin.

I think, if I understand you correctly, what Jim and I are proposing is more or less what you are after.

In my CIM I have a base (Parameterized) Collection Class.  The Collection Class is Directed by a number of Policies, each of which has a number of PolicyImplementations.  The policies include a number of those Jim and I have discussed so far.

When you create a new Collection Class from the (Template) Collection Class, you nominate which PolicyImplementations are to be used for the particular instance you are creating.  Through the magic of correct Inheritance and Realization (still to be implemented by EA) the instance will receive all the Features appropriate to the specification.

Keep those thoughts coming in,

Paolo

[size=0]©2005 Paolo Cantoni, -Semantica-[/size]

[jeshaw2]

Martin (Mike?);

I've been thinking about your last two posts and I now believe that I'm in full agreement with you.  

In my thought process, I discovered that, at the CIM level, not only should I not be concerned with how things are accomplished, I should also not let Economic considerations constrain my thinking either.

Unless specifically asked, I'll not try to explain how I got from your comments to that revalation, but I do thank you for the mental prodding.