Version 1.1 of ais/ai-00271.txt

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

!standard 07.01 (02)          01-05-31 AI95-00271/01
!class amendment 01-05-31
!status work item 01-06-02
!status received 01-05-31
!priority Medium
!difficulty Hard
!subject Handling mutually recursive types via package "abstracts"
!summary
A new construct, called a package "abstract," 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.
A package "abstract" is an extract of a package specification, containing types, and potentially subpackages, representation items, and static constants that may be needed to allow two packages to declare mutually recursive types. A package abstract is referenced by an "abstract with" clause. A package specification must conform to its package abstract, if any. The elaboration of a package abstract has no effect.
!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.
!proposal
Three new constructs are proposed: a package "abstract," an "abstract" with clause, and an incomplete tagged type.
PACKAGE ABSTRACT:
package_abstract ::= package abstract defining_program_unit_name is {package_abstract_item} end [[parent_unit_name.]identifier];
A package abstract may contain only the following kinds of declarative items:
package_abstract_item ::= incomplete_type_declaration | abstract_interface_declaration -- see AI-251 on interface types | type defining_identifier is access_type_definition ; | defining_identifier_list : constant [subtype_indication] := static_expression ; | attribute_definition_clause | package_abstract
Representation pragmas are also permitted.
No pool-specific access types may be declared in a package abstract.
The specification of a package must "conform" to the abstract of the package, if any, in the following sense:
- Each incomplete type declaration in the abstract of the package
must be completed in the visible part of the specification of package. A conforming incomplete type declaration may also appear prior to this completion in the visible part of the specification.
- Each access type declaration in the abstract must have a conforming
access type declaration in the visible part of the specification.
- Each constant or named number declaration in the abstract must
have a conforming constant or named number declaration in the visible part of the specification.
- Each representation item in the abstract must have a conforming
representation item in the specification.
If an access type is declared in a package abstract, all aspects of its representation except for its storage pool are frozen at the end of the package abstract. As indicated above, the access type must not be pool-specific.
The only representation items permitted in the package specification for the access type are those that conform to representation items appearing in the abstract, and those that apply to the storage pool of the type (Storage_Pool, Storage_Size).
The actual "collection" for the access type is not created until the package specification is elaborated. An allocator is illegal for an access type declared in an abstract, though not for the corresponding access type declared in the specification. Similarly, an access type in an abstract must not be passed as an actual for a formal access type in a generic instantiation.
ABSTRACT WITH CLAUSE:
abstract_with_clause ::= abstract with library_unit_package_name {, library_unit_package_name};
An abstract with clause on a compilation unit makes the abstract of each specified package visible within the compilation unit, and hides the specification of the package even if it is visible due to a with clause on some ancestor (or corresponding declaration) compilation unit. Similarly, a (normal) with clause on a compilation unit makes the specification visible, and hides the abstract even if some ancestor (or corresponding declaration) compilation unit made it visible. A given compilation unit must not mention a package in a (normal) with clause and specify the same package in an abstract with clause. [NOTE: This is to ensure that order of with clauses does not matter.]
Within the abstract for a child package, if the abstract of its parent is not already visible due to an abstract with clause, then the visible part of the specification of the parent is visible. Hence the abstract of the child has direct visibility on only the declarations of the abstract of the parent if the abstract of the parent is visible. If the abstract of the parent is visible, then either the specification or abstract of further ancestors is visible corresponding to which is visible in the abstract of the parent.
If a package specified by an abstract with clause on some compilation unit is a child package, then either the specification or abstract of its parent and each further ancestor is made visible within the compilation unit, as determined by which is visible within the specified child.
If an abstract or specification of a package is made visible by an abstract with clause, then a semantic dependence is created on that part of the package. [This in turn implies an elaboration dependence -- see 10.2(9).] The specification of a package has a semantic dependence on its abstract, if any.
NOTE: At no point should both the specification and the abstract of a package be visible by the "same" name. However, (a rename of) the specification may be visible under one name, while (a rename of?) the abstract is visible under a different name.
[TBD: Should "package abstract P renames Q;" be supported? Seems OK.] [TBD: Should a package abstract be permitted as a local package?
I don't see why not...]
[TBD: Should package renames be permitted inside of a package abstract?
Seems unnecessary.]
INCOMPLETE TAGGED TYPE:
incomplete_type_declaration ::= type defining_identifier [discrminant_part] [is 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 would be considered obsolescent.
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.)
!discussion
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.
There seem to be two general ways this kind of problem 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. 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.
!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.
package abstract Employees is
type Employee; type Emp_Ptr is access all Employee;
end Employees;
package abstract Departments is type Department; type Dept_Ptr is access all Department; end Departments;
abstract with Departments; package Employees is type Employee is private; type Emp_Ptr is access all Employee; procedure Assign_Employee(E : access Employee; D : access Departments.Department); ... function Current_Department(D : access constant Employee) return Departments.Dept_Ptr; end Employees;
abstract with Employees; package Departments is type Department is private; type Dept_Ptr is access all Department; procedure Choose_Manager(D : access Department; Manager : access Employees.Employee); ... end Departments;
!ACATS test
!appendix

From: Tucker Taft
Sent: Saturday, June 02, 2001 1:03 PM

Here is one of my first homework assignments.
-Tuck
------------------
!standard 07.01   (02)                                01-05-31  AI95-002xx/00
!class amendment 01-05-31
!status received 01-05-31
!priority Med
!difficulty Hard
!subject Handling mutually recursive types via package "abstracts"

!summary

A new construct, called a package "abstract," is proposed as a potential
solution to the "mutually recursive types across packages" problem.
This is an alternative to the "with type" proposal.

A package "abstract" is an extract of a package specification, containing
types, and potentially subpackages, representation items, and static
constants that may be needed to allow two packages to declare mutually
recursive types.  A package abstract is referenced by an "abstract with"
clause.  A package specification must conform to its package abstract,
if any.  The elaboration of a package abstract has no effect.

!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.

!proposal

Three new constructs are proposed: a package "abstract," an "abstract" with
clause, and an incomplete tagged type.

PACKAGE ABSTRACT:

    package_abstract ::=
        PACKAGE ABSTRACT defining_program_unit_name IS
            {package_abstract_item}
        END [[parent_unit_name.]identifier];


A package abstract may contain only the following kinds of declarative items:

   package_abstract_item ::=
       incomplete_type_declaration
     | abstract_interface_declaration    -- see separate AI on interface types
     | TYPE defining_identifier IS access_type_definition ;
     | defining_identifier_list : CONSTANT [subtype_indication]
         := static_expression ;
     | attribute_definition_clause
     | package_abstract

Representation pragmas are also permitted.

No pool-specific access types may be declared in a package abstract.

The specification of a package must "conform" to the abstract of the
package, if any, in the following sense:

   - Each incomplete type declaration in the abstract of the package
     must be completed in the visible part of the specification of
     package.  A conforming incomplete type declaration may also appear
     prior to this completion in the visible part of the specification.

   - Each access type declaration in the abstract must have a conforming
     access type declaration in the visible part of the specification.

   - Each constant or named number declaration in the abstract must
     have a conforming constant or named number declaration in the
     visible part of the specification.

   - Each representation item in the abstract must have a conforming
     representation item in the specification.

If an access type is declared in a package abstract, all aspects of
its representation except for its storage pool are frozen at the end
of the package abstract.  As indicated above, the access type
must not be pool-specific.

The only representation items permitted in the package specification
for the access type are those that conform to representation items
appearing in the abstract, and those that apply to the storage
pool of the type (Storage_Pool, Storage_Size).

The actual "collection" for the access type is not created until
the package specification is elaborated.  An allocator is illegal for an
access type declared in an abstract, though not for the corresponding
access type declared in the specification.  Similarly, an access
type in an abstract must not be passed as an actual for a formal
access type in a generic instantiation.


ABSTRACT WITH CLAUSE:

   abstract_with_clause ::=
        ABSTRACT WITH library_unit_package_name {, library_unit_package_name};

An abstract with clause on a compilation unit makes the abstract of
each specified package visible within the compilation unit, and hides
the specification of the package even if it is visible due to a with
clause on some ancestor (or corresponding declaration) compilation unit.
Similarly, a (normal) with clause on a compilation unit
makes the specification visible, and hides the abstract even
if some ancestor (or corresponding declaration) compilation unit made it
visible.  A given compilation unit must not mention a package in a (normal)
with clause and specify the same package in an abstract with clause.
[NOTE: This is to ensure that order of with clauses does not matter.]

Within the abstract for a child package, if the abstract of
its parent is not already visible due to an abstract with clause,
then the visible part of the specification of the parent is visible.
Hence the abstract of the child has direct visibility on only the declarations
of the abstract of the parent if the abstract of the parent is visible.
If the abstract of the parent is visible, then either the specification
or abstract of further ancestors is visible corresponding to which
is visible in the abstract of the parent.

If a package specified by an abstract with clause on some compilation unit
is a child package, then either the specification
or abstract of its parent and each further ancestor is made visible
within the compilation unit, as determined by which is visible within
the specified child.

If an abstract or specification of a package is made visible by
an abstract with clause, then a semantic dependence
is created on that part of the package.  [This in turn implies
an elaboration dependence -- see 10.2(9).]
The specification of a package has a semantic dependence on its
abstract, if any.

NOTE: At no point should both the specification and the abstract of a package
be visible by the "same" name.  However, (a rename of) the specification
may be visible under one name, while (a rename of?) the abstract is visible
under a different name.

[TBD: Should "package abstract P renames Q;" be supported?  Seems OK.]
[TBD: Should a package abstract be permitted as a local package?
   I don't see why not...]
[TBD: Should package renames be permitted inside of a package abstract?
   Seems unnecessary.]

INCOMPLETE TAGGED TYPE:

   incomplete_type_declaration ::=
       TYPE defining_identifier [discrminant_part] [IS 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 would be considered obsolescent.

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.)
may also be used as the type of a formal parameter.

!discussion

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 wheter 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.

There seem to be two general ways this kind of problem 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.
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.

!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.

    package abstract Employees is
        type Employee;
        type Emp_Ptr is access all Employee;
    end Employees;

    package abstract Departments is
        type Department;
        type Dept_Ptr is access all Department;
    end Departments;

    abstract with Departments;
    package Employees is
        type Employee is private;
        type Emp_Ptr is access all Employee;
        procedure Assign_Employee(E : access Employee;
          D : access Departments.Department);
        ...
        function Current_Department(D : access constant Employee) return
          Departments.Dept_Ptr;
    end Employees;

    abstract with Employees;
    package Departments is
        type Department is private;
        type Dept_Ptr is access all Department;
        procedure Choose_Manager(D : access Department;
          Manager : access Employees.Employee);
        ...
    end Departments;


Questions? Ask the ACAA Technical Agent