Equivalent keys/elements in Ada.Containers Maps and Sets

Equivalent keys/elements in Ada.Containers Maps and Sets

[Niklas Holsti]

To learn about Ada.Containers in Ada 2005 I have been reading the LRM 
section A.18 and John Barnes' Rationale. Some details about Maps and 
Sets are puzzling me enough to make me consider submitting a couple of 
comments to ada-auth. As I'm a novice in Ada.Containers I thought I 
would first ask here, on comp.lang.ada, in case I am misunderstanding 
things or raking up issues that have been discussed before. I looked 
through the Containers-related Ada Issues for Ada 2005 on ada-auth.org 
but found none that seemed relevant.

The points I want to ask about are so technical that I felt it necessary 
to make this posting rather long and detailed.

-- Background

The generic container packages for Maps and Sets deal with a concept 
called "equivalent keys" or "equivalent elements". This equivalence is 
called an "equivalence relation" in RM A.18.4(5/2) for Maps and RM 
A.18.7(5/2) for Sets. An equivalence relation is defined as a reflexive, 
symmetric and transitive relation: any key or element X is equivalent to 
itself; if X is equivalent to Y then Y is equivalent to X; and if X and 
Y are equivalent and Y and Z are equivalent then X and Z are equivalent.

I think I understand the idea, which is that two different values of the 
formal types Key_Type (for Maps) or Element_Type (for Sets) may still be 
similar enough (that is, "equivalent") to count as the same key or the 
same element when considered as (unique) keys to a map or as (unique) 
elements of a set. This is analogous to user-defined relational 
operators that only inspect meaningful components of their parameters.


-- First problem: "equivalence" in Ordered Maps and Sets

For hashed Maps and Sets, the actual "equivalence" is directly defined 
at instantiation time by the actual functions associated to the formal 
functions Equivalent_Keys (for Hashed_Maps) and Equivalent_Elements (for 
Hashed_Sets). The actual functions are required to be equivalence 
relations in A.18.5(44/2) and A.18.8(66/2). I have no problem with that.

For the Ordered_Maps and Ordered_Sets, however, the "equivalence" is 
defined *indirectly* by the actual ordering functions associated to the 
formal functions "<" on Keys or Elements, respectively, at instantiation 
time. Two keys/elements X and Y are defined to be "equivalent" if they 
are incomparable, that is, if both X < Y and Y < X are False. This is in 
A.18.6(55/2) and A.18.9(78/2).

The first problem I see is that the "equivalence" relation defined in 
this way from "<" is *not* necessarily an equivalence relation because 
it may not be transitive. It is obviously symmetric because "and" is 
commutative. It is reflexive because the actual for "<" is required to 
be a strict ordering and thus irreflexive. However, one can easily make 
an example of a strict ordering "<" in which the "incomparable" relation 
is not transitive; say we have three values X, Y, Z where the only 
relation is X < Z; thus X and Y are incomparable and Y and Z are 
incomparable, but X and Z are not incomparable.

So what? What if this "equivalence" is not transitive and is thus not 
really an equivalence (without quotes)? Well, firstly I think it is 
quite confusing to call something an "equivalence" when it is not 
transitive, but secondly the semantics of the Map and Set operations are 
defined in terms of "equivalent" keys or elements, and this can lead to 
surprising results if the "equivalence" relation is not transitive.

For example, by A.18.7(22/2) the function Equivalent_Sets reports two 
sets S1 and S2 as equivalent if they have the same number of elements 
and if for every element E1 of S1 there is an element E2 of S2 such that 
E1 and E2 are "equivalent". (Note the asymmetry of this definition: it 
"traverses" S1 and "searches" for equivalent elements in S2.)

Now, if "equivalence" of elements is not transitive, we can have two 
sets S1 and S2 such that Equivalent_Sets (S1, S2) is True even if S2 
contains an element that is not "equivalent" to any element in S1.

This strange result is possible because two different elements of S1 can 
be "equivalent" to the *same* element of S2, leaving one or more 
elements of S2 unpaired with any "equivalent" elements of S1.

A consequence is that Equivalent_Sets is not necessarily symmetric; it 
can return True for parameters (S1, S2) but False for (S2, S1).

If "equivalence" of elements is transitive, this strange result cannot 
happen. If two different elements E1 and E1' of S1 are "equivalent" to 
the same element E2 of S2, then by transitivity E1 and E1' are 
"equivalent" to each other, which is impossible because no Set can 
contain two or more "equivalent" elements, by A.18.6(5/2).

I haven't looked for similar strange results from the other operations 
because I think that the case of Equivalent_Sets is strange enough.

There is also a problem of definition. The definition of the "=" 
operator for Maps in A.18.4(22/2, 23/2) implicitly assumes that each key 
in the Left map is equivalent to at most one key in the Right map. This 
assumption is false if "equivalence" of keys is not transitive; then 
there may be many "equivalent" keys in the Right map that could be 
matched against the same key in the Left map, so the definition of "=" 
for Maps is ambiguous.

To avoid this problem I think that the RM paragraphs that specify the 
properties required or expected of the actual "<" functions should be 
extended to say that the "incomparable" relation must be transitive. 
This is A.18.6(56/2) and A.18.9(79/2).


-- Second problem: "=" for Element_Type in Sets

All generic packages for Maps and Sets take a generic formal "=" 
operator for the Element_Type. According to the Annotated LRM it is 
meant to be used only in the "=" operator for Maps and Sets. The actual 
"=" function is required to be deterministic, symmetric and reflexive. 
This is all understandable and natural.

For Sets, however, I find it puzzling that no relationship is required 
or expected between this "=" and the other formal functions 
Equivalent_Elements, Hash and "<". For example, in the case of two 
elements E1 and E2 in an Ordered_Set it would be very natural to require 
that if E1 "=" E2 then we cannot also have E1 "<" E2 or E2 "<" E1, in 
other words we should have E1 "equivalent" to E2.

