Re: Ada 9X: Eliminating the re-emergence of predefined operations

Re: Ada 9X: Eliminating the re-emergence of predefined operations

[cis.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!agate!dog.e]

In article <1993Sep14.022914@lglsun.epfl.ch> madmats@lglsun.epfl.ch 
(Mats Weber) writes:

>   This is a very technical discussion. Skip it if you don't like them.
>
>   In Ada 83, the way generic subprogram parameters are passed to
>   instantiations can make hidden predefined operations of a generic actual
>   type reemerge unexpectedly. For example, consider the following piece of
>   code:
>
>   package P is
>      type T is range 1 .. 23;
>      function "*" (Left, Right : T) return T;
>         -- redefine to do modular arithmetic or
>         -- some other weird thing.
>   end P;
>
>   generic
>      type T is range <>;
>   package GP is
>
>      function Predefined_Mult (Left, Right : T) return T renames "*";
>
>   end GP;
>
>   package IP is new GP(T => P.T);
>
>   As "*" is redefined in the package P, it seems that the predefined "*"
>   for type P.T is hidden forever. But this is not true: it reappears inside
>   the instance IP, and IP.Predefined_Mult denotes the previously hidden
>   predefined multiplication operator of the type P.T (yes, such are the
>   rules of Ada 83).

It seems to me that this can be worked around by doing the following.
However, I'm having trouble determining from the RM whether this is
true.

    generic
       type T is range <>;
       with function "*" (Left, Right : T) return T is <>;
    package GP is

       function Predefined_Mult (Left, Right : T) return T renames "*";

    end GP;

Now, it seems that Predefined_Mult will rename the user-defined "*"
(to do modular arithmetic or whatever) instead of the predefined "*".
Is this correct?  Please help.

>   [deleted]
>   It is possible that the above change reduces the opportunity to share
>   code among generic instances, but it is felt much more important to have
>   solid ADTs than small executables.  

Unfortunately, in the real world (particularly in the embedded world),
executable size does matter to many users.

>   Moreover, situations where the code
>   will not be as easily shareable are the seldom cases where, for instance,
>   "+" has been redefined for an integer type, which deserves special
>   treatment anyway.

This is correct only if the Ada compiler decides at *instantiation*
time whether to make the instantiation share code with other
instantiations.  This may be a significantly more difficult way to
implement generics than other methods.

If this isn't the case, you pay a penalty ANYTIME you declare a
generic, EVEN IF you never, ever redefine any predefined operators.
For example, suppose the compiler decides, when the generic formal is
compiled, that the generic is to be a shared-code generic.  Now,
without the rule in 12.3(15), any time a generic subprogram is called,
the caller must pass to it a table containing subprogram addresses for
*all* the predefined operators that may apply to the type; and the
generic subprogram must make an indirect call through that table any
time a predefined operator is encountered in the subprogram body.
Clearly this is a significant waste of time, but it's necessary
because you can't tell at the time the generic is compiled whether it
will be instantiated with any types for which the predefined operators
have been redefined.  The only alternative is not to share the code at
all, possibly wasting space.

Actually, there might also be a readability advantage to requiring the
"with" clause.  It alerts the reader to the fact that if she/he sees
the operation used within the body of the generic may not mean what
she/he thinks it means.  


  generic                       | generic                     
    type T is range <>;         |   type T is range <>;       
                                |   with function "+" (left, right : T)
                                |       return T is <>;
  procedure GP (x : in T);      | procedure GP (x : in T);    
                                |                             
  procedure GP is               | procedure GP is             
  begin                         | begin                       
    . . .                       |   . . .                     
    y := x + 1;                 |   y := x + 1;               
    . . .                       |   . . .                     
  end GP;                       | end GP; 


In the example on the left, it looks like you're just adding 1 to a
number, but on the right, it's clear that "+" is an *abstract*
operation that may be redefined for the particular type.  Personally,
I'd probably go even further and write the code like this:

  generic                     
    type T is range <>;       
    with function ADD (left, right : T) return T is "+"; 
  procedure GP (x : in T);    
                              
  procedure GP is             
  begin                       
    . . .                     
    y := ADD (x, 1); 
    . . .                     
  end GP;                     

just to make it even clearer what's going on.

Anyway, this is all my humble opinion.  I agree that the rule in
12.3(15) is a "gotcha" that may confuse someone who doesn't know the
rules. 

                                -- Adam

