Chapter 15 included some discussion of the problems encountered when attempting to make various techniques and abstract data types generic , that is, to make them readily applicable to a variety of underlying data types. Here, these goals and the difficulties with them are reviewed so as to set the stage for the introduction of more powerful techniques from ISO standard Generic Modula-2.
Chapters 14 and 15 emphasized the need to create conventional data structures in as generic a fashion as possible. The basic technique was to write the major part of the module in terms of some general data type name such as TheDataDype and then to have a renaming line at the top where the module was customized to a particular type. As this line is easily changed, the bulk of the code can readily be re-used.
Thus, one would write, for instance
DEFINITION MODULE IntSorts; FROM IntegerInfo IMPORT Compare; FROM Comparisons IMPORT CompareResults; TYPE Item = INTEGER; CONST GenCompare = Compare; TYPE CompareProc = PROCEDURE (Item, Item) : CompareResults; PROCEDURE Quick (VAR data : ARRAY OF Item); (* Other procedures and functions could be included as well. *) END IntSorts.
If the issue were the creation of a data structure, one could proceed as follows:
DEFINITION MODULE CardStack; TYPE Element = CARDINAL; CONST StackSize = 100; PROCEDURE Push (item : Element); PROCEDURE Pop (VAR item : Element); PROCEDURE Empty () : BOOLEAN; END CardStack.
The implementation module can access the renamed item, but its code has to be written in terms of the general name Element rather than the specific one CARDINAL. A simple change on one line of a copy the definition part of the module followed by a recompilation of both under a different module name then suffices to re-use the code with another numeric type.
IMPLEMENTATION MODULE CardStack; 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 CardStack.
As indicated in section 15.10, when one attempts to implement a fully generic technique (such as sorting), one is forced to sacrifice type checking, and this is a serious loss given the otherwise closely type-checked style of Modula-2. Consider, for example a simple swap, which in order to be generic has to be written:
PROCEDURE Swap (itemA, itemB : ARRAY OF LOC);
which is quite unsatisfactory, both because there is now no proper type checking.
Moreover one cannot even use the following --
TYPE SwapProc = PROCEDURE (VAR ARRAY OF LOC, VAR ARRAY OF LOC); CompareProc = PROCEDURE (ARRAY OF LOC, ARRAY OF LOC) : CompareResults;
because specific typed procedures, such as
PROCEDURE SwapReal (VAR x, y : REAL);
and
PROCEDURE CompareReal (x, y : REAL) : CompareResults;
cannot be assigned, respectively, to variables of these two types due to the type compatibility rules for parameters. (An ARRAY OF LOC is not the same kind of parameter as a REAL.)
Such code can also be made entirely generic, but at the same kind of cost as noted for techniques in section 16.1.1. For instance, an ADT such as a list can only be established if, upon creation of an instance of such a list, information is made available about the size of the items to be listed. This is possible by using the following strategy:
DEFINITION MODULE Lists;
TYPE
List;
PROCEDURE Init (Size : CARDINAL) : List;
PROCEDURE Append (Item : ARRAY OF LOC; To : List);
(* etc. *)
END Lists.
which could then be implemented in a manner similar to the following:
IMPLEMENTATION MODULE Lists;
IMPORT Storage;
FROM SYSTEM IMPORT
LOC;
TYPE
NodePointer = POINTER TO Node;
Node =
RECORD
to : NodePointer
END;
List = POINTER TO ListData;
ListData =
RECORD
item_size, length : CARDINAL;
head : NodePointer
END;
PROCEDURE Init (Size : CARDINAL) : List;
VAR
Res : List;
BEGIN
NEW (Res);
Res^.item_size := Size;
Res^.length := 0;
Res^.head := NIL;
RETURN Res
END Init;
PROCEDURE Append (Item : ARRAY OF LOC; To : List);
VAR
Ptr : ADDRESS;
Last : NodePointer;
BEGIN
IF To.size = SIZE (item)
THEN
ALLOCATE (Ptr, To.size);
IF To.length = 0
THEN
To.head := Ptr
ELSE
Last := To.head;
WHILE Last.to <> NIL
DO
Last := Last.to
END;
Last.to := Ptr;
Last.to.to := NIL
END
ELSE
(* code to raise a suitable exception *)
END
END Append;
END Lists.
Notice in this example that, apart from the awkwardness of this method, no safe check can be conducted on the type of the item being enlisted, or on the instance of the list itself. Only the size of the item one is attempting to enlist can be checked, so that if several lists of items of different types (but of the same size) are generated in a single application program, this technique is all but worthless. The only fix evident would be to generate yet another module that would serve as a kind of type registry to generate unique values of a type TypeId that would then have to be produced when generating the instance of the generic type and then supplied on every call to one of the procedures so that its value could be checked. Such a scheme might recover safety, but at the expense of both more awkwardness and re-inventing at run time the type checking that in most circumstances is done automatically by the compiler in a static fashion.
One is forced to conclude that truely generic software is difficult to produce in the base Modula-2 language, and that doing so has significant cost. That is, in the critical matter of producing re-usable code, Modula-2 fails to deliver on safe type-checked techniques, and so is a clumsy tool at best for generic software.
The question is, can the base language rules be modified in a simple and unobtrusive way to allow the development of generic structures and techniques that permit the translator to do its proper job of type checking on the actual parameters when an instance of the structure or technique is employed?
Such questions were raised by R. Sutcliffe at the 1987 meeting of the Modula-2 standards committee, and again in a discussion paper by K. Hopper and R. Sutcliffe at its 1994 meeting. After two years of considering various proposals, the committee decided that the answer is yes. In order to meet these requirements for modern programming facilities, Modula-2 can be extended by introducing parameterised type abstraction modules as described in the following sections.
NOTE: These facilities will only be available as described here in implementations that have included the generic Modula-2 extensions to the base language.