Sparx Systems Forum

Discussion => Uml Process => Topic started by: jeshaw2 on October 21, 2005, 12:46:12 pm

Title: Thoughts about Collections
Post by: jeshaw2 on October 21, 2005, 12:46:12 pm
In another thread, Paolo asserted:
Quote
Collections collect (group) things.

I'm not sure, but I don't think he was using the word group in the same way we do when discussing the <<memberOf>> meronymic relationship.  At least, I hope not, for I'm thinking that the term Collection is better reserved and used for a gathering of objects, in a simple association, which are not part of a meronymic relationship.

However, I've seen in other texts that in order for two objects to be associated, messages must pass between them.  I kind of like that thought, but I can also visualize a vector of objects that do not intercommunicate that I might also call a collection (e.g.; things in a shopping cart).  Perhaps, this latter context, the vector is a container of objects that are not in a collection?  But then I must reconcile myself to another truthful assertion:
Quote
All containers define collections (even if only implicitly - the objects contained)

I seem to be caught in a Catch-22 with this.  Can anyone help me clarify this?

Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 21, 2005, 05:47:05 pm
Quote
In another thread, Paolo asserted:
Collections collect (group) things
I'm not sure, but I don't think he was using the word group in the same way we do when discussing the <<memberOf>> meronymic relationship.

Jim, so you don't have to make any assumptions :):
I was using the noun  Collection: A group of objects or works to be seen, studied, or kept together.
and I was using the verb group: To place or arrange in a group
Quote
At least, I hope not, for I'm thinking that the term Collection is better reserved and used for a gathering of objects, in a simple association, which are not part of a meronymic relationship.
I think you have been offered the Eric Morecambe Gambit (Eric was a very famous British comedian - with his partner Ernie Wise):  "Get out of that - without moving!"
It seems to be you can't get a collection of things without a meronymic relation, since you automatically create a whole - the Collection.
Quote
However, I've seen in other texts that in order for two objects to be associated, messages must pass between them.  I kind of like that thought, but I can also visualize a vector of objects that do not intercommunicate that I might also call a collection (e.g.; things in a shopping cart).  Perhaps, this latter context, the vector is a container of objects that are not in a collection?  But then I must reconcile myself to another truthful assertion:
All containers define collections (even if only implicitly - the objects contained)
I seem to be caught in a Catch-22 with this.  Can anyone help me clarify this?
The message assertion is another example of how object modellers are constrained by their own language (as you concurred with the observation by my colleague Vince).

For two objects to be associated, someone/thing has to make the association.  The objects themselves never need know they are associated.  They can be associated by inference (derivation).  My brother (Luigi) is such, because he is also the son of both my mother and father.

Two objects that are associated may pass messages:
a) if they want to
b) if they can locate the associated object and their interface.

In neither case does this affect the association.

In the limiting case, the objects may be associated merely[/] because I have chosen (arbitrarily) to place them in the same collection (vector being a form of collection)

I once went to a talk on "Objects without Classes".  The presenter, a University lecturer, was going on about how his system merely created Objects and dynamically grouped them together using Attribute values.  So I asked him what he thought Classification was?  What is a Class but a collection (Classifier) of objects that share the same structure and behaviour?

What structure is the Collective whole we defined above?  A Classifier (in this case a Class).

I have previously expressed the view that Collection describes the Member_Of meronymy.  I still hold to that.

You appeared to have a problem with that.  Has my clarification resolved anything for you?

Assuming you have no further problem with Collection being the Member_Of meronymy, we can continue this (Collections) thread discussion the nature and properties of the various Collection types.

HTH,
Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 21, 2005, 06:34:22 pm
Paolo;
These statements were of great help!

Quote
[SNIP]In the limiting case, the objects may be associated merely because I have chosen (arbitrarily) to place them in the same collection (vector being a form of collection)

[SNIP]The objects themselves never need know they are associated.  They can be associated by inference (derivation).

[SNIP]
It seems to be you can't get a collection of things without a meronymic relation, since you automatically create a whole - the Collection.


All my uncertainties have been resolved.

So where do we go next on collections?
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 21, 2005, 07:16:58 pm
Quote
[size=13][SNIP][/size]
Assuming you have no further problem with Collection being the Member_Of meronymy, we can continue this (Collections) thread discussion the nature and properties of the various Collection types.
Go for it...

One thing where I think we might constructively start is on defining some terms in a (coding) language neutral way.

I've had trouble, in the past, getting a clear definition (with respect to collections) of the differences (if any) between :


Maybe we can start with that?

Also, while we are at it.  I think we should formally define that Collection meronyms are Items (not Elements etc)

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 21, 2005, 08:06:48 pm
Quote
One thing where I think we might constructively start is on defining some terms in a (coding) language neutral way.
Yes, I can think of several terms I'd like to do this with also; Just to be sure we are all properly calibrated together.

Quote
  • Iterator
  • Enumerator
  • Indexer
This is a good starting point.  I'll start gathering my thought on them.

Quote
I think we should formally define that Collection meronyms are Items (not Elements etc)
Agreed.  Items is a much better term.  Elements carries too much baggage with it.
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 22, 2005, 07:06:11 am
With regard to the terms Iterator, Enumerator, & Indexer and in the context of Collections, I have the following (personal & informal) thoughts and connotations attached to them:

A work in process...
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 22, 2005, 06:52:59 pm
Jim,

I've put your original quote in Blue and my response in   Navy...
With regard to the terms Iterator, Enumerator, & Indexer and in the context of Collections, I have the following (personal & informal) thoughts and connotations attached to them:

A work in process...
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 23, 2005, 07:18:46 pm
Quote
For the purposes of the discussion I'm going to propose the following definitions:
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.
Enumerate: To count off or name one by one; list  It's not clear to me what the difference is between an Enumerator an Iterator.  In this context.
Index: To guide, point out, or otherwise facilitate reference  This would appear to be the ability to randomly access something.

This was essentially the point at which I started with my thoughts.  

When you suggest objects of type Iterator, Indexer, and Enumerator, I'm envisioning  objects which interact with collections in specialized ways.  Is the abstractions of such objects what you are attempting to get at?

Rambling on a bit more...

When I include a collection within my model, at the CIM level,  I generally have a need to either impact the collection itself or interact with a subset of its items.  I either want to Modify the list of items in the collection (add, remove, count, etc.), Notify the items of some event (as in the publish/subscribe pattern), or Request a service of the Items (including a simple value mapping service).  All of these are facilitated by messages which are Synchronous or Asynchronous.  My desire is to see to it that these messages are sent to their targeted Items.  I don't care how the messages are sent, how the Items are organized within the collection, nor the technology or route the messenger takes to effect delivery (unless the problem domain is the delivery of messages).  In fact, in some cases, I don't even care if the message is successfully delivered or responded to.

I design, therefore, to the collector's interface which effects the delivery to the identified recipient(s) using the technologies and methodologies of the collector's choice.  I prefer not to become too dependent upon the collector itself.

Quote
I would suggest that our definition of an Enumerator be broad enough to include control of Item access, Ordering and inclusion within the Collection.  By Ordering I mean specification of the basis for ordering access to the Items, not the fact that the items are Ordered within the association.  Can you clarify?
Yes.  In another thread you said
Quote
isOrdered defines whether the Collection maintains an internal ordering based upon the identifier of the items such that a sequential traversal of the items will yield and ordered sequence.
My thought was to be able to request an Enumeration (Ordered set  ;) ) with an ordering not maintained internally by the collector; such ordering to be specified in the request.

Quote
I think the terms Iterator, Enumerator relate to the services provided by the container of a Collection.  I don't want to use the term Container (since I don't believe we've established that every Collection is a Container - only that every Container has a Collection), perhaps Collector (or Collection holonym).
Good point! I agree.  However, I'm having difficulty thinking in terms of Index, Iterate, or Enumerate at the CIM level.  They seem to be denizens of a lower abstraction level.

Title: Re: Thoughts about Collections
Post by: sargasso on October 23, 2005, 08:27:26 pm
I think all three access items are necessary - at an abstract level...

Client: "Where's the peanut butter?"

Indexer: "On the middle shelf in the fridge"
Iterator: "Look at the contents of each shelf in the fridge until you find it."
Enumerator: "Remove and inspect each object in the fridge until you find one that's labelled peanut butter, then you'll know where it was"

Notice that i have ordered them by decreasing "power",  IOW the Indexer has a lot of power as it knows something about the collection (and the container), the Iterator knows something about the structure of the container but little about the collection, the Enumerator only knows
that the collection exists in the container.

There are probably lots of examples where the power stucture could be different, but I hold that all are necessary.


bruce
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 23, 2005, 08:59:07 pm
Quote
I think all three access items are necessary - at an abstract level...

Client: "Where's the peanut butter?"

Indexer: "On the middle shelf in the fridge"
Iterator: "Look at the contents of each shelf in the fridge until you find it."
Enumerator: "Remove and inspect each object in the fridge until you find one that's labelled peanut butter, then you'll know where it was"

Notice that i have ordered them by decreasing "power",  IOW the Indexer has a lot of power as it knows something about the collection (and the container), the Iterator knows something about the structure of the container but little about the collection, the Enumerator only knows
that the collection exists in the container.

There are probably lots of examples where the power structure could be different, but I hold that all are necessary.
bruce
Great Example!  But...  IMO

Indexer: "On the middle shelf in the fridge"
Iterator: "Look at the contents of each shelf in the fridge until you find it."
Enumerator: "These two items are peanut butter"

I think if we ensure that Enumerator applies only to Enumerations (Ordered Sets) then we can be rigorous.

We might say the Iterator knows nothing about the Item.  The Enumerator knows that the Item can be Enumerated and returns a subset of the collection.  I think (and this is a repetition of my point in the earlier post) that you can only apply an Enumerator to an Enumerable collection (that is, contains items that can be classified by a simple Enumeration).  It has been put to me that such an Enumerator is, by definition, a filter.  I think this is a reasonable proposition.

In C#, you can have string Indexers that would do the job of: Find me the item marked Peanut Butter.  Note, I said marked (or labelled).  In my view, the Enumerator knows the Type.


Paolo
Title: Re: Thoughts about Collections
Post by: sargasso on October 24, 2005, 12:09:20 am
Sounds good to me!  ;) but for Enumerator I didn't ask for the peanut butter I asked for its location.

