!standard 12.3 (12)                     09-10-14  AI05-0074-5/01
!standard 12.3.1(0)
!class amendment 09-10-14
!status No Action (9-0-0) 10-02-27
!status work item 09-10-14
!status received 09-06-13
!priority Medium
!difficulty Hard
!subject Private Instantiations - Take 2

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

The view of the instance at the site of the private_instantiation_declaration
is equivalent to the view of the generic instantiation within the private part,
except that there are rules that restrict how this view may be used within the
immediately enclosing declarative region between the private instantiation
declaration and its completion in the private part.

A private type or private extension declared within the immediately enclosing
declarative region containing a private instantiation declaration cannot
directly contain a component of a composite type exported from the view of the
private instantiation declaration since such an exported type may have been
derived from a formal which may be a private type or private extension that has
not yet been completed.

The declaration of a component that is an array type exported from the view of
the instance is allowed within the immediately enclosing declaration region
however, but only if the components of the array are not composite types,
formal types, or formal derived types of the instance. These rules are needed
to prevent circular type definitions where the completion of a private type or
private extension contains components exported from the private instantiation
declaration that are based on the same type.

If the view of a type exported from the view of a private instantiation declaration
is a tagged view, then private extension derivations of that type are allowed
within the immediately enclosing declarative region.

The declaration of objects of types exported from the view of a private
instantiation declaration within the immediately enclosing declarative region
before the completing generic instantiation are not allowed, since objects may
be associated with private types or private extensions that have not yet been
completed. Similarly, objects exported from the view of the private
instantiation declaration may not be directly referenced within the immediately
enclosing declarative region before the declaration of the generic instantiation
that completes the private instantiation declaration.

In addition, calls may not be made to functions exported from the view of
private instantiation declaration within the immediately enclosing declarative
region before the declaration of the completing generic instantiation, since
such function calls may have side affects that involve changes to objects
exported from the view of the instance, and such object may be based on
formals that are private types or private extensions that have not yet been
completed.

!wording

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

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

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.


LEGALITY RULES


6 A private_instantiation_declaration declares a 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 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  * If an association is a named association in the private instantiation
 then the association shall be a named association in the completion. If an
 association is a positional association in the private instantiation then the
 association shall be positional in the completion.

12  * 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.

8   * For a formal subtype, the actuals match if they denote statically
 matching subtypes.

9  * 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.

10 A private_instantiation_declaration shall not have a generic_association with
 an explicit_generic_actual_parameter that has an incomplete view at the place
 of the private_instantiation_declaration.

11 A type shall be completely defined before it is frozen (see 3.11.1 and
13.14). Thus, neither the declaration of a variable of a type from a 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. In
addition, a callable entity from the view of the instance cannot be called
before the completion of a private_instantiation_declaration, nor may any
objects from the view of the instance be directly referenced.

AARM 11.a Reason: A callable entity from a view of an instance can have side
affects that can modify the state of variables exported from the view of an
instance. We disallow function calls into an instance from a private
instantiation declaration to avoid problems involving usage of types that
have not yet been completely defined.

12 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

13 All visible composite types other than array types with components that are
not of a composite type from the view of an instance associated with a
private_instantiation_declaration may not directly appear as a component in the
declaration of another composite type within the immediately enclosing
declarative region before the declaration of the generic instantiation that
completes the private_instantiation_declaration.

AARM

13.a Ramification: It is assumed that all such composite 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). This rule is needed to
prevents the declaration of illegal recursive types,or declaring other composite
types with components that have are not yet completely defined. Similarly, a
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.

14 The partial view of a type of an explicit_generic_actual_parameter of a
deferred_generic_association must conform 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

15.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 do not 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

16 A private_instantiation_declaration declares a private instantiation.

17 A private_instantiation_declaration defines a view of a generic instance. The
view is equivalent to the view of the instance declared by the
generic_instantiation that completes the private_instantiation_declaration.


NOTES

