Re: Dispatching and generics - language lawyer question

[Robert A Duff <bobduff@shell01.TheWorld.com>]

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