Version 1.9 of ais/ai-00123.txt

Unformatted version of ais/ai-00123.txt version 1.9
Other versions for file ais/ai-00123.txt

!standard 04.05.02 (24)          00-08-17 AI95-00123/12
!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-15):
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)
Insert after the paragraph:
the new paragraph:
For any composite type, the order in which "=" is called for components is unspecified. Furthermore, if the result can be determined before calling "=" on some components, it is unspecified whether "=" is called on those components.
!corrigendum 4.05.02(32)
Insert after the paragraph:
A membership test using not in gives the complementary result to the corresponding membership test using in.
the new paragraph:
Implementation Requirements

For all nonlimited types declared in language-defined packages, the "=" and "/=" operators of the type shall behave as if they were the predefined equality operators for the purposes of the equality of composite types and generic formal types.
!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.

****************************************************************

Questions? Ask the ACAA Technical Agent