Dispatching and generics - language lawyer question

Dispatching and generics - language lawyer question

[Adam Beneschan]

I have a couple questions about what's supposed to happen when a
generic is instantiated with a class-wide type as an actual type.  I'm
hoping that someone who really understands the intricacies of the
language will be kind enough to answer, and provide chapter and verse
from the RM to explain the correct answer.

(1) What is the correct output of the program below?

(2) What would be the correct output if "private" in line [A] is
changed to
    "tagged private"?

I'm pretty sure the answer to (1) is FALSE, since the "=" on line [B]
in the instance denotes the predefined "=" declared for T1 in the
generic, and not the "=" "defined" for the class-wide type, by
8.3(13).  I'm less clear about the answer to (2).  Here, the "="
implicitly declared for T1 is a dispatching operation, and thus should
dispatch if a controlling operand is of a class-wide type (3.9.2(5)),
but it's not clear to me whether the operands in this case are treated
as if they were of the formal type (which is not class-wide) or of the
actual type (which is class-wide).

Thanks in advance for your help.

				-- Adam




generic
    type T1(<>) is private;            -- [A]
package Pak1 is
    type T1_Access is access T1;
    function Check_Equal (X, Y : T1_Access) return boolean;
end Pak1;    

package body Pak1 is
    function Check_Equal (X, Y : T1_Access) return boolean is
    begin
        return X.all = Y.all;          -- [B]
    end Check_Equal;
end Pak1;    

package Pak2 is
    type Root_Type is tagged record
        F1 : Integer;
    end record;
end Pak2;

with Pak2;
package Pak3 is
    type Child is new Pak2.Root_Type with record
        F2 : Integer;
    end record;
    function "=" (Left, Right : Child) return boolean;
end Pak3;    
        
package body Pak3 is
    function "=" (Left, Right : Child) return boolean is
    begin
        return Left.F1 = Right.F1 and then 
               abs Left.F2 = abs Right.F2;
    end "=";
end Pak3;    
        

