Redefinition of Equality (Long)

Redefinition of Equality (Long)

[david scott gibson]

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

Re: Redefinition of Equality (Long)

[Robert A Duff]

In article <52hgmoINN7tg@snoopy.cis.ohio-state.edu>,
david scott gibson <dgibson@snoopy.cis.ohio-state.edu> wrote:
>In order to compare the elements from two sets, a redefined equality
>function must remove elements from the sets first. ...

It seems highly undesirable for "=" to modify its parameters.  If you
want to implement "=" in terms of some destructive operations, then you
ought to make a copyof the parameters first.  Why is this a problem?

I certainly agree that functions should allow 'in out' parameters, but
not so you can write evil "=" operations.  But even if 'in out' were
allowed, you would still have your problem, because for *tagged* types
an overriding operation has to be subtype conformant with what it's
overriding.

You ask why the rule about 'in out' wasn't changed.  I think it was for
two reasons: (1) Tucker was ambivalent, and was worried about
implementation difficulties (having to do copy-backs for out parameters
in the middle of an expression, rather than only at the end of a
statement, for an existing compiler that wasn't designed to do that).
(2) About half of the reviewers were rabidly anti-side-effect zealots.
Despite the fact that Ada functions allow side effects on globals, and
on stuff pointed to by parameters, this contingent believed that
preventing *some* forms of side effects (namely, on parameters) is
better than nothing.

I was very much in favor of removing this restricion.  And I've found it
frustrating when writing Ada 95 code.  I happen to think that *some*
kinds of side effects are OK, and I find it annoying that I have to use
access parameters, and put "aliased" and "'Access" all over the place.

- Bob

Re: Redefinition of Equality (Long)

[Robert Dewar]

Bob said

"In article <52hgmoINN7tg@snoopy.cis.ohio-state.edu>,
david scott gibson <dgibson@snoopy.cis.ohio-state.edu> wrote:
>In order to compare the elements from two sets, a redefined equality
>function must remove elements from the sets first. ...

It seems highly undesirable for "=" to modify its parameters.  If you
want to implement "=" in terms of some destructive operations, then you
ought to make a copyof the parameters first.  Why is this a problem?

I certainly agree that functions should allow 'in out' parameters, but
not so you can write evil "=" operations.  But even if 'in out' were
allowed, you would still have your problem, because for *tagged* types
an overriding operation has to be subtype conformant with what it's
overriding.
"


I completely agree with Bob here. In fact it is this kind of suggestion
of serious misuse of the ability to have in out parameters for functions
that feeds the enthusiasim of the rabid anti-side-effects-in-functions
folks :-)

Actually as we have discussed this issue over and over again, more and more
such horrible proposed uses have appeared, and although I still wish that
this very annnoying restrictions would have been lifted at LEAST for
interfaced functions, where the ability is really important, I must say
that I have to agree more than I did that this capability invites misuse.

Bob's analysis of why this feature did NOT go in is quite right. In fact
the requirements document (of which i was one of the authors) casually
mentioned the relaxation of this restriction as a *possible* example
of what we meant by stating the priniciple that unenecessary and 
undesirable restrictions should be removed.

A majority of all comments received on the requirements document were
rants and raves about even the *suggestion* that this restriction should
be dropped :-)

Re: Redefinition of Equality (Long)

[Robert A Duff]

In article <324FD267.954@cis.ohio-state.edu>,
Dave Gibson  <dgibson@cis.ohio-state.edu> wrote:
>Why pay the price of making a copy of an arbitrarily large object when 
>it is not necessary??  (Making a few copies of access values will do.)
>"=" should, of course, leave the abstract value of its parameters 
>unmodified. ...

Well, the goal is to make sure that the compiler can *check* that the
abstract value of an 'in' parameter is not modified.  And any time you
want to check things at compile time, you have to put up with rules that
are more pessimistic than they might be.  In this case, the compiler
knows nothing of you "abstract" values.  The language therefore requires
it to check that the concrete values are not modified.

The alternative would be for 'in' mode to just be a comment in the code,
and the compiler wouldn't check anything.  Then you could modify the
concrete value while making sure the abstract value is not modified.
But that would obviously be error prone.

I don't see any way around this.

Consider:

    X: constant Integer := 1;
    ...
    Y: Integer := Read_Data_From_Input_File;
    X := Y; -- Illegal!

Should the above be legal?  After all, if the programmer ensures that Y
is 1, then there's no harm done.

Consider:

    Do_Something("string literal");

If Do_Something is allowed to modify the concrete value of its "in"-mode
parameter, what is the compiler supposed to do with the result?

