CHAPTER 12: Generic Units

12.4 Rationale for the Formulation of Generic Units

A major simplification, in this respect, is achieved by adopting an approach based on a context-dependent extension of the traditional techniques of macro-expansion. This solution has the advantage of introducing only a minimum of additional features. It is well implementable within the state of the art, and it provides the flexibility required by the applications.

This approach has important consequences for the specification of generic formal parameters. The other major simplifying assumptions made in the language concern the requirement for explicit instantiation, and the specification of formal operations applicable to formal types. These issues will be discussed separately below.

12.4.1 Explicit Instantiation of Generic Units

The approach taken here clearly distinguishes between the instantiation of a program unit, obtained from a generic unit, and the invocation of the resulting program unit - calling a subprogram, using a package. Thereby it emphasizes the contrast between translation-time substitution of generic actual parameters and execution-time passage of actual parameters to subprograms. Explicit instantiation provides a well-defined locus for the point of instantiation and also for reporting any errors arising from inconsistent substitution. The resultant program unit can be invoked subsequently as often as required, with the same degree of power and security as for any other nongeneric program unit; this is a consequence of the fact that a program unit obtained by generic instantiation is indistinguishable from the same program unit defined explicitly at the point of instantiation.

An alternative solution considered was implicit instantiation. For the purpose of the discussion of the complexity of implicit instantiation, consider the following generic function (which is actually just a different way of writing the power function given in a previous section):

generic type ELEM is private; with function "*" (LEFT, RIGHT : ELEM) return ELEM; function POWER(E : ELEM; N : POSITIVE) return ELEM; function POWER(E : ELEM; N : POSITIVE) return ELEM is begin if N = 1 then return E; else return E * POWER(E, N - 1); end if; end POWER;

If implicit instantiation were provided, then for:

R : RATIONAL; I : INTEGER;

exponentiation could be applied without prior explicit instantiation. Thus:

POWER(R , 5) POWER(I , 5)

would both be legal. The actual type used for ELEM would be implicitly inferred from the actual parameter associated with E in each call - that is, RATIONAL for R, INTEGER for I.

Implicit instantiation would complicate the rules for the identification of overloaded subprograms. If a version of POWER were defined directly within the package RATIONAL_NUMBERS itself:

    function POWER(E :  RATIONAL;  N :  INTEGER) return RATIONAL;

then this explicit definition would hide the generic definition in an application such as POWER(R, 5). Thus the generic definition would be visible for some types and hidden for others. This added complexity would reflect on compilers, and also on program readability.

Another problem would arise for the identification of POWER in the body of the generic unit itself: would this be a recursive implicit instantiation or a recursive call of the same instance? In the simple example considered, it could be easily interpreted as a recursive call. However, in general, it is not at all clear that the problem can always be resolved by a static analysis of the program (unless restrictions are adopted). A sufficient condition to guarantee that no generic operation will ever require an unbounded number of implicit generic instantiations during execution has been given in [BJ 78]. However such checks require a quite complex analysis of the program.

In conclusion, implicit instantiation is still a research subject. The only solution within the current state of the art is explicit instantiation and this is therefore the solution chosen for Ada.

Explicit instantiation certainly requires more writing on the part of the user, but it provides better awareness of the instances that are created and thus contributes to reliability and readability. In addition, it offers distinct advantages in terms of efficiency, since compilers can easily identify the existing instantiations and, in some cases, achieve optimizations such as sharing of code among several instantiations of the same generic unit.

12.4.2 Generic Formal Parameters: The Contract Model

Consider by analogy what is done for subprograms. For a normal - that is, nongeneric - procedure, specification of parameters permits independent checks of the procedure body on the one hand, and of the procedure calls on the other hand. Both must conform to the formal parameter specifications and these legality checks can be done independently: the procedure specification is a sort of contract between the procedure body and the corresponding procedure calls.

The specification of generic formal parameters must achieve the same degree of independence:

1. For a given generic body, it should be possible to check that its text is consistent with respect to the formal parameter specifications.