bruce
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 24, 2005, 12:52:28 am
Quote
Sounds good to me!  ;) but for Enumerator I didn't ask for the peanut butter I asked for its location.
 
bruce
Good point Gunga Din...
Collection is: Items in the fridge (therefore Index is Item number)

Indexer: use this to retrieve the item numbers labeled "Peanut Butter"
Iterator: use this to iterate through the collection looking for items labelled "Peanut Butter" or of type Peanut_Butter (or both)
Enumerator: use this to return the subset of items of type Peanut_Butter

The Indexer uses some search strategy to locate the items (usually get me the nth item).
The Iterator uses a repetetive stepping through the items.
The Enumerator applies a filter to the list.

The Indexer and Enumerator are essentially declarative, the Iterator is essentially procedural.

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 24, 2005, 07:16:29 am
Quote
In C#, you can have string Indexers that would do the job of: Find me the item marked Peanut Butter.  Note, I said marked (or labelled).  In my view, the Enumerator knows the Type.
I lost you here...

Does your use of the word type mean an object's classifier/data type or are you referring to the attribute values shared by members in a <<memberOf>> relationship?  I'm with you if the term is used in the latter sense. :)
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 24, 2005, 02:34:10 pm
Quote
I lost you here...

Does your use of the word type mean an object's classifier/data type or are you referring to the attribute values shared by members in a <<memberOf>> relationship?  I'm with you if the term is used in the latter sense. :)
Yes Jim,
I think it's the latter sense is what I'm meaning.  This is a bit of thinking on-the-fly...

Essentially, I'm trying to make a distinction between a name given to something (like Jim, Paolo, bruce etc) and some categorisation (Senior, Youth, Adult, Baby) for which I can ascribe an Enumeration.

I previously said, we should use Enumerator for Enumerations.  This requires that each Item in the Collection has the Attribute that is the Enumeration.

Now, I suspect that if the collection is mixed, it may not need the same Attribute in each Item, but it must be there (and only one of) for the Enumerator to work.

Make sense?  It is on-the-fly.

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 24, 2005, 03:57:15 pm
Paolo;

Everything made sense and I agree with everything  up to this point...
Quote
it may not need the same Attribute in each Item, but it must be there (and only one of) for the Enumerator to work.
I agree with what I think you said, but I'm not sure that what you think you said is what I think you said.  Can you fly a bit slower? ???
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 24, 2005, 05:09:08 pm
Quote
Paolo;

Everything made sense and I agree with everything  up to this point...
it may not need the same Attribute in each Item, but it must be there (and only one of) for the Enumerator to work.  
 I agree with what I think you said, but I'm not sure that what you think you said is what I think you said.  Can you fly a bit slower? ???
When I wrote it I thought it might be contentious.
I'm taking my cue from the discussion on Indexers.
It seems to me that in the simple case, homogeneous collection.  Every item has the same Attribute with the same name and the same Enumeration.  So there should be no problem applying the Enumerator.  OK?  (I think we agree on this).

Now, assume a heterogeneous collection where some items are as before and some items have no such Attribute and no such Enumeration (in any other attribute).  By definition those Items without the Enumeration can't be part of the subset.  This should be OK (from first principles)

Now, consider a third case, heterogeneous collection with some of the original Items and some others That have the same Enumeration but with a different name.  If we allow that Enumerators are defined by their signature, then the compiler can work out that this other Attribute can be used to select subset Items.

Are you happier with that?

Example, Collection of Items.  Some are Jelly Beans (Attribute: BeanColour:ConfectionColour) others are Liquorice All-Sorts (AllSortColour:ConfectionColour).

We can ask the question get me the green items and get both Jelly Beans and All-Sorts.

Now, most (if not all) languages don't (natively) support this idea.  But we are defining CIM related concepts here.

Besides, to paraphrase the old aphorism:  Define it and they will code. ;D

Paolo


Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 24, 2005, 09:11:29 pm
Is it valid to say "The product of an enumeration on a bag is an ordered set"?  Similar to a SQL SELECT DISTINCT query on a database table?
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 24, 2005, 09:16:24 pm
OOPS!  Didn't see your response before I posted my question.

Yes, I'm happy with your explanation on heterogeneous sets.  That's what I thought you were saying.  :)
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 25, 2005, 01:32:12 am
Quote
Yes, I'm happy with your explanation on heterogeneous sets.  That's what I thought you were saying.  :)
OK Jim,

Now, lets look at Collections in general.

What are the features the most basic collection must have?

I've already alluded to two types of collections:
Associative (Maps, Hashes etc) and Non-Associative (Lists, Vectors etc).  

It seems to me that the Collection must have an Iterator.  Indexers and Enumerators are available depending upon the Collection type.

What Features should an Iterator implement?

Paolo

Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 25, 2005, 10:18:06 am
Just a quick note Paolo.  I must leave for work soon.

Quote
What are the features the most basic collection must have?
Before I can respond to this question, I need to build a specialization hierarchy of Collection classes, possibly based upon some combination their functionality and type.  Then I can abstract out common features to a generalized Collection class.  I'm exploring the idea that associative collections are a specialization of Sequential (non-associative) collections.

Quote
What Features should an Iterator implement?
Again, I see a specialization hierarchy of Iterator classes, paralleling the Collection hierarchy, to be analyzed for abstraction to the  top level of the hierarchy.

A couple of points on Iterators though:
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 25, 2005, 01:35:22 pm
Quote
[size=13][SNIP][/size]
I need to build a specialization hierarchy of Collection classes, possibly based upon some combination their functionality and type.  Then I can abstract out common features to a generalized Collection class.  I'm exploring the idea that associative collections are a specialization of Sequential (non-associative) collections.[size=13][SNIP][/size]
I'm having difficulty, looking at the list of Collection types from various sources, getting a good handle on the types of Collections.  In particular, which might apply to the CIM and which are more suited to the PIM and PSM or even the code itself.

Perhaps we might gainfully start by defining some named types and their functionality in a coding language neutral way?  We should resist terms like: Constant time random access is not supported or Insertion and removal in the middle take linear time.

I'll kick off with a few...

Vector:   (Non-Associative) Can be traversed in one direction only, Can add and remove from anywhere
List:   (Non-Associative) Can be traversed in both directions, Can add and remove from anywhere
Deque:   (Non-Associative) Can add and remove from either end only
Queue:   (Non-Associative) Can add at start only and remove from end only
Stack:   (Non-Associative) Can add at and remove from start only

Questions:
Traversal of Deque, Queue and Stack?
It would seem that Stack and Queue are specializations of Deque?
I've seen a definition of Deque that allows addition/removal in the middle (if so, how different from List)?
Is Uni- versus Bi-Directional traversal merely a policy to be applied?

Perhaps all we have is a matrix of policies and names to be given to specific combinations of policies?

Paolo
Title: Re: Thoughts about Collections
Post by: sargasso on October 25, 2005, 03:25:12 pm
Watch out Paolo, if you're not careful you'll invent Algol in a minute.  ;)

Dont forget linked lists, and in particular circular lists..  oh and trees as well.

Before y'all think these are implementation level constructs, last year I was involved in building a traffic simulation to check out a couple of business level queing options (single and double section clearances).  Given the nature of the network the traffic had to traverse,  a statically linked list that modelled the network was the best design we could come up with.... had to build the link handling  by hand as I couldn't find any suitable structures in the C# collections libraries.


bruce
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 25, 2005, 03:41:31 pm
Quote
Watch out Paolo, if you're not careful you'll invent Algol in a minute.  ;)
bruce,

You've guessed I'm an old Algol68 hand! ;D  Magic language!  The only mind expanding programming language I every used (except for Eiffel).  You thought, you wrote, it did!  I've been trying to regain that experience since... ;)

Quote
Don't forget linked lists, and in particular circular lists..  oh and trees as well.

Before y'all think these are implementation level constructs, last year I was involved in building a traffic simulation to check out a couple of business level queueing options (single and double section clearances).  Given the nature of the network the traffic had to traverse,  a statically linked list that modelled the network was the best design we could come up with.... had to build the link handling  by hand as I couldn't find any suitable structures in the C# collections libraries.
bruce
Point taken...
However,I want to re-iterate my point... The types of Collections in the CIM (Computationally Independent Model) cannot be described n therms of their computational characteristics.  They should only be described in terms of their functionality.

Now as a consequence there may be computational effects, but they are consequences not essentials.

Paolo

Title: Re: Thoughts about Collections
Post by: KP on October 25, 2005, 03:59:21 pm
Quote
Deque:   (Non-Associative) Can add and remove from either end only


I've never seen this word before - is it pronounced "deck" and does it behave the same as a deck of cards?
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 25, 2005, 04:17:39 pm
Quote
I've never seen this word before - is it pronounced "deck" and does it behave the same as a deck of cards?
As far as I know, it IS pronounced 'deck'

According to ACRONYM finder Deque stands for Double Ended Queue - which is in accord with the definition I gave.

So, it doesn't behave like a deck of cards...

HTH,
Paolo
Title: Re: Thoughts about Collections
Post by: KP on October 25, 2005, 04:21:49 pm
Quote
As far as I know, it IS pronounced 'deck'

According to ACRONYM finder Deque stands for Double Ended Queue - which is in accord with the definition I gave.

So, it doesn't behave like a deck of cards...

HTH,
Paolo

Thanks for that - my new word for the day!
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 25, 2005, 11:42:26 pm
Quote
Perhaps all we have is a matrix of policies and names to be given to specific combinations of policies?
I think this is the case!  I start with Non-Associative collections and Associative collections (as a specialization of Non-Associative collections) as a base.  To that, I add the following features:Applying these to the two base collection types, I can generate (dare I say all?) of the other specialized collection types.

I'm hoping that most of the these features may be Interface types to minimize the number of permutations.

Quote
I'll kick off with a few...  
Vector:   (Non-Associative) Can be traversed in one direction only, Can add and remove from anywhere
List:   (Non-Associative) Can be traversed in both directions, Can add and remove from anywhere
Deque:   (Non-Associative) Can add and remove from either end only
Queue:   (Non-Associative) Can add at start only and remove from end only
Stack:   (Non-Associative) Can add at and remove from start only