One point where this may be significant is the definition of the "=" 
operator on Sets in A.18.7(20/2). The definition requires each element 
of the Left set to be compared for "=" with the elements of the Right 
set. If the actual "=" function is unrelated to the Hash function or to 
the "<" operator for elements, I don't see how the "=" operator on Sets 
can be implemented in less than O(N**2) complexity.

Moreover, the "=" operator for Sets as now defined can report two sets 
S1 and S2 as "=" although S2 contains elements that are not "=" to any 
elements of S1. This is because the definition is asymmetric (it 
"traverses" S1 and "searches" S2), so two different elements of S1 can 
be "=" to the same element of S2, leaving some elements of S2 unmatched 
with elements of S1.

I think the definition of "=" for Sets expects the implementation to 
compare only "equivalent" elements of the Left and Right Sets. If 
"equivalence" is transitive this means that each element of Left can be 
compared with "=" to exactly one element of Right (or, for Hashed_Sets, 
to the elements in one bucket, if the implementation prefers to use "=" 
directly and not first check Equivalent_Elements).

I know that there are no RM requirements or advice on the complexity of 
the "=" operator for Sets, but under the current rules I think that the 
natural, fast implementation that only compares the equivalent elements 
is wrong.

To solve this problem I think that A.18.6(3/2) should be extended to 
also require or expect that two "=" elements are "equivalent".

For Hashed_Sets this means that if E1 "=" E2 then 
Equivalent_Elements(E1,E2) must be True. A consequence is that Hash(E1) 
= Hash(E2).

For Ordered_Sets this means that if E1 "=" E2 then both E1 "<" E2 and
E2 "<" E1 must be False.


-- Last words

Should I submit these comments to ada-comment@ada-auth.org? Or were the 
issues already considered in the design of Ada.Containers? I would be 
grateful for your advice.


-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Matthew Heaney]

Niklas Holsti wrote:
>
> -- First problem: "equivalence" in Ordered Maps and Sets
>
> However, one can easily make
> an example of a strict ordering "<" in which the "incomparable" relation
> is not transitive; say we have three values X, Y, Z where the only
> relation is X < Z; thus X and Y are incomparable and Y and Z are
> incomparable, but X and Z are not incomparable.

I don't see this.  Please provide an example.


> For example, by A.18.7(22/2) the function Equivalent_Sets reports two
> sets S1 and S2 as equivalent if they have the same number of elements
> and if for every element E1 of S1 there is an element E2 of S2 such that
> E1 and E2 are "equivalent". (Note the asymmetry of this definition: it
> "traverses" S1 and "searches" for equivalent elements in S2.)

The search only applies to the hashed set.  (A search is necessary
because hashed containers can have different capacities.)  For the
ordered set, you only need to traverse both sets simultaneously; there
is no search.


> Now, if "equivalence" of elements is not transitive, we can have two
> sets S1 and S2 such that Equivalent_Sets (S1, S2) is True even if S2
> contains an element that is not "equivalent" to any element in S1.

I still don't know what you mean by equivalence not being transitive.
Please provide an example.


> -- Second problem: "=" for Element_Type in Sets
>
> For Sets, however, I find it puzzling that no relationship is required
> or expected between this "=" and the other formal functions
> Equivalent_Elements, Hash and "<".

Equality implies equivalence, so there is no puzzle.  (But note that
equivalence does not imply equality -- hence two separate generic
formal functions.)


> For example, in the case of two
> elements E1 and E2 in an Ordered_Set it would be very natural to require
> that if E1 "=" E2 then we cannot also have E1 "<" E2 or E2 "<" E1, in
> other words we should have E1 "equivalent" to E2.

Yes, that is indeed implied.

  E1 = E2 => Is_Equivalent (E1, E2)


> One point where this may be significant is the definition of the "="
> operator on Sets in A.18.7(20/2). The definition requires each element
> of the Left set to be compared for "=" with the elements of the Right
> set. If the actual "=" function is unrelated to the Hash function or to
> the "<" operator for elements, I don't see how the "=" operator on Sets
> can be implemented in less than O(N**2) complexity.

No, your premise is false.

  E1 = E2 => Hash (E1) = Hash (E2)

Equality is always O(1).  There are no operations that are O(N**2).


> I think the definition of "=" for Sets expects the implementation to
> compare only "equivalent" elements of the Left and Right Sets. If
> "equivalence" is transitive this means that each element of Left can be
> compared with "=" to exactly one element of Right (or, for Hashed_Sets,
> to the elements in one bucket, if the implementation prefers to use "="
> directly and not first check Equivalent_Elements).

The implementation of "=" for hashed sets does not use
Equivalent_Elements to test the elemenets in the bucket -- it uses
element "=" (since element "=" implies that Is_Equivalent is also
true).


> I know that there are no RM requirements or advice on the complexity of
> the "=" operator for Sets, but under the current rules I think that the
> natural, fast implementation that only compares the equivalent elements
> is wrong.

The "=" operator for sets is O(n).


> To solve this problem I think that A.18.6(3/2) should be extended to
> also require or expect that two "=" elements are "equivalent".

That's already implied.


> For Hashed_Sets this means that if E1 "=" E2 then
> Equivalent_Elements(E1,E2) must be True. A consequence is that Hash(E1)
> = Hash(E2).

Yes, of course.


> For Ordered_Sets this means that if E1 "=" E2 then both E1 "<" E2 and
> E2 "<" E1 must be False.

Yes, of course.


> -- Last words
>
> Should I submit these comments to ada-comment@ada-auth.org? Or were the
> issues already considered in the design of Ada.Containers? I would be
> grateful for your advice.

Yes, they were indeed considered, and are already implied by the RM.

-Matt

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Matthew Heaney]