>...  It should be the responsibility of the person implementing 
>Set "=" to ensure that.  However, I do not see any good reason 
>to prevent the operation from manipulating the value passed in 
>in order to compute the function result - especially if it avoids
>unnecessary copying.  The way I'm writing code, the value passed in is
>always an access value although this is not visible at the client
>level. 

Well, if it's an access value, then you *can* modify what it points to.

>Are you saying that a hypothetical 'in out' mode "=" would only
>overload 
>and not override the automatically generated "=" function?  Or would it
>not even be allowed to overload?  Either way, that would be a problem.

I'm saying it would be illegal.  Consider procedures, which *can* have
'out' parameters.  If type T1 has a primitive:

    procedure P(X: in T1);

And "type T2 is new T1;" and T2 overrides:

    procedure P(X: in out T2); -- Illegal!

The parameters have to be of the same modes, and same subtypes.
Otherwise dispatching wouldn't work -- the caller of
P(T1'Class(something)) doesn't know whether he's supposed to copy
back the parameters, for example.

>Well, I'm almost in agreement with them.  I'd like to write functions 
>which do not have any side-effects at the abstract level.  How this is
>achieved concretely, however, should not be unduely hampered by the 
>compiler.  

Agreed.

- Bob

Re: Redefinition of Equality (Long)

[Dave Gibson]

Robert A Duff wrote:
> 
> In article <52hgmoINN7tg@snoopy.cis.ohio-state.edu>,
> david scott gibson <dgibson@snoopy.cis.ohio-state.edu> wrote:
> 
> It seems highly undesirable for "=" to modify its parameters.  If you
> want to implement "=" in terms of some destructive operations, then you
> ought to make a copy of the parameters first.  Why is this a problem?

Why pay the price of making a copy of an arbitrarily large object when 
it is not necessary??  (Making a few copies of access values will do.)
"=" should, of course, leave the abstract value of its parameters 
unmodified.  It should be the responsibility of the person implementing 
Set "=" to ensure that.  However, I do not see any good reason 
to prevent the operation from manipulating the value passed in 
in order to compute the function result - especially if it avoids
unnecessary copying.  The way I'm writing code, the value passed in is
always an access value although this is not visible at the client
level. 

> I certainly agree that functions should allow 'in out' parameters, but
> not so you can write evil "=" operations.  But even if 'in out' were
> allowed, you would still have your problem, because for *tagged* types
> an overriding operation has to be subtype conformant with what it's
> overriding.

Are you saying that a hypothetical 'in out' mode "=" would only
overload 
and not override the automatically generated "=" function?  Or would it
not even be allowed to overload?  Either way, that would be a problem.

> (2) About half of the reviewers were rabidly anti-side-effect zealots.
> Despite the fact that Ada functions allow side effects on globals, and
> on stuff pointed to by parameters, this contingent believed that
> preventing *some* forms of side effects (namely, on parameters) is
> better than nothing.

Well, I'm almost in agreement with them.  I'd like to write functions 
which do not have any side-effects at the abstract level.  How this is
achieved concretely, however, should not be unduely hampered by the 
compiler.  

> I was very much in favor of removing this restricion.  And I've found it
> frustrating when writing Ada 95 code.  I happen to think that *some*
> kinds of side effects are OK, and I find it annoying that I have to use
> access parameters, and put "aliased" and "'Access" all over the place.

The use of access types didn't help me out in this situation because 
I want to be able to move around object values by exchanging the access 
values pointing to the objects.  I also found it very annoying and
distracting placing "aliased" and "'access" all over the place.  

Thanks for your insights.

Dave
--
dgibson@cis.ohio-state.edu

Re: Redefinition of Equality (Long)

[Robb Nebbe]

Robert A Duff wrote:

> Well, the goal is to make sure that the compiler can *check* that the
> abstract value of an 'in' parameter is not modified. 
 
> ... And any time you
> want to check things at compile time, you have to put up with rules that
> are more pessimistic than they might be. 

In this particular case you may be right but I wouldn't expect this
to be true in general. I am sort of plucking this out of context but
I have seen other people say similar things. 

There is nothing intrinsic in compile time checking of semantic
properties that makes it necessarily pessimistic. In terms of model
theory (the branch of metamathematics that deal with these kinds of
issues) your statement is the equivalent of saying that no logic
(think logical system) can ever be both sound (~safe) and complete
(~not pessimistic) which is known to be false.

In a real language it might be the case that something isn't decidable
in which case you must choose to err on the side of safety or
expressiveness with dynamic checks to compensate. Or it might be
possible but just too complicated to be worth the effort. Or it just
might be that it isn't currently known how to do the checks.

Robb Nebbe

Re: Redefinition of Equality

[david scott gibson]

In article <DyKEBH.Gp3@world.std.com>,
Robert A Duff <bobduff@world.std.com> wrote:

>Well, the goal is to make sure that the compiler can *check* that the
>abstract value of an 'in' parameter is not modified.  And any time you
>want to check things at compile time, you have to put up with rules that
>are more pessimistic than they might be.  In this case, the compiler
>knows nothing of you "abstract" values.  The language therefore requires
>it to check that the concrete values are not modified.
>
>The alternative would be for 'in' mode to just be a comment in the code,
>and the compiler wouldn't check anything.  Then you could modify the
>concrete value while making sure the abstract value is not modified.
>But that would obviously be error prone.
>
>I don't see any way around this.

I don't think there is an easy solution.  In RESOLVE the behavior of
the operation would be formally specified.  The requirement that the
abstract value of an 'in' mode (RESOLVE's 'preserves' mode in this
case) parameter not change becomes a proof obligation.  I understand
why Ada takes the conservative approach.  However, this approach seems
to force unnecessary copying of objects and forces the programmer to
reason about the code at a less abstract level.

>Consider:
>
>    X: constant Integer := 1;
>    ...
>    Y: Integer := Read_Data_From_Input_File;
>    X := Y; -- Illegal!
>
>Should the above be legal?  After all, if the programmer ensures that Y
>is 1, then there's no harm done.

You wouldn't want to allow this, but what if X were an 'in' mode
formal parameter?  Then code similar to this would generate a proof
obligation that could not be satisfied.  As long as some form of
verification process is applied faithfully, allowing 'in' mode
parameters to be changed should not be a problem.

>Consider:
>
>    Do_Something("string literal");
>
>If Do_Something is allowed to modify the concrete value of its "in"-mode
>parameter, what is the compiler supposed to do with the result?

Literal values would require some special handling in an "all objects"
framework.  I think there are several different strategies that could
be used.  Upon elaboration of the unit containing the string literal
(and perhaps multiple references to it), a single object could be set
up with the literal as its value.  The above call could then be
implemented as a call passing in a String object, not a string value.
The string object could be manipulated, but Do_Something would be
required, as above, to return with the object's value unaltered.  I
doubt many current Ada compilers are likely to take this approach :-).