To this list I would add:
Some of the other comments related to trees, etc. Seem to be at lower abstraction levels.  Can something be abstracted from them and brought up to this level?

Quote
It would seem that Stack and Queue are specializations of Deque?
Yes, It would seem that way, but how would you handle sub setting the Inherited operations?

Quote
Is Uni- versus Bi-Directional traversal merely a policy to be applied?
Yes, but applied to the association ends not the collection holonym.
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 26, 2005, 12:08:05 am
Jim,

If you agree, I'll create an Excel 2000 spreadsheet to allow us to manage the matrix and load it up to the EA User site.

That way all the thoughts can eventually be put in one place and it will represent the current view (of the two of us at least).

Paolo

PS:  I'll use Excel 2000 since 1) I have it, 2) it seems to be the most widely available.
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 26, 2005, 04:39:43 am
Quote
If you agree, I'll create an Excel 2000 spreadsheet to allow us to manage the matrix and load it up to the EA User site.
Interesting!  A Collections Wiki   ;)  I agree.  I have Excel 2003, I think the two file types are the same, but you might consider *.cvs format to allow participation by those with steam-driven (and other alternatively fueled) computers. ;D

Need we a home for Policy & Feature Definition also?
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 26, 2005, 04:54:09 am
Quote
Quote:It would seem that Stack and Queue are specializations of Deque?  
Yes, It would seem that way, but how would you handle sub setting the Inherited operations?

[onFurtherReflection]

Perhaps it is the other way around. Deque seems to have DNA from both Stack and Queue. All three of these are controlled by a Mutation Policy.  A set of specalized interfaces seems appropriate here.

[/onFurtherReflection]
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 26, 2005, 04:59:40 am
Quote
Interesting!  A Collections Wiki   ;)  I agree.  I have Excel 2003, I think the two file types are the same, but you might consider *.cvs format to allow participation by those with steam-driven (and other alternatively fueled) computers. ;D

Need we a home for Policy & Feature Definition also?
We can include a pile of things in the Workbook.

But on the subject of Wiki.  Have you tried out TiddlyWiki?  It's cute.  A Wiki in one HTML file.  Maybe we can also use that for some other stuff?

Paolo
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 26, 2005, 05:03:10 am
Quote
[size=13][SNIP][/size] but you might consider *.CSV format to allow participation by those with steam-driven (and other alternatively fuelled) computers. ;D
I'd rather not use .CSV because I wanted to add formatting (and possibly images).

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 26, 2005, 05:04:44 am
Quote
Have you tried out TiddlyWiki?

No, but I'm interested.  I've come lately to the world of Wikis, Wikipedia being my only experience.

I'll check TiddlyWiki out.
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 26, 2005, 06:58:31 am
Jim,

It's up on the EA User Group site, under Shared Documents, UMLAbstractions.

Add some more entries.

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 26, 2005, 07:52:29 am
Paolo;
I can see it, but I can't save it.  I'm awaiting a UserId to the site.

I'll add to it.  First, I want to add some Policy Headings.

In the Associative column, is the heading read as isAssociative and does the "X" indicate true?
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 26, 2005, 01:39:31 pm
Quote
[size=13][SNIP][/size]
In the Associative column, is the heading read as isAssociative and does the "X" indicate true?
Yes and Yes
Title: Order Policy
Post by: jeshaw2 on October 26, 2005, 08:40:57 pm
Here are my thoughts on the Order Policy I mentioned earlier in this thread.

Order Policy

Collections that need an ordering of their Items are Ordered Collections.  

Ordered Collections may only contain items that, taken together, form a full order according the the collection's ordering function.  This does not and should not require the ordering function itself to realize a full order; ordering may be achieved by ways other than an ordering function.

The enumertion order of an Ordered Associative collection is a full order consistent with the partial order of the keys.  The enumeration order of an Ordered non-Associative collection is a full order consistent with the partial order of the items.

For both collection types, any remaining nondeterminism in the ordering of items must be absorbed by the Enumeration Policy.

For the Java programmer, the default Equivalence function for ordered collections is x.compareTo(y).

On a UML Class Structure diagram, Ordered Collections shall have the property string isOrdered displayed at the holonym end of the Collection/Item association.

Your thoughts?
Title: Re: Order Policy
Post by: KP on October 26, 2005, 08:51:12 pm
Quote
On a UML Class Structure diagram, Ordered Collections shall have the property string isOrdered displayed at the holonym end of the Collection/Item association.


UML 2.0 says the notation should be {ordered} rather than isOrdered (isOrdered is the name of the property)

Neil
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 26, 2005, 09:13:51 pm
OOPS!  You are correct.  I'll fix my notes.   :-[
Thanks.
Title: Collision Policy
Post by: jeshaw2 on October 26, 2005, 10:43:43 pm
Here are my thoughts on the Collision Policy I mentioned earlier in this thread.

Collision Policy

A collision policy comes into play in two circumstances:
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 27, 2005, 08:08:32 am
Quote
It's up on the EA User Group site, under Shared Documents, UMLAbstractions.
 
Add some more entries.
I've added some entries  :)

I'm wondering if you would consider all of the Sets to be Associative since, via an Indexer, one may 'retrieve the item numbers "Peanut Butter" '?  I put a grayed out X in the spreadsheet.
Title: Re: Collision Policy
Post by: jeshaw2 on October 27, 2005, 09:48:28 am
[onFurhterReflection]

Perhaps unique is a Homonym: same word, different meaning?

On an association, unique is a promise of the collection's nature, but on a mutator-operation it is a constraint upon the possible outcomes of the mutation, and on an derivation-operation it is a collision resolution specification within the derived collection?

If so, this would impact my logic on where it would be reasonable to use Replacing and Multi.

[/onFurhterReflection]
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 27, 2005, 03:13:37 pm
Quote
I've added some entries  :)

I'm wondering if you would consider all of the Sets to be Associative since, via an Indexer, one may 'retrieve the item numbers "Peanut Butter" '?  I put a grayed out X in the spreadsheet.
I've added some more back.   I'm happy to have Sets as Associative.  Is it possible to have an Associative Collection that doesn't allow Ordinal manipulation?  If so, we need another column.

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 27, 2005, 04:36:22 pm
Quote
Is it possible to have an Associative Collection that doesn't allow Ordinal manipulation?  If so, we need another column.
 Can you expand on what Ordinal manipulation might entail?

BTW, I just made indexed lists immutable. :)
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 27, 2005, 05:24:16 pm
Paolo

Quote
I'm happy to have Sets as Associative.

Actually, I was hoping you'd talk me out of it; because now, what is the difference between a set and a map  ???  Is it that a map has an explicit key and a set has a derived key (derived from the item's position)?  :-/

Perhaps the Indexer is an object that derives a map, which is associative, from an existing set which is non-associative?   :-/
Title: Enumeration Order Policy
Post by: jeshaw2 on October 27, 2005, 09:07:00 pm
Here are my thoughts on the Enumeration Order Policy I mentioned earlier in this thread.  This is a derivtive work based on a literature search across the internet.

Enumeration Order Policy

Collections may be designated as enumeratable or notEnumeratable.  enumeratable presupposes the existence of an object that traverses the collection in some specified manner.  In the context of this policy, the traversal may be performed by an Enumerator, Iterator, or an Indexer.

Enumeration Order Policies are specified in terms of operations used to derive new collections from existing collections. This policy does not address issues of collection containment, persistence, nor anything else beyond the ordering of Items within the derived collection.

There are usually three players to keep track of, for which I use the following terminology:

   newCollection := existingCollection.derivationOp (proposedContent)

A newCollection is derived from a subset of the existingCollection plus the addition of any proposedContent.  The existingCollection may, or may not, be a null collection and the subset may include zero to all of the existing items in the existingCollection.  The proposedContent may, or may not, be null, but it is fully included (not subsetted) in the newCollection. Collisions resulting from this merging of Items from two sources are resolved by the Collision Policy for the collection.

The default Enumeration Order for unsorted collections is based on where items were inserted to the existingCollection.  The default Enumeration Order for ordered collections is based upon the ordering function of the existingCollection.

Two, of the many other, Enumeration Order Policies are LIFO (specific to Stacks) and FIFO (specific to Queues and Priority Queues).
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 28, 2005, 03:56:40 am
Quote
 Can you expand on what Ordinal manipulation might entail?

BTW, I just made indexed lists immutable. :)
I just meant access via the integer Indexer.

I just say Indexer any more can I?  ;D

In the light of our discussions in this Thread, what do you mean by Indexed List?  And why is it immutable?

Paolo
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 28, 2005, 05:17:42 am
Quote
Paolo
Actually, I was hoping you'd talk me out of it; because now, what is the difference between a set and a map  ???  Is it that a map has an explicit key and a set has a derived key (derived from the item's position)?  :-/
A Set is a Collection whose Items are just values (for example, an Enumeration is an Ordered Set of EnumerationLiterals).  A Map is a Collection whose items consist of two parts, a Name and a Value (or Object).
Quote
Perhaps the Indexer is an object that derives a map, which is associative, from an existing set which is non-associative?   :-/
It's unfortunate that due to natural language constraints, we get confusion due to the Index homonym.  (I'm subject to it too...)

For my own work (and in my models, designs and documentation) I make a strict distinction between Keys and Indexes.  A Key is a uniqueness constraint which is (typically) supported by an underlying unique Index.  Thus I no longer use the phrase Unique Index, just Key.  Indexes aid access, Keys provide Referential Integrity.

In the context of the Collections and situations we are dealing with here, I don't think we need to directly expose any Indexes (in the DBMS sense).

An Indexer does not require an Index to provide Ordinal access to a Collection.
Interestingly, we haven't discussed if an Indexer can return more than one Item from the Collection (for example: give me every third Item).

An Indexer can be defined for non-Ordinal access (using some attribute value of the items).  Here, again, it may return more than one Item (for example, give me the "Blue" Items).  Indexes may be used to assist in returning these items, but that is an internal implementation issue.  Not a part of the definition.

In the case of {unique} collections, then Keys are involved.

In the case of Mapped Collections, the Name is used to access the Item.  In the case of a Map, the Name is unique (identifies exactly one item), in the case of the Multi-Map, there may be more than one Item with that Name.

