Version 1.1 of ai05s/ai05-0074-4.txt

Unformatted version of ai05s/ai05-0074-4.txt version 1.1
Other versions for file ai05s/ai05-0074-4.txt

!standard 3.9.3 (9)          09-02-15 AI05-0074-4/01
!standard 3.10.1 (10/2)
!standard 7.3 (4)
!standard 7.3.1 (12/2)
!standard 7.3.1 (13)
!standard 10.2.1 (17/2)
!standard 12.3 (12)
!standard 12.3.1(1-28)
!class amendment 09-02-15
!status work item 09-02-15
!status received 09-02-15
!priority Medium
!difficulty Hard
!subject Private Instantiations and Incomplete Instantiations
!summary
(See proposal.)
!problem
Ada 95 provides formal package parameters. One way of using these parameters is to define a "signature" for a class of abstractions, such as all set abstractions, or all physical unit abstractions, and then build a new generic abstraction on top of the original class of abstractions using this signature as the template for a formal package parameter.
Unfortunately, it is difficult to use signatures because of the fact that an instantiation freezes all of its actual parameters.
For example:
Given the signature for a set abstraction:
generic type Element is private; type Set is private; with function Size(Of_Set : Set) return Natural is <>; with function Union(Left, Right : Set) return Set is <>; with function Intersection(Left, Right : Set) return Set is <>; with function Empty return Set is <>; with function Unit_Set(With_Item : Element) return Set is <>; with function Nth_Element(Of_Set : Set) return Element is <>; package Set_Signature is end; ...
we could define a generic that required some set abstraction, but it didn't care which one so long as it implemented the above signature:
generic with package Base_Set is new Set_Signature(<>); package Layered_Abstraction is type Cool_Type(Set : access Base_Set.Set) is limited_private; procedure Massage(CT : in out Cool_Type; New_Set : Base_Set.Set); ... end Layered_Abstraction;
Now if we want to define a set type and provide the pre-instantiated signature for it, we run into trouble:
generic type Elem is private; with function Hash(El : Elem) return Integer; package Hashed_Sets is
type Set is private; function Union(Left, Right : Set) return Set; ...
package Signature is new Set_Signature(Elem, Set); private type Set is record ... end record; end Hashed_Sets;
The problem is that we can't do the instantiation of Set_Signature where we would want to do so, because the instantiation freezes the type "Set" prematurely.
A similar problem occurs when a type wants to include a pointer to a container based on the type being defined.
For example:
with Sequences; package Expressions is type Expr_Ref is private; package Expr_Sequences is new Sequences(Expr_Ref); -- Freezing trouble here! type Seq_Of_Expr is access Expr_Sequences.Sequence; function Operands(Expr : Expr_Ref) return Seq_Of_Expr; ... private type Expression; -- completion deferred to body type Expr_Ref is access Expression; end Expressions;
Here we have a case where we want to instantiate a generic using a private type, and use the results of the instantiation as the designated type of an access type, which is in turn used as a parameter or result type of an operation on the private type.
Unfortunately, we can't instantiate the "Sequences" generic with Expr_Ref, since it is private.
!proposal
Introduce new syntax (a private_instantiation_declaration) that exports a view of a generic instance declared in the private part of a package specification so that a type with a partial view in the visible part of the package can be used as an actual in the instantiation.
The real generic_instantiation that completes a private_instantiation_declaration is explicitly placed after the full_type_declaration that completes the type with the partial view, so there are no freezing concerns with the generic instance, nor is there a need to change rules or add restrictions to the generic contract model.
Two types of views of an instance are defined. (A partial view of an instance, and a full view of an instance.) A partial view of an instance is associated with a private_instantiation_declaration. A full view of an instance is equivalent to the view of the instance provided by the generic_instantiation that completes the partial view at the site of the completion.
A private_instantiation_declaration declares two views of an instance. (A partial view of the instance, and the full view of the instance). A partial view of the instance applied to the immediately enclosing declarative region, while the full view is available to outside program units.
Semantically, it is as though a partial view of an instance sees a copy of the generic template, but the mapping from actuals to formals (and the corresponding substitutions) has not taken place yet, so the view has to make certain limiting assumptions about the types that are exported from the view.
For a partial view of an instance, it is assumed that every visible composite type declaration of the instance (other than array types) have been derived from a formal type that has a partial view (an assume the worst rule), thus each such exported type from the view is considered to have a partial view until the completion of the partial view of the instance.
A private type or private extenstion cannot directly contain a component of a composite type from the partial view of an instance, since such an exported type may have been derived from a formal which may be the private type or private extension. An array type would be allowed, but only if the components of the array are not composite types, as these situations otherwise could potentially create an illegal circular type. The full_type_declaration of a private type or private extension however may define a recursive data structure using access types to designate objects of a type from the partial view of the instance. If the view of the type is a tagged view, then private extension derivations are allowed before the completion of the partial view of the instance.
A partial view of an instance does not include any object declarations in the instance, which prevents any references to objects in the instance until the generic_instantiation that completes the partial or incomplete view of the instance. It is also not allowed to declare any objects of types exported from the partial or incomplete view of the instance until the completion of the partial or incomplete view.
The syntax for a private_instantiation_declaration allows that actual parameters can be left unspecified until the private part of the package specification. This provides opportunities for improved data hiding and abstractions. Actuals for formal types and formal packagese cannot be deferred to the private part, but all other formals can. If the actual is visible at the place of a private_instantiation_declaration than it must be explictly named in the private_instantiation_declaration unless the formal has a default value or initialization.
!wording
Change 3.9.3 (9)
If a partial view {of a type} is not abstract, the corresponding full view shall not be abstract. If a generic formal type is abstract, then for each primitive subprogram of the formal that is not abstract, the corresponding primitive subprogram of the actual shall not be abstract.
Change 3.10.1 (10/2)
A prefix that denotes an object shall not be of an incomplete view {of a type}.
Change 7.3 (4)
A private_type_declaration or private_extension_declaration declares a partial view of the type; such a declaration is allowed only as a declarative_item of the visible part of a package, and it requires a completion, which shall be a full_type_declaration that occurs as a declarative_item of the private part of the package. The view of the type declared by the full_type_declaration is called the full view. A generic formal private type or a generic formal private extension is also a partial view {of a type. The view of a composite type of a partial view of an instance (see 12.3.1) that does not have an incomplete view and is not an array type, is a partial view of the type}.
AARM
4.a.1 All composite types (Record types, protected types, task types, etc) other than array types need to have the same restrictions as a private type or private extension if they are exported from a partial view of an instance, because we do not want to allow components of these types to be declared before the declaration of the full view of an instance that completes the partial view of the instance. Note that while an array type can be declared as a component of a type, it cannot be declared as a component of a private type or private extension if it has composite components because it is assumed that the components of the array have been derived from the private type or private extension.
Change 7.3.1 (12/2)
10 Partial views {of a type} provide initialization, membership tests, selected
components for the selection of discriminants and inherited components,
qualification, and explicit conversion. Nonlimited partial views also allow use of assignment_statements.
Change 7.3.1 (13) 11 For a subtype S of a partial view {of a type}, S'Size is defined (see 13.3). For an object A of a partial view {of a type}, the attributes A'Size and A'Address are defined (see 13.3). The Position, First_Bit, and Last_Bit attributes are also defined for discriminants and inherited components.
Change 10.2.1 (17/2)
A pragma Pure is used to declare that a library unit is pure. If a pragma Pure
applies to a library unit, then its compilation units shall be pure, and they shall depend semantically only on compilation units of other library units that are declared pure. Furthermore, the full view of any partial view {of a type} declared in the visible part of the library unit that has any available stream attributes shall support external streaming (see 13.13.2).
Change 12.3 (12)
A generic_instantiation declares {(a view of)} an instance; it is equivalent to the instance declaration (a package_declaration or subprogram_declaration) immediately followed by the instance body, both at the place of the instantiation.
Add new section: 12.3.1 Private Instantiations and Incomplete Instantiations
Add 12.3.1(1 - 31):
1 The declaration (in the visible part of a package) of a private instantiation serves to allow a generic package to be instantiated with an actual that has a partial view of a type.
SYNTAX
2 private_instantiation_declaration ::=
PACKAGE defining_program_unit_name IS
         PRIVATE NEW generic_package_name [deferred_generic_actual_part];   3 deferred_generic_actual_part ::=     (deferred_generic_association {, deferred_generic_association})
