ARG-Editor
commented
2 months ago Let's explore a possible solution to the co-derivation problem.
One approach to co-derivation that does appear to work is one where all of the types are tagged types. This doesn't harm functionality (as access types can be emulated with generalized references, and array types can be emulated with generalized indexing), but it eliminates problems with dispatching.
The basic idea is that a tagged type can be tied with one or more other tagged types declared in the same scope. (We'll discuss ways to specify that later.) For a single group of tied types, we get a tag group of related types. This has the following effects: (1) Having controlling operands of multiple tagged types is allowed for a single primitive operation if all of the types are tied in a single tag group. (2) The dispatch tables for tied types are effectively merged. (The tags are not the same as some slots are for operations on the specific object, and those obviously have to be different for different types that likely have different components and representations.) This makes a "tag group". For the purposes of tag checks when dispatching, the tags of a tag group (that is, of a particular set of tied types) compare as matching. (3) Extending a tied type always has to extend all of the tied types (a kind of co-extension - but of course Ada already has that term). Extending only one of a set of tied types is illegal. (Again, we'll discuss exactly how this is specified later.) (4) Other than for dispatching and type extensions, tied types work the same as a normal "untied" type. The majority of semantics is unchanged.
For example, our previous example of
procedure Delete (Container : in out Map; Position : in out Cursor);
which would be inherited as:
procedure Delete (Container : in out Map_Rec; Position : in out Map_Rec_Cursor);
Both parameters are considered controlling parameters in this scenario. The controlling parameters have to have types from the same tag group. For example, a dispatching call on Delete would have dynamically-tagged arguments of Map'Class and Cursor'Class. The actuals to those parameters would need to have tags from the same tag group.
Thus, if the actuals have types Map and Cursor, or Map_Rec and Map_Rec_Cursor, all is well. But if the actuals have types Map_Rec and Cursor, Constraint_Error will be raised (which is good, as no such routine exists to dispatch to).
One way to implement tag groups would be to include a special "tag group" slot in all tags. This slot would contain the tag value itself for types not in a tag group, but would contain the tag value for the group (probably one of the types would be defined to be the group-defining type, and that tag value would be used to represent the entire group). Then a dispatching call tag check can just be the comparison of the values in the "tag group" slot. This would cost just an extra indirection for each tag. It's probable that the compiler could use this more expensive check only in cases where tag groups exist, eliminating any distributed overhead. (Even if it can't do so, the overhead is an extra slot per type and an extra indirection per check, pretty minimal in both time and space.)
Turning to how tied types can be specified.
The obvious idea is to have some sort of syntax for this. After all, this has major effects on semantics.
Unfortunately, there are a number of issues with using syntax.
First, one needs a separator that doesn't get lost. The originally proposed syntax used a comma, but that does get lost between extensions (especially for record types and extensions, which can be lengthy).
"And" would have been a better choice, but of course that already has a meaning in type extensions and derivations. So we stuck with comma lacking a better idea.
Secondly, syntax can be huge for full types. When the first type has a lot of components, finding the start of the second type's declaration well below can be difficult (since it probably looks very similar, another list of components). Moreover, the names of the second (and possibly later) types can be a long way from the actual declaration. Reading these declarations can be confusing.
Finally, syntax is pervasive. One has to support tied types for full types, private types, private extensions, formal derived types, formal private types, and probably interface types and formal interface types. Whew! Each of those kinds of types needs the possibly to declare tied types and associated syntax changes.
This later reason was the main reason that I didn't fully write this up during the Ada 2022 process. The wording changes needed would be extensive, and it wasn't clear that this was the correct approach. Particularly as the proposal was in early days and needed a lot of vetting for interactions with other features.
For all of the above reasons, I believe it is better to define tied types with an aspect. It is much less pervasive, both in syntax changes and presumably in rule changes.
The basic idea is that each type that is tied would include a Tied_To aspect which would give a list of other types to which it is tied. The other types named would have to appear in the same declaration list as the declaration with the aspect. If they don't the program is illegal.
I believe it would be best for that to be repeated for each extension. That way, the compiler always knows the names of the types in a tag group when processing, and it can immediately check that derivations from tied types indeed are themselves tied. Moreover, the compile can assume that a later derivation will be coming along for the other tied types for a group. (If it doesn't, the program is illegal for a violation of the Tied_To rules.)
Using the aspect, our previous example would look something like:
type Map_Rec is new My_Map_Pkg.Map with private
with Tied_To => Map_Rec_Cursor;
type Map_Rec_Cursor is new My_Map_Pkg.Cursor with private
with Tied_To => Map_Rec;Note that both types include a Tied_To aspect. This seems necessary as these declarations could be far apart, and it's important that the fact that each of these declarations is tied is obvious without searching the entire declaration list (which can of course be very large for a package specification).
A useful side-effect of using an aspect is that it could be added to an Ada compiler now without needing an extensions switch (since implementation-defined aspects are always allowed).
Let's explore some of the other rules associated with tied types and tag groups.
For a private types, the private type declarations have to be tied. The full type declarations have to be tied in the same way. (I think that repeating the aspects is best in this case; this is too important to have implicit at any step. Note that if a syntax is used instead, that would naturally have to be repeated for the full types.) Similarly, private extensions would need to be tied, and certainly if the ancestor types are themselves tied.
Generic specifications also need indication of tied types. In particular, formal tagged private types and formal tagged derived types would need to indicate tying. If the formal types are tied, the actual types also have to be tied.
Individual formal types can match a member of a tied type set. A recheck is needed on any derivations from a formal type that the parent type is not tied. (Tagged type extensions are only allowed in the specification of a generic unit, so this is always possible.) I have not been able to think of any problems caused by an individual member of a tied set being used in a generic, so long as there are no type extensions. But more research is needed to determine if there are problems in corner cases.
One open question is whether tied types have to be restricted to the root of a derivation type, or if they can be added anywhere in a derivation tree. Obviously, the latter is more flexible, but it is unknown if having later additions of tying causes any semantic problems.
It's clear that cross-tying cannot be allowed (that is, tying a type that is in the middle of some other derivation tree). But it seems that allowing tying for a newly defined type would work properly. That's because dispatching through the root of the original hierarchy cannot reach any operations for the new type (it's new, after all). The other operations (which solely use the original type) can be dispatched to in the normal way - tying does not change how subprograms are called outside of dispatching calls.
It's not clear if tying is useful for interface types. But it is likely that someone will find a use for tied interface types, so it seems best to provide them. The rules appear to be the same for interfaces as for other kinds of types.
One clear downside of this aspect is that it can't be used with the existing container definitions. For that to work, the Map and Cursor types would have to be tied, and the Cursor type would have to be tagged. A change of that magnitude would likely be unacceptably incompatible.
Luckily, the changes to the containers made for Ada 2022 have mitigated the original problem. Ada 2022 added versions of all of the cursor-only routines that include a container parameter. That was done for contract reasons (one needs to know the container being accessed; otherwise, one has to assume that any container could be accessed, which generally reduces to anything could be accessed (given that Global aspects aren't very specific). However, it also means that one can derive a usable set operations by just deriving the container type. One doesn't get the cursor-only operations that way, but one doesn't need them, either. You do lose any compile-time checking on cursor values (they are all the same type), but that is much less of a problem than the hodgepodge of operations that you got from deriving an Ada 2012 container.
As such, this proposal would be mainly useful for newly created ADTs. But it would effectively allow dispatching on references (handles?) without having to resort to access types (especially anonymous access types), allow memory management to stay within a package rather than being forced onto every client.
So far as I can tell, the basic idea is sound. But much more thought will need to be put in regarding corner cases, especially those surrounding generics.
Additionally, we need to create complete examples of how this would work, to ensure that it actually solves the problem.
Finally, a prototype implementation is needed (both to try the examples, and to ensure that no implementation problems are missed).
jeremiahbreeden
This issue has been created to continue work on an unfinished topic from Ada 2022. This is in response to the ARG resolution of November 2022.
The containers are tagged types, with the idea that they would support extension if needed. But it turns out that one can't really extend them sensibly. Consider what happens if you try.
The obvious way to create an extension of a container would be something like:
The problem is that the inherited operations are NOT the ones we want. For the derivation making type Map_Rec, we have inherited primitive operations on Map_Rec and on My_Map_Pkg.Cursor (that is, the new map and the old cursor). For the derivation making type Map_Rec_Cursor, we have inherited primitive Operations on My_Map_Pkg.Map and on Map_Rec_Cursor (that is, the old map and the new cursor). That is certainly not what we want, for either type.
We could just use the original cursor type (rather than trying to declare a new one), but that has two problems. First, we've eliminated any compile-time checking associated with cursors; they could designate either a My_Map_Pkg.Map or a Map_Rec. There still will be a runtime check that they designate the right object, but generally we don't want to turn compile-time checks into runtime checks (as insufficient testing could leave a time-bomb in the code).
Second, we've lost all of the cursor-only operations; they only operate on a My_Map_Pkg.Map, and are not inherited into this scope at all. For Ada 2022, that is less of a problem than it was in previous Ada versions (as all of those operations now have counterparts that also take a container along with the cursor), but if it is desired to use those operations, they would have to be created manually.
Getting both a new map and new cursor type can only be accomplished by declaring all of the operations we want and then manually calling the correct original operations from them, a task that is very tedious and error-prone. (Plus we still have all of those junk operations declared and visible, meaning lots of potential errors in usage could go undetected.)
This problem comes up anytime you have an ADT and some other related type, with operations on both. This pattern often happens when the other type is some sort of reference to the ADT or its parts ("reference" here being used to name the general concept of having an object that designates another objects, as opposed to any specific implementation of that concept).
For tagged types, one can mitigate the problem if the "reference" is a raw access type, by using an access-to-classwide type for the handle. But that eliminates any compile-time checking, moving everything to runtime checks (with the usual resulting problems, especially when testing is inadequate), and it puts the onus of memory management on the client (since objects can be allocated outside of the control of the ADT).
Ada is all about compile-time checking, so there should be a way to simultaneously derive multiple types. That would eliminate the creation of unneeded junk operations.
AI12-0223-1 contains some initial analysis of this problem and possible solutions. (The mail in the !appendix expands this analysis as well.)
The straightforward solution of a co-derviation, such as something like:
has various problems. The basic idea was to support deriving multiple types at a time, with the types of the parameters of the primitive operations of each of the types substituted simultaneously.
Unfortunately, that causes issues in generics, especially with generic formal derived types. One can get situations where a formal derived type is expecting operations that were never declared for a possible actual type.
If one of the types is tagged (both cannot be tagged with the current rules, as that would imply a primitive operation that has controlling operands of multiple tagged types, which is not allowed), we also get problems with dispatching. The main problem is that the profile of the operations actually declared is different than those that one would (naturally) dispatch to.
For instance, with the above declaration, we'd inherit Delete, which is defined as:
procedure Delete (Container : in out Map; Position : in out Cursor);
which would be inherited as:
procedure Delete (Container : in out Map_Rec; Position : in out Map_Rec_Cursor);
However, a dispatching call on an object of My_Map_Pkg.Map'Class would call:
procedure Delete (Container : in out Map_Rec; Position : in out My_Map_Pkg.Cursor);
which doesn't exist.
This problem comes from the fundamental conflict between compile-time and runtime checking. Dispatching calls are necessarily runtime constructs, and the compile-time type checking implied by co-derivation is incompatible with that. One can imagine rules that would make dispatching work, but any such rules would necessarily eliminate the compile-time type checking (at least for dispatching calls).
Based on these considerations, co-derivation alone does not work. Is there another option? We'll explore that in a separate post.