Rationale for Ada 2005
4.2 Mutually dependent types
For many programmers the solution of the problem
of mutually dependent types will be the single most important improvement
introduced in Ada 2005.
This topic was discussed
in the Introduction using an example of two mutually dependent types,
Point and Line.
Each type needed to refer to the other in its declaration and of course
the solution to this problem is to use incomplete types. In Ada 95 there
are three stages. We first declare the incomplete types
type Point; -- incomplete types
type Line;
Suppose for simplicity that we wish to study patterns
of points and lines such that each point has exactly three lines through
it and that each line has exactly three points on it. (This is not so
stupid. The two most fundamental theorems of projective geometry, those
of Pappus and Desargues, concern such structures and so does the simplest
of finite geometries, the Fano plane.)
Using the incomplete
types we can then declare
type Point_Ptr is access Point; -- use incomplete types
type Line_Ptr is access Line;
and finally we can
complete the type declarations thus
type Point is -- complete the types
record
L, M, N: Line_Ptr;
end record;
type Line is
record
P, Q, R: Point_Ptr;
end record;
Of course, in Ada 2005,
as discussed in the previous chapter (see
3.3),
we can use anonymous access types more freely so that the second stage
can be omitted in this example. As a consequence the complete declarations
are simply
type Point is -- complete the types
record
L, M, N: access Line;
end record;
type Line is
record
P, Q, R: access Point;
end record;
This has the important advantage that we do not have
to invent irritating identifiers such as Point_Ptr.
But we will stick to
Ada 95 for the moment. In Ada 95 there are two rules
- the incomplete type can only be used
in the definition of access types;
- the complete type declaration must
be in the same declarative region as the incomplete type.
The first rule does
actually permit
type T;
type A is access procedure (X: in out T);
Note that we are here using the incomplete type T
for a parameter. This is not normally allowed, but in this case the procedure
itself is being used in an access type. The additional level of indirection
means that the fact that the parameter mechanism for T
is not known yet does not matter.
Apart from this, it
is not possible to use an incomplete type for a parameter in a subprogram
in Ada 95 except in the case of an access parameter. Thus we cannot have
function Is_Point_On_Line(P: Point; L: Line) return Boolean;
before the complete type declarations.
It is also worth pointing
out that the problem of mutually dependent types (within a single unit)
can often be solved by using private types thus
type Point is private;
type Point_Ptr is access Point;
type Line is private;
type Line_Ptr is access Line;
private
type Point is
record
L, M, N: Line_Ptr;
end record;
type Line is
record
P, Q, R: Point_Ptr;
end record;
But we need to use incomplete types if we want the
user to see the full view of a type so the situation is somewhat different.
As an aside, remember that if an incomplete type
is declared in a private part then the complete type can be deferred
to the body (this is the so-called Taft Amendment in Ada 83). In this
case neither the user nor indeed the compiler can see the complete type
and this is the main reason why we cannot have parameters of incomplete
types whereas we can for private types.
We will now introduce
what has become a canonical example for discussing this topic. This concerns
employees and the departments of the organization in which they work.
The information about employees needs to refer to the departments and
the departments need to refer to the employees. We assume that the material
regarding employees and departments is quite large so that we naturally
wish to declare the two types in distinct packages Employees
and Departments. So we would like to say
with Departments; use Departments;
package Employees is
type Employee is private;
procedure Assign_Employee(E: in out Employee; D: in out Department);
type Dept_Ptr is access all Department;
function Current_Department(E: Employee) return Dept_Ptr;
...
end Employees;
with Employees; use Employees;
package Departments is
type Department is private;
procedure Choose_Manager(D: in out Department; M: in out Employee);
...
end Departments;
We cannot write this because each package has a with
clause for the other and they cannot both be declared (or entered into
the library) first.
We assume of course that the type Employee
includes information about the Department
for whom the Employee works and the type Department
contains information regarding the manager of the department and presumably
a list of the other employees as well – note that the manager is
naturally also an Employee.
So in Ada 95 we are
forced to put everything into one package thus
package Workplace is
type Employee is private;
type Department is private;
procedure Assign_Employee(E: in out Employee; D: in out Department);
type Dept_Ptr is access all Department;
function Current_Department(E: Employee) return Dept_Ptr;
procedure Choose_Manager(D: in out Department; M: in out Employee);
private
...
end Workplace;
Not only does this give rise to huge cumbersome packages
but it also prevents us from using the proper abstractions. Thus the
types Employee and Department
have to be declared in the same private part and so are not protected
from each other's operations.
Ada 2005 solves this by introducing a variation of
the with clause – the limited with clause. A limited with clause
enables a library unit to have an incomplete view of all the visible
types in another package. We can now write
limited with Departments;
package Employees is
type Employee is private;
procedure Assign_Employee(E: in out Employee; D: access Departments.Department);
type Dept_Ptr is access all Departments.Department;
function Current_Department(E: Employee) return Dept_Ptr;
...
end Employees;
limited with Employees;
package Departments is
type Department is private;
procedure Choose_Manager(D: in out Department; M: access Employees.Employee);
...
end Departments;
It is important to understand that a limited with
clause does not impose a dependence. Thus if a package A
has a limited with clause for B, then A
does not depend on B as it would with a normal
with clause, and so B does not have to be
compiled before A or placed into the library
before A.
If we have a cycle of packages we only have to put
limited with on one package since that is sufficient to break
the cycle of dependences. However, for symmetry, in this example we have
made them both have a limited view of each other.
Note the terminology: we say that we have a limited
view of a package if the view is provided through a limited with clause.
So a limited view of a package provides an incomplete view of its visible
types. And by an incomplete view we mean as if they were incomplete types.
In the example, because an incomplete view of a type
cannot generally be used as a parameter, we have had to change one parameter
of each of Assign_Employee and Choose_Manager
to be an access parameter.
Having broken the circularity we can then put normal
with clauses for each other on the two package bodies.
There are a number of rules necessary to avoid problems.
A natural one is that we cannot have both a limited with clause and a
normal with clause for the same package in the same context clause (a
normal with clause is now officially referred to as a nonlimited with
clause). An important and perhaps unexpected rule is that we cannot have
a use package clause with a limited view because severe surprises might
happen.
To understand how this
could be possible it is important to realise that a limited with clause
provides a very restricted view of a package. It just makes visible
- the name of the package and packages
nested within,
- an incomplete view of the types declared
in the visible parts of the packages.
Nothing else is visible
at all. Now consider
package A is
X: Integer := 99;
end A;
package B is
X: Integer := 111;
end B;
limited with A, B;
package P is
... -- neither X visible here
end P;
Within package P
we cannot access A.X or B.X
because they are not types but objects. But we could declare a child
package with its own with clause thus
with A;
package P.C is
Y: Integer := A.X;
end P.C;
The nonlimited with clause on the child "overrides"
the limited with clause on the parent so that A.X
is visible.
Now suppose we were
allowed to add a use package clause to the parent package; since a use
clause on a parent applies to a child this means that we could refer
to A.X as just X
within the child so we would have
limited with A, B;
use A, B; -- illegal
package P is
... -- neither X visible here
end P;
with A;
package P.C is
Y: Integer := X; -- A.X now visible as just X
end P.C;
If we were now to change the with clause on the child
to refer to B instead of A,
then X would refer to B.X
rather than A.X. This would not be at all
obvious because the use clause that permits this is on the parent and
we are not changing the context clause of the parent at all. This would
clearly be unacceptable and so use package clauses are forbidden if we
only have a limited view of the package.
Here is a reasonably
complete list of the rules designed to prevent misadventure when using
limited with clauses
- a use
package clause cannot refer to a package with a limited view as illustrated
above,
limited with P; use P; -- illegal
package Q is ...
limited with P;
package Q is
use P; -- illegal
- a limited
with clause can only appear on a specification – it cannot appear
on a body or a subunit,
limited with P; -- illegal
package body Q is ...
- a limited
with clause and a nonlimited with clause for the same package may not
appear in the same context clause,
limited with P; with P; -- illegal
- a limited
with clause and a use clause for the same package or one of its children
may not appear in the same context clause,
limited with P; use P.C; -- illegal
- a limited
with clause may not appear in the context clause applying to itself,
limited with P; -- illegal
package P is ...
- a limited
with clause may not appear on a child unit if a nonlimited with clause
for the same package applies to its parent or grandparent etc,
with Q;
package P is ...
limited with Q; -- illegal
package P.C is ...
but note that the
reverse is allowed as mentioned above
limited with Q;
package P is ...
with Q; -- OK
package P.C is ...
- a limited
with clause may not appear in the scope of a use clause which names the
unit or one of its children,
with A;
package P is
package R renames A;
end P;
with P;
package Q is
use P.R; -- applies to A
end Q;
limited with A; -- illegal
package Q.C is ...
without this specific rule, the use clause in Q
which actually refers to A would clash with
the limited with clause for A.
Finally note that a limited with clause can only
refer to a package declaration and not to a subprogram, generic declaration
or instantiation, or to a package renaming.
We will now return to the rules for incomplete types.
As noted above the rules for incomplete types are quite strict in Ada
95 and apart from the curious case of an access to subprogram type it
is not possible to use an incomplete type for a parameter other than
in an access parameter.
Ada 2005 enables some
relaxation of these rules by introducing tagged incomplete types. We
can write
type T is tagged;
and then the complete
type must be a tagged type. Of course the reverse does not hold. If we
have just
type T;
then the complete type T
might be tagged or not.
A curious feature of
Ada 95 was mentioned in the Introduction. In Ada 95 we can write
type T;
...
type T_Ptr is access all T'Class;
By using the attribute
Class, this promises in a rather sly way that
the complete type
T will be tagged. This is
strictly obsolescent in Ada 2005 and moved to
Annex
J. In Ada 2005 we should write
type T is tagged;
...
type T_Ptr is access all T'Class;
The big advantage of introducing tagged incomplete
types is that we know that tagged types are always passed by reference
and so we are allowed to use tagged incomplete types for parameters.
This advantage extends to the incomplete view obtained
from a limited with clause. If a type in a package is visibly tagged
then the incomplete view obtained is tagged incomplete and so the type
can then be used for parameters.
Returning to the packages
Employees and Departments
it probably makes sense to make both types tagged since it is likely
that the types Employee and Department
form a hierarchy. So we can write
limited with Departments;
package Employees is
type Employee is tagged private;
procedure Assign_Employee(E: in out Employee; D: in out Departments.Department'Class);
type Dept_Ptr is access all Departments.Department'Class;
function Current_Department(E: Employee) return Dept_Ptr;
...
end Employees;
limited with Employees;
package Departments is
type Department is tagged private;
procedure Choose_Manager(D: in out Department; M: in out Employees.Employee'Class);
...
end Departments;
The text is a bit cumbersome
now with
Class sprinkled liberally around
but we can introduce some subtypes in order to shorten the names. We
can also avoid the introduction of the type
Dept_Ptr
since we can use an anonymous access type for the function result as
mentioned in the previous chapter (see
3.3).
So we get
limited with Departments;
package Employees is
type Employee is tagged private;
subtype Dept is Departments.Department;
procedure Assign_Employee(E: in out Employee; D: in out Dept'Class);
function Current_Department(E: Employee) return access Dept'Class;
...
end Employees;
limited with Employees;
package Departments is
type Department is tagged private;
subtype Empl is Employees.Employee;
procedure Choose_Manager(D: in out Department; M: in out Empl'Class);
...
end Departments;
Observe that in Ada
2005 we can use a simple subtype as an abbreviation for an incomplete
type thus
subtype Dept is Departments.Department;
but such a subtype cannot have a constraint or a
null exclusion. In essence it is just a renaming. Remember that we cannot
have a use clause with a limited view. Moreover, many projects forbid
use clauses anyway but permit renamings and subtypes for local abbreviations.
It would be a pain if such abbreviations were not also available when
using a limited with clause.
It's a pity we cannot
also write
subtype A_Dept is Departments.Department'Class;
but then you cannot have everything in life.
A similar situation arises with the names of nested
packages. They can be renamed in order to provide an abbreviation.
The mechanism for breaking cycles of dependences
by introducing limited with clauses does not mean that the implementation
does not check everything thoroughly in a rigorous Ada way. It is just
that some checks might have to be deferred. The details depend upon the
implementation.
For the human reader it is very helpful that use
clauses are not allowed in conjunction with limited with clauses since
it eliminates any doubt about the location of types involved. It probably
helps the poor compilers as well.
Readers might be interested to know that this topic
was one of the most difficult to solve satisfactorily in the design of
Ada 2005. Altogether seven different versions of
AI-217
were developed. This chosen solution is on reflection by far the best
and was in fact number 6.
A number of loopholes in Ada 95 regarding incomplete
types are also closed in Ada 2005.
One such loophole is
illustrated by the following (this is Ada 95)
package P is
...
private
type T; -- an incomplete type
type ATC is access all T'Class; -- it must be tagged
X: ATC;
procedure Op(X: access T); -- primitive operation
...
end P;
The incomplete type
T
is declared in the private part of the package
P.
The access type
ACT is then declared and since
it is class wide this implies that the type
T
must be tagged (the reader will recall from the discussion above that
this odd feature is banished to
Annex
J in Ada 2005). The full type
T is then
declared in the body. We also declare a primitive operation
Op
of the type
T in the private part.
However, before the
body of P is declared, nothing in Ada 95 prevents
us from writing a private child thus
private package P.C is
procedure Naughty;
end P.C;
package body P.C is
procedure Naughty is
begin
Op(X); -- a dispatching call
end Naughty;
end P.C;
and the procedure Naughty
can call the dispatching operation Op. The
problem is that we are required to compile this call before the type
T is completed and thus before the location
of its tag is known.
This problem is prevented in Ada 2005 by a rule that
if an incomplete type declared in a private part has primitive operations
then the completion cannot be deferred to the body.
Similar problems arise
with access to subprogram types. Thus, as mentioned above, Ada 95 permits
type T;
type A is access procedure (X: in out T);
In Ada 2005, the completion of T
cannot be deferred to a body. Nor can we declare such an access to subprogram
type if we only have an incomplete view of T
arising from a limited with clause.
Another change in Ada
2005 can be illustrated by the Departments
and Employees example. We can write
limited with Departments;
package Employees is
type Employee is tagged private;
procedure Assign_Employee(E: in out Employee; D: in out Departments.Department'Class);
type Dept_Ptr is access all Departments.Department'Class;
...
end Employees;
with Employees; use Employees;
procedure Recruit(D: Dept_Ptr; E: in out Employee) is
begin
Assign_Employee(E, D.all);
end Recruit;
Ada 95 has a rule that says "thou shalt not
dereference an incomplete type". This would prevent the call of
Assign_Employee which is clearly harmless.
It would be odd to require Recruit to have
a nonlimited with clause for Departments to
allow the call of Assign_Employee. Accordingly
the rule is changed in Ada 2005 so that dereferencing an incomplete view
is only forbidden when used as a prefix as, for example, in D'Size.
© 2005, 2006 John Barnes Informatics.
Sponsored in part by: