!standard 04.05.02 (24) 00-04-11 AI95-00123/10 !standard 04.05.02 (32) !class binding interpretation 96-07-23 !status Corrigendum 2000 99-07-28 !status WG9 approved (8-0-0) 97-07-04 !status ARG approved 10-0-2 (subject to editorial review) 96-10-07 !status work item (letter ballot was 6-6-0) 96-10-03 !status ARG approved 8-0-0 (subject to letter ballot) 96-06-17 !status work item 96-04-04 !status received 96-04-04 !priority High !difficulty Medium !qualifier Clarification !subject Equality for composite types !summary The primitive equality operators of a language-defined type compose properly (i.e., do not "reemerge"), when the type is used as a component type, or a generic actual type. For any composite type, the order in which "=" is called for components is not defined by the language. Furthermore, if the result can be determined before calling "=" on some components, the language does not define whether "=" is called on those components. !question The following language-defined types are private, and have an explicitly defined primitive "=" operator: System.Address Ada.Strings.Maps.Character_Set Ada.Strings.Bounded.Generic_Bounded_Length.Bounded_String Ada.Strings.Unbounded.Unbounded_String Ada.Strings.Wide_Maps.Wide_Character_Set Ada.Task_Identification.Task_ID This would seem to imply that the composability of these "=" operators depends on whether the implementation chooses to implement them as tagged types, by 4.5.2(14-25): For a type extension, predefined equality is defined in terms of the primitive (possibly user-defined) equals operator of the parent type and of any tagged components of the extension part, and predefined equality for any other components not inherited from the parent type. For a private type, if its full type is tagged, predefined equality is defined in terms of the primitive equals operator of the full type; if the full type is untagged, predefined equality for the private type is that of its full type. and by 4.5.2(21-24): Given the above definition of matching components, the result of the predefined equals operator for composite types (other than for those composite types covered earlier) is defined as follows: If there are no components, the result is defined to be True; If there are unmatched components, the result is defined to be False; Otherwise, the result is defined in terms of the primitive equals operator for any matching tagged components, and the predefined equals for any matching untagged components. This would cause portability problems. Also, in the above definition, what does "in terms of" mean? For a composite type, if some parts have an "=" with side effects, does the language define whether all of these side effects happen, and in what order? !recommendation (See summary.) !wording (See corrigendum.) !discussion Composability of equality for a type T means three things: 1. If a composite type has a component of type T with a user-defined equality operator, then the predefined equality of the composite type calls the user-defined equality operator of type T (for that component). 2. If an actual type T for a generic formal type has a user-defined equality operator, then the predefined equality on the generic formal type calls the user-defined equality operator of type T. 3. If a parent type T has a user-defined equality operator, then the predefined equality of a type extension of T calls the user-defined equality on T (for the parent part), in addition to comparing the extension parts. Non-composability means that the predefined equality is called for T, despite the fact that T has a user-defined equality operator. Of course, if there is no user-defined equality, then equality always composes properly. Item 3 is irrelevant here, since none of the types in question is (visibly) tagged. For a private type, if the underlying type is tagged, or if there is no user-defined equality, then equality composes. Otherwise, it does not. (Here, "underlying type" means the full type, or if that comes from a private type, then the underlying type of *that* type, and so on.) However, for the private types mentioned in the question, the standard does not specify whether the underlying type is tagged, nor whether the equality operator is truly user-defined (as opposed to just being the normal bit-wise equality). It is important that the composability of "=" for these types be defined by the language. We choose to make them composable. An implementation can achieve this by making the full type tagged. Alternatively, the implementation could simply use the predefined "=" for these types. (Alternatively, an implementation could treat these types specially, making them untagged, but with composable equality. However, this would add some complexity to the compiler.) Here is an analysis of implementation concerns for each type in question: - System.Address: The intent is for this type to directly represent a hardware address. Therefore, it is probably not feasible to implement it as a tagged type. The simplest implementation of equality of Addresses is thus the normal bit-wise equality. This is what most users would expect, anyway. On certain segmented architectures, it is possible for two different addresses to point to the same location. The same thing can happen due to memory mapping, on many machines. Such addresses will typically compare unequal, despite the fact that they point to the same location. - Ada.Strings.Maps.Character_Set: A typical implementation will use an array of Booleans, so bit-wise equality will be used, so it will compose. - Ada.Strings.Bounded.Generic_Bounded_Length.Bounded_String: Two reasonable implementations are: (1) Set the unused characters to some particular character, and use bit-wise equality, and (2) use a tagged type with a user-defined equality. Either way, equality will compose. This is, admittedly, a slight implementation burden, because it rules out an untagged record with user-defined equality. - Ada.Strings.Unbounded.Unbounded_String: A tagged (controlled) type will normally be necessary anyway, for storage reclamation. In a garbage-collected implementation, a tagged type is not strictly necessary, but we choose to require composability anyway. - Ada.Strings.Wide_Maps.Wide_Character_Set: Some sort of data structure built out of access types is necessary anyway, so the extra overhead of composability is not a serious problem; the implementation can simply make the full type tagged. - Ada.Task_Identification.Task_ID: This will typically be a pointer-to-TCB of some sort (access-to-TCB, or index-into-table-of-TCB's). In any case, bit-wise equality will work, so equality will compose. As to the second question, the standard clearly does not define any order of calling "=" on components, nor does it say whether the results are combined with "and" or "and then". Equality operators with side effects are questionable in any case, so we allow implementations freedom to do what is most convenient and/or most efficient. Consider equality of a variant record: The implementation might first check that the discriminants are equal, and if not, skip the component-by-component comparison. Alternatively, the implementation might first compare the common elements, and *then* check the discriminants. A third possibility is to first compare some portions with a bit-wise equality, and then (conditionally) call user-defined equality operators on the other components. All of these implementations are valid. !corrigendum 4.05.02(24) @dinsa @xbullet @dinst For any composite type, the order in which "=" is called for components is not defined by the language. Furthermore, if the result can be determined before calling "=" on some components, the language does not define whether "=" is called on those components. !corrigendum 4.05.02(32) @dinsa A membership test using @b gives the complementary result to the corresponding membership test using @b. @dinst @i<@s8>@hr For all nonlimited types declared in language-defined packages, the "=" operator of the type shall behave as if it were the predefined equality operator for the purposes of composite equality and generic formal type equality. !ACATS test Create a C-Test to check that equality of language-defined types compose properly when used as a component or as a generic formal. (There is no surefire way to do this, but a test that insures the results of predefined equality on a type with components of the language-defined types matches the results of the equality for those types should suffice. Try independently derived objects that have the same values, as well as some different objects.) !appendix !section 4.5.2(24) !subject Equality for composite types !reference RM95-4.5.2(24) !reference RM95-A.4.4 !reference RM95-A.4.5 !from Keith Thompson 96-01-12 !reference 96-5419.a Keith Thompson 96-1-12>> !discussion Equality for composite types is defined "in terms of" the primitive or predefined equals operators for the tagged or untagged components, respectively. What exactly does "in terms of" mean? In particular, given a type like type Rec is record T1: Tagged_Type; T2: Tagged_Type; end record; must the equality operation for type Rec always invoke "=" for Tagged_Type twice, or can it be optimized to something like Left.T1 = Right.T1 and then Left.T2 = Right.T2 This is relevant only if "=" for Tagged_Type has side effects (which of course is horrible style). The types Bounded_String and Unbounded_String have user-defined "=" operators. ("User-defined"? Well, the user in this case is the implementor.) Both are declared as private types, so they may or may not be tagged. (Most likely Unbounded_String will be controlled and therefore tagged, but Bounded_String probably will not be tagged in most implementations). Given the following (assuming the appropriate declarations): type Person is record Name: Bounded_String; Age: Natural; end record; the behavior of "=" for type Person would seem to be implementation-defined. Is this correct? Is this intended? This would also apply to any other types declared in predefined units with user-defined "=" operators; I don't know whether there are any. **************************************************************** !section A.4.5(04) !subject Equality on Ada.Strings.Unbounded !reference RM95-A.4.5(4, 72, 83) !from Mats Weber (e-mail: Mats.Weber@elca-matrix.ch) 96-01-11 !keywords equality predefined unbounded string !reference 96-5421.a Mats Weber 96-1-16>> !discussion The type Ada.Strings.Unbounded.Unbouned_String is defined as private, and nothing is said about its full implementation (private part of the package Ada.Strings.Unbounded). The function "=" on unbounded strings is redefined in the package. As the type is just private, not tagged, its predefined "=" will reemerge in some situations such as the following: type Person is record Name, First_Name : Ada.Strings.Unbounded.Unbouned_String; end record; This will cause different behaviour on different implementations: if the full representation of Unbouned_String is tagged, then equality on Person will be the equality of the string values, as is probably wanted; if the full representation of Unbouned_String is not tagged, then "=" (Person, Person) uses the predefined equality of the type Unbouned_String, which will not work most of the time. The reemergence of predefined equality also happens inside generics of the form generic type T is private; ... when they are instantiated with T => Ada.Strings.Unbounded.Unbouned_String. This situation can cause severe portability problems. To solve the problem, I propose that the standard require that the full definition of Ada.Strings.Unbounded.Unbouned_String be a tagged. (It was so in a previous version of Ada 9X but got removed). Variable length strings have been a shortcoming of Ada for 13 years now and I think it would be sad to introduce new problems in that area in Ada 95. (Message sent to ada-comment@sw-eng.falls-church.va.us and copied to comp.lang.ada). Mats Weber **************************************************************** !section 4.5.2(24) !subject Equality for composite types !reference RM95-4.5.2(24) !reference RM95-A.4.4 !reference RM95-A.4.5 !reference 96-5419.a Keith Thompson 96-1-12 !from Keith Thompson 96-02-01 !reference 96-5426.a Keith Thompson 96-2-1>> !discussion Regarding the issue of the "=" operator for composites with subcomponents of type Bounded_String or Unbounded_String, I wrote: > This would also apply to any other types declared in predefined units > with user-defined "=" operators; I don't know whether there are any. In fact, there are several. A search for '"="' in rmsource.ada indicates that the following types have explicitly defined "=" operators: System.Address Ada.Strings.Maps.Character_Set Ada.Strings.Bounded.Generic_Bounded_Length.Bounded_String Ada.Strings.Unbounded.Unbounded_String Ada.Strings.Wide_Maps.Wide_Character_Set Ada.Task_Identification.Task_ID (where Generic_Bounded_Length, of course, is a generic package). Of these, System.Address is potentially the most troublesome; it almost certainly shouldn't be a tagged type. On the other hand, an implementation for which "=" for System.Address is not a bitwise comparison will probably arrange for the predefined "=" to behave correctly. I think similar arguments apply to type Task_ID. The obvious implementation of type Character_Set is an array of Boolean; in this case, predefined "=" will work correctly. Type Wide_Character_Set may present some difficulties. I suppose it could be (required to be) implemented either as a tagged type or in such a way that predefined "=" works correctly. -- Keith Thompson (The_Other_Keith) kst@thomsoft.com (kst@alsys.com still works) TeleSoft^H^H^H^H^H^H^H^H Alsys^H^H^H^H^H Thomson Software Products 10251 Vista Sorrento Parkway, Suite 300, San Diego, CA, USA, 92121-2718 Et tu, Barada Nikto? **************************************************************** !section 04.05.02(24) !subject Equality for Composite Types !reference AI95-00123/01 !from Norman Cohen !reference 96-5689.b Norman H. Cohen 96-9-6>> !discussion I object to the exclusion of System.Address. Why are we so allergic to a straightforward, simply stated rule such as "Equality composes properly for all language-defined types"? I don't buy the argument that programs using type Address are inherently unportable anyway. It is easy to envision a record type with a component of type System.Address that gets filled in by some "toolkit class"--i.e., a portable interface with an implementation- dependent component--leaving the rest of the application portable. Or the address value might be obtained through a call to or from C code. Especially with such features as Address_To_Access_Conversions, it is easy to manipulate these addresses in a portable way. In some applications, it may suffice to receive an address from one call to C code, save the address, and pass it in another call on C code. With regard specifically to the implementation-defined nature of "=" for System.Address, it is easy to envision programs that don't care whether the 8086 addresses 1234:5678 and 1235:5668 compare equal, but do care that, whatever result is obtained by a standalone comparison for equality is also obtained when the addresses are parts of records that are compared for equality. Under the proposed AI, if comparisons of record types containing Address components are to be portable, equality must be implemented explicitly for record types, using component-by-component comparison. Given the guarantee of composability for othe language-defined types, this can only be considered a trap for the unwary programmer. The draft AI does not mention any harm that will result from requiring Address equality to compose properly. (In particular, the fact that Address, or any of the other predefined types, must behave like a tagged type in this respect does not require the type to actually be implemented as a tagged type!) (Editorial comment: The term "compose properly" in the !summary is to vague. Say something like "When components of the following types appear in a composite type, an equality test for the composite types invokes the explicitly declared versions of the "=" for these component types.") **************************************************************** !section 4.5.2(12) !subject Equality for Composite Types !reference AI95-00123/04 !reference RM95-4.5.2(12) !from Keith Thompson 96-11-19 !reference 96-5760.a Keith Thompson 96-11-19>> !discussion The analysis of type System.Address in AI95-00123 currently says: - System.Address: The intent is for this type to directly represent a hardware address. Therefore, it is probably not feasible to to implement it as a tagged type. This AI implies therefore that equality of Addresses must be implemented as the normal bit-wise equality. This is what most users would expect, anyway. On certain segmented architectures, it is possible for two different addresses to point to the same location. The same thing can happen due to memory mapping, on many machines. Such addresses will compare unequal, despite the fact that they point to the same location. This isn't necessarily true. If an implementation declares System.Address as a private type whose full type is an access type, the implementation may well use something other than bitwise comparison. Indeed, on certain segmented architectures it must do so to satisfy the definition of equality for access-to-object types (4.5.2(12)). **************************************************************** !section 4.5.2(12) !subject Equality for Composite Types !reference AI95-00123/04 !reference RM95-4.5.2(12) !reference as: 96-5760.a Keith Thompson 96-11-19 !from Robert Dewar 96-11-20 !reference 1996-5761.a Robert Dewar 1996-11-20>> !discussion Keith says This isn't necessarily true. If an implementation declares System.Address as a private type whose full type is an access type, the implementation may well use something other than bitwise comparison. Indeed, on certain segmented architectures it must do so to satisfy the definition of equality for access-to-object types (4.5.2(12)). This is an incorrect conclusion, there is no requirement that the semantics of equality on the private type correspond to the semantics of equality on the full type. It would be perfectly legitimate for an implementation to use an access type, and then use the normal bitwise comparison on this access type. The quoted paragraph is irrelevant. Keith if you disagree, you must be able to provide a test that demonstrates that this implementation would be inaccurate, using only the RM to provide the inaccuracy (i.e. you are not allowed to base your argument on what might or might not be in the private part or the body. Remember that it is perfectly fine for the private part and the body of the package to be in a language other than Ada, such as some extended or different version of Ada. Note that by this criterion, I also find the language of the AI dubious, since it also reasons by what might be in the Ada implementation. For example, suppose that I don't use a tagged type, and I still let some strange non-bit equality compose, is this improper? Certainly not, since there is nothing improper about implementing type Address with a tagged type, that is clear, and there is certainly nothing improper about providing some other implementation that is semantically equivalent to this tagged implementation. **************************************************************** !section 4.5.2(12) !subject Equality for Composite Types !reference AI95-00123/04 !reference RM95-4.5.2(12) !reference 96-5760.a Keith Thompson 96-11-19 !from Bob Duff !reference 96-5762.a Robert A Duff 96-11-20>> !discussion > This isn't necessarily true. If an implementation declares System.Address > as a private type whose full type is an access type, the implementation > may well use something other than bitwise comparison. This was my opinion when I wrote the *previous* version of this AI, but the ARG didn't buy it, and I guess I'm now convinced of the error of my ways. The *current* version of the AI requires "=" to compose properly for Addresses. This implies one of: - The underlying type for Address is a tagged type. I think that's ridiculous. - The implementation uses a special hack to make the "=" compose. IMHO, this simply isn't feasible -- it adds too much complexity to the compiler. In theory, it's possible, but in practice, no compiler writer would do this. - Make "=" be the normal bit-wise equality. This is the only viable alternative, in practice. The AI tries to make it clear that the requirement of composability essentially forces this implementation. >... Indeed, on > certain segmented architectures it must do so to satisfy the definition > of equality for access-to-object types (4.5.2(12)). I don't think that's true. Equality for access types has to work "properly" (i.e. X = Y if and only if they're null, or else X.all and Y.all are the same object) for certain cases: null, objects created by "new", and objects declared aliased -- these are the only legitimate ways to create access values. For type Address, on the other hand, people can do address arithmetic, 'Address of who-knows-what, get addresses from other languages or hardware, etc. There is no requirement the "=" return true if and only if the addresses point to the same location. The RM doesn't even define what locations are, in any precise way. On a segmented machine, the implementation will typically arrange that access values that designate the same object will have the same bits. It will typically not do that for Addresses. **************************************************************** !section 4.5.2(12) !subject Equality for Composite Types !reference AI95-00123/04 !reference RM95-4.5.2(12) !reference 96-5760.a Keith Thompson 96-11-19 !reference 1996-5761.a Robert Dewar 1996-11-20 !reference 96-5762.a Robert A Duff 96-11-20 !reference 96-5763.a Keith Thompson 96-11-21>> Both Roberts (Dewar and Duff) dispute my statement that "=" for System.Address, if it's declared as a private type whose full type is an access type, must use something other than bitwise comparison on certain segmented architectures. I see their points; I was probably not quite correct to say that "=" *must* use something other than bitwise comparison. However, that wasn't really my main point. The AI says that equality for System.Address *must* be implemented as bit-wise equality. My point is, in some circumstances, it *may* be implemented otherwise. For example, I claim that it's permissible to treat System.Address the same way as an ordinary access type. For example, consider a system implemented on an architecture on which two different pointers with different bit patterns can point to the same memory (e.g., a segmented architecture). Yes, compilers can handle this by not generating (non-erroneous) code that can generate such pointers, but suppose the compiler instead generates special compare_address instructions for access types. Then "=" for a composite type containing access components must use the compare_address instruction for those components. Suppose System.Address is a private type whose full type is an access type, and that the compiler doesn't do anything magical with it. (For that matter, it could be a non-private access type.) Then the compiler will generate compare_address instructions to compare System.Address components of composites rather than doing a bitwise comparison of the entire composite object. The AI is correct in saying that equality of System.Address must compose. It's incorrect in saying that this implies that equality of addresses must be implemented as bitwise equality. Going back over what Robert Dewar wrote, I see that this is basically what he said in his last paragraph. **************************************************************** !section 4.5.2(12) !subject Equality for Composite Types !reference AI95-00123/04 !reference RM95-4.5.2(12) !reference as: 96-5760.a Keith Thompson 96-11-19 !reference as: 1996-5761.a Robert Dewar 1996-11-20 !reference as: 96-5762.a Robert A Duff 96-11-20 !from Robert Dewar 96-11-20 !reference 1996-5764.a Robert Dewar 1996-11-21>> !discussion Bob Duff says - The implementation uses a special hack to make the "=" compose. IMHO, this simply isn't feasible -- it adds too much complexity to the compiler. In theory, it's possible, but in practice, no compiler writer would do this. Not at all, at least in GNAT it is trivial to extend proper equality composition to any type. Since Ada has this peculiar rule that sometimes equality composes and sometimes it does not, the compiler has to handle the general case anyway. I agree however that in practice address comparison will almost always involve comparing the bits. By the way in GNAT record equality always works by composing separate equality operations, then the backend may combine them into a block compare if the component equality operations are bit compares and there are no gaps. **************************************************************** !section 4.5.2(12) !subject Equality for Composite Types !reference AI95-00123/04 !reference RM95-4.5.2(12) !reference 96-5760.a Keith Thompson 96-11-19 !reference 1996-5761.a Robert Dewar 1996-11-20 !from Bob Duff !reference 96-5765.a Robert A Duff 96-11-21>> !discussion > Note that by this criterion, I also find the language of the AI > dubious, since it also reasons by what might be in the Ada > implementation. It's perfectly legitimate for the Discussion section of an AI to explain the reasons for our decision in implementations terms (e.g., we don't want to do so-and-so, because it would be an implementation burden, or because it would tend to discourage efficient implementations). I don't think the actual ruling of this AI is worded in implementation terms. Just the Discussion. >... For example, suppose that I don't use a tagged type, > and I still let some strange non-bit equality compose, is this > improper? No, of course not, but the Discussion argues that this is not a feasible implementation. I think it's important for the ARG to understand that if we require composability of "=" on Addresses, we are, IN PRACTICE, requiring a certain implementation strategy, even though, in theory, other strategies are of course allowed. >... Certainly not, since there is nothing improper about > implementing type Address with a tagged type, that is clear, and there > is certainly nothing improper about providing some other > implementation that is semantically equivalent to this tagged > implementation. Agreed, but I claim that no compiler writer would seriously consider such schemes. If the AI doesn't make this clear to you, please explain why, so I can fix it. - Bob **************************************************************** !section 4.5.2(12) !subject Equality for Composite Types !reference AI95-00123/04 !reference RM95-4.5.2(12) !reference 96-5760.a Keith Thompson 96-11-19 !reference 96-5761.a Robert Dewar 1996-11-20 !reference 96-5762.a Robert A Duff 96-11-20 !reference 96-5764.a Robert Dewar 1996-11-21 !from Randy Brukardt 96-11-22 !reference 96-5766.a Randy Brukardt 96-11-22>> !discussion >Bob Duff says: > > - The implementation uses a special hack to make the "=" compose. > IMHO, this simply isn't feasible -- it adds too much complexity to the > compiler. In theory, it's possible, but in practice, no compiler > writer would do this. > >Not at all, at least in GNAT it is trivial to extend proper equality >composition to any type. Since Ada has this peculiar rule that sometimes >equality composes and sometimes it does not, the compiler has to handle >the general case anyway. > >I agree however that in practice address comparison will almost always >involve comparing the bits. I agree completely with Robert. Our compiler also is prepared to compose everything properly, and do a component-by-component comparision for any type. In our case, all we need to do is to mark the scalar type appropriately, and a component-by-component comparison will be used. We used this property to great effect on the 1's complement U2200 compiler: bitwise comparsion of integers does not work, since -0 and 0 compare differently when a bitwise comparsion is made, and compare the same when an arithmetic comparsion is made. Doing something similar for address would be trivial, and we would do it in a minute if a case where it mattered arose. (Use of System.Address as an object ought to be rare in Ada 95, so the runtime cost is not a concern). Therefore, I strongly disagree with the statement that "in practice, no compiler writer would do this.", especially given that we had to do it for integer types on the U2200. ****************************************************************