16.6 Making New ATDs From Old with Generics

16.6 Making New ADTs from Old With Generics

The technique shown in the previous section is worth expanding upon in some additional detail as the most likely use of Generic Modula-2 will be to refine Abstract Data Types as separate library modules that are then used as many times as desired in an application. Along the way, new facilities could be added to a generic separate module to form a new generic separate module that could in turn be refined with a specific data type.

Suppose one begins with a classical data structure such as a list, parameterized for the type to list. A framework could look like:

GENERIC DEFINITION MODULE Lists (DataType : TYPE);
TYPE
  List;
PROCEDURE Create (VAR l : List);
PROCEDURE Destroy (VAR l : List);
PROCEDURE Add (l : List; item : DataType);
PROCEDURE Delete (l : List; item : DataType);
PROCEDURE Find (l : List; item : DataType);
END Lists.

GENERIC IMPLEMENTATION MODULE Lists (DataType : TYPE);
TYPE
  NodePointer = POINTER TO Node;
  Node = 
    RECORD
      theItem : DataType;
      next : NodePointer;
    END;
  List = POINTER TO ListRecord;
  ListRecord =
    RECORD
      Head : NodePointer;
      numberActive : CARDINAL;
    END;
(* all stubbs, testing concept only *)
PROCEDURE Create (VAR l : List);
END Create;
PROCEDURE Destroy (VAR l : List);
END Destroy;
PROCEDURE Add (l : List; item : DataType);
END Add;
PROCEDURE Delete (l : List; item : DataType);
END Delete;
PROCEDURE Find (l : List; item : DataType);
END Find;
END Lists.

This generic separate module may be refined as it is to produce new separate or local modules implementing lists for a specific data type, and as many of these lists as desired may then be employed. Alternately, one could refine in a generic module to produce, say, generic sorted lists. One first creates a new generic definition module and then refines the generic separate module above in the implementation, with appropriate exports per the definition:

GENERIC DEFINITION MODULE ListsSorted (DataType : TYPE; Compare : CompareProc ); 

FROM Comparisons IMPORT
  CompareResults;
  
TYPE
  List;
  CompareProc = PROCEDURE (DataType, DataType) : CompareResults;
  
PROCEDURE Create (VAR l : List);
PROCEDURE Destroy (VAR l : List);
PROCEDURE Delete (l : List; item : DataType);
PROCEDURE Find (l : List; item : DataType);
PROCEDURE Insert (theList : List; theItem : DataType);
END ListsSorted.

GENERIC IMPLEMENTATION MODULE ListsSorted (DataType : TYPE; Compare : CompareProc); 

MODULE SLists = Lists (DataType);
EXPORT List, Create, Destroy, Delete, Find;
END SLists;

PROCEDURE Insert (theList : List; theItem : DataType);
END Insert;

END ListsSorted.

This new generic separate module may now be refined to produce a separate module for lists of a particular data type; for instance:

DEFINITION MODULE IntListsSorted = ListsSorted (INTEGER, IntegerInfo.Compare);
END IntListsSorted.

A program module may be written that imports and uses this separate module, creating as many of the sorted lists of integers as desired.

Here is a second example of a similar kind--this one employing successive refinements of a generic Queue data type. One begins, as always, with the definition and implementation parts of the generic separate module.

GENERIC DEFINITION MODULE Queues (itemType : TYPE; maxSize : CARDINAL);
TYPE
  Queue;   (* details in implementation *)
  ActionProc = PROCEDURE (itemType);

PROCEDURE Init (VAR q : Queue);
PROCEDURE Destroy (VAR q : Queue);
PROCEDURE Full (q : Queue) : BOOLEAN;
PROCEDURE Empty (q : Queue) : BOOLEAN;
PROCEDURE Enqueue (q : Queue; item : itemType);
PROCEDURE Serve (q : Queue; VAR item : itemType);
PROCEDURE Traverse (q : Queue; Proc : ActionProc);

END Queues.

GENERIC IMPLEMENTATION MODULE Queues (itemType : TYPE; maxSize : CARDINAL);

TYPE
  Queue    (* details here *);

(* provide code *)
END Queues.

In the examples of local refinement taken thus far, no new facilities were added. However, this may also be done. Perhaps the most interesting way is to define new separate modules (whether Generic or not) that use some or all of the functionality developed in existing generic separate modules but with some changes or additions.

Suppose, for instance, one wished to develop a new separate module to define and implement priority queues, using as a partial base the generic separate module Queues illustrated above. The definition might be altered as follows:

