The first step is the introduction of a new type of library module called a generic separate module. This is a new kind of module having formal parameters that may be either type parameters and/or constant value parameters. A generic separate module serves as a template for constructing specific refinements of itself that have been customized using actual types and/or actual constant expressions.
A generic separate module consists of a generic definition module and a generic implementation module, each prefixed by the reserved word GENERIC. The generic definition module is a template from which a specific definition module may be refined. The generic implementation module is a template from which a specific implementation module may be refined.
NOTE: The process of refinement will be described in later sections of the chapter.
The important thing to note about this is that generic modules have formal parameters, just as do procedure definitions and declarations. The manner in which one substitutes actual parameters will be discussed in the next section. This one will concentrate on defining and declaring the generic modules.
As hinted at by the definition above, a generic module is distinguished from any other module by two things:
1. It starts with the reserved word GENERIC. This is how the module is flagged for the benefit of the compiler.
2. It (optionally) has formal parameters. These allow it to be used for a variety of data types. The formal parameters of a generic module are restricted to types and constant values only.
The definition part of a generic separate module is like any other definition module, except that it begins with the keyword GENERIC and it has a formal parameter list. The complete syntax is shown in figure 16.1.
Example 1: Produce a generic definition of a stack
Discussion: In such applications, it is expected that the structure will be manipulated independent of the kind of element it contains, so this data type is provided as a formal type parameter at this stage of things. All the work of programming is in the structure manipulation; the provision of the items to enter into the structure is made when the actual parameters are supplied as shown in the next section.
NOTE: This definition module is not complete; it is only an outline so as to show the syntax of a generic definition module.
GENERIC DEFINITION MODULE Stacks (Element: TYPE); CONST StackSize = 100; PROCEDURE Push (item : Element); PROCEDURE Pop (VAR item : Element); PROCEDURE Empty () : BOOLEAN; END Stacks.
NOTES: 1. Specification of a constant such as StackSize in the manner of this example constrains all the refinements of this module. If that were not the intention, such an item could instead be made a constant value parameter and then specified by the actual parameter.
2. Such a constant may be used in the corresponding generic implementation module, because as always implementation modules have access to such information in their corresponding definition modules.
3. Observe that the reserved word TYPE is here being used as though it were a type itself. That is, the word TYPE is here employed in the manner a pervasive standard identifier. It is, however, still a reserved word because of the base language definition of it.
Example 2: (A matrix generic as to both size and elements.)
Discussion: In cases like this the data structure itself needs parameterization in order to make the size (of the matrix in this case) generic.
GENERIC DEFINITION MODULE Matrix (Rows, Cols : CARDINAL; MatrixElement : TYPE); TYPE TMatrix = ARRAY [0 .. Rows-1] OF ARRAY [0 .. Cols-1] OF MatrixElement; PROCEDURE Invert (VAR m : TMatrix); END Matrix.
Example 3: Provide a generic definition of a module that defines a procedure type, and provides a procedure of this type that takes a generic parameter.
Discussion: This illustration defines a generic technique, as opposed to a generic Abstract Data Type (ADT). The definition below has both a parameter of the desired type and a procedure of the same type. This is unlikely in practice, as one would normally do one or the other in a given context. However, both approaches are allowed. Note that the type defined in the module can be used in the parameter list. This is a new kind of forward reference and can be employed only in this context.
GENERIC DEFINITION MODULE Validate (PType : TYPE; PValidProc : ValidProcType); TYPE ValidProcType = PROCEDURE (item : PType) : BOOLEAN; PROCEDURE Valid (item : PType) : BOOLEAN; END Validate.
Example 4: (An outline of a generic sort)
Discussion: This example illustrates the abstraction of a generic technique applied to an existing kind of structure (an array), rather than to the manipulation of a user-defined structure.
GENERIC DEFINITION MODULE Sorts (Item : TYPE; GenCompare : CompareProc); FROM Comparisons IMPORT CompareResults; TYPE CompareProc = PROCEDURE (Item, Item) : CompareResults; PROCEDURE Quick (VAR data : ARRAY OF Item); (* Other procedures and functions would be included as well. *) END Sorts.
Example 5: (Parameters are optional)
Discussion: This example illustrates that although in the majority of cases generic separate modules will be parameterized, this is not required, and non-parameterized instances are also useful. This module defines a counter, any number of instances of which may be refined under different names as shown in the next section.
GENERIC DEFINITION MODULE Counter; PROCEDURE Inc; PROCEDURE Reset; PROCEDURE Count () : CARDINAL; END Counter.
Each of the generic definition parts shown in the previous subsection also needs a corresponding generic implementation. As usual, however, the order in which all this is done depends somewhat on the needs of the project. It is possible to produce generic definition modules and the specific refinements with actual parameters as shown in the next section before writing the generic implementation parts (with their formal parameters) and then refining them with actual parameters.
The implementation part of a generic separate module is also like any other implementation module, except that it begins with the keyword GENERIC and it has a formal parameter list. The syntax is shown in figure 16.2.
In order to ensure that the generic definition and generic implementation parts have the same contract with the user that is implied by having parameters in the first place, generic Modula-2 adopts the following rule:
The parameters of the generic implementation module shall be identical to the parameters of the corresponding generic definition module.
This rule is similar to the rule that says that procedures defined as forward must have the same parameters when they are eventually declared and is also similar to the relationship between procedure definitions in a definition module and their declarations in the corresponding implementation module.
In each case, observe how the code sketches (for that is all they are) are done in terms of the formal (generic) parameters.
Shown below are the implementation parts that correspond to the definition parts of the generic modules in the last subsection.
Example 1: What follows is a possible generic implementation of the first example in section 16.2.1
GENERIC IMPLEMENTATION MODULE Stacks (Element : TYPE); VAR stack : ARRAY [0..StackSize] OF Element; stackPtr : CARDINAL; (* One could also arrange for StackSize to be a parameter. *) PROCEDURE Push (item : Element); BEGIN INC (stackPtr); stack[stackPtr] := item; END Push; PROCEDURE Pop (VAR item : Element); BEGIN item := stack[stackPtr]; DEC (stackPtr) END Pop; PROCEDURE Empty () : BOOLEAN; BEGIN RETURN stackPtr = 0 END Empty; BEGIN (* module body initialization *) stackPtr := 0 END Stacks.
NOTE: The constant StackSize is from the corresponding definition module. It may be used in this generic implementation module. However, the correctness of such use might not be checked until the refinement of that implementation is performed.
Example 2: The next module is a corresponding implementation for the generic definition of example 2 in section 16.2.1.
GENERIC IMPLEMENTATION MODULE Matrix (Rows, Cols : CARDINAL; MatrixElement : TYPE); (* Note that, as in any implementation module, the generic implementation module has access to the types defined in the corresponding definition. *) PROCEDURE Invert (VAR m : TMatrix); BEGIN (* your favourite technique *) END Invert; END Matrix.
Example 3: The next module is a corresponding implementation for the generic definition of example 3 in section 16.2.1.
GENERIC IMPLEMENTATION MODULE Validate (PType : TYPE; PValidProc : ValidProcType); PROCEDURE Valid (item : PType) : BOOLEAN; BEGIN RETURN PValidProc (item) END Valid; END Validate.
Example 4: Here is a sketch of a generic implementation of the Sorts module defined in example 4 of section 16.2.1.
GENERIC IMPLEMENTATION MODULE Sorts (Item : TYPE; GenCompare : CompareProc); FROM Comparisons IMPORT CompareResults; PROCEDURE Swap (VAR a, b : Item;) VAR temp : Item; BEGIN temp := a; a := b; b := temp; END Swap; PROCEDURE Quick (VAR data : ARRAY OF Item); BEGIN (* typical quicksort algorithm, except that compares are done by a procedure Compare which returns values of type Comparisons.CompareResults. Swaps are done using the refinement of the generic swap above. *) END Quick; END Sorts.
Example 5: (Parameters are optional) This example implements the non-parameterized counter found in section 16.2.1.
GENERIC IMPLEMENTATION MODULE Counter; VAR CurrentCount : CARDINAL; PROCEDURE Inc; BEGIN INC (CurrentCount); END Inc; PROCEDURE Reset; BEGIN CurrentCount := 0; END Reset; PROCEDURE Count () : CARDINAL; BEGIN RETURN CurrentCount END Count; BEGIN (* main *) Reset; END Counter.
As an optional part of the definition and implementation modules of a generic separate module, a formal module parameter provides an explicit interface between the body of the generic separate module and the body of any module refined from it. If the generic separate module has formal parameters (the usual situation), any refiner of it must provide corresponding actual parameters as shown in section 16.3. As indicated above, the code in the implementation part of the module works with the formal names, in the same manner as the code of a procedure.
There are two kinds of formal module parameters: constant value parameters and type parameters. The types of the former are specified by their formal type names; the latter are types, and this is specified by the keyword TYPE.
Constant value parameters provide a means of passing a constant to the refinement of a generic separate module. Constant value parameters are value parameters in almost the same sense as the value parameters used with procedures.
The type of a formal constant value parameter may be:
In the latter two cases, the type must be imported into or defined in (respectively) the generic definition module because the parameter lists of the definition and implementation modules are required to be the same.
Type parameters, on the other hand, provide a means of passing a type identifier to the refinement of a generic separate module.
NOTE: The new use of the word TYPE as a name is confined to the specific context of generic module parameters and does not extend to procedure parameter lists or any other context.