4 deferred_generic_association ::=     [generic_formal_parameter_selector_name =>] explicit_generic_actual_parameter
| [generic_formal_parameter_selector_name =>] PRIVATE | OTHERS => PRIVATE
5 A deferred_generic_association is named or positional according to whether or not the generic_formal_parameter_selector_name is specified. Any positional associations shall precede any named associations. If there is an association with the rserved word OTHERS, it shall come last.
LEGALITY RULES
6 A private_instantiation_declaration declares both a Partial View and a Full View of an instance; such a declaration is allowed only as a declarative_item of the visible part of a package, and it requires a completion, which shall be a generic_instantiation of a package. The completion of a private_instantiation_declaration occurs as a declarative_item of the private part of the package.
7 The generic_formal_parameter_selector_name of a deferred_generic_association shall denote a generic_formal_parameter_declaration of the generic unit being instantiated if the deferred_generic_association has an explicit_generic_actual_parameter. If two or more formal subprograms have the same defining name, then named associations are not allowed for the corresponding actuals.
8 A private_instantiation_declaration shall contain at most one deferred_generic_association for each formal. Each formal without an association shall have a default_expression or subprogram_default.
9 The actual parameters of a private_instantiation_declaration shall match the corresponding actual parameters of the completion, whether the actual parameters are given explicitly or by default.
10 The rules for matching of actual parameters between the completion and the private instantiation are as follows:
11 * A named association with the reserved word OTHERS matches all needed
actual parameters from the completion that are not associated with some previous association.
12 * If an association is a named association in the private instantiation
then the association shall be a named association in the completion unless the actual parameters are given by default and the association has the reserved word OTHERS in the private instantiation. If an association is a positional association in the private instantiation then the association shall be positional in the completion.
13 * An association with the reserved word PRIVATE but without the reserved
word OTHERS matches the actual of the completion that has the same generic_formal_parameter_selector_name if the association is a named association, or the actual in the corresponding relative position within the generic_actual_part if the association is a positional association.
14 * For a formal object of mode IN the actuals match if they are static
expressions with the same value, of if they statically denote the same constant, or if they are both the literal NULL.
15 * For a formal subtype, the actuals match if they denote statically
matching subtypes.
16 * For other kinds of formals, the actuals match if they statically
denote the same entity.
AARM NOTE: We considered using full conformance rules here instead of
formal-package-ish matching. However, we wanted to use rules consistent with formal packages, and it seemed simpler to just define the particular matching rules needed between instantiations. Also we wanted to ensure that no evaluations would take place at the point of the private instantiation.
17 If the actual of a generic_instantiation that completes a private_instantiation_declaration is visible at the place of the private_instantiation_declaration then there shall be a deferred_generic_association with an explicit_generic_actual_parameter that names the actual, if the associated formal does not have a default_expression or subprogram_default.
18 A private_instantiation_declaration shall not have a deferred_generic_association with an explicit_generic_actual_parameter that has an incomplete view at the place of the private_instantiation_declaration.
19 A private_instantiation_declaration shall have a deferred_generic_association with an explicit_generic_actual_parameter for every formal_type_declaration and formal_package_declaration of the completion.
20 Neither the declaration of a variable of a type from a partial view of an instance, nor the creation by an allocator of an object of a type from the view of the instance, are allowed before the completion of a private_instantiation_declaration. Similarly, before the completion, such a type cannot be used in a generic_instantiation or in a representation item.
21 All visible composite types other than an array type of a partial view of an instance that do not have an incomplete view have a partial view. If the view of the type is a tagged view, then the view of the type is a tagged partial view.
AARM
21.a Ramification: It is assumed that all such types have been derived from a formal type that has a partial view, or contains a component of a formal type that has a partial view (An assume the worst rule). By saying that these types have partial views, it prevents the declaration of illegal recursive types, or declaring other composite types with components that have a partial view of a type before the completion of the partial view of the instance in the private part. An derivative of an array type is allowed to be declared, but if the components of the array are composite types then the array is considered to be an array of types that have a partial view. This prevents the declaration of an array component within the completion of a private type or private extension which could lead to an illegal recursive type declaration.
22 The partial view of a type of an explicit_generic_actual_parameter of a deferred_generic_association must be conformant to the formal type declaration of the generic package specification. Specifically, if the partial view of a type is a limited view, then the formal_private_type_definition shall have the reserved word LIMITED in the formal type declaration. If the partial view of a type is an untagged view, then the formal_private_type_definition shall not have the reserved word TAGGED in the formal type declaration.
AARM
22.a This rule is needed because the full view of an untagged limited partial view may be of a type with an unlimited view. Similarly, a full view of an untagged partial view may be of a type that has a tagged view. We dont want to allow a generic_instantiation in the private part of a package that conflicts with the declarations of the actuals used in a private_instantiation_declaration.
STATIC SEMANTICS
23 A private_instantiation_declaration declares a private instantiation.
24 A private_instantiation_declaration defines two views of a generic instance. The declaration of a partial view of an instance defines the operations that are available within the immediately enclosing declarative region. The declaration of the full view defines the operations that are available to outside program units. The full view is equivalent to the view of the instance declared by the generic_instantiation that completes the private_instantiation_declaration.
25 A partial view of an instance is a view of a copy of the text of the generic template whereby the substitution of formal parameters with actual parameters has not taken place, and the mappings of actual parameters to formal parameters of the generic_instantiation are considered to be unresolved.
26 A partial view of an instance does not include a view of any object declarations from the instance.
AARM
26.a We do not want to allow any references to objects of a private view of an instance until the completion of the deferred_instantiation_declaration. This is because the objects really do not come into existence until the generic_instantiation declaration.
NOTES
27 The full_type_declaration that completes a partial view of a type cannot declare a component of a type from a partial view of an instance because it is assumed that any type of the instance could have been derived from the type with the partial view, and thus could potentially create an illegal circular data type.
28 A new type cannot be derived from a type from a partial view of an instance unless the type is a tagged type, since such a type may have been derived (directly or indirectly) from an actual that has a partial view. Such a derivation must be either a tagged private type or a tagged private extension.
!discussion
This proposal solves several problems that come up frequently in practice with private types. Certainly the most common is a desire to include an instantiation of a generic (possibly a signature generic as mentioned in the "problem" section above, or perhaps a container generic), with a private type as one of the actual parameters to the instantiation.
A second problem is a desire to be able to have a recursive data structure where a type declaration can contain a component that designates a type from an instance that was instantiated with an actual of the composite type.
An instantiation requires the type of an actual to be defined first, and since the instantiation comes after the type declaration, the type declaration cannot name any type declarations of the instantiation.
A third problem extends from the second problem as it is desirable that it be possible to declare such a recursive data structure that has a primitive that has a formal parameter of the type of a component that designates an object of an instantiated type or returns a result value of a component that designates an object of an instantiated type.
A fourth problem is another variant of the third, where it is desirable that it be possible to declare such a recursive data structure that has a primitive that has a formal parameter of the type of a component that is an instantiated type, or returns a result value of a component that is an instantiated type. In addition, we would like it to be possible to declare such a recursive type as a remote access to class wide type allowing usage in distributed applications.
A fifth problem is a desire to export a type derived from a tagged type that is exported from a generic instance that has a private type as one of the actual parameters.
A sixth problem is a desire to instantiate a generic in the visible part of a package, yet defer the declarations for some or all of the actuals to the private part of the package.
The basic idea of this proposal is to add syntax that provides more flexibility and capabilities for exporting functionality in the visible part of a package specification, creating recursive data structures, and hiding implementation details in the private part of a package specification.
This proposal is limited to packages because you can use renaming-as-body to get these effects for subprogram instantiations. Moreover, you cannot export a type from a generic subprogram, so there is no possibility of recursive use. [Note that we could lift this limitation if it if felt to be more regular.]
Ada 2005 provides solutions to some of these problems, but they are not ideal. For the first example, making the instantiation a child unit solves the problem. However, this is annoying, because accessing the instance requires an extra with and instantiation (since children of generics must be generic):
generic type Elem is private; with function Hash (El : Elem) return Integer; package Hashed_Sets is type Set is private; function Union(Left, Right : Set) return Set; ... private type Set is record ... end record; end Hashed_Sets;
generic package.Hashed_Sets.Signature is package The_Signature is new Set_Signature(Elem, Set); end Hashed_Sets.Signature;
A user of Hashed_Sets must with and instantiate Hashed_Sets.Signature in order to access the instance.
A simpler alternative involves the use of nested packages. This is better, but introducing a nested package can still be considered to be awkward.
generic type Elem is private; with function Hash (El : Elem) return Integer; package Hashed_Sets is package Sets is type Set is private; function Union(Left, Right : Set) return Set; private type Set is record ... end record; end Sets;
use Sets; package The_Signature is new Set_Signature(Elem, Set);
end Hashed_Sets;
The second problem can also be solved in some cases with child units, using the limited with:
with Sequences; limited with Expressions.Sequences; package Expressions is type Expr_Ref is private; type Seq_Of_Expr is access Expressions.Sequences.Sequence; function Operands(Expr : Expr_Ref) return Seq_Of_Expr; ... private type Expression; -- completion deferred to body type Expr_Ref is access Expression; end Expressions;
package Expressions.Sequences is package Expr_Sequences is new Sequences(Expr_Ref); type Sequence is new Expr_Sequences.Sequence; end Expressions.Sequences;
Here, besides the extra with clause, we need to declare an extra type simply so that the type is visible to the limited with clause (which operates purely syntactally). This means that extra type conversions are necessary. Another limitation is that this technique requires a type derivation (Sequence), and would not work for types that cannot be extended, such as synchronized tagged types.
Once again, the use of nested packages provides a simpler work around, but this still requires the extra type and having to declare a nested package can still be viewed as being awkward. Such a technique is something that would likely require the awareness of an expert Ada programmer, as it is questionable whether a less experienced programmer would come up with this technique on their own.
with Sequences; package Expression_Sequences is
type Expr_Seq; -- incomplete type type Seq_Of_Expr is access Expr_Seq;
package Expressions is type Expr_Ref is private; function Operands(Expr : Expr_Ref) return Seq_Of_Expr; ... private type Expression; -- completion deferred to body type Expr_Ref is access Expression; end Expressions;
use Expressions;
package Expr_Sequences is new Sequences(Expr_Ref); type Expr_Seq is new Expr_Sequences.Sequence; --completion of incomplete type
end Expression_Sequences;
This proposal attempts to provide a more intuitive approach for solving these and other problems and eliminates limitations that currently exist in the language as well as introduce new capabilities for data hiding and better abstractions.
First of all, an important capability is to be able to instantiate a generic with a private type or private extension as an actual. The concept is to place the generic instantiation in the private part after the completion of the private type or private view, but provide a view of the instance in the visible part of the package that is exported to outside program units.
This new syntactic construct is called a partial_instantiation_declaration. This is a declaration that is placed in the visible part of a package. It is completed by a generic_instantiation in the private part of the package. We now say that a generic_instantiation declares a full view of an instance. A partial_instantiation_declaration also declares a full view of the instance, but that view is only available to outside program units. A partial_instantiation_declaration also declares what is called a partial view of an instance which only applies to the immediately enclosing declarative region. A partial_instantiation_declaration can be distinguished from a generic_instantiation by the use of the word PRIVATE in the syntax.
e.g.,
with Ada.Containers.Doubly_Linked_Lists; package Pkg is type T is private; package I is private new Ada.Containers.Doubly_Linked_Lists (T); private type T is null record; package I is new Ada.Containers.Doubly_Linked_Lists (T); end Pkg;
The intent is that the exported (full) view of the instance of I is effectively the same as the view if the generic had been instantiated from outside the enclosing package;
i.e.
with Ada.Containers.Doubly_Linked_Lists; package Pkg is
package Nested is type T is private; private type T is null record; end Nested;
use Nested; -- "use all Nested" would be better here package I is new Ada.Containers.Doubly_Linked_Lists (T); end Pkg;
Now suppose we would like type T to be a recursive structure having a component that designates a type provided by the partial view of the instance. In Ada 2005, it is currently possible to achieve this using an approach involving a nested package and an Incomplete Type declaration.
e.g.,
with Ada.Containers.Doubly_Linked_Lists; package Pkg is type List_Type;
package Nested is type T is private; private type T is record List : access List_Type; end record; end Nested;
use Nested; -- "use all Nested" would be better here package I is new Ada.Containers.Doubly_Linked_Lists (T); type List_Type is new I.List with null record; -- ERROR Cannot derive if I.List is a syncronized tagged type end Pkg;
Note that the programmer really just wants to instantiate a list of T in the visible part of the package. Here the programmer has had to jump through three mental hurdles to achieve this. The programmer has to think of declaring a nested package, declaring an incomplete type outside the nested package, and completing the an incomplete type with an derived type from an instance. It is quite likely that a reasonably experienced programmer would not come up with this solution on their own, and this would have to be filed away in a book of "tricks" to get around programming problems that one might run into.
This proposal provide an more intuitive syntax that more closely maps to what the programmer wanted to express. Compare the complexity of the visible part of the example above, with the two line visible part using the new proposed syntax below. One cannot help but have to mentally process the private part in the example above as well, whereas in the example below, the mind is much more at ease without having to peek at the private part. If Ada is supposed to be a language involving code that is written once but read many times, then the improved readability of the new syntax should continue to generate savings over the maintainance lifecycle of the software. e.g.
with Ada.Containers.Doubly_Linked_Lists; package Pkg is type T is private; package I is private new Ada.Containers.Doubly_Linked_Lists (T); private type T is record; List : access I.List; end record; package I is new Ada.Containers.Doubly_Linked_Lists (T); end Pkg;
Note also, that if we replace the use of Ada.Containers.Doubly_Linked_List with a different container such as a protected queue that inherits from a synchronous interface, then the Ada 2005 example above wont even compile whereas the new proposed syntax will compile. This is because it is currently not possible to derive a new type from a synchronized tagged type. The Ada 2005 version relies on a type derivation of the private type whereas the new proposed syntax does not involve any type derivations. One might argue that perhaps Ada 2005 should be modified to allow derivations of synchronized tagged types. That may be true and perhaps that capability will be added to the language at some point in the future, but still it is less than ideal that the programmer is being forced to derive a new type here, when it really has nothing to do with the abstraction.
Taking this example one step further. Suppose we now want to introduce a primitive subprogram that exports the value of a recursive component. In Ada 2005, the workaround example now becomes;
with Ada.Containers.Doubly_Linked_Lists; package Pkg is type List_Type; type List_Ref is access List_Type;
package Nested is type T is private; function Get_List (Item : T) return List_Ref; -- Cannot return anonymous access type here because function cannot -- be dispatching on more than one type private type T is record List : List_Ref; end record; end Nested;
use Nested; -- "use all Nested" would be better here package I is new Ada.Containers.Doubly_Linked_Lists (T); type List_Type is new I.List with null record; end Pkg;
Here we needed to introduce a named access type because otherwise the Get_List subprogram would generate a compile error because the Get_List function cannot be dispatching on more than one type.
With the new proposed syntax, there is little change other than the additional primitive, since the I.List has a partial view, it can be returned with an anonymous access type. With the proposed syntax, you have more of a choice whether to use named access types or not.
with Ada.Containers.Doubly_Linked_Lists; package Pkg is type T is private; package I is private new Ada.Containers.Doubly_Linked_Lists (T); function Get_List (Item : T) return access I.List; private type T is record; List : access I.List; end record; package I is new Ada.Containers.Doubly_Linked_Lists (T); end Pkg;
Now consider that we would like to make T a tagged type and we would like to export a primitive of the tagged private type that returns the value of an object of an instantiated type that is designated by a component.
In Ada 2005, we would modify the workaround example as follows;
e.g.,
with Ada.Containers.Doubly_Linked_Lists; package Pkg is type List_Type; type List_Ref is access List_Type;
package Nested is type T is tagged private; private type T is tagged record List : List_Ref; end record; end Nested;
use Nested; -- "use all Nested" would be better here package I is new Ada.Containers.Doubly_Linked_Lists (T); type List_Type is new I.List with null record; function Get_List (Item : T) return List_Type; end Pkg;
The Get_List function has to be declared after the instantiation outside the nested package where T is declared, since List_Type is an incomplete type from within the context of the Nested package and it is not possible to declare a function that returns a value of an incomplete type. The problem is that Get_List is not a primitive function of T. Any derivations of T do not include the Get_List primitive.
With the new proposal, this is not a problem because the type I.List has a partial view. (The partial view of an instance assumes that all exported types of the view may have been derived from a formal type and thus are considered to have a partial view) This means that Get_List can be declared as a primitive of T, and thus is inherited by any derived types of T.
with Ada.Containers.Doubly_Linked_Lists; package Pkg is type T is tagged private; package I is private new Ada.Containers.Doubly_Linked_Lists (T); function Get_List (Item : T) return I.List; private type T is tagged record; List : access I.List; end record; package I is new Ada.Containers.Doubly_Linked_Lists (T); end Pkg;
Now suppose we would like to use this example in a distributed application, as a Remote_Types package. We run into several problems and a fatal roadblock that prevents a compilable solution in Ada 2005.
The hopeless workaround code we get ends up looking like;
with Ada.Containers.Doubly_Linked_Lists; package Pkg is
pragma Remote_Types;
type List; -- Incomplete View type RACW_T; -- Incomplete_View of a RACW
-- type List_Ref is access List; -- ERROR Could not use List_Ref declaration because of E.2.2 (9/3) and -- E.2.2 (9.2/3). So we try to go back to using an anonymous access type
package Nested is type L is limited interface; type T is synchronized new L with private; procedure Create (Item : in out T; Other : access RACW_T); -- Not a RACW here because anonymous access type of an incomplete view -- Cant do this because of E.2.2 (14/3)
package Doubly_Nested is
function Get_List (Item : T) return access List; -- Needs to be doubly nested because otherwise compiler -- complains saying that operation can be dispatching in -- only one type -- ERROR: Nevermind, this wouldn't be allowed anyway because of -- E.2.2 (14/3)
end Doubly_Nested; -- BAD BAD BAD having to return access to protected component!!!
private
protected type T is new L with procedure Create (Item : access RACW_T); function Get_List return access List; -- Cant return List without it being an access type here, -- since nested package only sees incomplete view. private The_List : access List; end T;
end Nested;
type RACW_T is access all Nested.T'Class; -- RACW_T becomes a RACW here
package I is new Ada.Containers.Doubly_Linked_Lists (RACW_T);
type List is new I.List with null record; function Get_List (Item : Nested.T) return List;
end Pkg;
With the proposed new syntax, we actually get a working solution, without having to pull out any hair.
with Ada.Containers.Doubly_Linked_Lists; package Pkg is
pragma Remote_Types;
type L is limited interface; type T is synchronized new L with private; type RACW_T is access all T'class; procedure Create (Item : in out T; Other : RACW_T); package I is private new Ada.Containers.Doubly_Linked_Lists (RACW_T); function Get_List (Item : T) return I.List;
private
protected type T is new L with procedure Create (Item : RACW_T); function Get_List return I.List; private List : access I.List; end T;
package I is new Ada.Containers.Doubly_Linked_Lists (RACW_T);
end Pkg;
It seems worth considering whether anyone would want to write a distributed application with this form. It is not hard to come up with an good example. Suppose we wanted to write a distributed social networking application similar to facebook. Consider a Remote Types package representing a person (type T in the example above). A person has a list of friends or contacts which are also persons (The List in the example above). We might want another person to be able to remotely retrieve the list of friends from the RACW value representing a different person (The Get_List function in the example above) so that the other person can consider whether any of the friends from the resulting list are also friends of the other person.
It turns out there are other problems with syncronous types, even if we give up on the idea of trying to make the workaround work in a distributed application. Suppose we just want to have type T be a protected type in a recursive structure that stores a list of references to type T, where we want to have a primitive that returns the list of references.
In Ada 2005, the workaround initially becomes;
with Ada.Containers.Vectors; package Pkg is
type List; -- Incomplete View
package Nested is type List_Ref is access List; type L is limited interface; type T is synchronized new L with private; type T_Ref is access all T; procedure Initialize (Item : in out T; Id : Natural); function "=" (L, R : T) return Boolean; procedure Append (Item : in out T; Other : T); function Get_List (Item : T) return List_Ref; -- BAD BAD BAD access to protected component!!!
private
protected type T is new L with procedure Initialize (Id : Natural); procedure Append (Item : T_Ref); function Id return Natural; function Get_List return List_Ref; -- Cant return List without it being an access type here, -- since nested package only sees incomplete view. -- This is BAD! Access to protected component! private Unique_Id : Natural; The_List : List_Ref; end T; end Nested;
package I is new Ada.Containers.Vectors (Index_Type => Natural, Element_Type => Nested.T_Ref, "=" => Nested."=");
type List is new I.Vector with null record; function Unsafe_Get_List (Item : Nested.T) return List; -- Looks safe but it really isnt because it has to get -- a pointer to a protected list, while it is copying the -- list in the return value, someone else could be -- modifying it.
end Pkg;
The problem here is that we are forced to return an access to a component of a protected object. This object (an access to Vector) is not safe to use because when Unsafe_Get_List is called, under the covers it has to call the Get_List protected function, and then return the dereferenced value. While Unsafe_Get_List is building the return object by dereferencing the return value, another task could be modifying the list via the Append call. This could lead to a nasty memory corruption problem. To get around this issue, one would have to replace the container being used in this example with a protected container. This also rules out containers that are synchronous tagged types because a type derivation is needed (type List), which is currently not possible with synchronous tagged types. Even if the programmer finds or creates a suitable container, this adds an extra protected structure which is less efficient.
With the new Syntax you can safely use any of the common Ada 2005 container libraries, and there is no need to introduce an extra protected object. This example shows;
a) Improved flexibility (More containers can be used safely, including
non-synchronous containers and containers of a synchronous tagged type)
b) Improved efficiency (List does not need to be synchronous) c) Improved data hiding ("=" for T can be hidden in private part)
(See next examples for explanation)
d) Improved readability (Compare visible parts,
7 contiguous lines vs 13 lines with a nested private part inbetween to distract the reader)
with Ada.Containers.Vectors; package Pkg is
type L is limited interface; type T is synchronized new L with private; type T_Ref is access all T; procedure Initialize (Item : in out T; Id : Natural); procedure Append (Item : in out T; Other : T);
package I is private new Ada.Containers.Vectors (Element_Type => T_Ref, Index_Type => Natural, others => private); -- Note "=" is deferred to private part
function Get_List (Item : T) return I.List;
private
protected type T is new L with procedure Initialize (Id : Natural); procedure Append (Item : T_Ref); function Id return Natural; function Get_List return I.List; private Unique_Id : Natural; List : access I.List; end T;
function "=" (L, R : T) return Boolean;
package I is new Ada.Containers.Vectors (Index_Type => Natural, Element_Type => T_Ref, "=");
end Pkg;
Now suppose we would like to be able to hide more details associated with a private_instantiation_declaration in the private part of a package specification. In particular, we want to be able to declare certain actuals in the private part, instead of having to declare them in the visible part of a package specification.
For example:
Supposing we have a generic package that can be used to create a specific abstraction, and we want the generic instantiation of this package to directly provide all the operations that are available to clients in the package containing the specific abstraction.
In other words, the generic instantiation needs to be declared in the visible part of the package associated with specific abstraction.
Currently this requires that all the generic actuals be fully visible at the point of the generic instantiation. This can lead to the exposure of constants, variable, subprograms, and entries in the visible part of the package that might have been better off hidden from view.
To illustrate these points, consider the following generic that provides a template for a device driver which can be plugged into some fictional target OS.
generic type Device_Type is private; Manufacturer : String; Model : String; Disabled : in out Boolean; with procedure Activate_Device (Device : Device_Type); with function Device_Is_Operational (Device : Device_Type) return Boolean; package Device_Driver is
protected Driver is procedure Activate; function Is_Operational return Boolean; private Device : Device_Type; end Driver; end Device_Driver;
package body Device_Driver is protected body Driver is
procedure Activate is begin Activate_Device (Device); end Activate;
function Is_Operational return Boolean is begin return Device_Is_Operational (Device); end Is_Operational; end Driver; end Device_Driver;
Now Suppose we want to create an Audio Driver that utilizes this generic. We really want to to expose just the calls provided by the generic to Activate the audio driver, and to check to see if the audio driver Is_Operational. Unfortunately, we end up having to expose other details that clients might have no business looking at, and the package specification suffers from poor readability due to the excess clutter.
with Device_Driver;
package Audio_Driver is
type Audio_Device is private;
procedure Power_On (Device : Audio_Device); -- Actual procedure function Playing_Music (Device : Audio_Device) return Boolean; -- Actual Function
Muted : Boolean := False; -- Actual Variable
Manfacturer : constant String := "Acme Corp"; Model : constant String := "SoundWhomper Mark IV";
package Audio_Device_Driver is private new Device_Driver (Device_Type => Audio_Device, Manufacturer => Manufacturer, Model => Model, Disabled => Muted, Activate_Device => Power_On, Device_Is_Operational => Playing_Music);
private
type Audio_Device is record ... end record;
package Audio_Device_Driver is new Device_Driver (Device_Type => Audio_Device, Manufacturer => Manufacturer, Model => Model, Disabled => Muted, Activate_Device => Power_On, Device_Is_Operational => Playing_Music);
end Audio_Driver;
The idea is to be able to indicate that declarations for actuals of the partial generic instantiation in the visible part of a package specification are being deferred into the private part of a package specification. The private keyword is used in the declaration of the private_instantiation_declaration to indicate that a particular actual (or group of actuals if the named association is others) is being deferred to the private part of the package specification.
Applying the syntax for a private_instantiation_declaration to the above allows us to write;
with Device_Driver;
package Audio_Driver is type Audio_Device is private;
package Audio_Device_Driver is private new Device_Driver (Device_Type => Audio_Device, others => private);
-- These renamed subprograms are the only visible operations procedure Activate renames Audio_Device_Driver.Driver.Activate; function Is_Operational return Boolean renames Audio_Device_Driver.Driver.Is_Operational;
private
type Audio_Device is record ... end record;
procedure Power_On (Device : Audio_Device); -- Actual procedure function Playing_Music (Device : Audio_Device) return Boolean; -- Clients cannot call these functions
Muted : Boolean := False; -- Actual Variable Manfacturer : constant String := "Acme Corp"; Model : constant String := "SoundWhomper Mark IV";
package Audio_Device_Driver is new Device_Driver (Device_Type => Audio_Device, Manufacturer => Manufacturer, Model => Model, Disabled => Muted, Activate_Device => Power_On, Device_Is_Operational => Playing_Music);
end Audio_Driver;
A second example of using deferred actuals would be helpful. Suppose we have a set of container packages that implement a queue abstraction. The root package defines the interface to a queue, and child packages create various implementations of the interface
generic type Element_Type is private; pragma Preelaborable_Initialization (Element_Type); package Queues is pragma Pure;
type Queue_Interface is limited interface;
-- Get and Put a single element from/to the queue procedure Get (Container : in out Queue_Interface; Item : out Element_Type) is abstract;
procedure Put (Container : in out Queue_Interface; Item : Element_Type) is abstract;
type Queue_Type (Capacity : Natural) is abstract new Queue_Interface with null record;
type Queue_Class_Access is access all Queue_Interface'Class;
end Queues;
Suppose that there exist two implementations of this interface.
1) A Bounded queue 2) A Queue of bounded queues that presents an abstraction of a
an array of Bounded queues as a single queue
1) Bounded Queue
generic package Queues.Bounded is
pragma Pure;
type Queue_Data (Capacity : Natural) is private; pragma Preelaborable_Initialization (Queue_Data);
type Queue (Capacity : Natural) is new Queue_Type (Capacity) with record Data : Queue_Data (Capacity); end record;
overriding procedure Get (Container : in out Queue; Item : out Element_Type); overriding procedure Put (Container : in out Queue; Item : Element_Type);
private ... end Queues.Bounded;
2) Queue of bounded Queues
generic type Queue_Array_Type is array (Natural range <>) of Queue_Class_Access; Queues : Queue_Array_Type; package Queues.Multi is
type Queue_Data (Capacity : Natural) is private; pragma Preelaborable_Initialization (Queue_Data);
type Queue (Capacity : Natural) is new Queue_Type (Capacity) with record Data : Queue_Data (Capacity); end record;
overriding procedure Get (Container : in out Queue; Item : out Element_Type); overriding procedure Put (Container : in out Queue; Item : Element_Type);
private ... end Queues.Multi;
Now suppose we want to create an instance of a queue of bounded queues. The proposed syntax allows us to write:
private with Queues.Bounded; -- Simple generic bounded queue with Queues.Multi; -- generic queue-of-bounded-queues container
package Pkg is
Maximum_Capacity : constant := 300; -- Max. no. of elements in the Q
type T is tagged private; pragma Preelaborable_Initialization (T);
-- Declare a private instantiation of the interface. package I is private new Queues (Element_Type => T);
-- NOTE: Instantiation I2 is hidden in the body
package I3 is private new I.Multi (others => private); -- Array formals hidden in body
private
type T is tagged record ... end record;
-- Instantiate interface for a queue package I is new Queues (Element_Type => T);
-- Instantiate the "low-level" bounded queue implementation capable -- of storing elements of type T package I2 is new I.Bounded;
-- Declare some queues to be used in instantiating a queue of queues Q1 : aliased I2.Queue (Capacity => 100); Q2 : aliased I2.Queue (Capacity => Maximum_Capacity - Q1.Capacity);
-- Declare types needed to instantiate queue of queues generic type Queue_Array is array (Natural range <>) of access I.Queue_Interface'Class; Queues : constant Queue_Array := Queue_Array'(1 => Q1'access, 2 => Q2'access);
-- Instantiate a queue of queues generic package I3 is new I.Multi (Queue_Array_Type => Queue_Array, Queues => Queues);
end Pkg;
!Example
Now lets look at how the proposed syntax could be applied to the examples in the problem section of this AI.
Here is the generic signature example:
generic type Elem is private; with function Hash (El : Elem) return Integer; package Hashed_Sets is type Set is private; function Union(Left, Right : Set) return Set; function Size(Of_Set : Set) return Natural is <>; function Intersection(Left, Right : Set) return Set is <>; function Empty return Set is <>; function Unit_Set(With_Item : Element) return Set is <>; function Nth_Element(Of_Set : Set) return Element is <>; package Signature is new private Set_Signature (Elem, Set); private type Set is record ... end record; package Signature is new Set_Signature(Elem, Set); end Hashed_Sets;
In this case, it appears that Hashed_Sets is itself a general purpose container abstraction meant to be used on its own, and the above would be an appropriate package specification.
Suppose however, that this package were intended to be only used to create higher level abstractions by using the Signature Instantiation as a package formal to instantiate a higher level generic package. In a sense this could be considered as a type of abstract package that is not to be used on its own. In this case, we would like to be able to hide more details in the private part, and ensure that only the Signature instantiation is exported from this generic package. Using the proposed syntax, this allows us to write:
generic type Elem is private; with function Hash (El : Elem) return Integer; package Hashed_Sets is
type Set is private; package Signature is private new Set_Signature (Elem, Set, others => private);
private
type Set is record ... end record; function Union (Left, Right : Set) return Set; function Size (Of_Set : Set) return Natural; function Intersection (Left, Right : Set) return Set; function Empty return Set; function Unit_Set (With_Item : Element) return Set; function Nth_Element (Of_Set : Set) return Element; package Signature is new Set_Signature (Elem, Set); end Hashed_Sets;
Here is an example where we want to instantiation a container:
package Expressions is type Expr_Ref is private; package Expr_Sequences is private new Sequences(Expr_Ref); function Operands (Expr : Expr_Ref) return access Expr_Sequences.Sequence; ... private type Expression; -- completion deferred to body type Expr_Ref is access Expression; package Expr_Sequences is new Sequences(Expr_Ref); end Expressions;
Note that being able to access the instantation in the visible part with a partial view provides a simple easy to understand solution without having to introduce incomplete types, derived types, or even named access types. Note with this proposal we also have the option of having the Operands function return an Expr_Sequences.Sequence instead of access Expr_Sequences.Sequence.
!ACATS test
ACATS B and C-Test(s) are necessary.
!appendix

