Re: Collections: Sets, bags or something else?

Ashok Malhotra wrote:
>
> I think David was gently suggesting that replacing ‘collection’ with
> ‘bag’ may be more accurate.
>
I have two concerns here:

First, I'm concerned about the use of bag (multiset) semantics at all. 
As I've said, absent a compelling reason it's better to stick with the
much more commonly understood and widely studied concept of sets.  In
the case of policies, it appears there is no reason not to define them
as sets of alternatives.

In the case of alternatives as bags of assertions, it's not clear to me
what use cases this is supporting.  There are two cases to consider:  If
the policy vocabulary doesn't care about multiplicity
(<All><A/><A/></All> means the same thing as <All><A/></All>) then we
have set semantics anyway and we might as well say so.  If there /is/ a
difference, e.g., A means "turn on tracing" and two A's means "turn on
lots of tracing", then it's not clear that we want to intersect
<All><A/></All> with <All><A/></All> and get <All><A/><A/></All>
(assuming, again, that that's how intersection works).  The least common
denominator of "turn on tracing" and "turn on tracing" would seem to be
"turn on tracing", not "turn on lots of tracing".

At the very least, if multiplicity is allowed to matter, there should be
some guidelines as to what ways it can matter and still compose well
with policy intersection.

My second concern is simply that the spec be well-defined.  Using
"collection" doesn't work since the term is ambiguous.  Using "set"
would be unambiguous, but appears not to be the intended meaning (at
least not for alternatives).  Using "bag" or "multiset", if those are
the semantics, is fine, but then don't expect the reader to know what
those are or how operations on them are defined.

One set of definitions is:

    * A bag is an unordered collection in which the same item may occur
      more than once.
    * If B1 and B2 are bags and item /i/ appears m1 times in B1 and m2
      times in B2 (m1 and m2 may either or both be zero) then
          o /i/ occurs m1 + m2 times in the /bag union/ of B1 and B2
          o /i/ occurs min(m1, m2) times in the /bag intersection/ of B1
            and B2.


There are probably nicer definitions, and you may not need to define
both intersection and union, but this level of description would define
behavior well enough for me.
>
> All the best, Ashok
>
> ------------------------------------------------------------------------
>
> *From:* public-ws-policy-request@w3.org
> [mailto:public-ws-policy-request@w3.org] *On Behalf Of *Asir Vedamuthu
> *Sent:* Tuesday, May 01, 2007 3:15 PM
> *To:* David Hull; public-ws-policy@w3.org
> *Subject:* RE: Collections: Sets, bags or something else?
>
>  
>
> > that "collection" here means "unordered collection with
>
> >duplicates allowed", informally known as a "bag".
> >Is this the intended meaning?
>
>  
>
> Yes
>
>  
>
> >If the intended meaning is to allow duplicates, is there
>
> >any special meaning to the same /alternative/ appearing more than
>
> >once in a policy
>
>  
>
> No
>
>  
>
> We hope this helps.
>
>  
>
> Regards,
>
>  
>
> Asir S Vedamuthu
>
> Microsoft Corporation
>
>  
>
>  
>
> *From:* public-ws-policy-request@w3.org
> [mailto:public-ws-policy-request@w3.org] *On Behalf Of *David Hull
> *Sent:* Monday, April 30, 2007 10:24 PM
> *To:* public-ws-policy@w3.org
> *Subject:* Collections: Sets, bags or something else?
>
>  
>
> A follow-up to my previous:
>
> The spec appears to carefully use "collection" and not "set".  This,
> together with the absence of expression equivalence rules like /a+a=a/
> and /a*a=a/ and the note that assertions of the same /type/ may occur
> in an alternative, suggest that "collection" here means "unordered
> collection with duplicates allowed", informally known as a "bag".
>
> Is this the intended meaning?  It's not unheard of to use "collection"
> to mean "set" (i.e., duplicates are not considered).  If the intended
> meaning is to allow duplicates, is there any special meaning to the
> same /alternative/ appearing more than once in a policy (as opposed to
> the same /assertion/ (type?) appearing more than once in an
> alternative, which behavior is out of scope).
>