Matthew Heaney wrote:
> Niklas Holsti wrote:
> >
> > One point where this may be significant is the definition of the "="
> > operator on Sets in A.18.7(20/2). The definition requires each element
> > of the Left set to be compared for "=" with the elements of the Right
> > set. If the actual "=" function is unrelated to the Hash function or to
> > the "<" operator for elements, I don't see how the "=" operator on Sets
> > can be implemented in less than O(N**2) complexity.
>
> No, your premise is false.
>
>   E1 = E2 => Hash (E1) = Hash (E2)
>
> Equality is always O(1).  There are no operations that are O(N**2).
                              ^^^^^^

Oops!  I meant to say that equality is always O(n).   

-Matt

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Niklas Holsti]

Matthew Heaney wrote:
> Niklas Holsti wrote:
> 
>>-- First problem: "equivalence" in Ordered Maps and Sets
>>
>>However, one can easily make
>>an example of a strict ordering "<" in which the "incomparable" relation
>>is not transitive; say we have three values X, Y, Z where the only
>>relation is X < Z; thus X and Y are incomparable and Y and Z are
>>incomparable, but X and Z are not incomparable.
> 
> 
> I don't see this.  Please provide an example.

Those X, Y, Z *were* the example, but let's make it clearer:

    type T is (X, Y, Z);

    function "<" (Left, Right : T) return Boolean is
    begin
       return Left = X and Right = Z;
    end "<";

This function "<" is a strict ordering relation for T, as required for 
Ada.Containers.Ordered_Maps/Sets. But the "equivalence" relation induced 
by this "<" is not transitive: X and Y are "equivalent" (both X < Y and 
Y < X are False) and Y and Z are "equivalent" (both Y < Z and Z < Y are 
False) but X and Z are not "equivalent" (because X < Z is True).

Of course this "<" is not a complete ordering, but that is not required 
in the RM and I'm sure it was not the intention to require it (because 
then "equivalence" would reduce to "identity").

>>For example, by A.18.7(22/2) the function Equivalent_Sets reports two
>>sets S1 and S2 as equivalent if they have the same number of elements
>>and if for every element E1 of S1 there is an element E2 of S2 such that
>>E1 and E2 are "equivalent". (Note the asymmetry of this definition: it
>>"traverses" S1 and "searches" for equivalent elements in S2.)
> 
> 
> The search only applies to the hashed set.  (A search is necessary
> because hashed containers can have different capacities.)  For the
> ordered set, you only need to traverse both sets simultaneously; there
> is no search.

I'm speaking of the way the Equivalent_Sets function is *defined* in the 
RM, not about how it might be implemented. The phrasing in the 
definition treats the Left and Right parameters (S1 and S2 in my 
message) asymmetrically. A symmetric phrasing would be something like: 
the elements in the Left and Right sets can be paired one-to-one such 
that the two components in each pair are "equivalent". But this is not 
the way the RM is written.

>>Now, if "equivalence" of elements is not transitive, we can have two
>>sets S1 and S2 such that Equivalent_Sets (S1, S2) is True even if S2
>>contains an element that is not "equivalent" to any element in S1.
> 
> 
> I still don't know what you mean by equivalence not being transitive.
> Please provide an example.

See above, the "<" for type T, but now I'll expand it a bit to show the 
consequence for Equivalent_Sets, for which I need four values of the 
Element_Type T:

   type T is (W, X, Y, Z);

    function "<" (Left, Right : T) return Boolean is
    -- This function implements the ordering:
    --     W < X < Z
    --     W < Y
    -- No other pairs are comparable.
    begin
        case Left is
           when W => return Right /= W;
           when X => return Right = Z;
           when Y => return False;
           when Z => return False;
        end case;
    end "<";

The "equivalence" relation derived from this "<" relation makes

    X "equivalent" to itself and Y
    Y "equivalent" to itself and X and Z
    Z "equivalent" to itself and Y
    W "equivalent" to itself only.

Now consider two Ordered_Sets, Left and Right, with Element_Type => T. 
Let the Left set be {X, Z} and the Right set be {W, Y}. Note that X is 
not "equivalent" to Z, so the Left set is "legal" with respect to 
A.18.6(5/2), and likewise for the Right set. Let's apply the RM 
definition A.18.6(22/2) to see what Equivalent_Sets (Left,Right) should 
return:

- Left and Right are not the same set object
   so we do not return True at once.

- Left and Right have the same number of elements (2)
   so we do not return False at once.

- Now we must check each element of Left and look for an
   "equivalent" element in Right:
   - X from Left is "equivalent" to Y from Right, ok.
   - Z from Left is "equivalent" to Y from Right, ok.
   Thus Equivalent_Sets (Left,Right) returns True.

However, Right contains the element W, which is not "equivalent" to any 
element in Left. That is an example of the problem I spoke of. Moreover, 
it means that Equivalent_Sets (Right,Left) will return False, showing 
that Equivalent_Sets is not always symmetric.


>>-- Second problem: "=" for Element_Type in Sets
>>
>>For Sets, however, I find it puzzling that no relationship is required
>>or expected between this "=" and the other formal functions
>>Equivalent_Elements, Hash and "<".
> 
> 
> Equality implies equivalence, so there is no puzzle.  (But note that
> equivalence does not imply equality -- hence two separate generic
> formal functions.)

Aha - I think I see where this arises for Hashed_Sets. The RM in 
A.18.8(66/2) requires the actual for Equivalent_Elements to be 
"reflexive". I understood this to mean that Equivalent_Elements (X, X) 
should always be True. It seems you understand "reflexive" to mean the 
implication

    if X = Y (using the actual "=" function)
    then
    Equivalent_Elements (X, Y) is True.

This is, of course, a much stronger requirement, and inded it relates 
the actual functions for "=" and for Equivalent_Elements in exactly the 
way that I wanted.

So here I would just like the RM to explain more clearly what it means 
by "reflexive", with reference to the actual "=" function.