As far as I can determine, an Unordered Map is a Hash.  Thus, notwithstanding that a unique Name is a precondition, you can't get an Ordered Iterator.  An Ordered Map provides the Ordered Iterator.

I have to admit I'm having difficulty comparing apples with apples in looking up stuff on Collections on the Net as they seem all to be language specific and sometimes the same word means slightly different things, depending on the language involved.

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 28, 2005, 12:42:21 pm
Quote
In the light of our discussions in this Thread, what do you mean by Indexed List?  And why is it immutable?
Given your last post, my meaning may change ;)  Here is what I meant at that time and allow me the fun of developing  a telephone book example that I'm contemplating for use with my students:

List: an unordered, disarrayed, not unique, un-contained, unaddressable collection of values.  For example, I cut the phone numbers out of my phone book.  I made sure each phone number individually appeared, with no other information, on its own little piece of confetti.  I blew the confetti through a fan and let the pieces fall where they may.  That gave me a list of phone numbers.  (I can't use the term set here, but if I swept them in to an envelope would I than have a bag ???)

Indexed list: a list where the values are arranged in sequence (not necessarily in an order) so that they may be referenced by their position in the sequence.  For example:  I brought in the neighborhood kids and had them arrange the phone number confetti in a long, single row down the sidewalk.  Thus, I could reference a phone number by its position (i) in the row -- fromHead(i) or fromTail(i). Now, needing the phone number located at Row.fromTail(1,234,592), I may send out a child to count back from the tail of the collection to the phone number desired and bring what they discover at that position back to me for use.  I refer to i as the index.

Why immutable? Well, technically it is mutable.  However, I find it difficult to carry the indexed phone list with me on trips out of town (too hard to get it past airport security and makes it difficult to maintain by the folks on the home front too), but I can remember my home phone number.  

When on a trip, I normally need access to a subset of the phone book (clients, friends, etc.), so I maintain a very small pocket phone book, on a preprinted, shiny, white plastic <<show-off in the pub>> reference card, containing the names of interesting individuals, but instead of including their phone numbers, I keep  the index to their number in the Row collection thus assuring that I'm in quasi-third normal form *feeling proud now".

When I need to call an associate, I first call my daughter at home and give her the index to the number I need.  She runs out, counts down to the referenced location, and calls me back (albeit a few days later) with the needed number.  

Imagine my dismay when I discover that several phone numbers have been removed from the list (I didn't even know those individuals either) and now all of the index numbers on my pre-printed, shiny, white plastic <<show off in the pub>> card are useless!!!  You can bet that when I got home, I made the Row collection immutable; problem fixed!  *Really feeling proud now!*

Well, my problem solution set my neighbor (Paolo)'s head to wagging and he posted something about indexes, keys, and such.  Let me read on and see what that's all about...

Title: Re: Thoughts about Collections
Post by: jkorman on October 28, 2005, 01:29:49 pm
Quote
Given your last post, my meaning may change ;)  Here is what I meant at that time and allow me the fun of developing  a telephone book example that I'm contemplating for use with my students:

List: an unordered, disarrayed, not unique, un-contained, unaddressable collection of values.  For example, I cut the phone numbers out of my phone book.  I made sure each phone number individually appeared, with no other information, on its own little piece of confetti.  I blew the confetti through a fan and let the pieces fall where they may.  That gave me a list of phone numbers.  (I can't use the term set here, but if I swept them in to an envelope would I than have a bag ???)


Jim, You lost me here. I was under the assumption that a list had order! Given your example of the phone list
As I see it, your phone book is a list of phone numbers. Each page, an arbitrarily sized sub-list.  Once you cut each entry from the other, you no longer have a list. Especially after spreading the confetti about the room.  ;)

Side note : I am enjoying these discussions. I'm looking forward to a compilation in more readable form.

Jim


Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 28, 2005, 02:11:46 pm
In my search on the INTERNET, bag is shown as a synonym of list  :-/  Paolo said in the thread isUnique isOrdered (http://www.sparxsystems.com.au/cgi-bin/yabb/YaBB.pl?board=UMLPRO;action=display;num=1128734367) a bag is un-orded and not unique.  I perceive a phone book (uncut) as an Ordered Map of phone numbers, given that it is associative between the phone numbers and the individual's names.  

I suspect there is a nuance of a difference between a list and a bag, but it is beyond any metrics I've come across so far.

Quote
Side note : I am enjoying these discussions. I'm looking forward to a compilation in more readable form.
Thanks...it is in my mind to do so.
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 28, 2005, 05:46:57 pm
Paolo;

Quote
A Set is a Collection whose Items are just values (for example, an Enumeration is an Ordered Set of EnumerationLiterals). A Map is a Collection whose items consist of two parts, a Name and a Value (or Object).
I agree with your assertions here, but I'm suspicious of the example ???  But no matter, I get your point.  BTW: Would you apply this portion of a set's definition to a vector, list, and bag? Further, do these collection types appear at the CIM level?

Quote
A Key is a uniqueness constraint which is (typically) supported by an underlying unique Index. Thus I no longer use the phrase Unique Index, just Key. Indexes aid access, Keys provide Referential Integrity.

In the context of the Collections and situations we are dealing with here, I don't think we need to directly expose any Indexes (in the DBMS sense).
This is a bit of a stretch for me, but I think I understand and can provisionally accept for now.  I need time to internalize this.  I'm sure you are correct for modeling this at the CIM level.  One 'Gunga Din' patch for your vest here!

Quote
An Indexer does not require an Index to provide Ordinal access to a Collection.
Agreed.

Quote
Interestingly, we haven't discussed if an Indexer can return more than one Item from the Collection (for example: give me every third Item).

An Indexer can be defined for non-Ordinal access (using some attribute value of the items). Here, again, it may return more than one Item (for example, give me the "Blue" Items). Indexes may be used to assist in returning these items, but that is an internal implementation issue. Not a part of the definition.
You seem to be blurring the distinctions you made earlier between Indexer and Iterator.

Quote
In the case of {unique} collections, then Keys are involved.
 I disagree with this.  I can allow this for maps, but for sets the item's value is used for the equivalence test.  (Ref; my thoughts on Collision Policy above.)

Quote
As far as I can determine, an Unordered Map is a Hash.
 If by this, you mean a hash table, then I would want it to be immutable also! ;D

Quote
Thus, notwithstanding that a unique Name is a precondition, you can't get an Ordered Iterator. An Ordered Map provides the Ordered Iterator.
???  Got lost here. Can you provide more words?  BTW: In my thinking, Indexers, Iterators, and enumerators (if available for a given collection) are objects nested within the collection object.  

Quote
I have to admit I'm having difficulty comparing apples with apples in looking up stuff on Collections on the Net as they seem all to be language specific and sometimes the same word means slightly different things, depending on the language involved.
 Agreed in spades.  A lot of that static shows up in my classes as quoted authorities (how dare I disagree with all those sources?) making me look like a heretic.  ::) The reasonings we are going through here are helping to deal with that in a more dignified manner. :)

And just to be clear:  Sets are essentially non-associative collections?  But they can be made to look associative? (this is where I'm at now.)

Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 28, 2005, 11:48:56 pm
[size=16]STOP PRESS!  Important edit[/size]
Jim,
I made the original post, but I had a lingering concern over my response to your question regarding Sets being non-associative.  I've now found the problem with my (original response).  I now believe my highest level categorisation of Collections into Associative and non-Associative is incorrect.  The Items in the categorisations, I still believe are correct.  That is, Sets go with Maps.  But the naming of the categorisation is incorrect.  What I called Associative Collections should now be called Value Based.   This means that Each Item in the collection is a Value, not an Object.  In the Object based collection, the items are objects.

In the case of Maps, we have an Associative collection since we associate something with the Value Item (an object, another value).  Value based collections can thus entertain the concepts of Ordering and/or Uniqueness

So, if you substitute the term Value Based for Associative and Object based for non-Associative everything I've said so far is still valid (I think) - I just named them incorrectly!
Quote
Paolo
A Set is a Collection whose Items are just values (for example, an Enumeration is an Ordered Set of EnumerationLiterals). A Map is a Collection whose items consist of two parts, a Name and a Value (or Object).
I agree with your assertions here, but I'm suspicious of the example   But no matter, I get your point.  BTW: Would you apply this portion of a set's definition to a vector, list, and bag?
No, because these are not Value based, they have no concept of uniqueness.  BTW, See below, I now understand an Enumeration is a Set (It doesn't have to be an OrderedSet).
Quote
Further, do these collection types appear at the CIM level?
Yes, I think so.
Quote
A Key is a uniqueness constraint which is (typically) supported by an underlying unique Index. Thus I no longer use the phrase Unique Index, just Key. Indexes aid access, Keys provide Referential Integrity.
In the context of the Collections and situations we are dealing with here, I don't think we need to directly expose any Indexes (in the DBMS sense).
This is a bit of a stretch for me, but I think I understand and can provisionally accept for now.  I need time to internalize this.  I'm sure you are correct for modeling this at the CIM level.  One 'Gunga Din' patch for your vest here!
The explanations above should have helped clarify this.
Quote
An Indexer does not require an Index to provide Ordinal access to a Collection.
Agreed.
Interestingly, we haven't discussed if an Indexer can return more than one Item from the Collection (for example: give me every third Item).
An Indexer can be defined for non-Ordinal access (using some attribute value of the items). Here, again, it may return more than one Item (for example, give me the "Blue" Items). Indexes may be used to assist in returning these items, but that is an internal implementation issue. Not a part of the definition.
You seem to be blurring the distinctions you made earlier between Indexer and Iterator.
I don't think so.  The iterator always returns one value (at a time) by applying some constant function to the collection - I said elsewhere in this thread that I felt that the Iterator was essentially procedural.  The Indexer and Enumerator are essentially declarative.  Consequently, they behave more like an SQL SELECT.  Therefore, we should allow the possibility that an Indexer could return several items.  Remember a non-ordinal Indexer uses the attributes of the Item to determine whether to return it or not.
Quote
In the case of {unique} collections, then Keys are involved.
I disagree with this.  I can allow this for maps, but for sets the item's value is used for the equivalence test.  (Ref; my thoughts on Collision Policy above.)
Having re-read the Collision Policy, I believe you are mistaken in discussing Uniqueness for an non-Value Based Collection.  As I discuss above, there is nothing to hang the uniqueness hat on.  I stand by my original statement,.  Hopefully, my clarifications may have helped convert you. ;D
Quote
As far as I can determine, an Unordered Map is a Hash.
If by this, you mean a hash table, then I would want it to be immutable also!
Do we have to introduce immutability at this point?  In the case of CIM level stuff, it may be moot.  Anyways, I'd like to clarify other stuff before attacking immutability (if that's OK with you).
Quote
Thus, notwithstanding that a unique Name is a precondition, you can't get an Ordered Iterator. An Ordered Map provides the Ordered Iterator.
Got lost here. Can you provide more words?  BTW: In my thinking, Indexers, Iterators, and Enumerators (if available for a given collection) are objects nested within the collection object.
They're surely Features.  In my view, behavioural features.  I'm not sure they're objects, they'd be more like the Properties we discussed earlier - not well handled by UML at present.
Back to the Hash - as I understand a Hash, there is no implied ordering.  You supply the key, you get the item.  If you iterate (or ordinally index) over  the Collection, the names will come out in no particular order.  In fact, I'm not sure that the same order is guaranteed between runs on an unchanged Collection.  To provide consistent ordering, you have to apply the Constraint: IsOrdered to the Map.  Good enough?
Quote
I have to admit I'm having difficulty comparing apples with apples in looking up stuff on Collections on the Net as they seem all to be language specific and sometimes the same word means slightly different things, depending on the language involved.
Agreed in spades.  A lot of that static shows up in my classes as quoted authorities (how dare I disagree with all those sources?) making me look like a heretic.   The reasonings we are going through here are helping to deal with that in a more dignified manner.
Well, we can easily dare to disagree since they disagree among themselves!  Remember my tag line and signature... ;D

Anyway, we have no particular axe to grind, other than trying to bring clarity and consistency to our understanding - for the purposes of creating better models - a noble endeavour! :)
Quote
And just to be clear:  Sets are essentially non-associative collections?  But they can be made to look associative? (this is where I'm at now.)
OK< Jim.  Assuming you were using my previous definition of Associative, then I'll reply in the negative, but use the new definitions. Sets are Value Based because they involve a Value (Name) corresponding to (associated with) the Item.  Elsewhere I said an Enumeration is an Ordered Set, this was incorrect! All Sets are Enumerations, if the set of values (the literals not the integers - remember in the CIM the only thing we have are the literals) is ordered then we have an OrderedSet or OrderedEnumeration.  OrderedEnumeration is of no real consequence to us in normal usage - it's just an Enumeration.
The UML 2 [size=13]Superstructure[/size] (http://www.omg.org/cgi-bin/doc?ptc/2004-10-02) Specification   7.3.44 Property (from Kernel, AssociationClasses) has a nice little table specifying how isOrdered and IsUnique interact - but in the context of the values...
isOrdered isUnique Collection type
false............true..............Set
true.............true........OrderedSet
false........... false.............Bag
true............ false..........Sequence

Apologies to all for not having thought carefully enough... But I think we're getting there.

Paolo
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 29, 2005, 12:25:14 am
Quote
Given your last post, my meaning may change ;)  Here is what I meant at that time and allow me the fun of developing  a telephone book example that I'm contemplating for use with my students:
Do we agree that the original phone book is a Multi-Map (valueBased, associative, ordered, nonUnique).  If not, then the rest of my response may clarify why you should agree... ;)  It's valueBased because each name has a number (and other information associated with it).
Quote
List: an unordered, disarrayed, not unique, un-contained, unaddressable collection of values.  For example, I cut the phone numbers out of my phone book.  I made sure each phone number individually appeared, with no other information, on its own little piece of confetti.  I blew the confetti through a fan and let the pieces fall where they may.  That gave me a list of phone numbers.  (I can't use the term set here, but if I swept them in to an envelope would I than have a bag ???)
According to UML 2 you have a bag (objectBased, unOrdered, nonUnique).  Now for some clarification.  You have a list of Items - you DON'T have a list of Values.  Each Item has a value but it ISN'T a value (in the valueBased Collection sense).  I think that's where confusion has crept in (even for me, I'm improving my mental metaCIM as I type!).  Jim Korman was saying something similar, I think.
Quote
Indexed list: a list where the values are arranged in sequence (not necessarily in an order) so that they may be referenced by their position in the sequence.  For example:  I brought in the neighborhood kids and had them arrange the phone number confetti in a long, single row down the sidewalk.  Thus, I could reference a phone number by its position (i) in the row -- fromHead(i) or fromTail(i). Now, needing the phone number located at Row.fromTail(1,234,592), I may send out a child to count back from the tail of the collection to the phone number desired and bring what they discover at that position back to me for use.  I refer to i as the index.
I don't think there's any point in distinguishing a List from an Indexed List.  All Collections have an Indexer (ordinal), I think.  According to UML 2 7.3.44 (mentioned in the previous post) Sequences are Ordered.  (They're OrderedBags).  That's why they only mention the isOrdered and isUnique properties.  Since the numbers are the Items, you can ask the kid to bring you "555-5555" but they will be behaving like an Indexer.
Quote
Why immutable? Well, technically it is mutable.  However, I find it difficult to carry the indexed phone list with me on trips out of town (too hard to get it past airport security and makes it difficult to maintain by the folks on the home front too), but I can remember my home phone number.

When on a trip, I normally need access to a subset of the phone book (clients, friends, etc.), so I maintain a very small pocket phone book, on a preprinted, shiny, white plastic <<show-off in the pub>> reference card, containing the names of interesting individuals, but instead of including their phone numbers, I keep  the index to their number in the Row collection thus assuring that I'm in quasi-third normal form *feeling proud now".
Your card is a ValueBased, Associative Collection - another (multi-)Map - you put in the Name and get a number.

Quote
When I need to call an associate, I first call my daughter at home and give her the index to the number I need.  She runs out, counts down to the referenced location, and calls me back (albeit a few days later) with the needed number.
What you have at home is a Bag.  Your daughter is the Indexer (ordinal).  Your call supllies the ordinal value to be looked up.
Quote
Imagine my dismay when I discover that several phone numbers have been removed from the list (I didn't even know those individuals either) and now all of the index numbers on my pre-printed, shiny, white plastic <<show off in the pub>> card are useless!!!  You can bet that when I got home, I made the Row collection immutable; problem fixed!  *Really feeling proud now!*
You got a number because the Bag still had an nth element.  You only know it was the wrong number because the person you contacted wasn't the person you expected.

The immutability is not a requirement of the Collections, but in the interface (you have created) between the two collections.  Because you have two collections, but the wrong way round!  If at home you kept the multi-map (phone book) you would only need to keep a list of names on your card (non-valueBased, ordered (as you will), possibly unique).  Your call would now be:  "Honey, can you look up Paolo's number and give it to me?"  So long as Paolo was in the book, she'd give it to you, regardless of where his ordinal position was.
Quote
Well, my problem solution set my neighbor (Paolo)'s head to wagging and he posted something about indexes, keys, and such.  Let me read on and see what that's all about...


Paolo ;D
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 29, 2005, 07:11:21 am
Paolo;
Just a quick note.  There is a lot of stuff here to consider, but the wife just handed me a "honey-do" list.
Quote
What I called Associative Collections should now be called Value Based. This means that Each Item in the collection is a Value, not an Object. In the Object based collection, the items are objects.

In the case of Maps, we have an Associative collection since we associate something with the Value Item (an object, another value). Value based collections can thus entertain the concepts of Ordering and/or Uniqueness

So, if you substitute the term Value Based for Associative and Object based for non-Associative everything I've said so far is still valid (I think) - I just named them incorrectly!
I came across a reference that seems to mirror this Typology.  

A few threads back, I used the term Sequential to refer to non-Associative collections.  It was this reference that led me into that.  Take a look, if you will, and let me know if this is helpful, or not, to our discussion.

C++ Lecture Notes, Steven J. Zeil, Dept CompSci, Old Dominion Univ.
His use of Containers is similar to our use of Collections.  These references are:

Sequential & Associative (http://www.cs.odu.edu/~zeil/cs361/Lectures-f02/05seq/std/seqassoc.html)  Can we use these names or must they be abstracted to a higher level and renamed?

Quick Reference for STL Containers (http://www.cs.odu.edu/~zeil/cs361/Handouts/STL/stlContainers/stlContainers.html) (Presents an interesting thought on Adapters.)

Another Typology I've seen is Vectors, Arrays, and Collections.  Vectors & Arrays hold values;  Collections hold objects.

Is there a way we can reconcile / unify all of this?

Quote
Do we agree that the original phone book is a Multi-Map (valueBased, associative, ordered, nonUnique).
Yes I agree.  I picked up on the non unique property after I posted.   :-[
Title: Unified Theory of CIM Collections
Post by: Paolo F Cantoni on October 29, 2005, 06:22:05 pm
Jim,

Here's an attempt to reconcile / unify the discussions so far:

What we're attempting to do is to define a set of Collection types, suitable for use in a CIM (Computationally Independent Model).
Accordingly, we focus only on their functionality, not any considerations of computational methods.  We will attempt to define a set of properties, functionalities, capabilities, constraints and operations whereby any given combination will produce a unique name for the Collection type.  Our set of Collection Types therefore will attempt to be Canonical.

In addition, where appropriate, we will apply the UML denotations regarding collections to be found in the [size=13]Superstructure[/size] (http://www.omg.org/cgi-bin/doc?ptc/2004-10-02) Specification   7.3.44 Property (from Kernel, AssociationClasses)

In order for the notions of isOrdered an/or isUnique to be applicable, each item in the collection must expose or provide or be associated with a Tag for this purpose.  We can liken the tag to those boards carried by advertisers on the street (such as "the End is Nigh" or "Eat at Joes")  Essentially, the Tag is visible outside the Item (to the Collector - the Collection holonym).

We can thus separate Collection types into two basic categorisations:

unTagged - We can only see the Item as Opaque.
Tagged - Each opaque Item also has a visible Tag.

I'll tackle the latter one first.


[size=16]Tagged Collections[/size][/b]

Tagged Collections have Items with a Tag visible to the Collector.

Sometimes, for whatever reason, the Item is the Tag.  "The Tag, the whole Tag and nothing but the Tag".  Predominantly, however,you have a Tag and the associated Item.  These latter are denoted Associative Collections (for the obvious reason).  Thus a Tagged Collection may be either Associative or nonAssociative.  Associative Collections are also known as Maps

Since we have determined that isUnique and isOrdered required Tags and the UML section only discusses their interaction, then the section applies ONLY to Tagged Collections.  NOTE: the UML section doesn't say anything about the Collection being Associative or not, thus the terms apply equally to both.

Once we have Tags, if the there can only be unique Tags in the Collection, then the Tag acts as a Key (uniqueness constraint).   Such Collections are known as Enumerations.

Where you do not have ordering, you can also have all the operations of unTagged Collections (see below).

The Tagged Collection Types are known as:
Set:    (unOrdered, unique)
OrderedSet:    (ordered, unique)
Bag:    (unOrdered, nonUnique)
Sequence:    (ordered, nonUnique)


[size=16]unTagged Collections[/size][/b]

UnTagged Collections have Items that are Opaque to the Collector.

We can ONLY describe (identify?) each Item by their ordinal position in the Collection.  Operations such as insertion and deletion can only be carried out at certain points in the Collection:
Add to start   (addToStart)
Add in middle    (addInMiddle)
Add to end    (addToEnd)
Remove from start    (i]removeFromStart[/i])
Remove from middle    (removeFromMiddle)
Remove from end    (removeFromEnd)

If all six operations are not available, then we have a Restricted Access Collection.

The unTagged Collection Types are known as:
List:   (addToStart,addInMiddle,addToEnd,RemoveFromStart,removeFromMiddle,removeFromEnd)
Deque:   (addToStart,addToEnd,removeFromStart,removeFromEnd)
Queue:   (addToStart,removeFromEnd)
Stack:   (addToStart,removeFromStart)


[size=16]Collection Features[/size][/b]

All collection types have two features:
Iterator:   Retrieves one item at a time by applying a function over the ordinal position of the current Item.
Indexer:   Retrieves one or more items at a time by applying a function some property of the Items.  NOTE: an Indexer can provide similar functionality to the Tag in a Tagged Collection.  The difference is that in the Tagged Collection the Collector provides a standard Indexer operation, in an unTagged collection, if no indexer is provided, then one will not exist.
In addition, where the Item contains an attribute whose values are an Enumeration one can define an:
Enumerator:   Retrieves one or more items at a time by applying a filter on an Enumerable property of the Items.

The Iterator is essentially procedural.  Indexer and Enumerator are essentially declarative.

Multiple Iterators, Indexers and Enumerators may be defined for a Collection, but they must vary in their signatures.


As far as I can tell, these are the ONLY Collection types available at the CIM level.  All others are either:
PIM (Platform Independent Model)
PSM (Platform Specific Model)
applicable due to some computational or logistical internals.

HTH,
Paolo

BTW: I've uploaded a new version of the Abstractions document, consistent with these definitions.
[size=0]©2005 Paolo Cantoni, -Semantica-[/size]
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 29, 2005, 06:22:53 pm
Paolo;

Quote
This means that Each Item in the collection is a Value, not an Object.  In the Object based collection, the items are objects.
 
In the case of Maps, we have an Associative collection since we associate something with the Value Item (an object, another value).  Value based collections can thus entertain the concepts of Ordering and/or Uniqueness

I need some help with this.  Can you  provide a real-word example from each of the two collection types including some represetnative data?
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 29, 2005, 06:30:37 pm
Quote
Paolo;

I need some help with this.  Can you  provide a real-word example from each of the two collection types including some representative data?
Does my new Unified Theory help?  If not, let me know and I'll provide examples...

Paolo  (going off to his "honey-do" list...)
Title: Re: Unified Theory on CIM Collections
Post by: jeshaw2 on October 29, 2005, 11:19:32 pm
Paolo!  Nice piece of work!  I think I understand this!  However, lets make sure I understand this by paraphrasing in a less formal language..
Quote
What we're attempting to do is to define a set of Collection types, suitable for use in a CIM (Computationally Independent Model).
Accordingly, we focus only on their functionality, not any considerations of computational methods. We will attempt to define a set of properties, functionalities, capabilities, constraints and operations whereby any given combination will produce a unique name for the Collection type. Our set of Collection Types therefore will attempt to be Canonical.
 There is a whole bunch of stuff we can do at the PIM, PSM and coding levels that we won't recognize as being available or existing at the CIM level.  We shall speak only of the real-world essence of things in our domain, what is to be done with them, and not how it will be done, or how it could be done when we develop the software.

Quote
In addition, where appropriate, we will apply the UML denotations regarding collections to be found in the Superstructure Specification 7.3.44 Property (from Kernel, AssociationClasses)
Specifically, collection properties and collection classification in to collection types.

Quote
In order for the notions of isOrdered an/or isUnique to be applicable, each item in the collection must expose or provide or be associated with a Tag for this purpose.
The collection association properties isOrdered=true|false and isUnique=true|false are constraints on the association.  Their evaluation requires information about the Items, from somewhere, to work against.  What ever the source of that information, we shall refer to it as the Item's Tag.
Quote
We can liken the tag to those boards carried by advertisers on the street (such as "the End is Nigh" or "Eat at Joes") Essentially, the Tag is visible outside the Item (to the Collector - the Collection holonym).
Our practice of Data hiding would normally prevent  the Collector object  (the one representing the whole collection) from accessing the collected Item's attributes.  At the CIM level, however, we trust that the needed information will (some how and in some way) be made available when needed, and for the present, we are content to simply give a name to this information so that we may make reference to it within or CIM level discussions and documentation.

Quote
We can thus separate Collection types into two basic categorizations:

unTagged - We can only see the Item as Opaque.
Tagged - Each opaque Item also has a visible Tag.
If we are able to evaluate isOrdered and isUnique the collection is of one type, if not it is of the other type.  Further, we shall proceed as if the Collector can not see any of the Item's attributes except for the Tag information which may be exposed to the collector.

Quote
Tagged Collections

Tagged Collections have Items with a Tag visible to the Collector.
By our own definition this is true.

Quote
Sometimes, for whatever reason, the Item is the Tag. "The Tag, the whole Tag and nothing but the Tag".
An atomic piece of data like my phone number confetti chips.
Quote
Predominantly, however, you have a Tag and the associated Item.
My phone number confetti chips would not qualify for this case.  Even though the phone number could  be associated with an individual, there is nothing on or within the confetti chips themselves to make that association.  To qualify, information about the individual would need to be present, but not necessarily visible, on or within the chip.
Quote
These latter are denoted Associative Collections (for the obvious reason).
 Thus a Tagged Collection may be either Associative or nonAssociative. Associative Collections are also known as Maps
Collections having Items similar to my confetti chips with out the information about the individual are nonAssociative.  Collections having Items similar to my confetti chips with the information about the individual are Associative.

Quote
Since we have determined that isUnique and isOrdered required Tags and the UML section only discusses their interaction,
In terms of collection types.
Quote
then the section applies ONLY to Tagged Collections. NOTE: the UML section doesn't say anything about the Collection being Associative or not, thus the terms apply equally to both.
If mom didn't tell me to "keep out of it", the cookie jar was fair game.

Quote
Once we have Tags, if the there can only be unique Tags in the Collection, then the Tag acts as a Key (uniqueness constraint).
Not to be confused with a DBMS type "key"...its a constraint, not a piece of data.  Also, we may say a similar thing about ordered collections.
Quote
Such Collections are known as Enumerations.
Huh ??? Enumerations must be unique?  I'm not sure about that yet, I need more thought about this.

Quote
Where you do not have ordering, you can also have all the operations of unTagged Collections (see below).
Gee! Can't I, at least, have some of them? Wondering if the uniqueness impacts their availability?

Quote
The Tagged Collection Types are known as:
Set: (unOrdered, unique)
OrderedSet: (ordered, unique)
Bag: (unOrdered, nonUnique)
Sequence: (ordered, nonUnique)
The number of these types are doubled when you take non- and Associative collections in to consideration.  [looking askance] at the naming conventions used in our spread sheet. [/looking askance]


Quote
unTagged Collections

UnTagged Collections have Items that are Opaque to the Collector.

We can ONLY describe (identify?) each Item by their ordinal position in the Collection. Operations such as insertion and deletion can only be carried out at certain points in the Collection:
Add to start (addToStart)
Add in middle (addInMiddle)
Add to end (addToEnd)
Remove from start (i]removeFromStart[/i])
Remove from middle (removeFromMiddle)
Remove from end (removeFromEnd)

If all six operations are not available, then we have a Restricted Access Collection.

The unTagged Collection Types are known as:
List: (addToStart,addInMiddle,addToEnd,RemoveFromStart,removeFromMiddle,removeFro mEnd)
Deque: (addToStart,addToEnd,removeFromStart,removeFromEnd)
Queue: (addToStart,removeFromEnd)
Stack: (addToStart,removeFromStart)
This is intuitively easy to understand.


Quote
Collection Features

All collection types have two features:
Iterator: Retrieves one item at a time by applying a function over the ordinal position of the current Item.
Indexer: Retrieves one or more items at a time by applying a function over ? some property of the Items.
True if that property is non-opaque to the indexer.
Quote
NOTE: an Indexer can provide similar functionality to the Tag in a Tagged Collection. The difference is that in the Tagged Collection the Collector provides a standard Indexer operation, in an unTagged collection, if no indexer is provided, then one will not exist.
In addition, where the Item contains an attribute whose values are an Enumeration one can define an:
Enumerator: Retrieves one or more items at a time by applying a filter on an Enumerable property of the Items.
Again, True if that property is non-opaque to the Enumerator.

Quote
The Iterator is essentially procedural. Indexer and Enumerator are essentially declarative.
For the benefit of the "greater unwashed", more words on procedural and declarative would be nice to have.

Quote
Multiple Iterators, Indexers and Enumerators may be defined for a Collection, but they must vary in their signatures.
This is an important point; and, not a problem to understand.


Quote
As far as I can tell, these are the ONLY Collection types available at the CIM level.
Might I suggest Priority Queues?

Well, I'm still up in the air about Enumerations being unique.  Well, how did I do?

Title: Re: Unified Theory on CIM Collections
Post by: Paolo F Cantoni on October 30, 2005, 01:32:30 am
Quote
Paolo!  Nice piece of work!  I think I understand this!  However, lets make sure I understand this by paraphrasing in a less formal language..
Yes, very good move Jim.  And an excellent job!
Quote
[size=13][SNIP][/size]
Our practice of Data hiding would normally prevent  the Collector object  (the one representing the whole collection) from accessing the collected Item's attributes.  At the CIM level, however, we trust that the needed information will (some how and in some way) be made available when needed, and for the present, we are content to simply give a name to this information so that we may make reference to it within or CIM level discussions and documentation.
Well, technically the Tag is not the Item, so it can come from anywhere.  It's not even the function of the Collector to find the Tag, they just have to accept it.  The object asking to add the Item provides the Tag.  How it got it is its business.
Quote
If we are able to evaluate isOrdered and isUnique the collection is of one type, if not it is of the other type.  Further, we shall proceed as if the Collector can not see any of the Item's attributes except for the Tag information which may be exposed to the collector.
Yes, I think this point is fundamental. I didn't get to this point until I started writing the previous post.  See also the regarding the Features below...
Quote
[size=13][SNIP][/size]
Not to be confused with a DBMS type "key"...its a constraint, not a piece of data.  Also, we may say a similar thing about ordered collections.
My use of Key in both places is identical.  A Key uniquely identifies the Row in the Table, the Item in the Collection.  While a Key is not required to enforce uniqueness, it does enforce uniqueness.  (In another post I make the clear distinction between Key and DBMS Index)
Quote
Huh ??? Enumerations must be unique?  I'm not sure about that yet, I need more thought about this.

The UML 2 [size=13]Superstructure[/size] (http://www.omg.org/cgi-bin/doc?ptc/2004-10-02) Specification
7.3.16 Enumeration (from Kernel)
An enumeration is a data type whose values are enumerated in the model as enumeration literals.
7.3.17 EnumerationLiteral (from Kernel)
An EnumerationLiteral has a name that can be used to identify it within its enumeration datatype. The enumeration literal
name is scoped within and must be unique within its enumeration.
Enumeration literal names are not global and must be
qualified for general use.
(emphasis mine)
Quote
[size=10][SNIP][/size]
Gee! Can't I, at least, have some of them? Wondering if the uniqueness impacts their availability?
Yes, that was exactly my assessment, uniqueness robs you of their availability.
Quote
The number of these types are doubled when you take non- and Associative collections in to consideration.  [looking askance] at the naming conventions used in our spread sheet. [/looking askance]
Yes, I agree, but I couldn't see any way around it.
Quote
[size=13][SNIP][/size]
For the benefit of the "greater unwashed", more words on procedural and declarative would be nice to have.

procedural   concerned with how to manipulate symbols, concepts, and rules to accomplish a task or solve a problem
declarative    concerned with the recall of facts and events
In a declarative request, I ask the system to return me some result.  The System figures out how to do it.
In a procedural request, I have to tell the system how to return me the result.  You can better appreciate the difference by comparing a DBMS stored procedure to a DBMS select statement.
Quote
[size=10][SNIP][/size]
Might I suggest Priority Queues?
Yeah, I looked at them before I moved them out.  I couldn't see how they differed from sufficiently from a normal queue to warrant their own type.  They are certainly a specialization of Queue.  Do we have a new Feature... Prioritiser?
Quote
Well, I'm still up in the air about Enumerations being unique.  Well, how did I do?
Enumerations should be sealed by now...  You done good!

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 30, 2005, 06:45:39 am
Paolo;  Thanks.  This is going well I think.

Quote
Well, technically the Tag is not the Item, so it can come from anywhere.  It's not even the function of the Collector to find the Tag, they just have to accept it.  The object asking to add the Item provides the Tag.  How it got it is its business.
We trust that, having received the tag, the collection will have some mechanism for keeping the tag visible and associated with the Item it identifies? (This is also needed to test isUnique and to support isOrdered.)

Quote
A Key uniquely identifies the Row in the Table, the Item in the Collection.
Sounds like a Primary Key to me?

Quote
The enumeration literal name is scoped within and must be unique within its enumeration
Sounds similar to SQL's SELECT ... DISTINCT capability.

Quote
Quote:Where you do not have ordering, you can also have all the operations of unTagged Collections (see below).  
 
Gee! Can't I, at least, have some of them? Wondering if the uniqueness impacts their availability?

Yes, that was exactly my assessment, uniqueness robs you of their availability.
But I can have some restricted access to support Priority queues?

Quote
procedural   concerned with how to manipulate symbols, concepts, and rules to accomplish a task or solve a problem
declarative    concerned with the recall of facts and events
In a declarative request, I ask the system to return me some result.  The System figures out how to do it.
In a procedural request, I have to tell the system how to return me the result.  You can better appreciate the difference by comparing a DBMS stored procedure to a DBMS select statement.
So, in my CIM model, I might include some dynamic diagrams to support the procedural request, but probably not for the declarative?

Quote
Might I suggest Priority Queues?  
 
Yeah, I looked at them before I moved them out.  I couldn't see how they differed from sufficiently from a normal queue to warrant their own type.  They are certainly a specialization of Queue.  Do we have a new Feature... Prioritiser?
Well, it seems natural to access a priority queue in the same way as we access a normal queue.   I wouldn't want to burden the accessor with prioritizing responsibilities.  But we now have a queue that would allow the Prioritizer to add in middle to supporting an ordering that is not purely FIFO. (Perhaps a FIFO ordering within a priority level.)
Title: Unified Theory of CIM Collections
Post by: jeshaw2 on October 31, 2005, 04:33:30 am
Quote
In order for the notions of isOrdered an/or isUnique to be applicable, each item in the collection must expose or provide or be associated with a Tag for this purpose.
I must admit that the first time I saw the term Tag in the above context, I almost confused it with the concept of UML Tagged Values.  I have a natural aversion to overloading terms in technical documents.

Instead of Tag, might I suggest another term, such as Moniker?
Title: Re: Unified Theory of CIM Collections
Post by: Paolo F Cantoni on October 31, 2005, 05:39:59 am
Quote
I must admit that the first time I saw the term Tag in the above context, I almost confused it with the concept of UML Tagged Values.  I have a natural aversion to overloading terms in technical documents.

Instead of Tag, might I suggest another term, such as Moniker?
I've no particular penchant for Tag.  But...

There are two basic types of Collections:
Monikered and Unmonikered  
...sounds a bit naff, as the Brits say...

How about I see your Moniker, and raise a Label?

Paolo  ;D
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 31, 2005, 06:13:45 am
Quote
How about I see your Moniker, and raise a Label?


For me, Label carries more of a burden than Tag  :(

I'll see your Label and check for a bit.  *Headed for my Thesaurus*  ;D
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on October 31, 2005, 06:20:05 am
Quote
Paolo;  Thanks.  This is going well I think.
Yes, I agree.  But what about others?  I think Jim and I would like feedback.
Quote
We trust that, having received the tag, the collection will have some mechanism for keeping the tag visible and associated with the Item it identifies? (This is also needed to test isUnique and to support isOrdered.)
Yes.  This is implicit in Tagged(Labelled) Collections.
Quote
Sounds like a Primary Key to me?
I don't want to publish my monograph on DB keys and Indexes, unless specifically requested.  But just like we are doing with Collections, it presents a Unified Theory of Keys and Indexes and their names that clarifies the terms very precisely.  In that Ontology, a Key is a unique identifier (A primary Key is just one of these).
Quote
Sounds similar to SQL's SELECT ... DISTINCT capability.
Precisely.
Quote
But I can have some restricted access to support Priority queues?
No, you can't you naughty boy!  Take your medicine like a man!  Even in a priority queue, you put things in at one end and get them out at the other...  It's what goes on inside the queue - to which you don't have access that's the real issue.

I suspect we can handle this by saying that just as Stacks have special operations: Push & Pop.  A Queue also has special operations:  Enqueue and Dequeue.  The Enqueue operation can be defined to determine where in the collection, the Enqueued Item will go.  Dequeue just takes the Item off the end.  The action of Enqueue can be determined by the Prioritization Policy (which could be quite complex).

How does that sound?
Quote
So, in my CIM model, I might include some dynamic diagrams to support the procedural request, but probably not for the declarative?
No, you can have diagrams for both.  My point is really that because the Indexer and Enumerator are essentially declarative, they operate at the (mathematical) Set level and can return manifold Items at a time.  The Iterator only returns one Item at a time.

Quote
Well, it seems natural to access a priority queue in the same way as we access a normal queue.   I wouldn't want to burden the accessor with prioritizing responsibilities.  But we now have a queue that would allow the Prioritizer to add in middle to supporting an ordering that is not purely FIFO. (Perhaps a FIFO ordering within a priority level.)
This should have been dealt with above.

Paolo
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 31, 2005, 07:08:01 am
Quote
Quote:But I can have some restricted access to support Priority queues?  
 
No, you can't you naughty boy!  Take your medicine like a man!  Even in a priority queue, you put things in at one end and get them out at the other...  It's what goes on inside the queue - to which you don't have access that's the real issue.
 
I suspect we can handle this by saying that just as Stacks have special operations: Push & Pop.  A Queue also has special operations:  Enqueue and Dequeue.  The Enqueue operation can be defined to determine where in the collection, the Enqueued Item will go.  Dequeue just takes the Item off the end.  The action of Enqueue can be determined by the Prioritization Policy (which could be quite complex).
 
How does that sound?


Oh man!!! :'(  I wanted to play too!  :P  Well, as long as I have some pretty buttons to push, I'll get by ... I think.   8)

I like the pretty Enqueue button.  ;D  Is it <<Stereotyped>>???
Title: Re: Thoughts about Collections
Post by: jeshaw2 on October 31, 2005, 07:33:57 am
Quote
I don't want to publish my monograph on DB keys and Indexes, unless specifically requested.  But just like we are doing with Collections, it presents a Unified Theory of Keys and Indexes and their names that clarifies the terms very precisely.  In that Ontology, a Key is a unique identifier (A primary Key is just one of these).


Well I, for one, am interested!  That topic seems to be relevant to our discussions here and it would be useful to get those terms clarified too.

Is anyone else in this forum interested?

Title: Re: Unified Theory of CIM Collections
Post by: jeshaw2 on October 31, 2005, 02:15:38 pm
Paolo;

I've been giving thought to your Tags and an Item's opaqueness trying to imagine what their UML notations might be.  That triggered some questions:

In your Ontology, does the concept of an Interface exist at the UML Level?  I'm thinking that there might be some utility for implementing Tags with them.

RE:  Items being opaque.  If the association is navigable from the Collection end, as I think is it must be for the collection to be useful, why is the Item so opaque that a tag construct is needed?
Title: Re: Unified Theory of CIM Collections
Post by: Paolo F Cantoni on October 31, 2005, 05:36:39 pm
Quote
Paolo;

I've been giving thought to your Tags and an Item's opaqueness trying to imagine what their UML notations might be.  That triggered some questions:

In your Ontology, does the concept of an Interface exist at the UML Level?  I'm thinking that there might be some utility for implementing Tags with them.

RE:  Items being opaque.  If the association is navigable from the Collection end, as I think is it must be for the collection to be useful, why is the Item so opaque that a tag construct is needed?
Two issues here I think Jim,

1) I used the word Opaque to imply that there is nothing special in the Item to make it part of the Collection.   The Item is what it is.  The Collector has to use whatever the Item exposes in order to determine (according to its Policies) whether the Item should be accepted into the collection or not.  With hindsight, Opaque may not have been the best word. The Item has an Interface which the needs to provide everything the Collector needs to manipulate the Item successfully.  Does this clarify things?

2) Tags are used to provide Associativity.  In an Associative Collection, the Collector (Sgt Schultz) says:  About the Item, "I know Nozzink"; but give me the Tag and I'll get the associated Item for you.  The Tag can be arbitrary and may contain no information directly related to the Item.  Associative Collections are built with two parts for each slot - the Tag and the Item (or reference thereto).

Paolo

[size=0]©2005 Paolo Cantoni, -Semantica-[/size]
Title: Re: Thoughts about Collections
Post by: jeshaw2 on November 01, 2005, 11:20:53 am
Paolo;

Quote
Once we have Tags, if the there can only be unique Tags in the Collection, then the Tag acts as a Key (uniqueness constraint). Such Collections are known as Enumerations.
Quote
In addition, where the Item contains an attribute whose values are an Enumeration one can define an:
Enumerator: Retrieves one or more items at a time by applying a filter on an Enumerable property of the Items.
Quote
sounds similar to SQL's ... DISTINCT capability
Precisely.

I submit that a requirement for collected parts to have an Enumeration attribute is not a requirement of an Enumerator. The Enumerator may certainly return an Enumeration by applying a Distinctness filter to the collection.  The Tags in the returned collection would then, of necessity, be unique, not necessarily the Parts themselves.  :)

Further, I would suggest that a collection's isEnumerable property would be true if an Enumerator is defined for the collection.
Title: Re: Thoughts about Collections
Post by: lex_cz on November 01, 2005, 04:18:39 pm
Hi,
some thoughts that came into my mind while reading this interesting discussion.

I think maybe a better idea to describe the all possible collections would be gen-spec instead of a "Collection subtype" x "Policy" table. Ie. the mother of all collections is: Collection (defined as collection of elements of some type, where collection implements methods(policies) eg. Add (not defined if at start, end,...), Del (not defined if from start, end, ...), Iterate)
Subtype of Collection is eg. CollectionIndexed (defined as Collection with additional method GetAt (returns an element thats nth) )
Another subtype is eg. CollectionOrdered (defined as Collection where elements must support the less, greater methods and when calling Iterate() the next element is always greater or equal than the previous)
Another subtype is eg. CollectionUnique (defined as Collection where elements must be unique = elements must support the equals method and there are no elements elem1, elem2 such that elem1 = elem2)
Etc.

Usage in PIM should be easy than. When I write in the model: CollectionUnique, in PSM must be used some sort of CCollectionUnique or subtype of CollectionUnique but not CCollection.

Regards Martin
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on November 01, 2005, 05:28:07 pm
Quote
Paolo;
[size=13][SNIP][/size]
I submit that a requirement for collected parts to have an Enumeration attribute is not a requirement of an Enumerator. The Enumerator may certainly return an Enumeration by applying a Distinctness filter to the collection.  The Tags in the returned collection would then, of necessity, be unique, not necessarily the Parts themselves.  :)

Further, I would suggest that a collection's isEnumerable property would be true if an Enumerator is defined for the collection.
To part 1 of your post, Jim:
Do we agree that Iterators and Indexers work on the Items?  If so, then so must the Enumerator.

If we allow (as I think we've now agreed) an Indexer to return multiple items.  Then I could probably substitute an (equivalent) Indexer for every Enumerator (of the type I've previously defined).

However, you've sparked an idea with the "SELECT DISTINCT".  Perhaps the Enumerator should return the Set (unique) of a particular Enumerated Property in the Item.  For example:
I have 12 Red pebbles, 6 Green, 2 Blue.  The Colour attribute has 8 possible values.
The enumerator would return the Set: Red,Green,Blue - since these were the only values in this collection at this time.

This would make the Enumerator sufficiently distinct from the Indexer and still keep the notion of Enumeration.

If this isn't what you'd like the Enumerator to do, can you spell it out with an example?

To the second part:

This seems a logical consequence.

I presume that the isIndexable and isIterable would come under the same banner?

I haven't worked out yet whether a Collection is Iterable (by definition).  I suspect it is, but I haven't worked out the proof yet.

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

Title: Re: Thoughts about Collections
Post by: jeshaw2 on November 01, 2005, 09:30:33 pm
Martin;

Welcome to the discussion, glad to have you in here.  :)