Re: Ada 9X: Eliminating the re-emergence of predefined operations

[cis.ohio-state.edu!math.ohio-state.edu!darwin.sura.net!spool.mu.edu!agate]

In article <CDBqDH.HqF@irvine.com>, adam@irvine.com (Adam Beneschan) writes:
|> 
|> It seems to me that this can be worked around by doing the following.
|> However, I'm having trouble determining from the RM whether this is
|> true.
|> 
|>     generic
|>        type T is range <>;
|>        with function "*" (Left, Right : T) return T is <>;
|>     package GP is
|> 
|>        function Predefined_Mult (Left, Right : T) return T renames "*";
|> 
|>     end GP;
|> 
|> Now, it seems that Predefined_Mult will rename the user-defined "*"
|> (to do modular arithmetic or whatever) instead of the predefined "*".
|> Is this correct?  Please help.

Yes, it is correct. You can work it around this way.

I think the problem is not very severe when applied to the "*" operator.
One can still argue that, for numeric types, it is a good thing to have
the predefined view within generics.

I picked the "*" operator simply to make the example legal Ada 83, but
the point I really wanted to show is that it becomes very bad when applied
to the "=" operator, as in the following example:

package P is

   type T is private;

   function "=" (Left, Right : T) return Boolean;

   ...

end P;

If you redefine "=" for T, you really don't want it to re-emerge inside
generics that you instantiate with P.T as a formal parameter. The
following example shows how bad this can be:

package V_String is

   type Text (Max_Length : Natural) is private;

   function "=" (L, R : Text) return Boolean;

private

   type Text (Max_Length : Natural) is
      record
         current_Length : Natural := 0;
         value : string(1 .. Max_Length);
      end record;

end;

Predefined equality on type Text is erroneous because in most cases it
will compare non-initialized components of Text.Value (I know, erroneous
has changed in Ada 9X). So, you really don't want the predefined version
of "=" to re-emerge inside generics.

--
Mats Weber
e-mail: weber@lglsun.epfl.ch

Re: Ada 9X: Eliminating the re-emergence of predefined operations

[Tucker Taft]

In article <1993Sep14.022914@lglsun.epfl.ch> 
  madmats@lglsun.epfl.ch (Mats Weber) writes:

> . . .
>Now, and this is where the bad things happen, Ada 9X allows "=" to be
>redefined for any type, so that predefined equality can be made to 
>re-emerge just as the predefined "*" does in the above example. I think
>this is very dangerous because an invalid equality can break the
>abstraction for which it applies.

In Ada 9X, predefined operators do not "reemerge" for tagged types, 
or private types whose full type is tagged.  We considered extending
this rule to nontagged types, but there were some subtle technical
and upward-compatibility reasons why that didn't work.  (See below.)

So, the bottom line is that if you want to fully control the
operations on a type, and prevent "reemergence" of predefined
operators in a generic instantiation, then you will have to use 
a tagged type.

Here is the more technical explanation (this might be 
a question on next year's Ada 9X language lawyer bar exam ;-):

  For nontagged types, the rules for overriding operators
  and other inherited (aka "derivable") subprograms are pretty
  lax.  In particular, the subtypes don't have to match,
  and in the case of a procedure, even the parameter modes
  don't have to match (not a problem for operators since they
  are functions).  Here is a particularly pathological example:

      type T is new Integer;
      subtype Positive_T is T range 1..T'Last;
      
      function "+"(A, B : Positive_T) return Positive_T;
        -- This overrides the predefined "+" of T.
        -- Note that the parameter subtypes don't match those
        -- of the predefined "+".

      generic
          type Q is range <>;
      function Double(X : Q) return Q;
      function Double(X : Q) return Q is
      begin
          return X + X;  -- ** --
      end Double;

      function T_Double is new Double(T);

      Z : T := T_Double(-5);

  The "+" appearing on the line marked "-- ** --"
  is the predefined "+" in both Ada 83 and Ada 9x.
  If the predefined "+" did not reemerge, then not only would
  the code generated for T_Double have to call a user-provided
  "+", it would also have to do a constraint check against the range
  of Positive_T before calling the user's "+".
  This could make sharing generics significantly harder and
  less efficient, requiring not only out-of-line calls on every 
  use of an operator, but also the generation of "thunks" to handle 
  parameter subtype mismatches like this one.

  Ada 9X exacerbates this situation a bit, because it supports
  formal derived types, so that the formal type can have
  more than just the predefined operators, it can also
  have a bunch of primitive procedures.  The actual type
  passed against the formal derived type might have overridden
  some of these primitive procedures with procedures having
  different parameter modes, which wouldn't just affect the
  code quality of shared generics, but would affect the legality
  of an instantiation, thereby breaking the generic contract model.

  As it turns out, none of these problems arise with tagged types.
  This is because the parameter subtypes and modes must match
  when overriding a predefined operator or an inherited subprogram. 
  To go along with this, tagged types already have a very handy
  type descriptor (at least in most implementations) which is
  exactly what a shared generic needs to call things like "="
  indirectly.
  