Dave
dgibson@cis.ohio-state.edu

Re: Redefinition of Equality (Long)

[david scott gibson]

In article <531ng6$frs@nntpa.cb.lucent.com>,
Kenneth Almquist <ka@socrates.hr.att.com> wrote:

>How about the following?  Borrowing the term from C++, we define
>
>    pragma Mutable(T);
>
>which causes "in" parameters of type T to be passed using "in out"
>conventions and prevents constants of type T from being stored in
>read-only storage.  Now we allow "in" parameters to be modified,
>but only if
>
>  1)  The type is mutable.
>
>  2)  The full type is visible.  In other words, an "in" parameter
>      of a type declared "private" cannot be modified by a function
>      or procedure which is outside the package declaring the type.

Would you allow an "in" mode formal of a mutable type to be used as an
actual corresponding to another "in" mode parameter in a call to an
operation declared outside the package?  That is, could the (concrete)
value indeed be modified by an outside operation, but only if that
operation also saw that the type in question was marked as mutable?

>This last suggestion may be overkill, since most abstract data types
>will not require pragma Mutable.  Self-ordering data structures such
>as splay trees are one example.  Data structures which cache the
>results of recently performed queries are another.  Data structures
>which are implemented using other data structures whose access methods
>contain state is a third.  

Good examples.  I'm working on a general framework for specifying and
implementing components in Ada.  I don't want it to rule out any
implementations such as these and swapping-base implementations.

>(In this regard, Dave's example of a Set
>data type using a List data type seems to have been misunderstood by
>some people.  The point of his example was that his List type did
>not allow you to determine which elements were in the list without
>modifying the list.)

Right (except that it was the Set type which did not allow
you to determine its elements without modification).

>None of these three types of data structures are
>common, so the support that the language provides for implementing
>them is not critical.

In the swapping-base paradigm I'm working with, it is common to
"decompose" an object and then put it back together without changing
its abstract value (and without any copying).  To implement this
scheme in Ada using functions would probably require all non-built-in
types to be mutable in the sense you suggest.

> What is important is the ability to separate
>interface from implementation.  I want to be able to take a table
>package and replace a hash table with a splay tree--without modifying
>the public part of the package specification.

Absolutely!  Programming languages should fully support this.

Dave
dgibson@cis.ohio-state.edu

Re: Redefinition of Equality (Long)

[Kenneth Almquist]

