Version 1.2 of ais/ai-30217.txt

Unformatted version of ais/ai-30217.txt version 1.2
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.

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

From: Tucker Taft
Sent: Thursday, February 7, 2002,  5:42 AM

I think there are two kinds of checks (at least) relevant to ai-217-04:

1) A use of the stub name, or a dereference of an access-to-stub;
     should it be considered incomplete or not?

2) A matching between a non-incomplete type, and a stub name that
    according to (1) would be considered incomplete;
    do they match?

For (1) I would propose that we have fairly rigid rules, in particular
that the package (or a library package renaming thereof) identifed
by the library package "specifier" given in the type stub declaration
be enclosing the current place, or be mentioned in a with clause that
applies to the current place.  [I would require that the specifier be
the full expanded, no-renames-allowed, name of the package, by the way.]

For (2) I would be very liberal.  If the name of the package containing
the non-incomplete type declaration matches the package specifier of
the stub, then the two types match.

The key difference here is that once you have a non-incomplete type,
it can "pull" other type stubs into completeness where it must
"match" them.  However, if you have a reference to a type stub
in a fairly stand-alone way, it requires that the specified package
be "with"ed or enclosing at the place of the (de)reference.
This prevents "ripple" effects due to "distant" semantic dependences
on the completing type.

For example:
    X : <type_stub>;  -- legal only if completing
                      -- package withed/enclosing

    Y : access-to-stub;
    Q : Integer := Y.all.F1;  -- legal only if completing package
                              -- withed/enclosing

In contrast:
    Z : <completing_type> := Y.all;  -- Legal even if completing package
                                     -- not withed/enclosing

This means that deciding whether Y.all is legal means waiting for
overload resolution to complete.  During overload resolution,
if the expected type is a type-stub (that isn't completed by (1))
and the name or expression is the completing type, or vice-versa,
the resolution will proceed, treating the type-stub as the
completing type.  On the other hand, two distinct type-stubs which
happen to have the same completing type don't match.

One important example of something which I presume is *not* legal is the
following:

     package S is
          type T is tagged separate in P;
          procedure Print(X : T);
          type Acc_T is access T;
     end S;

     with S;
     procedure Proc(Y : S.Acc_T) is
     begin
          S.Print(Y.all);  -- illegal use of incomplete type
     end Proc;

In the above, I suggest you would have to add a "with P;" to procedure
Proc to make it legal. (I think... ;-)

In general, we probably need a number of concrete examples of both
legal and illegal uses to make sure we have rules that we can
all accept, and the "average" user will find palatable as well.
Arguing these entirely in the abstract is difficult, and often
misleading.

-------------------------

As a side note, I certainly agree with Randy that we should
allow the completing type to be a private type or extension.
I suspect it was just miswording that had disallowed this.

Also, I think it is important that we introduce the new concept
of "tagged incomplete types" in general, and then use that concept
here.  Hence "type T is tagged;" would be legal in general,
and its main advantage is use as formal parameters and with 'Class.
Introducing these capabilities only as part of type stubs would
seem more confusing and clearly less flexible.

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

From: Erhard Ploedereder
Sent: Thursday, February 7, 2002,  7:50 AM

>>The completing type declaration must be a full type declaration in the

> 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

Unintentional. It should say non-incomplete type declaration.

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

From: Erhard Ploedereder
Sent: Thursday, February 7, 2002, 10:03 AM

The "operational" model that I had in mind with the "check-as-needed"
model is the following:

Use of a stub name or access-to-stub is a-priori considered use of an
incomplete type. (Normal visibility rules apply, of course.)

If the usage is legal for an incomplete type or access-to-incomplete, no
further check happens.

If the usage is not legal, then the completion check is performed and, if
successful, the usage is checked by the rules that apply for the completed
type. The usage may, but need not, imply visibility of the completing type
declaration -- the usual rules for visibility of operations apply.

A possible restriction that I mulled over was to say that usage of the
separate incomplete type is restricted entirely to the package that
declares the stub. That's worth debating.

> For (1) I would propose that we have fairly rigid rules, in particular
> that the package (or a library package renaming thereof) identifed
> by the library package "specifier" given in the type stub declaration
> be enclosing the current place, or be mentioned in a with clause that
> applies to the current place.

But doesn't this put a compilation order requirement in place ? I don't
see why this restriction is needed/desirable. And I fear an unnecessary
restriction arising here.

Can you provide a scenario for the ripple effect that you worry about ?
The one I constructed doesn't seem worrisome, quite the contrary.

On your examples:

    Y : access-to-stub;
    ...

    Z : <completing_type> := Y.all;  -- Legal even if completing package
                                     -- not withed/enclosing

I am not sure what you mean by the comment. That this is legal in any case?
I hope not. The completion check must occur here (or at some prior point).

> This means that deciding whether Y.all is legal means waiting for
> overload resolution to complete.  During overload resolution,
> if the expected type is a type-stub (that isn't completed by (1))
> and the name or expression is the completing type, or vice-versa,
> the resolution will proceed, treating the type-stub as the
> completing type.  On the other hand, two distinct type-stubs which
> happen to have the same completing type don't match.

My model is:

During overload resolution, if the expected type is a type-stub and the name
or expression is of the completing type, or vice-versa, THE COMPLETION CHECK
HAPPENS and THEN the resolution will proceed, treating the type-stub as the
completing type. Two distinct type-stubs which happen to
have the same completing type DO match. (I think that the last part is
important!).

------------
And on.....

     package S is
          type T is tagged separate in P;
          procedure Print(X : T);
          type Acc_T is access T;
     end S;

     with S;
     procedure Proc(Y : S.Acc_T) is
     begin
          S.Print(Y.all);  -- illegal use of incomplete type
     end Proc;

> In the above, I suggest you would have to add a "with P;" to procedure
> Proc to make it legal. (I think... ;-)

As written, I agree :-) But in terms of intent, I would much prefer the
semantic closure model than the visibility model. It's kind of hard
to explain why dereferencing normally does not require visibility of
the type, but merely semantic closure, while this should be
different for a completing type.

I can be convinced by good examples, though :-) but I have not seen
one yet. Hence the request for a ripple example that's bad for the user.

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

