From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,611f4b10cbf9af69,start
X-Google-Attributes: gid103376,public
From: dgibson@snoopy.cis.ohio-state.edu (david scott gibson)
Subject: Redefinition of Equality (Long)
Date: 1996/09/27
Message-ID: <52hgmoINN7tg@snoopy.cis.ohio-state.edu>
X-Deja-AN: 185741059
organization: The Ohio State University,
 Department of Computer and Information Science
newsgroups: comp.lang.ada
Date: 1996-09-27T00:00:00+00:00
List-Id: <comp.lang.ada>


Here's a long winded question for the language lawyers.

------------------

Background:

With the introduction of controlled types with Adjust and a
redefinable equality operation, I had thought that I would be able to
use non-limited types as the basis for building software components in
Ada95.  It now appears to me that the limitation of function
parameters to in mode only thwarts this possibility as it did in
Ada83.  It is certainly possible to build many components for which
this limitation is not a problem.  However, in the general case where
the component's abstract concept of equality is decoupled from any
implementations of that concept, the function parameter restriction
seems to get in the way.  The example below demonstrates this problem.

Assumptions:

Several commonly accepted assumptions about component-based software
engineering underlie the problem.

1) Components should have hidden implementations.  Both the data
   representation and operation implementations should be private and
   inaccessible to client code.

2) An implementation of an ADT's equality operation cannot always (and
   often doesn't) amount to simply applying equality operations to the
   representation of each of the ADT's constituent parts.  This is
   presumably a major motivation for why Ada95 makes it possible to
   redefine the "=" operator in Ada95.

3) It should be possible to reuse all components to build new
   components which also have the same good composition properties.
   This makes it possible to build increasingly complex systems by
   "layering".  The implementation of a large complex component may be
   built on top of simpler components, which are in turn built on even
   simpler components and so on.  

Example of the Problem:

Consider a simple bounded Integer list ADT specification:

with Ada.Finalization;
package Bounded_Integer_List is

   type List is abstract new Ada.Finalization.Controlled with null record;

   procedure Insert (l: in out List; i: in Integer) is abstract;
   procedure Remove (l: in out List; i: out Integer) is abstract;
   procedure Move_Forward (l: in out List) is abstract;
   procedure Move_Back (l: in out List) is abstract;
   function  Length (l: in List) return Natural is abstract;
   function  At_Front (l: in List) return Boolean is abstract;
   function  At_Back (l: in List) return Boolean is abstract;
   function  "=" (l1, l2: in List) return Boolean is abstract;

end Bounded_Integer_List;

Clearly there are many possible implementations of this ADT.  Some
implementations may require that Initialize, Finalize, and Adjust be
redefined.  Others may use the null-body implementations of these
operations inherited from Ada.Finalization.Controlled.  There should
be no problem implementing these operations as long as the "="
operation has direct access to the representation.

Now consider the following specification for a bounded Integer set ADT:

with Ada.Finalization;
package Bounded_Integer_Set is

   type Set is abstract new Ada.Finalization.Controlled 
          with null record;

   procedure Insert (s: in out Set; i: in Integer) is abstract;
   procedure Remove (s: in out Set; i: out Integer) is abstract;
   procedure Remove_Any (s: in out Set; i: out Integer) is abstract;
   function  Cardinality (s: in Set) return Natural is abstract;
   function  Is_Member(s: in Set) return Boolean is abstract;
   function  "=" (s1, s2: in Set) return Boolean is abstract;

end Bounded_Integer_Set;

Again, there are many possible implementations, some of which may
redefine Initialize, Finalize, and Adjust.  Note that the Remove_Any
operation simply removes any element in the set and provides for an
iteration capability.

Suppose you want to create an implementation of the Set ADT which uses
an implementation of the List ADT as its representation.  Now you
might believe that these two ADT's are poorly designed and you might
believe that the List ADT is a poor choice as a representation for the
Set ADT.  That is beside the point.  I see no good reason why Ada
should prohibit the implementation and composition of component
designs such as these.  Due to the parameter mode restriction on
functions, however, the "=" operation of Set cannot be redefined if
the representation of Set is an implementation of List.

Using a Set representation like:

type Set is new Ada.Finalization.Controlled with
    record
        rep: Bounded_Integer_List.List
    end record;

the automatically defined "=" operation for Set using List's "="
operation could work for implementations of Set which maintain their
elements in order.  However, there is no reason why an implementation
of Set must maintain its elements in order just to use List as its
representation.  There is nothing in the (assumed) abstract
specification of List or Set which would require this.

In order to compare the elements from two sets, a redefined equality
function must remove elements from the sets first.  In order to remove
the elements, the formals of the Set equality operation must be used
in the actuals to a List operation for which the corresponding formals
are of "in out" mode.  Since the formals of Set's "=" function are
"in" mode, Ada prohibits their use as actuals for "in out" mode
parameters.  Thus, due to the parameter mode restriction, these two
components will not compose as they would if functions were allowed
to have "in out" mode parameters.

As far as I have been able to determine, the use of access parameters
and other new Ada95 language features do not help solve this problem.
The only solutions I see are:

1) Limit component designs and implementations to those for which the
   automatically defined equality based on the equality operations of
   constituent components is correct.  

2) Use limited private types for all components to ensure the highest
   degree of composability and generality.  This entails using
   procedures rather than functions to test for equality between two
   components.

For some libraries of components, the first option may not be a
significant limitation.  However, for a general object-based component
design and implementation strategy, it seems too restricting.  While
possible implementations will influence abstract component design to
some degree, option 1 seems to be going too far.  Option 2 is quite
workable, but I had thought that Adjust and a redefinable equality
operation would have made non-limited types a more viable option.  Am
I missing something here?  Was this sort of argument considered when
the Ada95 team came up with the new rules for redefining equality?

Dave
dgibson@cis.ohio-state.edu