18 Type derivations of visible types from the view associated with a
private_instantiation_declaration are not allowed within the immediately
enclosing declarative region before the completion of the
private_instantiation_declaration unless the declaration is a tagged private
extension, since such a type may have been derived (directly or indirectly) from
an actual that has a partial view.


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

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 and creating recursive data structures.

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 syntactically). 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.

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 private_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.
The view of the instance provided by the private_instantiation_declaration is
equivalent to the view of the instance provided by the generic instantiation,
though there are restrictions on how this view may be used within the package
specification before the completion of the declaration in the private part.
Other program units that reference the package do not have these restrictions
however.

A private_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 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 match to the above
     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 synchronized 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 provides 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. The improved
readability of the new syntax should continue to generate savings over
the maintainance life cycle 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. Someone reading the visible parts
of both packages should get an understanding of the package below more readily.

   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 and can be returned as a result type. This means that Get_List can
be declared as a primitive of T, and thus is inherited by any derived types of
T. The change in the result type from an access type to a normal type had
a significant impact on the design of the program written using the existing
syntax. Using the new proposed syntax, the only change needed was to change
the result type.

   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 go back to returning an access to an instantiation,
but this time, we want the instantiation to be a synchronous tagged type.
In this example, we have instantiate a generic with an object of a limited
interface representing a work item, and the generic gives us a worker task
to operate on the item.

package Work_Item is
   type Job is limited interface;
   procedure Analyze (Item : in out Job) is null;
end Work_Item;

generic
   type Work is limited new Job with private;
package Work_Item.Worker is
   task type Periodic_Worker is new Job with
     ...
   end Periodic_Worker;
end Work_Item.Worker;

We would like to have Get_Worker as a primitive function of our new type,
but we cant, since that requires a derivation of a synchronous tagged type.
We end up having to make Get_Worker a non-primitive function using current
Ada 2005 syntax.

with Work_Item.Worker;
package Pkg is
   type Worker_Task;
   type Worker_Access is access Worker_Task;
   package Nested is
      type T is limited new Work_Item.Job with private;
      overriding procedure Analyze (Item : in out T);
      function Get_Worker (Item : T) return Worker_Access;

   private
      type T is limited new Work_Item.Job with
         record
            ...
         end record;
   end Nested;

   use Nested;

   package T_Worker is new Work_Item.Worker (Work => T);
   type Worker_Task is new T_Worker.Periodic_Worker with null record;
   -- ILLEGAL: Cannot derive a new type from a synchronous tagged type

   -- Instead we have to declare a non-primitive function
   function Get_Worker (Item : T) return access T_Worker.Periodic_Worker;

end Pkg;

Using the new proposed syntax, we can do what we want to do. If we decide
we want the Get_Worker primitive to return a task instead of an access to
task, simply delete the word access in the following example.

with Work_Item.Worker;
package Pkg is
   type T is limited new Work_Item.Job with private;
   overriding procedure Analyze (Item : in out T);
   package T_Worker is PRIVATE new Work_Item.Worker (Work => T);
   function Get_Worker (Item : T) return access T_Worker.Periodic_Worker;

private
   type T is limited new Work_Item.Job with
      record
         ...
      end record;
   package T_Worker is new Work_Item.Worker (Work => T);
end Pkg;

Now suppose that we want to create a set of general purpose containers that
utilize an iterator interface.

   generic
       type Cursor is private;
       No_Element : in Cursor;
   package Ada.Iterator_Interfaces is
       type Basic_Iterator is limited interface;
       function First
          (Object : Basic_Iterator) return Cursor is abstract;
       function Next (Object : Basic_Iterator; Position : Cursor)
          return Cursor is abstract;
   end Ada.Iterator_Interfaces;

For this example, we will modify the existing
standard Doubly_Linked_Lists container to show how this might be done. The
biggest difficulty is that a cursor needs a reference to a node and to the full
container (the List in this example). The node probably could be defined in the
private part of package Cursors, but we can't define a reference to List in the
private part -- it hasn't been declared yet! And it *can't* be declared yet,
because it depends on the interface that we haven't yet created.