From: Tucker Taft
Sent: Thursday, February 7, 2002, 10:57 AM

I think I understand your model now.  You are saying that
any use that is illegal for incomplete types would trigger
an attempt to find the completing type.  There would be
no requirement to explicitly "with" anything.  It would
be like the current rules for attributes like 'Address,
where you end up with an implicit dependence on package System
if you use 'Address.  Of course in 99 44/100 % of the time,
you would already have such a dependence.

That seems reasonable, and it is clearly easiest for the user.
It is probably not worth worrying about the rare cases
where this is creating an implicit dependence, just
as we decided it wasn't worth worrying about it for 'Address.

As far as ripple effects, your approach (presuming I understand
it) eliminates the problem, in the same way that the Ada 95
approach to 'Address eliminated the problem.  Adding or removing
a "distant" with clause has no effect on the legality of the
usage.

This does mean that we need to be careful not to get into a cyclic
dependence, since we don't have the normal "with" clause processing
to protect us.

-------------
Exactly When the Search for the Completion Occurs

Presuming I understand your model, we need to be very clear
about what sort of usage triggers the search for the completing type --
Clearly dereferencing an access value.  I suppose any use of
the stub name (or stub name'Class) other than after the word
"access" or as a formal parameter (if tagged) would trigger
the search as well.

Perhaps we should disallow any usage that
would trigger such a "search" in the compilation unit where
the type stub itself is defined.  If such a use appeared there,
that would clearly defeat the purpose of making it a stub.
Pretty much any place else is a reasonable place to cause
the search (and the implicit dependence) to occur.

-------------
Usages of Stub Name Outside the Defining Package?

It is an intriguing idea to disallow usages of the stub name
outside the defining package.  Of course we want to allow
usages of the access-to-stub type anywhere.  My fear is
that disallowing such usages of the stub name might get
in the way of certain reasonable structures.  On the other
hand, I suppose there is no particular reason you can't
just throw in another stub with the same completing type.
But that might get tedious or confusing, and it wouldn't
work for library subprograms, where there is no place
to put the stub declaration (at least there is no place
to put it if you want to use it as a formal parameter).
Similarly, it would be difficult to use a type stub
in the generic formal part, if you disallowed references
outside the defining package.

Perhaps we should allow stubs to appear anywhere, since
they are really more like subtypes.  It would only be the
completing type which would have to be a type declared immediately
within a library package.  (This begins to make the stub sound
more like a "with type" again!  Groan ;-)

On balance, even if we choose to allow stubs to appear in many
contexts, I think we should allow references outside
the defining package.

-------
Generics?

By the way, should we allow the completing type to be in a child of a
generic package, if the stub is in a child of the same generic package?
Or something like that?  We would need an example, I suppose,
to show how this whole thing could work with generics.  I'm not
sure it is that big a deal, since you can accomplish roughly
the same thing by using a formal type.

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

From: Erhard Ploedereder
Sent: Thursday, February 7, 2002, 12:03 PM

> Also, I think it is important that we introduce the new concept
> of "tagged incomplete types" in general, and then use that concept
> here.  Hence "type T is tagged;" would be legal in general,
> and its main advantage is use as formal parameters and with 'Class.

I agree. (Just didn't want to muddy the separate type issue with this.)

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

From: Erhard Ploedereder
Sent: Thursday, February 7, 2002, 12:41 PM

> I think I understand your model now.  You are saying that
> any use that is illegal for incomplete types would trigger
> an attempt to find the completing type.  There would be
> no requirement to explicitly "with" anything.

Yes.

> It would be like the current rules for attributes like 'Address,
> where you end up with an implicit dependence on package System
> if you use 'Address.  Of course in 99 44/100 % of the time,
> you would already have such a dependence.

I actually believe it's 100% in the sense that my rules require
the existing dependence (or else the type remains incomplete).
I am not advocating an implicit dependence to be created, i.e.,
send the compiler off in search of a package not yet in the semantic
closure. (I am not dead set against it either.) All it needs to do
is to check whether the pkg named in the stub is in the semantic
closure and has a matching type decl.

....
> Perhaps we should disallow any usage that
> would trigger such a "search" in the compilation unit where
> the type stub itself is defined.

For the interesting cases, such usage would effectively be illegal, because
the completing decl is not in the semantic closure. For the non-interesting
case, where it is in the closure...well, it is worth to introduce a special
rule ? Nothing bad is going to happen.

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

From: Tucker Taft
Sent: Thursday, February 7, 2002,  2:24 PM

> ...
> > It would be like the current rules for attributes like 'Address,
> > where you end up with an implicit dependence on package System
> > if you use 'Address.  Of course in 99 44/100 % of the time,
> > you would already have such a dependence.
>
> I actually believe it's 100% in the sense that my rules require
> the existing dependence (or else the type remains incomplete).
> I am not advocating an implicit dependence to be created, i.e.,
> send the compiler off in search of a package not yet in the semantic
> closure. (I am not dead set against it either.) All it needs to do
> is to check whether the pkg named in the stub is in the semantic
> closure and has a matching type decl.
>
> ....

Now I don't like it again.  We worked to remove any search
of the semantic closure from Ada 95.  One reason is the
ripple effects, where the adding or removing of a "distant with"
might change the legality of a compilation unit.  For example

    package P_with_stub is
        type T is tagged separate in P_with_completion;
        procedure print(X : T);
        type T_Ptr is access T;
    end;

    with P_with_stub, Q;
    procedure test(Y : P_with_stub.T_Ptr) is
    begin
        P_with_stub.print(Y.all);
                -- the legality of this depends on
                -- whether Q has a "with" for P_with_completion
                -- That seems undesirable.
                -- Either it should be always illegal (my original rule),
                -- or always legal (what I *thought* was your rule),
                -- independent of "with"s on the otherwise unrelated package Q.
    end;

> > Perhaps we should disallow any usage that
> > would trigger such a "search" in the compilation unit where
> > the type stub itself is defined.
>
> For the interesting cases, such usage would effectively be illegal, because
> the completing decl is not in the semantic closure. For the non-interesting
> case, where it is in the closure...well, it is worth to introduce a special
> rule ? Nothing bad is going to happen.

I don't like the semantic closure rule, as explained above.
I think we should say that a type defined by a type stub is
incomplete throughout the compilation unit in which it is defined.
In other compilation units (so long as they are *not* within the semantic
closure of the completing package, to avoid circularities), it is
equivalent to the completing_type wherever used in a context that
requires a non-incomplete type.  Alternatively, go back to something
based on explicit "with" clauses.

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

From: Randy Brukardt
Sent: Thursday, February 7, 2002,  3:20 PM

Tuck said:

> It would be like the current rules for attributes like 'Address,
> where you end up with an implicit dependence on package System
> if you use 'Address.  Of course in 99 44/100 % of the time,
> you would already have such a dependence.

I don't like this idea at all from an implementation perspective (at least in
Janus/Ada). The 'Address rule is silly, but harmless, as System is a predefined
unit that is included in every compilation whether or not it is in the closure.
(We have special code to reject uses of System when it is not withed).

OTOH, this rule would require mucking around in the program library for some
unit not processed with the other context clauses, and then effectively trying
to with it. But the routines that handle withs expect to do all of them at once
(and thus be able to order them appropriately), and expect to work into a
freshly initialized symbol table. Changing either one of those properties would
be none trivial.

From an implementation perspective, either a rule based on semantic closure or
on explicit withs would work. From a user perspective, it probably makes the
most sense to require explicit withs.

In any case, Erhard's point seems to be that he doesn't find the ripple effect
particularly bad in this case. It can't change the meaning of a program, only
change its legality. At worst, the user goes DUH! and puts in the with that
they need (and perhaps are puzzled why they didn't need it before). So I think
he is looking for a more compelling example of a problem with ripples in this
case.

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

From: Tucker Taft
Sent: Thursday, February 7, 2002,  4:38 PM

Unfortunately, it looks like we are entering into
an area where implementations differ significantly.
I vaguely remember Rational objecting to the "search
the semantic closure" approach, because of incremental
compilation.  For us, searching the semantic closure
is somewhat harder than just going after the package
when it is needed, but we can probably add a hash table
that will solve the problem.

I still don't like the "ripple" effect, so I guess I would
vote for a "with" clause-based rule, which I think is
straightforward for all implementations to support,
albeit somewhat more complicated to specify.

I am surprised Erhard isn't disturbed by the ripple effect.
It just seems weird to me that someone somewhere removes
an apparently unused with clause, and then a group of
seemingly unrelated compilation units suddenly fail at
compile-time.  I know there are tools and compiler warnings
that indicate a "with" clause is not being used.  These might
no longer be accurate in these sorts of situations.

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

From: Robert Dewar
Sent: Thursday, February 7, 2002,  6:25 PM

<<I still don't like the "ripple" effect, so I guess I would
vote for a "with" clause-based rule, which I think is
straightforward for all implementations to support,
albeit somewhat more complicated to specify.>>

I agree with Tuck on this

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

From: Erhard Ploedereder
Sent: Thursday, February 7, 2002,  5:45 PM

>    package P_with_stub is
>        type T is tagged separate in P_with_completion;
>        procedure print(X : T);
>        type T_Ptr is access T;
>    end;

>    with P_with_stub, Q;
>    procedure test(Y : P_with_stub.T_Ptr) is
>    begin
>        P_with_stub.print(Y.all);
>                -- the legality of this depends on
>                -- whether Q has a "with" for P_with_completion
>                -- That seems undesirable.
>                -- Either it should be always illegal (my original rule),
>                -- or always legal (what I *thought* was your rule),
>                -- independent of "with"s on the otherwise unrelated package Q.
>    end;

I will readily agree that this "ripple effect" is a kink (although none that
would allow for really bad consequences or could not be repaired
locally). But the "visibility model" has a quite similar kink:

    package P_with_stub is
        type T is tagged separate in P_with_completion;
        type T_Ptr is access T;
    end;

    package P_with_completion is
        type T is tagged record....;
        type T_Ptr is access T;
    end;

    with P_with_X;
    package R is
        Y: P_with_X.T_Ptr;
    end R;

    with R;
    procedure test is
    begin
        ... R.Y.all ....

Now, under the "visibility" model, it will depend on which of the 2 packages
is used for "P-with-X" whether or not one needs to add a "with
P_with_completion" to test. I find that rather counterintuitive from
the usage point of view (Users basically assume that the two "T"s are one
and the same, as they should be.) It's clearly in the category of ripple,
too.

The issues that I see with "implicit dependencies" being created
on a unit that isn't in the semantic closure already, are:
- This has elaboration consequences.
- This is tough/impossible to figure out for tools that try to
  find the semantic or the link closure without doing full-fledged
  semantic analysis.
- The user might not actually be aware that (s)he just pulled in a
  huge extra module with its support and support's support....

I find those more scary than the relatively harmless ripple effect in
the semantic closure model (where I simply can add a with-clause locally,
if the ripple hits me).

Unfortunately, your example also destroyed my basic assumption that for
most interesting cases the completion will be in the semantic closure
anyway, because the context of the operation needed the "real" T anyway.
Your "test" is a good counter-example.
I have no feeling yet how prevalent such usage might be. I do have a
sneaking suspicion, though, that it's mainly the "is tagged" permission
that creates most of those opportunities.
In the style of Ada, would it not be sufficient to be content with formals
that are of the access flavor ?
In OOP-reality, these mutually dependent types will surely use the access
type as component type and hence offer interfaces that take access params
rather than T params. That would match the Java and C++ reality much better
anyway than T params, which par force get copied when being assigned to
components of T type.
Just a thought ....

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

From: Randy Brukardt
Sent: Thursday, February 7, 2002,  6:09 PM

> Your "test" is a good counter-example. I have no feeling yet how prevalent
> such usage might be. I do have a
> sneaking suspicion, though, that it's mainly the "is tagged" permission
> that creates most of those opportunities.
> In the style of Ada, would it not be sufficient to be content with formals
> that are of the access flavor ?

No, absolutely not.

> In OOP-reality, these mutually dependent types will surely use the access
> type as component type and hence offer interfaces that take access params
> rather than T params.

No, absolutely not. I'll use an access parameter over my dead body. (I don't
believe there is a single one in Claw.)

That's because you never want to force memory allocation issues on users, which
you do if they have to use explicit access types. And if you're not using
explicit access types, why would you want to force the users into the noise of
requiring 'Access on every actual parameter object? "in out" and "access" are
semantically equivalent inside of the units in the absence of explicit access
types, so you don't lose anything by sticking with "in out".

If you force users into memory allocation decisions, then the Java people who
claim that you have to have garbage collection are right. We avoid the issue in
Claw by letting the normal scoping mechanisms do any garbage collection
necessary.

> That would match the Java and C++ reality much better
> anyway than T params, which par force get copied when being assigned to
> components of T type.
> Just a thought ....

I'm not against letting people program like they would Java if they want, but
I'm very against requiring them to do so. Ada is supposed to be better, after
all. :-)

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

From: Randy Brukardt
Sent: Thursday, February 7, 2002,  6:23 PM

> No, absolutely not. I'll use an access parameter over my dead body. (I don't
> believe there is a single one in Claw.)

Before Robert complains again about my getting too emotional :-), I should
point out that I meant in the public interfaces of Claw. We do use a few access
parameters in the private implementation of Claw, and there are a lot of them
in the C interface routines that underlie Claw. But I don't believe in forcing
people to include noise in all of their calls, or (worse) convincing them that
it would be easier to allocate everything off the heap.

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

From: Robert Dewar
Sent: Thursday, February 7, 2002,  7:04 PM

Well I don't mind people having odd idiosyncratic ideas about language
features they don't like and therefore forbid themselves to use, but in
evaluating new proposals, such voluntary crippling is irrelevant. The fact
that Randy will not use access parameters in no way affects their first
class citizenship in the language.

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

From: Randy Brukardt
Sent: Thursday, February 7, 2002,  7:17 PM

Of course not. However, Erhard was proposing that you could use ONLY access
parameters with tagged separate incomplete types, and I find that sort of
restriction unacceptable.

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

From: Robert Dewar
Sent: Thursday, February 7, 2002,  7:20 PM

Seems OK to me, and I don't understand your objection. You did not give any
technical argument, just a declaration about dead bodies, which did not give
much of a clue as to what your objection is.

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