>>For example, in the case of two
>>elements E1 and E2 in an Ordered_Set it would be very natural to require
>>that if E1 "=" E2 then we cannot also have E1 "<" E2 or E2 "<" E1, in
>>other words we should have E1 "equivalent" to E2.
> 
> 
> Yes, that is indeed implied.
> 
>   E1 = E2 => Is_Equivalent (E1, E2)

Aha - again. The RM in A.18.9(79/2) requires the actual for "<" to be 
"irreflexive". I understood this to mean that X < X is always False. It 
seems that you understand "irreflexive" to mean the implication

    if X < Y (using the actual "<" function)
    then
    X /= Y (using the actual "=" function).

Again, this is a stronger requirement and what I was hoping for, so 
again I would only wish that this RM paragraph would explain 
"irreflexive" more clearly, with reference to the actual for "=".

[As an aside, I think there is also a small typo in A.18.9(79/2): it 
says "pair of key values" when it should say "pair of Element_Type values".]

Thanks for your answer, which clears up my "second problem". I 
misunderstood the meaning of "reflexive" and "irreflexive" because the 
RM paragraphs did not explain how these terms related to the actual "=" 
function. I'm now also satisfied with the definition of "=" on Sets.

> Yes, they were indeed considered, and are already implied by the RM.

Agreed for the second problem ("=" on Set elements and Sets), modulo a 
wish for better explanation of "reflexive" and "irreflexive" in the RM.

I still have the first problem (possible non-transitivity of the 
"equivalence" relation defined by "<") and its effect on Equivalent_Sets 
for Ordered_Sets.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Randy Brukardt]

"Niklas Holsti" <niklas.holsti@nospam.please> wrote in message
news:45b69499$0$31527$39db0f71@news.song.fi...
> Matthew Heaney wrote:
> > Niklas Holsti wrote:
> >
> >>-- First problem: "equivalence" in Ordered Maps and Sets
> >>
> >>However, one can easily make
> >>an example of a strict ordering "<" in which the "incomparable" relation
> >>is not transitive; say we have three values X, Y, Z where the only
> >>relation is X < Z; thus X and Y are incomparable and Y and Z are
> >>incomparable, but X and Z are not incomparable.
> >
> >
> > I don't see this.  Please provide an example.
>
> Those X, Y, Z *were* the example, but let's make it clearer:
>
>     type T is (X, Y, Z);
>
>     function "<" (Left, Right : T) return Boolean is
>     begin
>        return Left = X and Right = Z;
>     end "<";
>
> This function "<" is a strict ordering relation for T, as required for
> Ada.Containers.Ordered_Maps/Sets. But the "equivalence" relation induced
> by this "<" is not transitive: X and Y are "equivalent" (both X < Y and
> Y < X are False) and Y and Z are "equivalent" (both Y < Z and Z < Y are
> False) but X and Z are not "equivalent" (because X < Z is True).

I don't believe this function meets the requirements. It has to be the case
that the function is reversible (we can't know the order of the operands)
and it can't be the case that
   neither (X < Z) nor (Z < X) nor (X = Z) (where "=" means equivalent).

One of these three things has to hold, or the function is not acceptable.

> Of course this "<" is not a complete ordering, but that is not required
> in the RM and I'm sure it was not the intention to require it (because
> then "equivalence" would reduce to "identity").

The basic idea of equivalence is to allow case-insensitive keys. Of course,
it doesn't make sense to just support case-insensitive keys.

But I do think you need a complete ordering, in the sense that things that
are not equivalent have to have one of X < Y or Y < X be true.

I haven't a clue as to what wording is missing. The original wording that
Matt and I had proposed simply gave a bunch of relationships that had to be
true. Then the mathemations got at it and rephrased it into mathematical
terms that make it hard to tell if it is actually right. (I can never
remember which is which of reflective, transitive, and symmetric). I simply
gave up at that point and trusted them...

...
> The "equivalence" relation derived from this "<" relation makes
>
>     X "equivalent" to itself and Y
>     Y "equivalent" to itself and X and Z
>     Z "equivalent" to itself and Y
>     W "equivalent" to itself only.

That cannot be an acceptable equivalence relationship. There are disjoint
sets of equivalent elements, and every element belongs to exactly one set.
For ordered cases, there is a complete ordering between the sets. For hashed
cases, each set has its own hash value. If the RM language doesn't imply
those things, it is wrong.

But if you think the RM language is wrong, please also tell us how to fix
it. Just saying it is wrong is no help whatsoever. (Well, at least not for
me.)

...
> >>-- Second problem: "=" for Element_Type in Sets
> >>
> >>For Sets, however, I find it puzzling that no relationship is required
> >>or expected between this "=" and the other formal functions
> >>Equivalent_Elements, Hash and "<".
> >
> >
> > Equality implies equivalence, so there is no puzzle.  (But note that
> > equivalence does not imply equality -- hence two separate generic
> > formal functions.)

Well, equality *ought to* imply equivalence. But Matt, you can't reason from
what was intended, but rather what the RM words require.

> Aha - I think I see where this arises for Hashed_Sets. The RM in
> A.18.8(66/2) requires the actual for Equivalent_Elements to be
> "reflexive". I understood this to mean that Equivalent_Elements (X, X)
> should always be True.

No, Matt is just reasoning from what he'd like to be true, not what the RM
implies. You'll note he didn't give any RM paragraph references.

...
> Thanks for your answer, which clears up my "second problem". I
> misunderstood the meaning of "reflexive" and "irreflexive" because the
> RM paragraphs did not explain how these terms related to the actual "="
> function. I'm now also satisfied with the definition of "=" on Sets.

Well, I'm not. I don't believe Matt was referring in any way to the actual
wording of the RM. I don't see any wording that would require any
relationship between "=" and Equivalent_Elements, and this is needed.

> > Yes, they were indeed considered, and are already implied by the RM.

Nothing is "implied" by the RM. Please explain how you think that these
issues are covered by the RM wording, as opposed to what we intended the RM
to say.

> Should I submit these comments to ada-comment@ada-auth.org?