Again, the bottom line is that, if you want to fully control
an abstract data type, which includes defining your own
initialization, finalization, assignment, and equality, 
you will have to use tagged types.  Note that you can declare
a type as (untagged) private and still have the full type
tagged, so you don't need to change the external interface
to the type.
  
One last technical point:

  The reemergence problem doesn't only come up with generics.  It also
  comes up with type composition.  That is, if a component has its
  own equality operator, how does that affect the (predefined) equality
  operator for the composite type.  

  Ada 83 skirts this isssue because the only kinds of types for
  which you can easily define your own "=" are limited, and
  limited types "poison" any composite type that contains them
  (even when they have a user-defined "=") by making the composite
  type limited as well.  So there is no composition of "=" to
  worry about.

  In Ada 9X (as of version RM9X;3.0), the "=" operator for
  a composite type is similar to a generic in that the
  predefined "=" reemerges for untagged components, but
  the user-defined "=" is what counts for tagged components.

  So once you define your own "=" for a tagged type, the
  predefined "=" is gone for good -- it is not visible
  in a generic, nor will it reemerge if you wrap the type
  in a record (even an untagged record) or an array.

Conclusion: user-defined "=" for untagged, nonlimited types is not
as useful as it could be.  It is best used for situations where
the predefined "=" is well-defined, but perhaps not as "generous"
as it could be about when two things are equal.  By analogy to Lisp,
for untagged types the predefined "=" would correspond to the 
Lisp "EQ" whereas the user-defined "=" would correspond to the Lisp "EQUAL."

Note that to change the way assignment works for a type,
it will have to be tagged anyway, so this issue may not
come up that much, because the truly abstract data types
will be tagged for other reasons already.

By the way, one possible alternative approach to the problem,
which would not impose much of a burden on shared generics,
would be to prevent reemergence for the "=" of all record types,
whether tagged or untagged.  One might then argue for disallowing 
overriding the predefined "=" for other types (though
you could still overload it).  These choices are always hard...

>Mats Weber
>Software Engineering Lab
>Swiss Federal Institute of Technology
>CH-1015 Lausanne
>Switzerland
>e-mail: weber@lglsun.epfl.ch

S. Tucker Taft     stt@inmet.com
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138

Re: Ada 9X: Eliminating the re-emergence of predefined operations

[cis.ohio-state.edu!math.ohio-state.edu!darwin.sura.net!news.dfn.de!scsing.switch.ch!epflnews!disuns2.epfl.ch!lglsun!madmats]

In article <CDGv9s.DDK@inmet.camb.inmet.com>, stt@spock.camb.inmet.com (Tucker 
Taft) writes:

|> [much interesting stuff deleted]

|> By the way, one possible alternative approach to the problem,
|> which would not impose much of a burden on shared generics,
|> would be to prevent reemergence for the "=" of all record types,
|> whether tagged or untagged.  One might then argue for disallowing 
|> overriding the predefined "=" for other types (though
|> you could still overload it).  These choices are always hard...

I think your post makes a good argument in favor of forbidding the
redefinition of "=" for non-tagged non-limited types, in order to
preserve the consitency of already written Ada-83 components. I wasn't
aware of the re-emergence in record types, which I think should be
avoided at almost any price.

Well, in fact, I would take the approach that is hardest on
implementors with respect to sharing code in instances, but too many
people would disagree...

|> S. Tucker Taft     stt@inmet.com
|> Ada 9X Mapping/Revision Team
|> Intermetrics, Inc.
|> Cambridge, MA  02138

-- 
Mats Weber
e-mail: mats.weber@lglsun.epfl.ch