From: Randy Brukardt
Sent: Thursday, February 7, 2002,  7:44 PM

To expand on my original message a bit, the point is that any access
manipulations occur inside the abstractions, not in the public interface. In
Erhard's example, I probably would use an access type to avoid the assignment
-- but that would occur completely inside the abstraction, and would not be
visible to the user.

This happens in Claw; consider a tool "selected" into a canvas. The public
interface for doing that is:

    procedure Choose (Easel  : in out Basic_Canvas_Type;
                      Brush  : in out Claw.Brushes.Brush_Type'Class);

and the implementation is something like (ignoring the various OS calls
involved):

    Easel.Brush_Access := Brush'Unchecked_Access;

Since these are all controlled objects, the Finalization routines do the
cleanup.

Now, Canvases and Brushes are mutually dependent types. We got around that by
declaring the root versions of both in the ultimate parent Claw. But, if we had
had this new feature, we could have avoided that by declarations something
like:

    package Claw.Canvases is
      type Basic_Canvas_Type is ...; -- Controlled
      type Brush_Type is tagged separate in Claw.Brushes; -- Using Erhard's syntax
      procedure Choose (Easel  : in out Basic_Canvas_Type;
                        Brush  : in out Claw.Brushes.Brush_Type'Class);
    private
      type Brush_Access_Type is access all Brush_Type;
      type Basic_Canvas_Type is record
          ...
          Brush_Access : Brush_Access_Type;
          -- Or even Brush_Access : access Brush_Type; -- if AI-230 is adopted.
      end record;
    end Claw.Canvases;

Erhard would like to prevent the declaration of Choose here, requiring the use
of an access parameter.

But that would force all calls (assuming locally declared brush objects, which
is the most typical use of this construct) to include the 'Access "noise". That
is something that is a constant annoyance, much like operators being invisible.
It happens every time you write some code, and has the same effect as
fingernails on a blackboard. We can't do anything about the existing language
cases, but I certainly object to adding more cases like that.

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

From: Robert Dewar
Sent: Thursday, February 7, 2002,  7:55 PM

OK, Randy's argument makes sense, I agree that the declaration of
Choose makes sense (I am a bit dubious on the entire feature mind you :-)

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

From: David Emery
Sent: Thursday, February 7, 2002,  6:31 PM

I think Randy's right on avoiding public access types like the plague.
It really can be a fatal disease; many of the problems with X Windows
came from "delegating" memory management to the application programmer.

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

From: Erhard Ploedereder
Sent: Thursday, February 7, 2002,  7:50 PM

Randy, Dave, Give me a break...
we are doing this in the context of mutually dependent
types in different packages, not in the setting of any arbitrary type
structure, so general insights on OOP don't help.

Now, please tell me how you make two types mutually dependent (and hence
require the type stubs) without using access types to these
types to hook them into the respective components of the other type(s) ?

You can't do it in Ada and you can't do it any other language unless
the language hides the pointer behind a reference semantics so that all
types are the equivalent of access types (with the dreaded memory
implications).

You can, of course, argue that there need not be a component decl in
order to need the other type for some argument list of a subprog.
Further that this subprog must be a primitive of the local type. (In
all other cases, a subprog in a child seems a better way, anyway,
since it would not require mutual dependency.)

I am trying to understand how frequent one would expect this to be.

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

From: Randy Brukardt
Sent: Thursday, February 7, 2002,  7:58 PM

> Now, please tell me how you make two types mutually dependent (and hence
> require the type stubs) without using access types to these
> types to hook them into the respective components of the
> other type(s) ?

That's not the point at all. The point is that I don't want to make the access
semantics visible through the public interface. Whether there is some in the
implementation of the type is irrelevant. See the example I just posted of how
the exact problem comes up in Claw and how we handled it, and how we'd have
handled it if we had this feature.

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

From: Tucker Taft
Sent: Thursday, February 7, 2002,  8:10 PM

> ...
> Unfortunately, your example also destroyed my basic assumption that for
> most interesting cases the completion will be in the semantic closure
> anyway, because the context of the operation needed the "real" T anyway.
> Your "test" is a good counter-example.
> I have no feeling yet how prevalent such usage might be. I do have a
> sneaking suspicion, though, that it's mainly the "is tagged" permission
> that creates most of those opportunities.
> In the style of Ada, would it not be sufficient to be content with formals
> that are of the access flavor ?

I don't think that is necessary.  The reason we allowed incomplete
tagged as parameters was because they were always passed by reference.
That implies that dereference should be legal for an incomplete
tagged type as well, but anything that implies copying, assignment,
or referencing a component would clearly not be permitted.
Hence you could write "Y.all" if Y is access-to-incomplete-tagged, but
about all you could do with it would be to pass it as a (non-controlling)
parameter.

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


Questions? Ask the ACAA Technical Agent