Yes, because the people who could give you a better mathematical example
than Matt or I can don't come here. And the discussion of the problem should
be on the record, not hidden here where it will never be seen again.

                                 Randy Brukardt, ARG Editor

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Niklas Holsti]

Randy Brukardt wrote:
> "Niklas Holsti" <niklas.holsti@nospam.please> wrote in message
> news:45b69499$0$31527$39db0f71@news.song.fi...

Thanks for your reply, Randy.

>>Matthew Heaney wrote:
>>
>>>Niklas Holsti wrote:

   [snip] [wow -- this was the biggest snip I've made so far :-]
> 
>>Should I submit these comments to ada-comment@ada-auth.org?
> 
> 
> Yes, because the people who could give you a better mathematical example
> than Matt or I can don't come here. And the discussion of the problem should
> be on the record, not hidden here where it will never be seen again.

OK. I will submit to ada-comment and include a summary of the replies 
from you and Matt, as I understand them. Can I hope to be included in 
the subsequent discussion, if any?

I have also found a couple of points in A.18 that seem to me like simple 
editing mistakes, so I'll practice by submitting those first.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Matthew Heaney]

On Jan 23, 6:04 pm, Niklas Holsti <niklas.hol...@nospam.please> wrote:
> Matthew Heaney wrote:
> > Niklas Holsti wrote:
>
> Those X, Y, Z *were* the example, but let's make it clearer:
>
>     type T is (X, Y, Z);
>
>     function "<" (Left, Right : T) return Boolean is
>     begin
>        return Left = X and Right = Z;
>     end "<";
>
> This function "<" is a strict ordering relation for T, as required for
> Ada.Containers.Ordered_Maps/Sets.

The exact requirement is for a "strict weak ordering"; that is,
irreflexive, antisymmetric, transitive, and equivalence is transitive
(where equivalence is defined as x < y and y < x are both false).

<http://www.sgi.com/tech/stl/StrictWeakOrdering.html>
<http://en.wikipedia.org/wiki/Strict_weak_ordering>


> But the "equivalence" relation induced
> by this "<" is not transitive: X and Y are "equivalent" (both X < Y and
> Y < X are False) and Y and Z are "equivalent" (both Y < Z and Z < Y are
> False) but X and Z are not "equivalent" (because X < Z is True).

Right, which is why your less-than operator doesn't specify a strict
weak ordering.  Hence it is not an acceptable as a generic actual for
ordered associative containers.


> Of course this "<" is not a complete ordering, but that is not required
> in the RM and I'm sure it was not the intention to require it (because
> then "equivalence" would reduce to "identity").

Yes, for a total ordering, equivalence is the same as equality, and no,
that's not required by the RM (which is why there are two generic
formal operators, and why ordered sets have both an equality operator
and an Equivalent_Sets operation).


> >>For example, by A.18.7(22/2) the function Equivalent_Sets reports two
> >>sets S1 and S2 as equivalent if they have the same number of elements
> >>and if for every element E1 of S1 there is an element E2 of S2 such that
> >>E1 and E2 are "equivalent". (Note the asymmetry of this definition: it
> >>"traverses" S1 and "searches" for equivalent elements in S2.)

I don't know why you think the "asymmetry of the definition" is
significant.  The Equivalent_Sets operation is of course symmetric.


> > The search only applies to the hashed set.  (A search is necessary
> > because hashed containers can have different capacities.)  For the
> > ordered set, you only need to traverse both sets simultaneously; there
> > is no search.
>
> I'm speaking of the way the Equivalent_Sets function is *defined* in the
> RM, not about how it might be implemented.

It works out to be the same.  The RM is technically correct here.  An
implementation of Equivalent_Sets could certainly search the right-hand
set for the current element of the left-hand set, but in practice no
implementation would ever do it that way.


> The phrasing in the
> definition treats the Left and Right parameters (S1 and S2 in my
> message) asymmetrically.

So what?  Equivalent_Sets is symmetric.


> A symmetric phrasing would be something like:
> the elements in the Left and Right sets can be paired one-to-one such
> that the two components in each pair are "equivalent". But this is not
> the way the RM is written.

Yes, and Pepsi tastes different from Coke!  Again, so what?


> >>Now, if "equivalence" of elements is not transitive, we can have two
> >>sets S1 and S2 such that Equivalent_Sets (S1, S2) is True even if S2
> >>contains an element that is not "equivalent" to any element in S1.

Equivalence must be transitive, otherwise this would not be a strict
weak ordering.


> > I still don't know what you mean by equivalence not being transitive.
> > Please provide an example.

> See above, the "<" for type T, but now I'll expand it a bit to show the
> consequence for Equivalent_Sets, for which I need four values of the
> Element_Type T:

Your definition is not a strict weak ordering.


> >>-- Second problem: "=" for Element_Type in Sets
>
> Aha - I think I see where this arises for Hashed_Sets. The RM in
> A.18.8(66/2) requires the actual for Equivalent_Elements to be
> "reflexive". I understood this to mean that Equivalent_Elements (X, X)
> should always be True.

Yes, of course Equivalent_Elements is reflexive.


> It seems you understand "reflexive" to mean the
> implication
>
>     if X = Y (using the actual "=" function)
>     then
>     Equivalent_Elements (X, Y) is True.

I don't know why you'd think this has anything to do with what "I
understand reflexive to mean".  Equivalence is reflexive, and equality
is reflexive, but that has nothing to do with the separate requirement
that equality implies equivalence.


> This is, of course, a much stronger requirement, and inded it relates
> the actual functions for "=" and for Equivalent_Elements in exactly the
> way that I wanted.

It has nothing to do with what anyone wants.  It simply wouldn't work
otherwise!


> So here I would just like the RM to explain more clearly what it means
> by "reflexive", with reference to the actual "=" function.

That "=" is reflexive is implied by the meaning of equality!  You're
not free to define "=" willy-nilly.


> >   E1 = E2 => Is_Equivalent (E1, E2)