From: Brad Moore
Sent: Sunday, February 15, 2009  4:05 PM

I have made significant changes to the proposal I have been working on for
AI05-0074. Thanks to Randy for providing good feedback, I have had a pretty
good email exchange with him on these ideas over that past month or so.

Randy will probably be somewhat surprised however, as what I have ended up
with has changed quite a bit since our last email exchange. My thoughts have
evolved considerably since I started on this, but I think I am finally at a
stable place and hopefully something worthy of consideration.

To summarize the changes and where I am at now;

1) I have done away with the need for a May_Be_Partial pragma with this
   proposal
2) There are no changes to the freezing rules, or the generic contract
   model.
3) There are no restrictions placed on the content of a generic package,
   Though there are restrictions on the use of the instance until the
   completion of the private instantiation.
4) I still have the ability to defer actuals to the private part
5) I have done away with a lot of other features that I had been toying
   with.  (No derivations of partial untagged types, no private objects)
6) I have also realized that there isn't sufficient need to be able to
   instantiate generics with a type that has an incomplete view.
   One workaround is to make the type a private type and use a
   private_instantiation_declaration.

    -- Private_Instantiation_Declaration eg. package Foo is private new 
       Ada.Containers.Doubly_Linked_Lists 
         (Element_Type => T, Others => Private);
    --  "=" has been deferred to the private part

However, actuals for formal types or formal packages must be explicitly
specified and cannot be deferred. This eliminates cases that I found to be
problematic.

A private_instantiation_declaration declares two views of an instance.
A partial view of an instance, and a full view of an instance.
The partial view applies to the immediately enclosing declarative region,
while the full view applies to outside program units, and is equivalent to
the view provided by the generic_instantiation declaration in the private
part, which is placed after the actuals have been defined.

Semantically, a partial view of an instance is like a view of the text of
the generic template, without having made substitutions of actuals for
formals, and where the mappings from actuals to formals has not yet been
resolved.

In my travels, I have also ran into some problems with existing workarounds,
which are addressed by this proposal, and I have captured these in the
attachment.

Looking forward to seeing everyone in Tallahassee

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

Questions? Ask the ACAA Technical Agent