You raise some interesting points and I confess that, early on, I had similar ideas.  You arguments (as you say) are relative to models at the PIM and PSM level of abstraction.  There it is permissible to think in terms of how collections may be implemented in code and how the computations might go forward in methods.

Paolo and I haven't gotten that far yet.  We are discussing collections in terms that do not allude to how the collections are implemented within a computer.  In our discussion time-line, we have yet to make a decision to use a computer for system's implementation.  Our models would also apply to a non-automated (manual) technology too.  But be it automated, or non-automated, we don't foreclose on any options until we leave the CIM level and head for the PIM level of modeling. In the Top-down, Bottom-up methodology, we are at the first step, you are at the second step.  Therefore, we are denied use of the concepts you find so useful.
Title: Re: Thoughts about Collections
Post by: jeshaw2 on November 01, 2005, 10:43:12 pm
Paolo;
Quote
Do we agree that Iterators and Indexers work on the Items?  If so, then so must the Enumerator.
Agreed. But if a Tag is available in the collection it may contain information of interest not in the Item, I don't see any reason why the accessors can't work on Tags also.

Quote
If we allow (as I think we've now agreed) an Indexer to return multiple items.  Then I could probably substitute an (equivalent) Indexer for every Enumerator (of the type I've previously defined).
(We have so agreed) and yes an equivalent Indexer could be substituted.  I see an Enumerator as a specialization of an Indexer, at least in terms of the derived collection, but I'm keeping my thoughts open on this. I havent fully evaluated the possibilities of your filter concept.