> Aha - again. The RM in A.18.9(79/2) requires the actual for "<" to be
> "irreflexive". I understood this to mean that X < X is always False.

Um, yeah.


> It seems that you understand "irreflexive" to mean the implication
>
>     if X < Y (using the actual "<" function)
>     then
>     X /= Y (using the actual "=" function).

Again, you are imputing beliefs to me that have nothing to do with what
I think nor what is implied by the RM.

Your implication is also backwards.  It should be:

  "=" (X, Y) => not "<" (X, Y) and not "<" (Y, X)

That is, equality implies equivalence.


> Again, this is a stronger requirement and what I was hoping for, so
> again I would only wish that this RM paragraph would explain
> "irreflexive" more clearly, with reference to the actual for "=".

No.  You're confusing reflexivity of equality and reflexivity of
equivalence with a distinct implication, that equality implies
equivalence.


> I still have the first problem (possible non-transitivity of the
> "equivalence" relation defined by "<") and its effect on Equivalent_Sets
> for Ordered_Sets.

There is no problem.  Equivalence must be transitive, since that is
what "strict weak ordering" means.  (Without transivity of equivalence,
then this would be a mere partial ordering, not a strict weak
ordering.)

Regards,
Matt

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Matthew Heaney]

On Jan 23, 7:43 pm, "Randy Brukardt" <r...@rrsoftware.com> wrote:
>
> I haven't a clue as to what wording is missing. The original wording that
> Matt and I had proposed simply gave a bunch of relationships that had to be
> true. Then the mathemations got at it and rephrased it into mathematical
> terms that make it hard to tell if it is actually right. (I can never
> remember which is which of reflective, transitive, and symmetric). I simply
> gave up at that point and trusted them...

The requisite term for ordered associative containers is "strict weak
ordering".  An equivalence relation that is not transitive is not a
strict weak ordering, and that's why the relation would not be
acceptable.


> > > Equality implies equivalence, so there is no puzzle.  (But note that
> > > equivalence does not imply equality -- hence two separate generic
> > > formal functions.)
>
> Well, equality *ought to* imply equivalence. But Matt, you can't reason from
> what was intended, but rather what the RM words require.

How could it work otherwise?  You first search for the element (using
equivalence -- that's what "search" means), and if the (equivalent)
element is found, you then compare the elements for equality.  It
cannot be the case that elements could be equal without also being
equivalent, because you must search for the element first, and a
successful search implies that the elements must be equivalent.


> No, Matt is just reasoning from what he'd like to be true, not what the RM
> implies. You'll note he didn't give any RM paragraph references.

Because I was using the Dewar Rule.


> I don't believe Matt was referring in any way to the actual
> wording of the RM. I don't see any wording that would require any
> relationship between "=" and Equivalent_Elements, and this is needed.

It cannot be any other way, for the reason I gave above.


> Nothing is "implied" by the RM. Please explain how you think that these
> issues are covered by the RM wording, as opposed to what we intended the RM
> to say.

In the case of ordered associative containers, the less-than operator
must define a "strict weak ordering".  That's the most succinct
statement of the precondition, since that term has a precise definition
in discrete mathematics.

With respect to the requirement that equality implies equivalence, I
would argue that that requirement already ennunciated by existing
wording (though I suppose an AARM note wouldn't hurt anything).

I'm a pragmatist in these matters.  No matter what the RM says (or
doesn't say), the developer has all the incentive he needs to do the
right thing.  If he doesn't do the right thing, then his program simply
won't work...

-Matt

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Niklas Holsti]

Matthew Heaney wrote:
> 
> On Jan 23, 6:04 pm, Niklas Holsti <niklas.hol...@nospam.please> wrote:
> 
>>Matthew Heaney wrote:
>>
>>>Niklas Holsti wrote:
>>
>>Those X, Y, Z *were* the example, but let's make it clearer:
>>
>>    type T is (X, Y, Z);
>>
>>    function "<" (Left, Right : T) return Boolean is
>>    begin
>>       return Left = X and Right = Z;
>>    end "<";
>>
>>This function "<" is a strict ordering relation for T, as required for
>>Ada.Containers.Ordered_Maps/Sets.
> 
> 
> The exact requirement is for a "strict weak ordering"; that is,
> irreflexive, antisymmetric, transitive, and equivalence is transitive
> (where equivalence is defined as x < y and y < x are both false).
> 
> <http://www.sgi.com/tech/stl/StrictWeakOrdering.html>
> <http://en.wikipedia.org/wiki/Strict_weak_ordering>

I don't find the word "weak" in the RM paragraphs that define the 
expected properties of "<", in A.18.6(56/2) for Ordered_Maps and 
A.18.9(79/2) for Ordered_Sets. Both paragraphs just say "strict ordering".

Moreover, these paragraphs then expand "strict ordering" into 
irreflexive, transitive and "asymmetric", not "antisymmetric", and they 
say nothing of equivalence (really "incomparability") being transitive. 
So your "exact requirement" does not match the RM wording. I think the 
RM wording should be changed to make them match.

I did not know that the term "weak" is used for this kind of ordering. 
Had I known that, perhaps I could have described my points better.

The definitions of these mathematical terms on Wikipedia don't seem 
universal because Wikipedia refers to "some contexts" and "other 
contexts" in which the terms are used differently, and Wikipedia is 
anyway not a good authority for the Ada RM. Moreover, mathematical terms 
like "reflexivity" can be tricky to use in a situation where X = Y does 
not mean X that can be substituted for Y in any expression E(Y), as it 
cannot for Ada expressions. I should prefer the RM to speak more 
concretely of logical connections between Ada expressions, with less use 
of mathematical terms like "reflexive relation".

You and I agree completely that the "<" function for the Ordered 
containers *should* be such that the "equivalence" (incomparability) 
relation is transitive, so we don't have to argue about that. The only 
open question is if and how the RM currently expresses this requirement, 
or this expected behaviour of the "<" function.

My examples of other kinds of "<" functions were only meant to test the 
RM wordings. I did not and still don't see where the RM explicitly 
requires the "incomparability" relation to be transitive.

I have sent a message on this issue to ada-comment@ada-auth.org and I 
suggest that the discussion should be continued there.


>>>>-- Second problem: "=" for Element_Type in Sets

I will send a message on this issue to ada-comment@ada-auth.org and I 
suggest that this discussion, too, should be continued there.

I'll only say here that I did not intend to offend you by "imputing" any 
"beliefs" to you; I was only explaining where I thought we might be 
understanding the RM differently, based on our discussion. I'm sorry if 
  I offended.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Adam Beneschan]