2. For a given generic instantiation, it should be possible to check that the actual parameters are consistent with respect to the formal parameter specifications.

3. The precision of the formal parameter specifications should be sufficient to guarantee that if the checks (a) and (b) are successful, then the corresponding instantiations produce legal program units.

• For a formal type specified as limited private, no operation is assumed available (apart from certain attributes: see RM 7.4.2). Hence any operation that is applied to an object of the formal type within the generic unit must be provided as an explicit generic formal parameter.

• For a formal type specified as private (not limited), the same holds except that assignment and the predefined comparison for equality and inequality are available.

• For a generic formal type declared as a type pattern with a box, the operations of the corresponding kind of type are available: they are implicitly declared. For example, the floating point operators are available for any generic formal type defined by "digits <>". Any other operation must be provided explicitly by a generic formal parameter.

Consider for example the generic formal part given for the generic function POWER:

generic type ELEM is private; with function "*" (LEFT, RIGHT : ELEM) return ELEM; function POWER(E : ELEM; N : POSITIVE) return ELEM;

The operation "*" is explicitly provided as a generic parameter, along with the type ELEM itself. The parameter E and the result of the function POWER are both specified as being of this formal type. Thereafter the identification of the "*" appearing within the generic body:

function POWER(E : ELEM; N : POSITIVE) return ELEM is begin if N = 1 then return E; else return E * POWER(E, N - 1); end if; end POWER;

within the expression E * POWER(E, N-1) can be done as usual - it refers to the "*" declared in the generic formal part. Similarly the recursive call of POWER can be correctly identified (since implicit instantiation is not allowed). Hence the generic body can be completely checked.

Similarly a generic instantiation such as

    function "**" is new POWER(ELEM =>  MATRIX, "*" => MULT);

can be fully checked: Consider the function specification obtained by substituting in the generic formal function the name MULT for the designator "*", and the actual type MATRIX for the formal type ELEM:

    function MULT(LEFT, RIGHT :  MATRIX) return MATRIX;

Then the instantiation is correct if there is - in the context of the instantiation - a function MULT with this parameter and result profile - the only allowed difference being for the names of the parameters (LEFT and RIGHT). Conversely, consider:

    function "**" is new POWER(ELEM =>  RATIONAL,  "*" =>  "not");     -- ILLEGAL!

This generic instantiation can be reported as incorrect since there is no operation not corresponding to the specification

    function "not" (LEFT, RIGHT :  RATIONAL) return RATIONAL;     -- ILLEGAL!

An alternative considered in this design was the implicit inference of operations of a formal type. The reasons for rejecting this alternative are similar to those leading to the rejection of implicit instantiation. With implicit inference of operations, the previous example could be rewritten as:

generic type ELEM is private; function POWER(E : ELEM; N : POSITIVE) return ELEM;

and we would be left with the problem of identifying the "*" operation used in the body. For a given instantiation, say with the type RATIONAL, should the "*" operation be identified as a global operation in the context of the generic declaration or in the context of the generic instantiation? The two alternatives might lead to different results.

Note also that a statement such as

    return E * E * E;

would be ambiguous in the presence of several overloadings of "*"; for example:

function "*" (X, Y : RATIONAL) return RATIONAL; -- (1) function "*" (X, Y : RATIONAL) return INTEGER; -- (2) function "*" (X, : INTEGER; Y : RATIONAL) return RATIONAL; -- (3)

One possible interpretation would identify both operations with definition (1); another interpretation would identify the first "*" with (2) and the second with (3).

In general, the specifications of the identified operations could be quite different from instantiation to instantiation depending on the operations visible in the context of the instantiation. None of this can happen with an explicit specification of the formal operation "*".

To summarize, implicit inference of operations, based on the instantiation, would introduce awkward context-dependence and would require complete rechecking of the generic body for each instantiation. This last consequence would be particularly unfortunate, since generic bodies could not be checked (and proved correct) independently of the context. It would defeat the goal stated initially, since some error messages would have to be stated in terms of what is done within the generic body.