One way to workaround this problem is to use a Taft-amendment type in the
private part of Cursors. But we can't complete that with the type List
itself; we'd have to use a derived type. And that is undesirable as it would
force many junk type conversions. Even using class-wide types won't get rid of
those conversions, because they would be toward the root of the tree.

Another possible workaround would be to clutter the spec with an incomplete
type List before the nested package. But that could not be completed with
the private extension List, so we would still end up with the same problem.
To allow this approach, the Ada language would require modifications to allow
incomplete types to be completed by private type extensions.

   with Ada.Iterator_Interfaces;
   generic
      type Element_Type is private;
   package Ada.Containers.Doubly_Linked_Lists is
      type List; -- Needed so that cursor can store access to container
      package Cursors is
         type Cursor is private;
         No_Element : constant Cursor;
      private
         ... -- not specified by the language
      end Cursors;

      package Iterators is new
          Ada.Iterator_Interfaces (Cursors, No_Element);

      type List is new Iterators with private;
      -- ILLEGAL: Completing an incomplete type with a private extension,
      -- currently not allowed in Ada 2005

      Empty_List : constant List;
      function Is_Empty (Container : List) return Boolean;
      procedure Clear (Container : in out List);
      function Element (Position : Cursor)
         return Element_Type;
      ...
   private
      ... -- not specified by the language
   end Ada.Containers.Doubly_Linked_Lists;

Using the proposed syntax for private extension declarations however, these
issues do not arise. There is no need to create nested packages, incomplete
types, or complete an incomplete type with a private extension.

with Ada.Iterator_Interfaces;
generic
   type Element_Type is private;
package Ada.Containers.Doubly_Linked_Lists is

   type Cursor is private;
   No_Element : constant Cursor;

   package Iterators is private new
     Ada.Iterator_Interfaces (Cursor, No_Element);

   type List is new Iterators.Basic_Iterator with private;
   Empty_List : constant List;

   function Is_Empty (Container : List) return Boolean;
   procedure Clear (Container : in out List);
   function Element (Position : Cursor)
      return Element_Type;
   overriding function First (Container : List) return Cursor;
   overriding function Next (Container : List; Position : Cursor) return Cursor;

private
   ... -- Not specified by the language
end Ada.Containers.Doubly_Linked_Lists;

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


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 instantiation in the visible part
with a partial view provides a simple 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
Date: Saturday, June 13, 2009  2:40 PM

>> This proposal does not "feel right" to me.
>
> Let me add that the reasons are not that obvious and surely this is no
> reflection on the author of the proposal. (Part of the reason for
> complaining now is the hope that Tucker or I or someone will have an
> inspiration before the next meeting, that won't happen if the proposal
> is thought to be "good enough".)

I agree with this sentiment. The proposal does not "feel right" to me either.

The whole business of requiring the declaration of a nested package, then
invoking (new) machinery to make it appear that we didn't declare a nested
package feels like a kludge to me.

I decided to rework the proposal I had submitted for AI05-0074-4.
I would like to call this a new proposal however (AI05-0074-5?), rather than an
update on the old proposal, because I have significantly reduced what I had
before, and made significant changes to simplify the semantic model. In
particular, I eliminated deferring actuals to the private part, and eliminated
the concept of a private instantiation declaration declaring a full view and a
partial view of an instance.

In Tallahassee I recall a conversation with Steve Baird where he was asking me
to explain my proposal. A couple of sentences into the description, I realized
what I was proposing was overly complex.

I will now attempt to describe the new model here in simplest terms.

- A private instantiation declaration occurs in the visible part of a package
  and is completed by a generic instantiation in the private part of a package.

- A generic instantiation declares a view of an instance, and if a  private
  instantiation declaration is associated with a generic instantiation, then it
  declares another (forward) view of the same instance.

- Both views of an instance are equivalent semantically, however there are
  restrictions that apply to the use of the private instantiation declaration
  within the immediately enclosing declarative region, before the completion in
  the private part. To outside program units, these restrictions do not apply.