On Jan 23, 4:43 pm, "Randy Brukardt" <r...@rrsoftware.com> wrote:

> > This function "<" is a strict ordering relation for T, as required for
> > Ada.Containers.Ordered_Maps/Sets. But the "equivalence" relation induced
> > by this "<" is not transitive: X and Y are "equivalent" (both X < Y and
> > Y < X are False) and Y and Z are "equivalent" (both Y < Z and Z < Y are
> > False) but X and Z are not "equivalent" (because X < Z is True).

> I don't believe this function meets the requirements. It has to be the case
> that the function is reversible (we can't know the order of the operands)
> and it can't be the case that
>    neither (X < Z) nor (Z < X) nor (X = Z) (where "=" means equivalent).
>
> One of these three things has to hold, or the function is not acceptable.

This doesn't make sense to me.  "Equivalent" is defined in terms of "<"
(A.18.9(78/2)), and it's defined in such a way that

   neither (X < Z) nor (Z < X) nor (X === Z)

[using === for "equivalent"] will tautologically be true.  Thus, it's
logically impossible to come up with a function "<" that is
"unacceptable" according to the last criterion you state.

As far as I can tell from the wording of the RM (A.18.9(79/2)), the
function "<" that Niklas wrote does indeed meet the requirements: it's
irreflexive (A < A is false for all A), asymmetric (A < B and B < A are
not both true, for all A and B), and transitive (A < B and B < C
implies A < C, for all A, B, and C---because, in this case, there are
no such A, B, and C for which the first two relations hold).  If there
is some other requirement that "<" should meet but doesn't, then that
requirement is missing from the RM.

                          -- Adam

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Adam Beneschan]

On Jan 24, 12:56 pm, "Adam Beneschan" <a...@irvine.com> wrote:
> This doesn't make sense to me.  "Equivalent" is defined in terms of "<"
> (A.18.9(78/2)), and it's defined in such a way that
>
>    neither (X < Z) nor (Z < X) nor (X === Z)
>
> [using === for "equivalent"] will tautologically be true.

... will tautologically be false, sorry.

                           -- Adam

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Randy Brukardt]

"Niklas Holsti" <niklas.holsti@nospam.please> wrote in message
news:45b70ee8$0$22512$39db0f71@news.song.fi...
> Randy Brukardt wrote:
...
> >>Should I submit these comments to ada-comment@ada-auth.org?
> >
> > Yes, because the people who could give you a better mathematical example
> > than Matt or I can don't come here. And the discussion of the problem
should
> > be on the record, not hidden here where it will never be seen again.
>
> OK. I will submit to ada-comment and include a summary of the replies
> from you and Matt, as I understand them. Can I hope to be included in
> the subsequent discussion, if any?

Typically, discussions started on Ada-Comment stay there. And that is a
public list which I assume you've joined.

Of course, the final deliberations will be made at an ARG meeting. And
unless you come as an observer, you won't be able to impact that discussion.

                       Randy.

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Randy Brukardt]

"Matthew Heaney" <mheaney@on2.com> wrote in message
news:1169657427.881916.284570@l53g2000cwa.googlegroups.com...
> On Jan 23, 7:43 pm, "Randy Brukardt" <r...@rrsoftware.com> wrote:
...
> > No, Matt is just reasoning from what he'd like to be true, not what the
RM
> > implies. You'll note he didn't give any RM paragraph references.
>
> Because I was using the Dewar Rule.

I don't think anyone doubts what the rules ought to mean here. The question
was whether the RM actually requires that.

The Dewar rule doesn't mean that we can ignore errors/omissions in the RM,
it simply lowers the priority of fixing them (and lets us fix them in a
Corrigendum rather than an Amendment).

> > I don't believe Matt was referring in any way to the actual
> > wording of the RM. I don't see any wording that would require any
> > relationship between "=" and Equivalent_Elements, and this is needed.
>
> It cannot be any other way, for the reason I gave above.

But that's irrelevant to whether or not the RM states it. And sooner or
later, someone will find some clever way to "use" the mistake, and then
claim that their implementer doesn't implement the standard properly.

> > Nothing is "implied" by the RM. Please explain how you think that these
> > issues are covered by the RM wording, as opposed to what we intended the
RM
> > to say.
>
> In the case of ordered associative containers, the less-than operator
> must define a "strict weak ordering".  That's the most succinct
> statement of the precondition, since that term has a precise definition
> in discrete mathematics.
>
> With respect to the requirement that equality implies equivalence, I
> would argue that that requirement already ennunciated by existing
> wording (though I suppose an AARM note wouldn't hurt anything).
>
> I'm a pragmatist in these matters.  No matter what the RM says (or
> doesn't say), the developer has all the incentive he needs to do the
> right thing.  If he doesn't do the right thing, then his program simply
> won't work...

That probably is the correct approach for a user (I can't see why anyone
would want to ignore the obvious intent). It's not the correct approach for
the actual RM, and it's questionable for the implementer of the containers
(it's better to get errors and omissions fixed, than just ignoring them.
Else you will have users than don't understand the intent and they could
claim your implementation is wrong).

                                    Randy.

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Adam Beneschan]