GENERIC DEFINITION MODULE PriorityQueues
     (itemType : TYPE; maxSize : CARDINAL, Compare : CompareProc);

TYPE
  PQueue;   (* details in implementation *)
  ActionProc = PROCEDURE (itemType);
  CompareResults = (less, equal, greater);
  CompareProc = PROCEDURE (itemType, itemType) : CompareResults;

PROCEDURE Init (VAR q : PQueue);
PROCEDURE Destroy (VAR q : PQueue);
PROCEDURE Full (q : PQueue) : BOOLEAN;
PROCEDURE Empty (q : PQueue) : BOOLEAN;
PROCEDURE Enqueue (q : PQueue; item : itemType);
PROCEDURE Serve (q : PQueue; VAR item : itemType);
PROCEDURE Traverse (q : PQueue; Proc : ActionProc);

END PriorityQueues.

In this version, refinement requires a procedure parameter that provides the functionality of determining the relative priority of two items of the type to be enqueued (presumably by examining some field of the data), so that a new item can be placed in the proper place in the queue.

When the implementation part is written, most of the procedures in the original generic implementation part can be retained by exporting them in the refinement. The Enqueue procedure will, however, have to be changed. Portions of the implementation would look like:

GENERIC IMPLEMENTATION MODULE PriorityQueues
     (itemType : TYPE; maxSize : CARDINAL; Compare : CompareProc);

IMPORT Queues; (* this done for refinement purposes *)
TYPE
  PQueue = Queue; (* type exported from local refiner *)
MODULE LocalQueues = Queues (itemType, maxSize); (* pass along parameters. *)
EXPORT Queue, Init, Destroy, Full, Empty, Serve, Traverse;
END LocalQueues;

PROCEDURE Enqueue (q : PQueue; item : itemType);
(* code to place a data item in position by doing comparisons as needed *)
END Enqueue;
END PriorityQueues.

NOTES: 1. Since a local refinement is performed on the implementation part of the generic separate module, the details of the data type PQueue itself are available in the new module for its use and therefore it is possible to replace the procedure Enqueue in this way. This should not be thought of as a relaxation of the rules for opaque types, but rather as the inclusion of what can be regarded as a copy of the (refined) code (that is, with the appropriate parameter substitutions made) in the implementation module.

2. For clients of refinements of this new module, the type PQueue is of course exported opaquely by the refinements of the definition part of the module.

3. Because the refined implementation can export into the scope of the refinement only those items named in the generic separate definition module, any other items in the implementation can not be made available in the scope of the refinement for use there and remain strictly private.

Should it be also be thought desirable to refine a separate module specified as to the data type and size, it would be a simple matter to define the appropriate type in a separate module, import from this in the new definition part, and then refine fully in the implementation part, thus:

DEFINITION MODULE StudentPriorityQueues;

FROM Students IMPORT
  Student;
TYPE
  PQueue;   (* details in implementation *)
  ActionProc = PROCEDURE (CHAR);

PROCEDURE Init (VAR q : PQueue);
PROCEDURE Destroy (VAR q : PQueue);
PROCEDURE Full (q : PQueue) : BOOLEAN;
PROCEDURE Empty (q : PQueue) : BOOLEAN;
PROCEDURE Enqueue (q : PQueue; item : Student);
PROCEDURE Serve (q : PQueue; VAR item : Student);
PROCEDURE Traverse (q : PQueue; Proc : ActionProc);

END StudentPriorityQueues.

IMPLEMENTATION MODULE StudentPriorityQueues;

IMPORT Queues;
FROM Students IMPORT
  Student, CompareStudent;

TYPE
  PQueue = Queues.Queue;
MODULE LocalQueues = Queues (Student, maxSize );
EXPORT Queue, Init, Destroy, Full, Empty, Serve, Traverse;
END LocalQueues;

PROCEDURE Enqueue (q : PQueue; item : Student);
(* code to place a data item in position by doing comparisons
   as needed *)
END Enqueue;
END StudentPriorityQueues.

In this version, the functionality associated with the data type Student and that associated with the generic separate module Queues is combined (and extended as above) into a single refined module with a standard client interface.

NOTE: The new definition part of the refined module must be produced in full in such cases, because the base language does not permit a definition module to contain a local module, and hence it cannot itself contain a refining local module acting on the definition part of the original generic separate module. This is one reason why the refinement of generic modules as local modules is defined in standard Generic Modula-2 to be the refinement of the implementation part of the generic separate module.

The partial refinement of a generic separate module allows the programmer to add facilities to or restrict facilities from an existing generic separate module when producing either a new separate module (generic or not) or a refinement in a program module.

Contents