Quote
However, you've sparked an idea with the "SELECT DISTINCT".  Perhaps the Enumerator should return the Set (unique) of a particular Enumerated Property in the Item.  For example:
I have 12 Red pebbles, 6 Green, 2 Blue.  The Colour attribute has 8 possible values.
The enumerator would return the Set: Red,Green,Blue - since these were the only values in this collection at this time.
This is a good illustration of the nature of the Enumerator's specialization.  It also conforms to my earlier stated specifications which allows an enumeration to be derived, by an enumerator, from any base collection type.

Quote
If this isn't what you'd like the Enumerator to do, can you spell it out with an example?
 No need, its what I expect of an Enumerator.

Quote
I presume that the isIndexable and isIterable would come under the same banner?
That is my view.

Quote
I haven't worked out yet whether a Collection is Iterable (by definition).
By definition?  In my view, probably not at the CIM level.  In the real-world, except for queues at the bank teller's window, few of the parts of a collection are conveniently lined up in a ordinal fashion.  

Just as I assert a required presence of an Enumerator object for isEnumerable to be true, I also assert the required presence of an Indexer object and Iterator object.  I think of isEnumerable, isIndexable and isIterable a interfaces which define a method which returns a reference to the respective Enumerator, Indexer, or Iterator object that is nested within the collection.
Collections having such access objects implement the appropriate interfaces (note the plurality here).