On Jan 24, 1:18 pm, "Randy Brukardt" <r...@rrsoftware.com> wrote:
> "Matthew Heaney" <mhea...@on2.com> wrote in messagenews:1169657427.881916.284570@l53g2000cwa.googlegroups.com...

> > It cannot be any other way, for the reason I gave above.

> But that's irrelevant to whether or not the RM states it. And sooner or
> later, someone will find some clever way to "use" the mistake, and then
> claim that their implementer doesn't implement the standard properly.

It doesn't even need someone to be "clever".  I can envision that
someone might write a "<" function that isn't perfectly designed, then
they try using the package and they find it doesn't work, then they
read the RM to try to get an idea of why, then they come across the
section that describes what the requirements for "<" are, then they
check carefully and find that the "<" they wrote meets those
requirements (even though it doesn't make the equivalence relation
transitive), then they scratch their heads trying to figure out why
things aren't working, and eventually they go berserk and vow never to
code in anything besides C ever again.

                        -- Adam

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Matthew Heaney]

On Jan 24, 4:27 pm, "Adam Beneschan" <a...@irvine.com> wrote:
>
> ... then they scratch their heads trying to figure out why
> things aren't working, and eventually they go berserk and vow never to
> code in anything besides C ever again.

This is a silly argument.  The Ada container library is modeled on the
C++ STL, and in that library the requirement for "strict weak ordering"
for the binary predicate for ordered associative containers is clear.

Whatever putative difficulties Ada programmers have defining a
less-than operator for instantiating a generic container, that is no
different from the same problems C++ programmers would have defining a
binary predicate for instantiating a container template.  Yet somehow,
some way, thousands of C++ programmers have managed to instantiate
their container templates without any problems.  I hope you're not
suggesting that C++ programmers are smarter than Ada programmers!

Ambiguities in the Ada RM happen all the time, that's why we have an
ARG.   There's nothing special about (assumed) ambiguity in the
requirement for strict weak ordering.

(And besides, even if the RM doesn't say so, what's the alternative?
If you define a less-than operator for which equivalence is not
transitive, then the container won't work.  It's not as if there's a
competing RM interpretation what could make it otherwise.)

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Matthew Heaney]

On Jan 24, 3:56 pm, "Adam Beneschan" <a...@irvine.com> wrote:
>
> As far as I can tell from the wording of the RM (A.18.9(79/2)), the
> function "<" that Niklas wrote does indeed meet the requirements...

Even if that's true, the container doesn't work with that function!
What would be the point of defining a function that satisfies RM
requirements but doesn't satisfy the requirement for program
correctness???

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Randy Brukardt]

"Matthew Heaney" <mheaney@on2.com> wrote in message
news:1169679410.534272.110960@s48g2000cws.googlegroups.com...
> On Jan 24, 3:56 pm, "Adam Beneschan" <a...@irvine.com> wrote:
> >
> > As far as I can tell from the wording of the RM (A.18.9(79/2)), the
> > function "<" that Niklas wrote does indeed meet the requirements...
>
> Even if that's true, the container doesn't work with that function!
> What would be the point of defining a function that satisfies RM
> requirements but doesn't satisfy the requirement for program
> correctness???

To show that the RM is wrong. That's all Niklas was asking anyway -- he
wasn't asking what the container *should* be, but rather whether the RM
accurately reflected the intent. It doesn't help to answer some other
question that wasn't even asked....

                         Randy.

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Adam Beneschan]

On Jan 24, 2:50 pm, "Matthew Heaney" <mhea...@on2.com> wrote:

> This is a silly argument.  The Ada container library is modeled on the
> C++ STL, and in that library the requirement for "strict weak ordering"
> for the binary predicate for ordered associative containers is clear.
>
> Whatever putative difficulties Ada programmers have defining a
> less-than operator for instantiating a generic container, that is no
> different from the same problems C++ programmers would have defining a
> binary predicate for instantiating a container template.  Yet somehow,
> some way, thousands of C++ programmers have managed to instantiate
> their container templates without any problems.  I hope you're not
> suggesting that C++ programmers are smarter than Ada programmers!

No, of course not.  But I guess I am suggesting that the Ada
programming community expects the RM to be correct.  The idea that we
should let the RM say something is correct when it isn't, because
nobody will ever do it wrong anyway, isn't the Ada way.  That sounds
more like the C way.  The same "C way" that says "We don't need to
check our input for sanity because nobody will enter insane input
anyway."  "We don't need to check for buffer overflow because no data
is going to be that large anyway."  Or maybe that's the Microsoft
way---I don't know.  But I think our standards are higher than that.

> Ambiguities in the Ada RM happen all the time, that's why we have an
> ARG.   There's nothing special about (assumed) ambiguity in the
> requirement for strict weak ordering.

But there's no ambiguity in the RM.  The RM's requirements for the "<"
function are unambiguous.  Wrong, but unambiguous.

                     -- Adam

Re: Equivalent keys/elements in Ada.Containers Maps and Sets

[Georg Bauhaus]

On Wed, 2007-01-24 at 18:22 -0800, Adam Beneschan wrote:
> 
> On Jan 24, 2:50 pm, "Matthew Heaney" <mhea...@on2.com> wrote:
> 
> > This is a silly argument.  The Ada container library is modeled on the
> > C++ STL, and in that library the requirement for "strict weak ordering"
> > for the binary predicate for ordered associative containers is clear.

Whew, this is _not_ an argument for being practical in my view.
Are you implying that a programmer who wants to use Ada.Containers,
whether he/she is familiar with the STL or not,
should see to it that both ISO/IEC 8652:2007(E) (Ada)
and ISO/IEC 14882:2003 (C++) and associated documents
are available for reference?

> No, of course not.  But I guess I am suggesting that the Ada
> programming community expects the RM to be correct.

Yes, and the RM should stay helpful, too. If I wanted to use shared
variables in a C++ program, and be asked to consult the Ada programming
language and protected types, will this suggestion be acceptable
to any practical C++ programmer? No.


 -- Georg