Re: Equality operator overloading in ADA 83

[bobduff@world.std.com (Robert A Duff)]

In article <335CAEFE.35DC@elca-matrix.ch>,
Mats Weber  <Mats.Weber@elca-matrix.ch> wrote:
>The same holds for Ada.Strings.Unbounded, and there was some discussion
>on this a year ago or so here in c.l.a. Is anything being done so that
>an AI is issued to ensure this (if AIs still exist) ?

This is AI95-123, which has been approved by the ARG, but not (yet) by
WG9.  I've included it below.  In general, I believe that ACVC tests do
not get written based on AIs until WG9 has approved.

In case anyone's interested, the AI's are stored on
sw-eng.falls-church.va.us, in /public/adaic/standards/95com/ada-issues.

- Bob

!standard 04.05.02 (24)                               97-03-19  AI95-00123/05
!class binding interpretation 96-07-23
!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
!subject Equality for Composite Types

!summary 96-11-19

The primitive equality operators of language defined types compose
properly, 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 is
determined before calling "=" on some components, the language does not
define whether "=" is called on those components.

!question 96-07-23

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-24):

  14   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.

  15   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.
  ...
  21   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:

     22  If there are no components, the result is defined to be True;

     23  If there are unmatched components, the result is defined to be
         False;

     24  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 96-11-16

(See summary.)

!wording 96-07-23

!discussion 97-03-19

Composability of equality 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.

Number 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 RM 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
      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) Nul-out the unused
      characters, 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 RM 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.

!appendix 97-03-19

...