Version 1.1 of ais/ai-30217.txt

Unformatted version of ais/ai-30217.txt version 1.1
Other versions for file ais/ai-30217.txt

!standard 03.10.01 (02)          02-02-06 AI95-00217-04/01
!class amendment 02-02-06
!status work item 02-02-06
!status received 02-02-06
!priority Medium
!difficulty Hard
!subject Handling mutually recursive types via separate incomplete types with package specifiers
!summary
A new construct, called a separate incomplete type, is proposed as a potential solution to the "mutually recursive types across packages" problem. This is an alternative to the "with type" proposal of AI-217-01, the "package abstract" proposal of AI-217-02, and the initial proposal for separate incomplete types in AI-217-03.
A separate incomplete type is an incomplete type which is completed in another package. Where the type is to be regarded as completed and where it is incomplete, subject to all the restrictions of incomplete types, is discussed in !discussion. << A final resolution will go here :-) Preliminary investigation says that it cannot be based on visibility !>>
As the added capability is primarily targeted at mutually recursive tagged types, for which it is important that the incomplete separate type be allowed in the parameter profile of primitive operations, a capability is added to declare the imcomplete type to be a tagged type. For such tagged incomplete types, the respective restriction for incomplete types is eliminated.
The separate incomplete type identifies the package in which the completion is to occur. No semantic dependence on the package is created by this identification. In order for a type declaration to be a completion of the separate incomplete type declarations, both must declare the same identifier and the completing type declaration must be in the package identified by the separate incomplete type declaration. A completion may not be a incomplete type declaration. A tagged incomplete type declaration can only be completed by a tagged type declaration.
There may be multiple incomplete type declarations that are completed by a single completing type declaration. Note that this is essential if separate incomplete types are allowed in generic packages.
!problem
Ada only allows mutually recursive types to be declared if they are all declared within the same library unit. This can force all of the major data structures of a program into a single library unit, which is clearly undesirable in some situations.
The goal of the proposed features is to allow mutual recursion among separately compiled types (types containing (pointers to) each other as components, and primitive operations with (pointers to) each other as parameters.) And to do this in a way that doesn't place any other restrictions on the programmer.
!proposal
<<< I may have undone a desirable change, which would allow the good old incomplete types to be specified as tagged, with the rules as below. I don't recall that discussion, but this change could be easily undone. Without this secondary capability, I felt the syntax below to be simpler. >>>
An additional kind of type declaration is proposed:
separate_type_declaration ::= type defining_identifier [discriminant_part] is [ tagged ] separate in package_name;
A separate_type_declaration introduces an incomplete type whose completion occurs in another package identified by the package_name.
The specified package_name is neither subjected to the name resolution rules at the place of the separate_type_declaration, nor does it create a semantic dependency on the named package. [Rather than introducing this special rule of not interpreting the name at this place, the language-lawyerly approach would be to syntactically include the package name by means of a string_literal. This, however, is not user-friendly because of the quotes and the lack of a syntax check on the package name.]
A separate type whose declaration contains the reserved word "tagged" (an "incomplete tagged type") may be used as the type of a formal parameter prior to its completion, in addition to the normal places where an incomplete type may be used. Also, the Class attribute is defined for an incomplete tagged type. The class-wide type denoted by the Class attribute of an incomplete type may also be used as the type of a formal parameter. An incomplete tagged type must be completed by a tagged type.
Note that we are not proposing that an incomplete tagged type may be used as a return type, because of the many special rules and implementation issues associated with returning tagged types (e.g. functions becoming abstract, accessibility checks on returning limited by-reference types, dispatching on result coupled with tag indeterminacy, finalization associated with returning potentially controlled types, etc.)
In order to be a completion, the completing type declaration must be in the visible part of the package identified by the incomplete type declaration, must not be an incomplete type declaration, and must satisfy all other rules for type completion. This rule is enforced when << fill in the resolution after discussion >>.
There may be multiple incomplete type declarations that are completed by a single completing type declaration. Note that this is essential if separate incomplete types are allowed in generic packages.
The restricting rules on the use of incomplete types apply to separate types. The separate type is completed at places that semantically depend on the unit containing the completion. The usual visibility rules apply to the operations on the type, which are declared together with the completing type.
!discussion
There seem to be two general ways the problem of mutually recursive types is solved in other languages. One approach is to permit unrestricted forward references. This is the approach adopted by Eiffel, Java, and Smalltalk. The other approach is to require "forward" or "incomplete" declarations, sometimes called "signatures" or "partial revelations." This is generally the approach adopted by Ada, as well as Pascal, Modula, ML, C/C++, etc.
We chose the simple approach of extending a single existing Ada feature, rather than adding a basket of heavy new features to provide the needed capability. This simplifies both the conceptual burden and the implementation cost.
The model of a separate incomplete type per se does not add any new implementation burden, because it is very similar to the incomplete-deferred-to-body type which Ada 95 already has. The compiler does not need to know the real type involved as long as the usage rules for incomplete types are enforced.
Determining the representation of an access type that designates a separate incomplete type could be a problem for some implementations that select the representation of an access type based on the designated type. However, this would be no different than for a type whose completion is deferred to the body. Such implementations must already be able to handle this somehow.
Since an access type that designates a separate incomplete type is a normal declaration, representation clauses (for storage pools, for instance) can be used as needed. This eliminates many of the problems found in the "with type" proposal. Note that such an access type can be used normally (including allocators, deallocators, and the like) when the completing type is visible.
Conceptual and implementation dificulties arise from the question where the type is to be regarded as completed and hence allows for object creation and availability of operations of the type. It is clear that such a place must have a semantic dependence on (the package containing) the type completion.
Two issues remain: 1. when does the checking take place to ensure that a type declaration is a
legal completion for the incomplete type declaration (and how is the correlation specified) ?
2. independent of 1), the implementation will have to take special action to
ensure that in places where the incomplete type is to be regarded as completed, the incomplete type declaration is "tied" to its completion.
On issue 1) there are three approaches conceivable: a) The completing declaration identifies the declaration it completes. The
conformance check occurs at this point. This is the approach of AI-277. While simple at first glance, it has serious disadvantages:
- the type declaration syntax is already "heavy"; adding more options
to the syntax of full type declarations is not advisable.
- to perform the check, a semantic dependence on the package containing
the incomplete type needs to be created. In simple cases of breaking but one mutual recursion of types across two packages, this may be acceptable. In cases involving multiple packages, it may be difficult to find a suitable and maintainable hierarchy (without introducing artificial connector packages).
- because of this requirement, incomplete types cannot be sensibly
used in generic packages. (Which instantiation does the completor refer to ?)
- clearly, a post-compilation check is needed to prevent multiple,
different completions in a partition.
- also, a rule is needed that prevents multiple completions
in the semantic closure of a compilation. It is not clear (to the author) how such a rule could be formulated without causing significant implementation burden.
- the implementation effort to solve issue 2 is required regardless.
b) The incomplete declaration identifies the expected place of the
completion. Then, for any unit that has a semantic dependence on the incomplete type and also on the package containing its completion, the completion check and the implementation "tie-in" is made prior to compiling the unit at hand. (Compilations that depend on only one of the two units obey the usual rules of incomplete, resp,. full type declarations.) See, however, some further discussion below.
c) The incomplete declaration identifies the expected place of the
completion. Any operation involving the incomplete type that normally would require prior completion of the type is combined with the completion check (and the creation of the necessary "tie-in").
A concern is that a legal unit depending (only) on the package with the completing type declaration remain legal when an "extraneous" with-clause in another package is subsequently added and establishes a semantic dependence on the package containing the incomplete type. (Removal of a with-clause, on the other hand, is not a problem.) Thus, the rule should not be based on the semantic dependence concept. Here is an example that illustrates the issue:
package P is type T is record Comp:integer; end record; end P;
with P; package Q is Obj: aliased P.T; end Q;
package X is type T is tagged separate in P; end X;
[with X;] -- originally not there package Y is ...
with Y, Q; procedure Test is begin Q.Obj.Comp := 5; end;
Without the with-clause in question, this is clearly legal. Note that P.T is NOT visible in Test (and yet operations on T are legal).
It is arguable whether the (failing) conformance test on the separate type should be performed in Test when the with-clause has been added. If it is performed, it leaves the worry about ripple effects of extraneous with-clauses. If it is not performed, then semantic dependence alone cannot be cause for the check.
Now consider a slight change to the example:
package X is type T is separate in P; -- removed the offending "tagged" end X;
with X; package Y is type T_Acc is access all X.T; end Y;
with Y, Q; procedure Test is A: Y.T_Acc; begin A := Q.Obj'access; end;
Note that neither P.T nor X.T are visible. Here, clearly the check needs to be performed and the "tie-in" must happen or else the legality of the assignment will not be realized.
Conclusion: Visibility of the type declaration(s) per se is the wrong criterion.
We could, of course, force the user by special semantic rule to create visibility, whenever there is a need for completion. But how to tell the user precisely when (s)he needs to create such visibility ? It's a non-trivial list, see below, and the compiler might as well figure it out silently. Also, as a minor point, what about
with P, X; -- imported for many other reasons procedure Test is begin -- no mention of T anywhere end;
Should correspondence be checked, even though the common visibility is accidental ?
with Y, Q, P; -- slight revision of the 2. example; P now visible procedure Test is begin Q.Obj.Comp := 5; end;
Should correspondence be checked, although X is not visible but semantically depended on ?
... more variations of the theme, but it becomes boring....
And so we turn to the third model.
With Visibility awkward and Semantic Dependence somewhat dubious (the author actually doesn't think too badly about it despite the ripple), the obvious route is to explore a "check-as-needed" model, i.e., whenever an operation is attempted that involves both the complete and the incomplete type, the check is performed. These operations are:
- dereferencing on access types with the incomplete type as target - assignment and comparison of such access types - parameter matching with tagged incomplete types for formals - access-to-subprogram matching involving such types for formals or result - <<< others ? >>>
These checks are automatic - no need to complicate the language...other than saying after the "shall match" rule that the rule is enforced any time an operation is attempted that involves both the incomplete and the completing type.
Beyond the "when" of the check, we need to specify more clearly the "what" of the check.
We propose the following: The name specified in the package_name of the separate_type_declaration must be the name of a package in the environment. The named package must either be a root package or a child package. In the case of a private child package, the package containing the separate incomplete type declaration must be a private descendant of the direct parent unit of the child unit. In the case of a non-private child package, the package containing the separate incomplete type declaration must be a descendant of any private parent unit of the child unit. (Note that there are no remnants of "order" within Standard in these rules,
i.e., of the visibility model, so that forward references are truly allowed and there is no question about local homographs, etc. We do guarantee the privateness rules, however.)
The completing type declaration must be a full type declaration in the visible part of the package [this could be extended to private parts for the case where the other package is a private child, but I don't think this is worth it] and must declare a type with the same defining_identifier.
Whether or not the package name may involve renamings is debatable. The issue is not essential to the proposal. Arguments should be heard on the subject. (The author's opinion is to allow renamings, since the restriction is hard to sell to users who like to abbreviate their "working set" of packages.)
We propose to allow the separate incomplete type to not be completed at all in the program. There is no problem with not having a completion (no object of the type could be created), and there is no implementation problem. Not having a completion can be useful in the prototype stages of a program, and also can be useful for a program with multiple implementations. (For instance, a compiler front-end could have an incomplete type for code generation information. A checkout version of the compiler, with no need for code generation, would not need to complete the incomplete type.) As an added benefit to implementers, the need for a post-compilation check is avoided.
!example
Here is the classic case of mutual dependence, where an employee belongs to a particular department, and a department has a manager who is an employee. (We assume the use of tagged types here to illustrate the use of tagged incomplete types.)
Two versions are presented. One uses a separate interface package, possibly advisable to have single well defined place for the access types. The other does a more direct coupling. (Note that, while it looks simpler and much more elegant, it can be used only in settings where the access types are needed in only one of the respective packages.)
package Employees_Interface is type Employee is tagged separate in Employees; type Emp_Ptr is access all Employee'Class; end Employees_Interface;
package Departments_Interface is type Department is tagged separate in Departments; type Dept_Ptr is access all Department'Class; end Departments_Interface;
with Departments_Interface, Employees_Interface; package Employees is type Employee is tagged private; procedure Assign_Employee(E : in out Employee; D : in out Departments_Interface.Department); ... function Current_Department(D : in Employee) return Departments_Interface.Dept_Ptr; end Employees;
with Departments_Interface, Employees_Interface; package Departments is type Department is tagged private; procedure Choose_Manager(D : in out Department; Manager : in out Employees_Interface.Employee); ... end Departments;
-----------------
package Employees is type Department is tagged separate in Departments; type Dept_Ptr is access all Department'Class; type Employee is tagged private; procedure Assign_Employee(E : in out Employee; D : in out Department); ... function Current_Department(D : in Employee) return Dept_Ptr; end Employees;
package Departments is type Employee is tagged separate in Employees; type Emp_Ptr is access all Employee'Class; type Department is tagged private; procedure Choose_Manager(D : in out Department; Manager : in out Employee); ... end Departments;
!appendix

[For discussion on the original version of this proposal, see AI-00217-03.

*************************************************************

From: Tucker Taft
Sent: Monday, February 4, 2002,  5:49 PM

[ai-217-02 is the AI formerly known as "ai-277" ;-]

I thought I would mention that we went ahead and did a prototype
implementation of incomplete type stubs, following the suggestion
from Erhard where the package that defines the type is specified
at the point of the stub.  It turned out to be a relatively modest
enhancement to the existing support for incomplete types.

The only tricky part is defining under exactly what circumstances a
reference to the stub (say "P.T") is equivalent to a reference to
the completing type (say "A.B.C.T").  The basic rule was that,
presuming the package name given in the type stub declaration
was "A.B.C" then "A" must be the name of a (root) library
package that is visible in package Standard at the point
of the reference (because it was "with"ed or because it encloses
the point of reference); similarly B must be a (child) library package
visible within A, and C must be visible within B.  A, B, and C must
not be renamings, to avoid multiple names for the same completion.
And of course a (non-type-stub?) type with the same name as the type stub
(say "T") must be declared within the visible part of "C".  Presumably if "A"
is not *directly* visible (because it is hidden by an inner
homograph) that is OK, so long as <pkg_standard>.A is visible.

This check is done at pretty much any use of P.T *except* as a
designated subtype, as well as any dereference of an access-to-P.T.
One question is if A.B.C is visible at the point of a declaration
of an access-to-P.T type, should you "remember" that?  Our presumption
was no, since the user could have written "A.B.C.T" if they had wanted
those semantics.  Instead, if they write P.T as the designated subtype,
then this may be dereferenced only where A.B.C is visible.

Note that we require A.B.C to be visible, not merely in scope, so
that "ripple" effects due to adding or removing a "distant" with
clause don't alter the semantics.

I suppose another question is what happens when there are two
incomplete stubs with the same completing type.  Are they considered
statically matching subtypes?  Or only where their (shared) completion
is "available."  (I am using the term "available" to mean
the full type's full name, e.g. A.B.C.T, is visible.)

*************************************************************

From: Randy Brukardt
Sent: Monday, February 4, 2002,  5:49 PM

> [ai-217-02 is the AI formerly known as "ai-277" ;-]

Well, actually, AI-00217-03 (the third alternative of AI-217) is the AI
formerly known as AI-277.

> I thought I would mention that we went ahead and did a prototype
> implementation of incomplete type stubs, following the suggestion
> from Erhard where the package that defines the type is specified
> at the point of the stub.  It turned out to be a relatively modest
> enhancement to the existing support for incomplete types.

Great! I need this yesterday in the Claw Builder. :-)

I've been waiting for a proposal (and the upcoming meeting) before doing
anything about an implementation.

How did you describe the package "name" in the incomplete stub (since it cannot
be a 'name' in the Ada sense, as it is not visible and cannot 'denote' anything
in the stub -- at least if it is to be a useful construct)?

> The only tricky part is defining under exactly what circumstances a
> reference to the stub (say "P.T") is equivalent to a reference to
> the completing type (say "A.B.C.T").  The basic rule was that,
> presuming the package name given in the type stub declaration
> was "A.B.C" then "A" must be the name of a (root) library
> package that is visible in package Standard at the point
> of the reference (because it was "with"ed or because it encloses
> the point of reference); similarly B must be a (child) library package
> visible within A, and C must be visible within B.  A, B, and C must
> not be renamings, to avoid multiple names for the same completion.
> And of course a (non-type-stub?) type with the same name as the type stub
> (say "T") must be declared within the visible part of "C".  Presumably if "A"
> is not *directly* visible (because it is hidden by an inner
> homograph) that is OK, so long as <pkg_standard>.A is visible.

Is the restriction against renames really necessary? It seems odd to introduce
a case where a renamed package is not semantically equivalent to the package it
renames. Such a restriction may make sense for the declaration (that would be
equivalent to the rule for child packages), but I don't think you would want to
enforce that on the checks (which is the 'use' of the rename, which is
certainly allowed for child units).

> ...
>
> I suppose another question is what happens when there are two
> incomplete stubs with the same completing type.  Are they considered
> statically matching subtypes?  Or only where their (shared) completion
> is "available."  (I am using the term "available" to mean
> the full type's full name, e.g. A.B.C.T, is visible.)

I would think only when the (shared) completion is available. But it doesn't
seem important either way.

*************************************************************

From: Tucker Taft
Sent: Monday, February 4, 2002,  9:11 PM

[NOTE: as Randy pointed out, it is really 217-03 I am talking about]

Randy Brukardt wrote:

> ...
> How did you describe the package "name" in the incomplete stub (since it
> cannot be a 'name' in the Ada sense, as it is not visible and cannot
> 'denote' anything in the stub -- at least if it is to be a useful
> construct)?


We didn't describe it formally.  I agree it would be nice
to have a word or phrase for this.  Perhaps we could call
it a "library package specifier" which is somewhat ambiguous
as to whether it is a visible.


>>The only tricky part is defining under exactly what circumstances a
>>reference to the stub (say "P.T") is equivalent to a reference to
>>the completing type (say "A.B.C.T").  The basic rule was that,
>>presuming the package name given in the type stub declaration
>>was "A.B.C" then "A" must be the name of a (root) library
>>package that is visible in package Standard at the point
>>of the reference (because it was "with"ed or because it encloses
>>the point of reference); similarly B must be a (child) library package
>>visible within A, and C must be visible within B.  A, B, and C must
>>not be renamings, to avoid multiple names for the same completion.
>>And of course a (non-type-stub?) type with the same name as the type stub
>>(say "T") must be declared within the visible part of "C".  Presumably if
>>
> "A"
>
>>is not *directly* visible (because it is hidden by an inner
>>homograph) that is OK, so long as <pkg_standard>.A is visible.
>>
>
> Is the restriction against renames really necessary? It seems odd to
> introduce a case where a renamed package is not semantically equivalent to
> the package it renames. Such a restriction may make sense for the
> declaration (that would be equivalent to the rule for child packages), but I
> don't think you would want to enforce that on the checks (which is the 'use'
> of the rename, which is certainly allowed for child units).


I think I know what you are saying.  You are saying that A, A.B, and A.C
need not be visible.  However, a library package must be
visible whose full expanded name is "A.B.C."  Unfortunately,
this gets tricky.  What if there is a renaming of A.B.C in some
other package that is with'ed (say "D") but that A.B.C or
a library unit renaming thereof has *not* been with'ed?
That seems a bit dodgey -- sort of a ripple effect due to
adding or removing a rename in some with'ed package.

So perhaps the rule could be that the library package whose
full name is A.B.C, or a library renaming thereof, must be
"withed." There is no requirement for A or A.B to be with'ed.

This would imply some kind of hash table to determine whether
some renaming of A.B.C has been with'ed, because you probably
wouldn't want to actually go and "load" A.B.C just to find out
whether it had already been with'ed.  I suppose this sort of
hash table might already exist for other reasons...


>...


>>I suppose another question is what happens when there are two
>>incomplete stubs with the same completing type.  Are they considered
>>statically matching subtypes?  Or only where their (shared) completion
>>is "available."  (I am using the term "available" to mean
>>the full type's full name, e.g. A.B.C.T, is visible.)
>>
>
> I would think only when the (shared) completion is available. But it doesn't
> seem important either way.


I think that makes sense.  Either the stub is an incomplete type,
and considered distinct from all other types, or its completion
is "available," in which case it is considered a subtype of
its completion.  There is no middle ground, and no need to
do "string" comparisons of the library package specifiers to
see if two type stubs are really the "same."


I hope Erhard is listening.  I think he is on the hook to
write this up.

*************************************************************

From: Randy Brukardt
Sent: Monday, February 4, 2002,  9:28 PM

> So perhaps the rule could be that the library package whose
> full name is A.B.C, or a library renaming thereof, must be
> "withed." There is no requirement for A or A.B to be with'ed.

This sounds right to me.

> This would imply some kind of hash table to determine whether
> some renaming of A.B.C has been with'ed, because you probably
> wouldn't want to actually go and "load" A.B.C just to find out
> whether it had already been with'ed.  I suppose this sort of
> hash table might already exist for other reasons...

Humm, this just seems like a fairly normal symboltable lookup (possibly with
broader than normal visibility). It certainly would be in Janus/Ada (with some
visibility checks afterwards to dump out anything not with'ed).

*************************************************************

From: Randy Brukardt
Sent: Wednesday, February 6, 2002,  9:48 PM

AI (version 1) comments:

<<< I may have undone a desirable change, which would allow the good
old incomplete types to be specified as tagged, with the rules as below.
I don't recall that discussion, but this change could be easily undone.
Without this secondary capability, I felt the syntax below to be simpler.
>>>

I think this was an intentional change. Two main reasons for it:

To make the rule about 'Class being allowed for an incomplete, but then the
full type has to be tagged obsolescent; and to make Bob Duff happy by not
requiring people to use a separate incomplete in order to get an unrelated
desirable feature (the use of an incomplete type as a parameter
declaration). I intentionally preserved it in my version. (I believe it is
present in all of the other alternatives.)

---

>The specified package_name is neither subjected to the name resolution
>rules at the place of the separate_type_declaration, nor does it create a
>semantic dependency on the named package. [Rather than introducing this
>special rule of not interpreting the name at this place, the
>language-lawyerly approach would be to syntactically include the
>package name by means of a string_literal. This, however, is not
>user-friendly because of the quotes and the lack of a syntax check on
>the package name.]

Well, the *real* language lawyerly thing to do would be define a new item
package_specifier:

    package_specifier ::= identifier {. identifier}

Rather than using an "ignore everything you know about this name".
Certainly, I'd have to do this in Janus/Ada (where the production "name"
implies all of the things you said don't happen, even before we look at the
context).

>The completing type declaration must be a full type declaration in the
>visible part of the package [this could be extended to private parts
>for the case where the other package is a private child, but I don't
>think this is worth it] and must declare a type with the same
>defining_identifier.

Humm, this would prevent completing with a private type, which has to be
allowed. (It is not at full type in the visible part of the package!!) Your
examples would be illegal by this rule.

*************************************************************


Questions? Ask the ACAA Technical Agent