Note that none of the problems of implicit inference based on the instantiation arise with the implicit specification of formal operations that exists for type patterns with boxes. Consider for example:

generic type ELEM is digits <>; function SQUARING(X : ELEM) return ELEM; function SQUARING(X : ELEM) return ELEM is begin return X * X; end;

Here the declaration of the formal type has the effect of providing implicit declarations for the operators of floating point types. Thus we have an implicitly declared formal function

    function "*" (LEFT, RIGHT :  ELEM) return ELEM;

so that identification of the "*" used in the generic body is done solely in terms of the generic specification.

The Ada solution permits independent checking of generic units and of generic instantiations. Hence it largely fulfills our goal of permitting the user to ignore the internal details of the generic units instantiated in his programs.

One limitation of the contract model concerns the ability to declare unconstrained objects. Consider a variant of the formulation of the generic procedure EXCHANGE:

generic type ITEM is private; procedure EXCHANGE(LEFT, RIGHT : in out ITEM); procedure EXCHANGE(LEFT, RIGHT : in out ITEM) is TEMPORARY : ITEM; begin TEMPORARY := LEFT; LEFT := RIGHT; RIGHT := TEMPORARY; end;

Then an instantiation with an unconstrained array type such as

    procedure SWAP is new EXCHANGE(ITEM =>  STRING);

will not work since a declaration of an unconstrained variable of type STRING (here TEMPORARY) would not be allowed. The same problem would arise if the actual type were a type with discriminants that must be constrained. Note on the other hand that the problem does not exist for constants - as in the original formulation:

    OLD_LEFT :  constant ITEM  :=  LEFT;

This limitation means that some instantiations may be rejected on the grounds that the body requires the ability to declare unconstrained objects of the formal type. We have considered this consequence to be preferable to an increase in the complexity of the syntax.

Another limitation concerns representation clauses. It is illustrated by the following example:

generic type T is private; package OCTETS is type R is record A : T; end record; for R'SIZE use 8; end;

since any instantiation with a type such that T'SIZE > 8 will fail. Again, such cases are considered sufficiently abnormal not to warrant any special language rule.

To conclude this section on formal types let us note that Ada provides formal types for all classes of type except record and task types. The major reason for this is that it is not clear that reasonable criteria for matching exist for these type classes - criteria that would be consistent with the degree of type checking performed elsewhere, yet at the same time have a good probability of being usable for many actual record types and task types.

12.4.3 Default Generic Parameters

In many cases, such defaults will actually be expressed by boxes. For example, the generic formal part of the generic function POWER can be rewritten as follows:

generic type ELEM is private; with function "*" (LEFT, RIGHT : ELEM) return ELEM is <>;

This parallels exactly the treatment of in parameters with default values for subprograms. The default parameter is optional, and an instantiation such as

    function "**" is new POWER(RATIONAL);

is taken as equivalent to the generic instantiation

    function "**" is new POWER(ELEM =>  RATIONAL,  "*" =>  "*");

where the actual operation "*" should have the specification

    function "*" (name_1, name_2 :  RATIONAL) return RATIONAL;

and the instantiation is legal if there is such a "*" operation for the type RATIONAL, whatever may be the parameter names. For the same reason

    function "**" is new POWER(BOOLEAN);

would be an error, since no such operation exists for the type BOOLEAN (assuming no explicit definition). Again, the generic body and the generic instantiations can be checked independently. Furthermore, the default can always be overridden by providing an explicit parameter as in

    function "**" is new POWER(VECTOR, MULT);

To summarize, the necessity to be able to check a generic body independently of its generic instantiations (an important user requirement) forces all operations applicable to a formal type to be specified, explicitly or implicitly, by the generic formal part. This could increase the number of generic parameters that must be supplied and could hence lead to a heavy syntax of generic instantiations. However, defaults can be specified for these operations, thus restoring much of the simplicity while losing none of the security.

In most applications it should be possible to have only types as mandatory parameters and to provide defaults for all operations. This is consistent with the goal stated in the introduction, that writing a generic unit may well require some care, but using it ought to be extremely simple.