with Pak1;
with Pak2;
with Pak3;
with Text_IO;
procedure Test62 is
    package Pak1_Inst is new Pak1 (Pak2.Root_Type'Class);
    A1 : Pak1_Inst.T1_Access;
    A2 : Pak1_Inst.T1_Access;
    B  : Boolean;
begin
    A1 := new Pak3.Child' (F1 => 4, F2 => 6);
    A2 := new Pak3.Child' (F1 => 4, F2 => -6);
    B := Pak1_Inst.Check_Equal (A1, A2);
    Text_IO.Put_Line (Boolean'Image (B));
end Test62;

Re: Dispatching and generics - language lawyer question

[Stephen Leake]

adam@irvine.com (Adam Beneschan) writes:

> I have a couple questions about what's supposed to happen when a
> generic is instantiated with a class-wide type as an actual type.  I'm
> hoping that someone who really understands the intricacies of the
> language will be kind enough to answer, and provide chapter and verse
> from the RM to explain the correct answer.
> 
> (1) What is the correct output of the program below?

GNAT 3.15a1 says "TRUE". Not a definitive answer, but possibly helpful :).

> (2) What would be the correct output if "private" in line [A] is
> changed to "tagged private"?

GNAT 3.15a1 also says "TRUE" for this. 

> I'm pretty sure the answer to (1) is FALSE, since the "=" on line
> [B] in the instance denotes the predefined "=" declared for T1 in
> the generic, and not the "=" "defined" for the class-wide type, by
> 8.3(13). 

I think the controlling paragraph is 12.5.1 (21). I think the behavior
exhibited by GNAT 3.15a1 agrees with this. Note that both variations
of your formal type declaration are "formal private types"; the
presence of "tagged" does not matter here. There is different behavior
for a "formal derived type", which is indicated by the keyword "new".

There is a problem with "reemergence" of predefined operators for
generic formal types, but I don't have an example of when it occurs. I
didn't see a discussion of this in Cohen's "Ada as a Second Language",
either. Nor in the Rationale. But maybe I just didn't look hard
enough.

You might try reading the Rationale for generics; it has some good
stuff in it. It's online at www.adapower.com; click the "resources"
button (I hate html frames!).

-- 
-- Stephe

Re: Dispatching and generics - language lawyer question

[Stephen Leake]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> There is a problem with "reemergence" of predefined operators for
> generic formal types, but I don't have an example of when it occurs. I
> didn't see a discussion of this in Cohen's "Ada as a Second Language",
> either. Nor in the Rationale. But maybe I just didn't look hard
> enough.

Based on a hint from Christoph Grein, I wrote the following code to
demonstrate the "reemergence problem". It occurs for non-tagged types;
for tagged types, Ada 95 fixed the problem.

 
with Ada.Text_IO; use Ada.Text_IO;
procedure Reemerge
is
   type X is new Integer;
   function "=" (L, R: X) return Boolean;  -- redefine

   function "=" (L, R: X) return Boolean
   is begin
      Put_Line ("in redefined ""="" (X)");
      return Integer (L + R) = 0;
   end "=";

begin
Type_Compose :
    declare
       type Y is record
          C : X;
       end record;

       A : Y := (C => 1);
       B : Y := (C => 1);
    begin
       Put_Line ("Type_Compose");
       Put_Line ("A = B => " & Boolean'Image (A = B));
       -- Here predefined "=" on component C is used, not the
       -- equality redefined above

       New_Line;
       Put_Line ("A.C = B.C => " & Boolean'Image (A.C = B.C));
       -- Here the equality redefined above is used.
    end Type_Compose;

    New_Line;

Generic_Reemerge:
    declare

       generic
          type T is private;
       procedure Compare (L, R : in T);
       -- Print a message with the result of "=" (L, R).

       procedure Compare (L, R : in T)
       is begin
          Put_Line ("L = R => " & Boolean'Image (L = R));
       end Compare;

       procedure Compare_X is new Compare (X);

    begin
       Put_Line ("Generic_Reemerge");
       Compare_X (1, 1);
    end Generic_Reemerge;

    New_Line;
Generic_Correct:
    declare

       generic
          type T is private;
          with function "=" (L, R : in T) return Boolean is <>;
       procedure Compare (L, R : in T);
       -- Print a message with the result of "=" (L, R).

       procedure Compare (L, R : in T)
       is begin
          Put_Line ("L = R => " & Boolean'Image (L = R));
       end Compare;

       procedure Compare_X is new Compare (X);

    begin
       Put_Line ("Generic_Correct");
       Compare_X (1, 1);
    end Generic_Correct;

    New_Line;
Generic_Tagged:
    declare

       package Tagged_Type is
          type Y is tagged record
             Z : Integer;
          end record;

          function "=" (L, R : in Y) return Boolean;
       end Tagged_Type;

       package body Tagged_Type is

          function "=" (L, R : in Y) return Boolean
          is begin
             return L.Z + R.Z = 0;
          end "=";
       end Tagged_Type;

       generic
          type T is private;
       procedure Compare (L, R : in T);
       -- Print a message with the result of "=" (L, R).

       procedure Compare (L, R : in T)
       is begin
          Put_Line ("L = R => " & Boolean'Image (L = R));
       end Compare;

       procedure Compare_Y is new Compare (Tagged_Type.Y);

    begin
       Put_Line ("Generic_Tagged");
       Compare_Y ((Z => 1), (Z => 1));
    end Generic_Tagged;

end Reemerge;

-- 
-- Stephe

Re: Dispatching and generics - language lawyer question

[Grein, Christoph]

> There is a problem with "reemergence" of predefined operators ...

For untagged types, _redefined_ equality does not correctly compose and 
_predefined_ equality reemerges in generics if not properly transferred by a 
formal parameter:

  type X is something;
  function "=" (L, R: X) return Boolean;  -- redefine

  type Y is record
    C: X;
  end record;

  A, B: Y;
  L: Boolean := A = B;  -- here predefined "=" on component C is used, not the
                        -- equality redefined above

  generic
    type T is private;
    --with function "=" (L, R: T) return Boolean is <>;
  package P is ...

  package P_on_X is new P (X);  -- here also predefined "=" on X is used,
                                -- not the equality redefined above

You have to uncomment the generic parameter function to prevent reemergence.

This whole astonishing rule has been introduced because of compatibility with 
Ada 83 (note there were no tagged types in Ada 83 so there reemergence could 
safely be avoided).

In Ada 83, it was not possible to redefine "=" without using a trick (I do not 
remember the exact way to do it, I never did this; you have to use generics with 
the a limited private formal type). When you used this trick to redefine 
equality, also the predefined equality reemerged as in the cases above. Thus for 
compatibility, we have this rule in Ada 95.

Re: Dispatching and generics - language lawyer question

[Robert A Duff]

"Grein, Christoph" <christoph.grein@eurocopter.com> writes:

> For untagged types, _redefined_ equality does not correctly compose and 
> _predefined_ equality reemerges in generics if not properly transferred by a 
> formal parameter:

What do you think the rule *should* be?  It does seem bad that
predefined "=" reemerges.  And of course the rule for "/=" should be the
same as for "=".

What about "<"?  Should the predefined one reemerge?  If a generic
sorting package calls the primitive "<" of the generic formal type,
it would seem desirable to use the user-defined one, rather than the
predefined one.

But what about "+" and "mod" and so forth?  Package Text_IO.Integer_IO
probably uses the predefined "mod" to format the number as a string.
But the *spec* of that package doesn't say that -- it just says the
string is formatted according to some rules.  If the predefined "mod"
did *not* reemerge, then a user-defined "mod" operator would break
Text_IO.Integer_IO.  You may say, "tough luck; that's the programmer's
fault".  But how should the semantics of Integer_IO be defined in the
RM?  Surely the use of "mod" there is an implementation detail.

- Bob

Re: Dispatching and generics - language lawyer question

[Ben Brosgol]

> > For untagged types, _redefined_ equality does not correctly compose and
> > _predefined_ equality reemerges in generics if not properly transferred
by a
> > formal parameter:
>
> But what about "+" and "mod" and so forth?  Package Text_IO.Integer_IO
> probably uses the predefined "mod" to format the number as a string.
> But the *spec* of that package doesn't say that -- it just says the
> string is formatted according to some rules.  If the predefined "mod"
> did *not* reemerge, then a user-defined "mod" operator would break
> Text_IO.Integer_IO.  You may say, "tough luck; that's the programmer's
> fault".  But how should the semantics of Integer_IO be defined in the
> RM?  Surely the use of "mod" there is an implementation detail.

As another interesting case, suppose that you declare an integer type T with
"mod" specified as abstract.  If "mod" on the formal type is invoked from
the generic body, then either the instantiation Ada.Text_IO.Integer_IO(T)
would need to be rejected (a rather flagrant violation of the "contract
model") or else the predefined "mod" would need to reemerge.

Re: Dispatching and generics - language lawyer question

[Robert A Duff]

Hi, Ben.

"Ben Brosgol" <brosgol@world.std.com> writes:

> As another interesting case, suppose that you declare an integer type T with
> "mod" specified as abstract.  If "mod" on the formal type is invoked from
> the generic body, then either the instantiation Ada.Text_IO.Integer_IO(T)
> would need to be rejected (a rather flagrant violation of the "contract
> model") or else the predefined "mod" would need to reemerge.

Yes, that *is* an interesting case, which I hadn't thought of.

Note that for tagged types, the generic declares whether it wants to
accept types with abstract primitive ops, so the instantiation can be
rejected without violating the contract model.  It's uncomfortable that
there are misc. rules like this that distinguish tagged types from
untagged types.  Could we do better if designing the language from
scratch?  (I think many such rules are needed for compatibility with Ada
83.)  I'm not sure what the right answer is in this case.

I'm disappointed that nobody answered my previous question -- what
should the rules about predefined operators in generics be?  I don't
like the current Ada rules (which require reemergence of the "wrong"
operator), but the alternatives are uncomfortable in various ways.
Christoph Grein, or anybody else want to comment?

Here's an interesting case: a generic Sort routine, that takes "<" as a
parameter.  (Or it could be called "Less_Than" -- it doesn't matter what
it's called, or whether it's an operator symbol.)  The Sort routine
might require that the "<" behave in certain ways (like if A<B and B<C
both return True, then A<C should always return True).  Is there any way
to specify that (other than via comments)?  Is there some way to design
the language so that the generic Sort could formally require such
properties of "<"?

This is similar to the Text_IO.Integer_IO example, where the code wants
to assume that "mod" behaves according to some mathematical rules.
(I'm not even sure how to state those rules precisely.)

- Bob

Re: Dispatching and generics - language lawyer question

[Dmitry A.Kazakov]

Robert A Duff wrote:

> "Ben Brosgol" <brosgol@world.std.com> writes:
> 
>> As another interesting case, suppose that you declare an integer type T
>> with
>> "mod" specified as abstract.  If "mod" on the formal type is invoked from
>> the generic body, then either the instantiation Ada.Text_IO.Integer_IO(T)
>> would need to be rejected (a rather flagrant violation of the "contract
>> model") or else the predefined "mod" would need to reemerge.
> 
> Yes, that *is* an interesting case, which I hadn't thought of.
> 
> Note that for tagged types, the generic declares whether it wants to
> accept types with abstract primitive ops, so the instantiation can be
> rejected without violating the contract model.  It's uncomfortable that
> there are misc. rules like this that distinguish tagged types from
> untagged types.  Could we do better if designing the language from
> scratch?  (I think many such rules are needed for compatibility with Ada
> 83.)  I'm not sure what the right answer is in this case.

[away from Ada 95] There should be only tagged types and no untagged ones. 
Then I suppose the formal derived types will do the whole work, because the 
set of all available operations will be defined by the root type. All types 
tagged means only that T'Class exists for all but class-wide types. The tag 
should be kept in the instances of T'Class and class-wide pointers, but not 
in the values of T, so no performance hit when objects are specific.

> I'm disappointed that nobody answered my previous question -- what
> should the rules about predefined operators in generics be?  I don't
> like the current Ada rules (which require reemergence of the "wrong"
> operator), but the alternatives are uncomfortable in various ways.
> Christoph Grein, or anybody else want to comment?
> 
> Here's an interesting case: a generic Sort routine, that takes "<" as a
> parameter.  (Or it could be called "Less_Than" -- it doesn't matter what
> it's called, or whether it's an operator symbol.)  The Sort routine
> might require that the "<" behave in certain ways (like if A<B and B<C
> both return True, then A<C should always return True).  Is there any way
> to specify that (other than via comments)?  Is there some way to design
> the language so that the generic Sort could formally require such
> properties of "<"?

[far away form Ada 95] You should simply have different root types. 
Transitive_Ordered should be a[!] root type for "all" types with transitive 
"<". "All" means the types you want to pass the actual parameter. Of course 
then the language should allow creating supertypes on-fly, because one 
cannot foresee all possible root types like Ada tries with its 
classification of formal types. Let Integer is not a descendant of 
Transitive_Ordered. Then one could create a "proxy" type which is 
simultaneously a supertype of Integer and a subtype of Transitive_Ordered. 
[The compiler should check that "<" be implemented.] So Integer would 
become a subtype Transitive_Ordered in the given context and thus could be 
used as an actual parameter of the generic. This of course would require MI 
and dynamically maintained dispatch tables.

> This is similar to the Text_IO.Integer_IO example, where the code wants
> to assume that "mod" behaves according to some mathematical rules.
> (I'm not even sure how to state those rules precisely.)

Well, this is about LSP. No one can enforce semantics of an operation. 
However, the difference between what we have in Ada now and what I would 
like to have, is that presently operations of a private formal type are 
matched by their profiles. This warranties absolutely nothing. With generic 
derived types, you would have a subtype relation which assumes a 
meaningfull implementation of the root type operations.

-- 
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Dispatching and generics - language lawyer question

[Robert A Duff]

Dmitry A.Kazakov <mailbox@dmitry-kazakov.de> writes:

> [away from Ada 95] There should be only tagged types and no untagged ones. 
> Then I suppose the formal derived types will do the whole work, because the 
> set of all available operations will be defined by the root type. All types 
> tagged means only that T'Class exists for all but class-wide types. The tag 
> should be kept in the instances of T'Class and class-wide pointers, but not 
> in the values of T, so no performance hit when objects are specific.

This is a reasonable idea (not new -- I and probably others have thought
of it before).

As you imply, there are two ways to implement tags: (1) Store the tag
with each object.  Then an access value (or a pass-by-reference
parameter) can be represented as the address of the object.  Or (2),
do not store the tag with each object, but gin it up when necessary.
This requires access values and parameters to be a pair -- the tag, plus
the address of the object.  When you do X'Access, the compiler creates
the pair.

Neither method is uniformly better: there are some programs that will be
more efficient with method (1), and some more efficient with method (2).
This indicates that the user should have the option.  I would suggest
the default (in this hypothetical language) should be (2), and a
per-type pragma could request (1) for that type and its descendants.
This preserves the Bauer Principle -- if you never say 'Class, you never
have any overhead for storing or manipulating tags at run time.

Of course, having options like that complicates compilers.

For most of the Ada 9X design, either (1) or (2) were feasible (for
tagged types).  However, a last-minute change to the language made (2)
infeasible.  Namely, the fact that all tagged parameters are aliased.

As far as I know, all existing compilers use (1).

Note that the distinction between (1) and (2) is analogous to the
compiler storing array bounds with the array, or with pointers to the
array.  Neither one is uniformly better.  I believe GNAT allows a user
choice, and I think all other compilers store bounds with the array
(analogous to (1)).

> > I'm disappointed that nobody answered my previous question -- what
> > should the rules about predefined operators in generics be?  I don't
> > like the current Ada rules (which require reemergence of the "wrong"
> > operator), but the alternatives are uncomfortable in various ways.
> > Christoph Grein, or anybody else want to comment?
> > 
> > Here's an interesting case: a generic Sort routine, that takes "<" as a
> > parameter.  (Or it could be called "Less_Than" -- it doesn't matter what
> > it's called, or whether it's an operator symbol.)  The Sort routine
> > might require that the "<" behave in certain ways (like if A<B and B<C
> > both return True, then A<C should always return True).  Is there any way
> > to specify that (other than via comments)?  Is there some way to design
> > the language so that the generic Sort could formally require such
> > properties of "<"?
> 
> [far away form Ada 95] You should simply have different root types. 
> Transitive_Ordered should be a[!] root type for "all" types with transitive 
> "<". "All" means the types you want to pass the actual parameter. Of course 
> then the language should allow creating supertypes on-fly, because one 
> cannot foresee all possible root types like Ada tries with its 
> classification of formal types. Let Integer is not a descendant of 
> Transitive_Ordered. Then one could create a "proxy" type which is 
> simultaneously a supertype of Integer and a subtype of Transitive_Ordered. 
> [The compiler should check that "<" be implemented.] So Integer would 
> become a subtype Transitive_Ordered in the given context and thus could be 
> used as an actual parameter of the generic. This of course would require MI 
> and dynamically maintained dispatch tables.

Again, good ideas.  But they don't solve the problem I was thinking of.

By the way, I don't see why you need dynamically maintained dispatch
tables.  To me, "on the fly" means "somewhere later in the code" --
i.e. in some module other than where the type is first declared.
That need not imply "at run time", I think.

The notion of dynamically maintained dispatch tables scares me: I hope
that "<" on type T does not dispatch to different subprogram bodies
at different times (for the same type tag)!

It seems like adding new operations to a type should only be allowed at
the same nesting level as the original type declaration.  I shudder to
think of the run-time overhead of adding an operation in a recursive
procedure.  ("Adding new op" is essentially the same thing as "adding a
new parent type", here.)

But anyway, as you explain below, none of this solves the problem.  The
compiler checks that "<" exists with the right parameter types, but that
doesn't *prove* its transitive (whether or not the Transitive_Ordered
idea is used).

> > This is similar to the Text_IO.Integer_IO example, where the code wants
> > to assume that "mod" behaves according to some mathematical rules.
> > (I'm not even sure how to state those rules precisely.)
> 
> Well, this is about LSP. No one can enforce semantics of an operation. 

Exactly my point.  For *this* issue, all of the above good ideas are
equivalent to simply changing the language so that predefined operators
do not reemerge.

> However, the difference between what we have in Ada now and what I would 
> like to have, is that presently operations of a private formal type are 
> matched by their profiles. This warranties absolutely nothing.

Right, it warranties nothing.

>... With generic 
> derived types, you would have a subtype relation which assumes a 
> meaningfull implementation of the root type operations.

But this also warranties nothing.  One must "assume" that operations do
what they're supposed to do; the compiler can't prove it.  That's no
different from the current case, where "mod" could be redefined to do
something weird, thus breaking Text_IO.Integer_IO (I mean, if we changed
the rules to avoid the reemergence).

You still haven't answered my question: What should the RM say that
Integer_IO.Put does?  (Or if it were user-defined, what should the
comment on its spec say?)  I don't care whether the language removes
reemergence, or all your nice ideas above, including about formal
derived types, are adopted -- either way, it's difficult to define the
semantics of Put if it might be calling some user-defined version of
"mod".

The current RM doesn't even mention that Put calls "mod".  In fact,
there are various ways of implementing Put, some of which call "mod" and
some of which don't.  Surely, Put calling "mod" is an implementation
detail?

- Bob

Re: Dispatching and generics - language lawyer question

[Dmitry A.Kazakov]

Robert A Duff wrote:

> Dmitry A.Kazakov <mailbox@dmitry-kazakov.de> writes:
> 
>> [away from Ada 95] There should be only tagged types and no untagged
>> [ones.
>> Then I suppose the formal derived types will do the whole work, because
>> the set of all available operations will be defined by the root type. All
>> types tagged means only that T'Class exists for all but class-wide types.
>> The tag should be kept in the instances of T'Class and class-wide
>> pointers, but not in the values of T, so no performance hit when objects
>> are specific.
> 
> This is a reasonable idea (not new -- I and probably others have thought
> of it before).
> 
> As you imply, there are two ways to implement tags: (1) Store the tag
> with each object.  Then an access value (or a pass-by-reference
> parameter) can be represented as the address of the object.  Or (2),
> do not store the tag with each object, but gin it up when necessary.
> This requires access values and parameters to be a pair -- the tag, plus
> the address of the object.  When you do X'Access, the compiler creates
> the pair.
> 
> Neither method is uniformly better: there are some programs that will be
> more efficient with method (1), and some more efficient with method (2).
> This indicates that the user should have the option.  I would suggest
> the default (in this hypothetical language) should be (2), and a
> per-type pragma could request (1) for that type and its descendants.
> This preserves the Bauer Principle -- if you never say 'Class, you never
> have any overhead for storing or manipulating tags at run time.
> 
> Of course, having options like that complicates compilers.

I think that (1) would cause many problems with MI. When tag is a part of 
the value and then view conversions are problematic.

> For most of the Ada 9X design, either (1) or (2) were feasible (for
> tagged types).  However, a last-minute change to the language made (2)
> infeasible.  Namely, the fact that all tagged parameters are aliased.

There is also redispatch which is IMO incompatible with (1). I think 
redispatch must be removed, because when object identification is really 
necessary (to redispatch) one could use a solution similar to J.-P. Rosen 
trick.

> As far as I know, all existing compilers use (1).
> 
> Note that the distinction between (1) and (2) is analogous to the
> compiler storing array bounds with the array, or with pointers to the
> array.  Neither one is uniformly better.  I believe GNAT allows a user
> choice, and I think all other compilers store bounds with the array
> (analogous to (1)).

Yes. Same with discriminants. I have only a vague idea, that there should 
be way to separate all things like that from values. The goal is of course 
to make arrays, strings etc user-defined types without additional overhead. 
Then of course you should be able to derive from an abstract array and 
provide an implementation which is internally not an array at all. So the 
client will never know.

>> > I'm disappointed that nobody answered my previous question -- what
>> > should the rules about predefined operators in generics be?  I don't
>> > like the current Ada rules (which require reemergence of the "wrong"
>> > operator), but the alternatives are uncomfortable in various ways.
>> > Christoph Grein, or anybody else want to comment?
>> > 
>> > Here's an interesting case: a generic Sort routine, that takes "<" as a
>> > parameter.  (Or it could be called "Less_Than" -- it doesn't matter
>> > what
>> > it's called, or whether it's an operator symbol.)  The Sort routine
>> > might require that the "<" behave in certain ways (like if A<B and B<C
>> > both return True, then A<C should always return True).  Is there any
>> > way
>> > to specify that (other than via comments)?  Is there some way to design
>> > the language so that the generic Sort could formally require such
>> > properties of "<"?
>> 
>> [far away form Ada 95] You should simply have different root types.
>> Transitive_Ordered should be a[!] root type for "all" types with
>> transitive "<". "All" means the types you want to pass the actual
>> parameter. Of course then the language should allow creating supertypes
>> on-fly, because one cannot foresee all possible root types like Ada tries
>> with its classification of formal types. Let Integer is not a descendant
>> of Transitive_Ordered. Then one could create a "proxy" type which is
>> simultaneously a supertype of Integer and a subtype of
>> Transitive_Ordered.
>> [The compiler should check that "<" be implemented.] So Integer would
>> become a subtype Transitive_Ordered in the given context and thus could
>> be used as an actual parameter of the generic. This of course would
>> require MI and dynamically maintained dispatch tables.
> 
> Again, good ideas.  But they don't solve the problem I was thinking of.
> 
> By the way, I don't see why you need dynamically maintained dispatch
> tables.  To me, "on the fly" means "somewhere later in the code" --
> i.e. in some module other than where the type is first declared.
> That need not imply "at run time", I think.
> 
> The notion of dynamically maintained dispatch tables scares me: I hope
> that "<" on type T does not dispatch to different subprogram bodies
> at different times (for the same type tag)!
>
> It seems like adding new operations to a type should only be allowed at
> the same nesting level as the original type declaration.  I shudder to
> think of the run-time overhead of adding an operation in a recursive
> procedure.  ("Adding new op" is essentially the same thing as "adding a
> new parent type", here.)

Yes, I also do not think that one could override in any context without a 
heavy penalty. I think if that would be allowed then no expression would be 
static when used in a subprogram. No, I meant another thing. If a derived 
type is created in some nested context and overrides, say "<", then the 
dispatching table of "<" should be modified once when the type is 
elaborated and restored when the context is finalized.

> But anyway, as you explain below, none of this solves the problem.  The
> compiler checks that "<" exists with the right parameter types, but that
> doesn't *prove* its transitive (whether or not the Transitive_Ordered
> idea is used).
> 
>> > This is similar to the Text_IO.Integer_IO example, where the code wants
>> > to assume that "mod" behaves according to some mathematical rules.
>> > (I'm not even sure how to state those rules precisely.)
>> 
>> Well, this is about LSP. No one can enforce semantics of an operation.
> 
> Exactly my point.  For *this* issue, all of the above good ideas are
> equivalent to simply changing the language so that predefined operators
> do not reemerge.

One should distinguish overloading and overriding. If ">" is overridden 
then a reemergence would clearly violate LSP. On contrary in the case of 
overloading reemergence would enforce LSP. So logically, the reemergency 
rule is OK so far the type is untagged [but there should be no such (:-))]. 
But look at this:

package Some_Type is
   type X is tagged null record;
   function "<" (A, B : X) return Boolean;
end Some_Type;

package body Some_Type is
   function "<" (A, B : X) return Boolean is
   begin
      return True;
   end "<";
end Some_Type;

with Ada.Text_IO; use Ada.Text_IO;
with Some_Type;   use Some_Type;

procedure Test is
   XX : X;

   generic procedure Compare (A : X);

   procedure Compare (A : X) is
   begin
      if A < A then
         Put_Line ("Reemerged");
      else
         Put_Line ("Overloaded");
      end if;
   end Compare;

   procedure G1 is new Compare;
   procedure N1 (A : X) is
   begin
      if A < A then
         Put_Line ("Reemerged");
      else
         Put_Line ("Overloaded");
      end if;
   end N1;

   function "<" (A, B : X) return Boolean is
   begin
      return False;
   end "<";

   procedure G2 is new Compare;
   procedure N2 (A : X) is
   begin
      if A < A then
         Put_Line ("Reemerged");
      else
         Put_Line ("Overloaded");
      end if;
   end N2;

begin
   G1 (XX); -- Reemerged
   N1 (XX); -- Reemerged
   G2 (XX); -- Reemerged
   N2 (XX); -- Overloaded
end Test;

Is THIS OK? I do not think so. The first thought is to prohibit overloading 
of primitive operations.

>> However, the difference between what we have in Ada now and what I would
>> like to have, is that presently operations of a private formal type are
>> matched by their profiles. This warranties absolutely nothing.
> 
> Right, it warranties nothing.
> 
>>... With generic
>> derived types, you would have a subtype relation which assumes a
>> meaningfull implementation of the root type operations.
> 
> But this also warranties nothing.  One must "assume" that operations do
> what they're supposed to do; the compiler can't prove it.

To some extent it could. Let we introduce, as many proposed, pre-, 
post-conditions and invariants. Then some of requirements on operations of 
Transitive_Order could be expressed in their terms. Then (do not ask me 
how) the compiler could check that a pre-condition of a derived type 
declared to be a "strong subtype" is not stronger than it was for the base 
type etc.

This will still warranty nothing, but it is much like 
Unchecked_Deallocation. How do you warranty that it is not called twice? 
One thing is when the compiler silently uses ">", just because it has a 
right name and profile. Another thing is when the compiler says: sorry guy, 
">" is abstract, please, override it, even if the overriding would be a 
simple renaming, even if some idiot would call a TRAP instruction from the 
overriding.

> That's no
> different from the current case, where "mod" could be redefined to do
> something weird, thus breaking Text_IO.Integer_IO (I mean, if we changed
> the rules to avoid the reemergence).
> 
> You still haven't answered my question: What should the RM say that
> Integer_IO.Put does?  (Or if it were user-defined, what should the
> comment on its spec say?)  I don't care whether the language removes
> reemergence, or all your nice ideas above, including about formal
> derived types, are adopted -- either way, it's difficult to define the
> semantics of Put if it might be calling some user-defined version of
> "mod".

The precondition of Integer_IO is that the generic parameter is of some 
integer type. It means that all what is said about integer types in RM 
should be true for it. RM could say that for an integer type for any x and 
any y/=0 there are d and r of the type that x=y*d+r and etc (*). There is a 
related question: how to make preconditions as weak as possible? 
Definitely, Put does not need *all* integer operations. How to express 
that? To refine further the type hierarchy like with Transitive_Order would 
be a heavy burden for a programmer, because then he/she should instantiate 
each procedure of the package separately depending on what subset of 
operations (subtype) the procedure require.

(*) You can always write in RM: "it is a bounded error if" and a draconian 
requirement follows (:-))

Also any polymorphic solution (generic or class-wide) may face 
substitutability problems because of overriding. Thus for simple things 
like Integer_IO it could be better to have a non-polymorphic one. I mean 
user-defined type conversions and subtyping through conversions. In fact we 
do it manually on daily basis when write something like:

type X is range ...;
A : X;

Put (Integer'Image (Integer (A)));

Let we have some integer type Int_Out which cannot have instances 
(variables). Then let's declare Put on it. Then if I would like to make an 
output for X, I would declare X a subtype of IO_Int by providing a 
conversion X->Int_Out. The compiler would apply the conversion should I 
write Put (X). This suffers no substitutability problems (**), because Put 
will always deal with an Int_Out.

(**) If Int_Out is capable to represent all values of the derived type.

> The current RM doesn't even mention that Put calls "mod".  In fact,
> there are various ways of implementing Put, some of which call "mod" and
> some of which don't.  Surely, Put calling "mod" is an implementation
> detail?

Yes. Yet it is consistent, because what is not an implementation detail is 
that Put *may* call "mod" expecting a meaningfull behaviour from it. 

-- 
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Dispatching and generics - language lawyer question

[Hyman Rosen]

Dmitry A.Kazakov wrote:
> I think that (1) would cause many problems with MI. When tag is a part of 
> the value and then view conversions are problematic.
> There is also redispatch which is IMO incompatible with (1). I think 
> redispatch must be removed, because when object identification is really 
> necessary (to redispatch) one could use a solution similar to J.-P. Rosen 
> trick.

C++ uses (1), storing multiple "tags" (actually, virtual
table pointers) in the object if necessary, and supports
redispatch just fine. The scheme used by the new version
of g++ is described at
<http://www.codesourcery.com/cxx-abi/abi.html>.

I doubt that the language designers, assuming they do add
MI to Ada, would be so silly as to deliberately choose to
implement it in a way that could never be compatible with
C++ object layout.

Re: Dispatching and generics - language lawyer question

[Dmitry A.Kazakov]

Hyman Rosen wrote:

> Dmitry A.Kazakov wrote:
>> I think that (1) would cause many problems with MI. When tag is a part of
>> the value and then view conversions are problematic.
>> There is also redispatch which is IMO incompatible with (1). I think
>> redispatch must be removed, because when object identification is really
>> necessary (to redispatch) one could use a solution similar to J.-P. Rosen
>> trick.
> 
> C++ uses (1), storing multiple "tags" (actually, virtual
> table pointers) in the object if necessary, and supports
> redispatch just fine. The scheme used by the new version
> of g++ is described at
> <http://www.codesourcery.com/cxx-abi/abi.html>.

So in C++ int will never be a class, worse to C++.
 
> I doubt that the language designers, assuming they do add
> MI to Ada, would be so silly as to deliberately choose to
> implement it in a way that could never be compatible with
> C++ object layout.

I do not think that to repeat others faults is a good idea. As long as we 
have no C++ operating system APIs (shudder), I doubt that it is worth 
effors to keep objects Ada and C++ compatible. To communicate with C++ one 
could declare a simple record type with fields reserved for places where 
vtptrs are.

-- 
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Dispatching and generics - language lawyer question

[Hyman Rosen]

Dmitry A.Kazakov wrote:
> So in C++ int will never be a class, worse to C++.

It's never going be a class in Ada either.

 > I doubt that it is worth effors to keep objects Ada
 > and C++ compatible.

I think that the GNAT creators would disagree with you.
As far as I know, they make corresponding Ada and C++
objects layout compatible. Perhaps one of them will
explain why.

Re: Dispatching and generics - language lawyer question

[Stephen Leake]

Hyman Rosen <hyrosen@mail.com> writes:

> Dmitry A.Kazakov wrote:
> > So in C++ int will never be a class, worse to C++.
> 
> It's never going be a class in Ada either.
> 
>  > I doubt that it is worth effors to keep objects Ada
>  > and C++ compatible.
> 
> I think that the GNAT creators would disagree with you.
> As far as I know, they make corresponding Ada and C++
> objects layout compatible. Perhaps one of them will
> explain why.

It allows you to derive a new Ada type from a C++ class, and vice
versa. Then a dispatching call from a C++ routine can call an Ada
body, and vice versa.

It allows _full_ mixed language programming with Ada and C++. This is
a _very_ good feature. The alternative requires a C interface between
C++ and Ada, which is simply not as good.

-- 
-- Stephe

Re: Dispatching and generics - language lawyer question

[Warren W. Gay VE3WWG]

Stephen Leake wrote:
> Hyman Rosen <hyrosen@mail.com> writes:
>>Dmitry A.Kazakov wrote:
>>>So in C++ int will never be a class, worse to C++.
>>
>>It's never going be a class in Ada either.
>>
>> > I doubt that it is worth effors to keep objects Ada
>> > and C++ compatible.
>>
>>I think that the GNAT creators would disagree with you.
>>As far as I know, they make corresponding Ada and C++
>>objects layout compatible. Perhaps one of them will
>>explain why.
> 
> It allows you to derive a new Ada type from a C++ class, and vice
> versa. Then a dispatching call from a C++ routine can call an Ada
> body, and vice versa.
> 
> It allows _full_ mixed language programming with Ada and C++. This is
> a _very_ good feature. The alternative requires a C interface between
> C++ and Ada, which is simply not as good.

At least at the level of GNAT 3.13p, the C++ support was not quite
"full". To the best of my knowledge, the C++ destructors did
not work when the object went out of scope within Ada code.

You could call the destructor manually, but this of course is
not as convenient as the Ada.Finalization.Controlled type of
object that GNAT does support finalization for.

So in this respect, unless they have fixed this in later
versions (I did not check), the C++ level of support is not yet
"full" in GNAT.

Warren.

Re: Dispatching and generics - language lawyer question

[Dmitry A. Kazakov]

On Fri, 02 Aug 2002 11:49:34 -0400, Hyman Rosen <hyrosen@mail.com>
wrote:

>Dmitry A.Kazakov wrote:
>> So in C++ int will never be a class, worse to C++.
>
>It's never going be a class in Ada either.

It was rather about an imaginary successor of Ada, which should not be
Ada++ in the sense of C++ = "C with classes". At some point one will
have to drive the line.

> > I doubt that it is worth effors to keep objects Ada
> > and C++ compatible.
>
>I think that the GNAT creators would disagree with you.
>As far as I know, they make corresponding Ada and C++
>objects layout compatible. Perhaps one of them will
>explain why.

Maybe because they get it more or less free. (:-))

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Dispatching and generics - language lawyer question

[Robert Dewar]

Hyman Rosen <hyrosen@mail.com> wrote in message news:<1028303374.179416@master.nyc.kbcfp.com>...

> I think that the GNAT creators would disagree with you.
> As far as I know, they make corresponding Ada and C++
> objects layout compatible. Perhaps one of them will
> explain why.


That's a bit confused. The layout of tagged types in
GNAT is defined by the body of the run-time unit Ada.Tags.
Whether this corresponds or not to some particular C++
compiler depends on whether you tailor Ada.Tags
appropriately. 

In practice, the only significant use of the tight C++
binding of objects and tagged types in GNAT was by SGI
for some of their graphics packages, otherwise I don't
think the feature has been used. 

(there are lots of things in GNAT that are very interesting
but don't get used, e.g. the entire Information Systems
Annex :-)

Re: Dispatching and generics - language lawyer question

[Randy Brukardt]

Robert A Duff wrote in message ...
Bon Duff wrote:

>Note that the distinction between (1) and (2) is analogous to the
>compiler storing array bounds with the array, or with pointers to the
>array.  Neither one is uniformly better.  I believe GNAT allows a user
>choice, and I think all other compilers store bounds with the array
>(analogous to (1)).


Janus/Ada actually does neither -- the bounds are stored separately, and
belong to neither. (The memory used is allocated separately if needed.)
Indeed, I don't think you can store the bounds with the array for
slices, so I think your analogy is incorrect (there is nothing like
slices for tagged types, of course).

           Randy.

Re: Dispatching and generics - language lawyer question

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> Janus/Ada actually does neither -- the bounds are stored separately, and
> belong to neither. (The memory used is allocated separately if needed.)
> Indeed, I don't think you can store the bounds with the array for
> slices, so I think your analogy is incorrect (there is nothing like
> slices for tagged types, of course).

Good point.  If a slice is passed as a parameter, the bounds ought to be
passed separately from the pointer-to-data.  In Ada 83, I suppose one
could always copy slices, but in Ada 95, some types require pass by
reference.  Including a slice of one of those.

- Bob

Re: Dispatching and generics - language lawyer question

[Robert Dewar]

"Grein, Christoph" <christoph.grein@eurocopter.com> wrote in message news:<mailman.1027489082.2047.comp.lang.ada@ada.eu.org>...
> When you used this trick to redefine 
> equality, also the predefined equality reemerged as in 
> the cases above. Thus for 
> compatibility, we have this rule in Ada 95.

The compatibility consideration here does not relate solely
to the use of the trick for redefining equality.