* Equivalent keys/elements in Ada.Containers Maps and Sets @ 2007-01-23 12:56 Niklas Holsti 2007-01-23 15:45 ` Matthew Heaney 0 siblings, 1 reply; 19+ messages in thread From: Niklas Holsti @ 2007-01-23 12:56 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-23 12:56 Equivalent keys/elements in Ada.Containers Maps and Sets Niklas Holsti @ 2007-01-23 15:45 ` Matthew Heaney 2007-01-23 16:47 ` Matthew Heaney 2007-01-23 23:04 ` Niklas Holsti 0 siblings, 2 replies; 19+ messages in thread From: Matthew Heaney @ 2007-01-23 15:45 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-23 15:45 ` Matthew Heaney @ 2007-01-23 16:47 ` Matthew Heaney 2007-01-23 23:04 ` Niklas Holsti 1 sibling, 0 replies; 19+ messages in thread From: Matthew Heaney @ 2007-01-23 16:47 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-23 15:45 ` Matthew Heaney 2007-01-23 16:47 ` Matthew Heaney @ 2007-01-23 23:04 ` Niklas Holsti 2007-01-24 0:43 ` Randy Brukardt 2007-01-24 16:11 ` Matthew Heaney 1 sibling, 2 replies; 19+ messages in thread From: Niklas Holsti @ 2007-01-23 23:04 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-23 23:04 ` Niklas Holsti @ 2007-01-24 0:43 ` Randy Brukardt 2007-01-24 7:52 ` Niklas Holsti ` (2 more replies) 2007-01-24 16:11 ` Matthew Heaney 1 sibling, 3 replies; 19+ messages in thread From: Randy Brukardt @ 2007-01-24 0:43 UTC (permalink / raw) "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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 0:43 ` Randy Brukardt @ 2007-01-24 7:52 ` Niklas Holsti 2007-01-24 21:06 ` Randy Brukardt 2007-01-24 16:50 ` Matthew Heaney 2007-01-24 20:56 ` Adam Beneschan 2 siblings, 1 reply; 19+ messages in thread From: Niklas Holsti @ 2007-01-24 7:52 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 7:52 ` Niklas Holsti @ 2007-01-24 21:06 ` Randy Brukardt 0 siblings, 0 replies; 19+ messages in thread From: Randy Brukardt @ 2007-01-24 21:06 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 0:43 ` Randy Brukardt 2007-01-24 7:52 ` Niklas Holsti @ 2007-01-24 16:50 ` Matthew Heaney 2007-01-24 21:18 ` Randy Brukardt 2007-01-24 20:56 ` Adam Beneschan 2 siblings, 1 reply; 19+ messages in thread From: Matthew Heaney @ 2007-01-24 16:50 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 16:50 ` Matthew Heaney @ 2007-01-24 21:18 ` Randy Brukardt 2007-01-24 21:27 ` Adam Beneschan 0 siblings, 1 reply; 19+ messages in thread From: Randy Brukardt @ 2007-01-24 21:18 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 21:18 ` Randy Brukardt @ 2007-01-24 21:27 ` Adam Beneschan 2007-01-24 22:50 ` Matthew Heaney 0 siblings, 1 reply; 19+ messages in thread From: Adam Beneschan @ 2007-01-24 21:27 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 21:27 ` Adam Beneschan @ 2007-01-24 22:50 ` Matthew Heaney 2007-01-25 2:22 ` Adam Beneschan 0 siblings, 1 reply; 19+ messages in thread From: Matthew Heaney @ 2007-01-24 22:50 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 22:50 ` Matthew Heaney @ 2007-01-25 2:22 ` Adam Beneschan 2007-01-26 0:08 ` Georg Bauhaus 0 siblings, 1 reply; 19+ messages in thread From: Adam Beneschan @ 2007-01-25 2:22 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-25 2:22 ` Adam Beneschan @ 2007-01-26 0:08 ` Georg Bauhaus 0 siblings, 0 replies; 19+ messages in thread From: Georg Bauhaus @ 2007-01-26 0:08 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 0:43 ` Randy Brukardt 2007-01-24 7:52 ` Niklas Holsti 2007-01-24 16:50 ` Matthew Heaney @ 2007-01-24 20:56 ` Adam Beneschan 2007-01-24 20:57 ` Adam Beneschan 2007-01-24 22:56 ` Matthew Heaney 2 siblings, 2 replies; 19+ messages in thread From: Adam Beneschan @ 2007-01-24 20:56 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 20:56 ` Adam Beneschan @ 2007-01-24 20:57 ` Adam Beneschan 2007-01-24 22:56 ` Matthew Heaney 1 sibling, 0 replies; 19+ messages in thread From: Adam Beneschan @ 2007-01-24 20:57 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 20:56 ` Adam Beneschan 2007-01-24 20:57 ` Adam Beneschan @ 2007-01-24 22:56 ` Matthew Heaney 2007-01-25 0:44 ` Randy Brukardt 1 sibling, 1 reply; 19+ messages in thread From: Matthew Heaney @ 2007-01-24 22:56 UTC (permalink / raw) 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??? ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 22:56 ` Matthew Heaney @ 2007-01-25 0:44 ` Randy Brukardt 0 siblings, 0 replies; 19+ messages in thread From: Randy Brukardt @ 2007-01-25 0:44 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-23 23:04 ` Niklas Holsti 2007-01-24 0:43 ` Randy Brukardt @ 2007-01-24 16:11 ` Matthew Heaney 2007-01-24 18:12 ` Niklas Holsti 1 sibling, 1 reply; 19+ messages in thread From: Matthew Heaney @ 2007-01-24 16:11 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: Equivalent keys/elements in Ada.Containers Maps and Sets 2007-01-24 16:11 ` Matthew Heaney @ 2007-01-24 18:12 ` Niklas Holsti 0 siblings, 0 replies; 19+ messages in thread From: Niklas Holsti @ 2007-01-24 18:12 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 19+ messages in thread
end of thread, other threads:[~2007-01-26 0:08 UTC | newest] Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2007-01-23 12:56 Equivalent keys/elements in Ada.Containers Maps and Sets Niklas Holsti 2007-01-23 15:45 ` Matthew Heaney 2007-01-23 16:47 ` Matthew Heaney 2007-01-23 23:04 ` Niklas Holsti 2007-01-24 0:43 ` Randy Brukardt 2007-01-24 7:52 ` Niklas Holsti 2007-01-24 21:06 ` Randy Brukardt 2007-01-24 16:50 ` Matthew Heaney 2007-01-24 21:18 ` Randy Brukardt 2007-01-24 21:27 ` Adam Beneschan 2007-01-24 22:50 ` Matthew Heaney 2007-01-25 2:22 ` Adam Beneschan 2007-01-26 0:08 ` Georg Bauhaus 2007-01-24 20:56 ` Adam Beneschan 2007-01-24 20:57 ` Adam Beneschan 2007-01-24 22:56 ` Matthew Heaney 2007-01-25 0:44 ` Randy Brukardt 2007-01-24 16:11 ` Matthew Heaney 2007-01-24 18:12 ` Niklas Holsti
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox