CVS difference for ais/ai-20217.txt
--- ais/ai-20217.txt 2001/09/21 04:07:45 1.1
+++ ais/ai-20217.txt 2001/09/22 01:18:08 1.2
@@ -1,13 +1,21 @@
-!standard 07.01 (02) 01-09-21 AI95-00277/00
+!standard 03.10.01 (02) 01-09-21 AI95-00277/01
!class amendment 01-09-21
!status work item 01-09-21
!status received 01-09-21
-!subject Handling mutually recursive types via forever incomplete types
+!subject Handling mutually recursive types via separate incomplete types
+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 and
+the "package abstract" proposal of AI-271.
+A separate incomplete type is an incomplete type which is never completed.
+Another type can be "bound" to the separate incomplete type, which then allows
+the types to be used interchangeably.
@@ -23,24 +31,66 @@
+ incomplete_modifier ::= IS TAGGED | IS SEPARATE | IS TAGGED SEPARATE;
+ incomplete_type_declaration ::=
+ TYPE defining_identifier [discriminant_part] [incomplete_modifier];
+An incomplete type containing 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. The Class attribute of a non-tagged incomplete
+type is considered obsolescent. 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.)
+An incomplete type containing the reserved word "separate" (a "separate
+incomplete type") is completed by a type declaration with a completion_clause.
+ completion_clause ::= for <separate_incomplete_type_name>
+ full_type_declaration ::=
+ type <Defining_Identifier> [completion_clause] [known_discriminant_part]
+ is type_definition;
+The name in a completion_clause must name a visible separate incomplete type.
+There is a post compilation rule that a separate incomplete type may have
+only a single completion. The type defined by a type declaration with a
+completion_clause is known as a completing type for the separate incomplete
+type. The rules in 3.10.1(4) about a completion for an incomplete type
+apply to a completing type.
+Where the completing type (or the full type declaration for the completing
+type, if the completing type is a private type) is visible, the separate
+incomplete type name (and the names of any subtypes of it) is treated as a
+subtype naming the completing type. (That is, it is a alternative name for
+the completing type.) In other places, the standard rules for the use of the
+name of an incomplete type apply. A separate incomplete type is exempted from
+the rule that completed declarations are hidden from all visibility (8.3(19)).
+(Since the name is declared in an different scope, there is no need to hide it;
+doing so probably would be additional, unnecessary work.)
+A separate incomplete type can be frozen; it does not need a completion when
+it is frozen. Only non-separate incomplete types are excluded from freezing
+at the end of a scope (13.14(3)).
-(*** TBD ***)
-The concept of a package abstract has been discussed before, under
-different guises. At the time, the "with type" seemed somewhat more
-attractive. However, various technical difficulties associated with
-making access types visible via "with type" have reduced the
-capability of the "with type" proposal. Also, implementation discussions
-about how to implement "with type" have revealed some significant issues
-associated with whether or not the specification must be in the
-environment prior to compiling a "with type" clause. Other problems
-that have arisen relate to the need to implicitly create an "abstract"
-for a package to implement "with type," with the attendant issues associated
-with implicit structures in the program library, their longevity, their
-consistency, etc. Finally, "with type" requires creating some rather
-strange "fictions" to explain to the user what is really going on.
+The concept of a forward or separate incomplete type has been proposed
+in the past. At the time, other proposals looked more attraction. However,
+the complexity of those proposals (particularly the far reaching effects
+of adding a new kind of compilation unit) makes them less attractive to
+solve these problems.
There seem to be two general ways this kind of problem is solved in
other languages. One approach is to permit unrestricted forward
@@ -48,67 +98,133 @@
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.
-The notion of a package "abstract" is analogous to the "incomplete"
-type in Ada, the signature in ML, and the partial revelation in Modula.
-The "with type" approach seems to be a bit of an awkward half-way
-position, allowing a kind of "restricted" forward reference, lacking
-the generality of unrestricted forward reference, and lacking the
-flexibility of a true "forward" declaration, where representation
-items and other capabilities can be accommodated.
-The package abstract approach seems more natural for Ada, and gives
-the user something to look at and conceptually "hold onto," which
-should make the concept easier to understand.
-From an implementation point of view, the "optionality" of a package abstract
-is analogous to the "optionality" of a subprogram specification, and presumably
-similar program library mechanisms can be used to accommodate them.
-Currently, a package has three parts: visible part, private part, and body.
-The visible and private parts are syntactically combined, because the compiler
-needs to see them both at once, in order to generate reasonably efficient code.
-More precisely, when compiling a compilation_unit that says "with P;" the
-compiler needs to look at both the visible and private parts of P.
-This proposal adds another part, so we have four: abstract, visible part,
-private part, and body. In terms of syntax, these form *three* compilation
-units: abstract, spec, and body. The visibility rules work as usual,
-considering an abstract to come before the visible part/private part/body.
+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 does not add any new implementation
+burden. That's because it is very similar to the incomplete-deferred-to-body
+which Ada 95 already has. The compiler does not need to know the real type
+involved as long as the incomplete usage rules 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 doing that for a type whose completion
+is deferred to the body. So 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.
+This proposal allows 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.)
+An alternative model where the place and name of the completion is specified
+in the separate incomplete type's declaration was considered. This model was
+rejected for two reasons:
+ -- The name of the completion does not exist at the point of the separate
+ incomplete declaration. Indeed, we must not have a semantic dependence
+ on the unit of the completion, or we will not be able to solve the
+ mutual dependence problem. Thus, describing the semantics of such a
+ requires a new language mechanism.
+ -- We want to insure that the separate incomplete type is visible to the
+ completion. This would require additional rules.
+The model chosen has neither of these problems. Since we don't try to reference
+the completion in the separate declaration, we don't have to describe what it
+means. A comment may be appropriate, but that is out of control of the
+standard. Secondly, by requiring the name of the separate incomplete type in
+the completing declaration, we automatically require that the incomplete type
+The legality checks for the use of the name of the separate incomplete type
+depend on the visibility of the completing type. This works because types
+can only be hidden from all visibility by a completion. We don't want to
+use "scope" here, as the scope of a library-level type includes the entire
+program. We only want to allow full use of the type where the package
+containing the completion is withed. (Keep in mind we are talking about
+"visibility", not "direct visibility", here.)
+An alternative model where the separate incomplete type is never completed
+(a "forever incomplete type") was considered. In this model, a type is "bound"
+to a separate incomplete type. Then, anywhere in the scope of the binding, the
+two types are considered equivalent. In this model, the separate incomplete
+type can never be used anywhere declare an object, write an allocator, or
+instantiate a generic. This seems unnecessary, and the difficulty of writing
+the needed type matching rules caused it to run aground.
+The model chosen allows separate incomplete types to be frozen, eliminating the
+anomaly of having unfrozen types imported from other units. It also eliminates
+having types that are never frozen anywhere in the program.
+The author would prefer to change the freezing model for incomplete types to
+ - Incomplete types freeze like other types. (The "except incomplete types"
+ in 13.14(3) is deleted.)
+ - When an incomplete type is frozen, if the incomplete type is not separate,
+ and not declared in the private part of a package specification, then
+ it must have already been completed.
+The author believes this is equivalent (with one minor exception) to the
+existing model, as the name usage rules 3.10.1(5-9) prevent any freezing
+before the completion anyway. (The exception is that the completion of an
+incomplete-deferred-to-body could appear after a body in the package body.)
+This change would eliminate the anomaly of unfrozen types ever existing outside
+of their declarative_part. This was not done mainly to avoid cluttering this
+proposal with a non-required change (thus making it seem bigger than it is).
+The syntax for completion_clause does not apply to task or protected types
+in this proposal. These were omitted solely to keep the proposal simple; there
+is no known need to omit them. Adding them would require four additional
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.
+is an employee. (We assume the use of tagged types here to illustrate the
+use of tagged incomplete types.)
- package abstract Employees is
- type Employee;
- type Emp_Ptr is access all Employee;
- end Employees;
+ package Employees_Interface is
+ type Employee is tagged separate;
+ type Emp_Ptr is access all Employee'Class;
+ end Employees_Interface;
+ package Departments_Interface is
+ type Department is tagged separate;
+ type Dept_Ptr is access all Department'Class;
+ end Departments_Interface;
- package abstract Departments is
- type Department;
- type Dept_Ptr is access all Department;
- end Departments;
- with Departments abstract;
+ with Departments_Interface, Employees_Interface;
package Employees is
- type Employee is private;
- type Emp_Ptr is access all Employee;
- procedure Assign_Employee(E : access Employee;
- D : access Departments.Department);
+ type Employee for Employees_Interface.Employee is tagged private;
+ procedure Assign_Employee(E : in out Employee;
+ D : in out Departments_Interface.Department);
- function Current_Department(D : access constant Employee) return
+ function Current_Department(D : in Employee) return
- with Employees abstract;
+ with Departments_Interface, Employees_Interface;
package Departments is
- type Department is private;
- type Dept_Ptr is access all Department;
- procedure Choose_Manager(D : access Department;
- Manager : access Employees.Employee);
+ type Department for Departments_Interface.Departments is tagged private;
+ procedure Choose_Manager(D : in out Department;
+ Manager : in out Employees_Interface.Employee);
@@ -875,7 +991,7 @@
Con: Can't handle access types (due to representation issues).
- Implementation needs "psuedo packages" internally.
+ Implementation needs "pseudo packages" internally.
What happens when multiple paths to the same item "meet"?
Pro: Easy to describe to users.
@@ -895,5 +1011,18 @@
is easy to understand (it is an extension of existing rules). No
run-time implementation problems; the implementation is identical
+From: Dan Eilers
+Sent: September 6, 2001 6:17 PM
+The writeup for this AI should probably reference:
Questions? Ask the ACAA Technical Agent