- The restrictions that apply only to the immediately enclosing declarative
  region before the completion are;
  a) Composite types (except array types whose components are not
     composite types) exported from the view of the instance may
     not directly appear as a component in a declaration.
  b) Calls (function calls) may not be made to the generic
     instantiation.
  c) Objects or expressions involving objects of visible types
     exported from the view of the instance are not allowed.

Now looking at Randy's example, we find that his issues do not arise. There is
no need to declare a nested package. No need to declare anonymous type that is
completed with a private extension (Not currently supported in the language). No
need to invoke special machinery (the proposed integrated package solution) to
make it appear that the nested package is not nested. There are less changes
needed to the existing container libraries.

   generic
       type Cursor is private;
       No_Element : in Cursor;
   package Ada.Iterator_Interfaces is
       type Basic_Iterator is limited interface;
       function First
          (Object : Basic_Iterator) return Cursor is abstract;
       function Next (Object : Basic_Iterator; Position : Cursor)
          return Cursor is abstract;
   end Ada.Iterator_Interfaces;

with Ada.Iterator_Interfaces;
generic
   type Element_Type is private;
package Ada.Containers.Doubly_Linked_Lists is

   type Cursor is private;
   No_Element : constant Cursor;

   package Iterators is private new
     Ada.Iterator_Interfaces (Cursor, No_Element);

   type List is new Iterators.Basic_Iterator with private;
   Empty_List : constant List;

   function Is_Empty (Container : List) return Boolean;
   procedure Clear (Container : in out List);
   function Element (Position : Cursor)
      return Element_Type;
   overriding function First (Container : List) return Cursor;
   overriding function Next (Container : List; Position : Cursor) return Cursor;

private
   ... -- Not specified by the language
end Ada.Containers.Doubly_Linked_Lists;


The new AI proposal is attached. I would encourage reading of the discussion
section, because it shows simple comparative examples using the new nested
package approach vs the private instantiation declaration approach. In each
case, I find that the private instantiation is easier to read and understand.

One issue that has not been addressed with the integration package solution, is
that type derivations are often necessary, and if the type involved is a
synchronous tagged type, you are out of luck, since derivations of synchronous
tagged types are not currently allowed. If we do end up deciding to go with the
integrated package solution, it would at least be good to know how we might plan
to address this problem. The private instantiation solution does not require a
solution for this issue, because it avoids the need to create junk derivations.

The example I give in my proposal is a case where we want to have a type that
returns an access to an instantiation, where the instantiation involves a
synchronous tagged type.

In this example, we instantiate a generic with an object of a limited interface
representing a work item, and the generic gives us a worker task to operate on
the item.

package Work_Item is
   type Job is limited interface;
   procedure Analyze (Item : in out Job) is null; end Work_Item;

generic
   type Work is limited new Job with private;
package Work_Item.Worker is
   task type Periodic_Worker is new Job with
     ...
   end Periodic_Worker;
end Work_Item.Worker;

We would like to have Get_Worker as a primitive function of our new type, but we
cant, since that requires a derivation of a synchronous tagged type. We end up
having to make Get_Worker a non-primitive function using current Ada 2005
syntax.

with Work_Item.Worker;
package Pkg is
   type Worker_Task; -- Needed for nested Get_Worker call
   type Worker_Access is access Worker_Task;
   package Nested is
      type T is limited new Work_Item.Job with private;
      overriding procedure Analyze (Item : in out T);
      function Get_Worker (Item : T) return Worker_Access;

   private
      type T is limited new Work_Item.Job with
         record
            ...
         end record;
   end Nested;

   use Nested;

   package T_Worker is new Work_Item.Worker (Work => T);
   type Worker_Task is new T_Worker.Periodic_Worker with null record;
   -- ILLEGAL: Cannot derive a new type from a synchronous tagged type

   -- Instead we have to declare a non-primitive function
   function Get_Worker (Item : T) return access
        T_Worker.Periodic_Worker;

end Pkg;