BTW:  I now see Trees as a specalization of Linked-lists which in turn is a specalization of a List.  I no longer think of trees as a base collection type.
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on November 01, 2005, 11:27:37 pm
Looks like we're in violent agreement again!  8)  8)  8)

(I also came to the same conclusion as you wrt to Trees.)

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.

Paolo
[size=0]©2005 Paolo Cantoni, -Semantica-[/size]
Title: Re: Thoughts about Collections
Post by: jeshaw2 on November 02, 2005, 05:57:35 am
Quote
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.  ;D

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.
Title: Re: Thoughts about Collections
Post by: mikewhit on November 02, 2005, 10:23:27 am
Excuse me parachuting in, I may have missed most of the context (and therefore be talking rubbish), but
Quote
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.
Title: Re: Thoughts about Collections
Post by: jeshaw2 on November 02, 2005, 05:02:14 pm
Hi Mike;  Glad you jumped in.  Reviews are always good.  :)

You quoted me as saying
Quote
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).
Quote
Iterator: Retrieves one item at a time by applying a function over the ordinal position of the current Item.

You also said:
Quote
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:
Quote
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:
Quote
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?


Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on November 02, 2005, 05:33:04 pm
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
Title: Re: Thoughts about Collections
Post by: mikewhit on November 03, 2005, 03:29:32 am
Quote
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.)
Title: Re: Thoughts about Collections
Post by: Paolo F Cantoni on November 03, 2005, 05:24:25 am
Quote
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]

Title: Re: Thoughts about Collections
Post by: jeshaw2 on November 03, 2005, 10:39:40 am
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.  :)