> Dave Gibson  <dgibson@cis.ohio-state.edu> wrote:
>> Why pay the price of making a copy of an arbitrarily large object when 
>> it is not necessary??  (Making a few copies of access values will do.)
>> "=" should, of course, leave the abstract value of its parameters 
>> unmodified. ...
>
> Well, the goal is to make sure that the compiler can *check* that the
> abstract value of an 'in' parameter is not modified.  [snip]

That's the goal.  It is not fully achieved because if the "in"
parameter is a pointer or a record containing a pointer, the thing
pointed to can be modified.

> The alternative would be for 'in' mode to just be a comment in the code,
> and the compiler wouldn't check anything.  Then you could modify the
> concrete value while making sure the abstract value is not modified.
> But that would obviously be error prone.

How about the following?  Borrowing the term from C++, we define

    pragma Mutable(T);

which causes "in" parameters of type T to be passed using "in out"
conventions and prevents constants of type T from being stored in
read-only storage.  Now we allow "in" parameters to be modified,
but only if

  1)  The type is mutable.

  2)  The full type is visible.  In other words, an "in" parameter
      of a type declared "private" cannot be modified by a function
      or procedure which is outside the package declaring the type.

The purpose of the second rule is to allow the compiler to ensure
that the abstract value of an "in" parameter cannot be modified
unless the implementer of the abstract data type provides a function
that does this.

Following the tradition of making dangerous Ada constructs as ugly
as possible, we could require an attribute to be used when a
modifiable version of an "in" parameter is required:

    function Lookup(Tree : Splay_Tree) return Item is
       ...

       Tree'Variable.Root := ...;

This last suggestion may be overkill, since most abstract data types
will not require pragma Mutable.  Self-ordering data structures such
as splay trees are one example.  Data structures which cache the
results of recently performed queries are another.  Data structures
which are implemented using other data structures whose access methods
contain state is a third.  (In this regard, Dave's example of a Set
data type using a List data type seems to have been misunderstood by
some people.  The point of his example was that his List type did
not allow you to determine which elements were in the list without
modifying the list.)  None of these three types of data structures are
common, so the support that the language provides for implementing
them is not critical.  What is important is the ability to separate
interface from implementation.  I want to be able to take a table
package and replace a hash table with a splay tree--without modifying
the public part of the package specification.
				Kenneth Almquist

Re: Redefinition of Equality (Long)

[Kenneth Almquist]

dgibson@cayman.cis.ohio-state.edu (david scott gibson) asks:
> Would you allow an "in" mode formal of a mutable type to be used as an
> actual corresponding to another "in" mode parameter in a call to an
> operation declared outside the package?  That is, could the (concrete)
> value indeed be modified by an outside operation, but only if that
> operation also saw that the type in question was marked as mutable?

If I understand the question, the answer is no for private types.  In
other words, if you have:

    package Set_Package is
       type Set_Type is limited private;
       procedure Insert(Item : Integer; Set : Set_Type);
       function Is_Member(Item : Integer; Set : Set_Type) return Boolean;
    private
       pragma Mutable(Set_Type);
       type Tree_Entry;
       type Tree_Entry_Ptr is access Tree_Entry;
       type Tree_Entry is record
          Left, Right : Tree_Entry_Ptr;
          Value : Integer;
       type Set is 
    end Set_Package;

then the body of Set_Package can include

    procedure Move_To_Root(Key : Integer; Set : in out Set_Type);
       -- Moves the item containing Key to the root of the tree
       -- if it is present in the tree.

    function Is_Member(Item : Integer; Set : Set_Type) return Boolean is
    begin
       Move_To_Root(Item, Set);
       return Set /= null and then Set.Value = Item;
    end Is_Member;

Inside the body of the package there is no semantic difference between
"in" parameters and "in out" parameters, so we could equally well have
written:

    procedure Move_To_Root(Key : Integer; Set : in Set_Type);


Outside of the package, the legality of various operations is not
affected by the presence of pragma Mutable:

    procedure P(Set : in Set_Type) is
    begin
       if Is_Member(1, Set) then -- Legal
          Insert(2, Set);        -- Not legal
       end if;
    end P;

The point is that the abstract value of an "in" parameter should not be
modified.  Inside the body of the package, it is the responsibility of
the programmer to ensure this.  Outside the package the compiler will
check this.

Note that when code is generated for P, Set must be treated as an "in
out" parameter because Is_Member may modify the concrete value of Set.
This is why the pragma applies to the type, as opposed to applying to
particular operations provided by the package.

In my description, I allowed pragma Mutable to be applied to types
which are not private.  In this case there is no distinction between
inside and outside the package; an "in" parameter of the type can be
modified anywhere.  I cannot think of any valid use for this, so I'm
inclined to prohibit it.
					Kenneth Almquist