Using the proposed private instantiation syntax, we can do what we want to do.
If we decide we want the Get_Worker primitive to return a task instead of an
access to task, simply delete the word access in the following example.

with Work_Item.Worker;
package Pkg is
   type T is limited new Work_Item.Job with private;
   overriding procedure Analyze (Item : in out T);
   package T_Worker is PRIVATE new Work_Item.Worker (Work => T);
   function Get_Worker (Item : T) return access T_Worker.Periodic_Worker;

private
   type T is limited new Work_Item.Job with
      record
         ...
      end record;
   package T_Worker is new Work_Item.Worker (Work => T); end Pkg;

A question I have about the integrated package solution is, other than the need
to instantiate generics with private types, how likely is this new language
feature to be used? What other sorts of situations are there where this feature
would be useful?

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

From: Bob Duff
Date: Wednesday, June 17, 2009  4:16 PM

I agree with your decision to make this a separate alternative.

But I still prefer the "use package" thing, perhaps with some modifications,
over the special instantiation idea.

For one thing, the "use package" thing solves more problems -- not just the
instantiation-related ones.  The "use package" thing also allows some
interesting ways of composing abstractions (and allows "mis"use, but I don't
care about that).

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

From: Brad Moore
Date: Saturday, June 27, 2009  2:26 PM

True, but also note that the most recent incarnation of the special
instantiation idea does solve problems that the "use package" thing doesn't seem
to solve.

For example, it gives you the ability to declare primitive subprograms that have
formals or results of an object of the instantiation. (as opposed an access type
designating an object of the instantiation) That seems useful to me.

People who are "use adverse" may not want to use this "use package" thing (for
the same reasons they don't use the existing "use"), and therefore the feature
may not address the instantiation problem for all the Ada community, whereas I
unable to imagine a reason why people would become "special-instantiation
adverse".

I am also not sure I see all the new "interesting ways of composing
abstractions".

For example, I'm not sure how often this feature would be needed for regular
(non-instance) nested packages, since the special instantiation idea eliminates
one of the main reasons for having to declare nested packages in the first
place. Otherwise, when I've needed to create nested packages (pretty rarely), is
when I have several variations of an abstraction. I can only think of examples
where we used this in Ada 83 code, as Ada 95 child packages eliminates a lot of
the need to declare nested packages I think.

As for declaring non-primitive constructor type functions, I think I would tend
to not use this feature there either as a matter of style. Using a Nested
package name such as "Constructors" or "Non_Dispatching", makes it more clear to
me that the subprogram is non-dispatching.

eg. Foo := Pkg.Constructors.Create;

The real benefit I see is that it allows you to present declarations of an
instantiation as though they were declared locally in a package spec,
potentially eliminating rename declarations. This doesn't sound like a "new way"
to me, it sounds more like a nicer, more convenient shorthand for an "old way".

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

From: Robert Dewar
Date: Saturday, June 27, 2009  2:59 PM

> People who are "use adverse" may not want to use this "use package"
> thing (for the same reasons they don't use the existing "use"), and
> therefore the feature may not address the instantiation problem for
> all the Ada community, whereas I unable to imagine a reason why people
> would become "special-instantiation adverse".

a) I don't think the language design should pay attention to peculiar
    adverse reactions of this type.

b) I don't think you can possibly guess what strange adverse reactions
    people wil acquire.

Specifically, the use adverse crowd likes to require explicit qualification of
all references, but this principle is badly broken for derived types anyway, so
that object oriented code routinely has references to a variable Clunk with no
explicit declaration of Clunk in sight, even if no use clauses are present. Yes,
there is an implicit declaration and a tool could point you to this implicit
declaration, but once you depend on such tools, the whole motivation for
explicit qualification is dubious if you ask me.

I somewhat share the preference for the "use package" approach, though I do
understand what you are saying (that so far at least this is not as expressive).

[Editor's note: The rest of the "use-averse" thread is filed in AI05-0150-1, as
it has more to do with use clauses than this proposal.]

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