2.5.5 Generics

In a generic interface or module, some of the imported interface names are treated as formal parameters, to be bound to actual interfaces when the generic is instantiated.

A generic interface has the form

    GENERIC INTERFACE G(F_1, ..., F_n);
      Body
    END G.

where G is an identifier that names the generic interface, F_1, ..., F_n is a list of identifiers, called the formal imports of G, and Body is a sequence of imports followed by a sequence of declarations, exactly as in a non-generic interface.

An instance of G has the form

    INTERFACE I = G(A_1, ..., A_n) END I.

where I is the name of the instance and A_1, ..., A_n is a list of actual interfaces to which the formal imports of G are bound. The instance I is equivalent to an ordinary interface defined as follows:

    INTERFACE I;
      IMPORT A_1 AS F_1, ..., A_n AS F_n;
      Body
    END I.

A generic module has the form

    GENERIC MODULE G(F_1, ..., F_n);
      Body
    END G.

where G is an identifier that names the generic module, F_1, ..., F_n is a list of identifiers, called the formal imports of G, and Body is a sequence of imports followed by a block, exactly as in a non-generic module.

An instance of G has the form

    MODULE I EXPORTS E = G(A_1, ..., A_n) END I.

where I is the name of the instance, E is a list of interfaces exported by I, and A_1, ..., A_n is a list of actual interfaces to which the formal imports of G are bound. ``EXPORTS E'' can be omitted, in which case it defaults to ``EXPORTS I''. The instance I is equivalent to an ordinary module defined as follows:

    MODULE I EXPORTS E;
      IMPORT A_1 AS F_1, ..., A_n AS F_n;
      Body
    END I.

Notice that the generic module itself has no exports; they are supplied only when it is instantiated.

For example, here is a generic stack package:

    GENERIC INTERFACE Stack(Elem);
      (* where Elem.T is not an open array type. *)
      TYPE T <: REFANY;
      PROCEDURE Create(): T;
      PROCEDURE Push(VAR s: T; x: Elem.T);
      PROCEDURE Pop(VAR s: T): Elem.T;
    END Stack.

    GENERIC MODULE Stack(Elem);

      REVEAL
        T = BRANDED OBJECT  n: INTEGER;  a: REF ARRAY OF Elem.T  END;

      PROCEDURE Create(): T =
        BEGIN  RETURN NEW(T, n := 0, a := NIL)  END Create;

      PROCEDURE Push(VAR s: T; x: Elem.T) =
        BEGIN
          IF s.a = NIL THEN
            s.a := NEW(REF ARRAY OF Elem.T, 5)
          ELSIF s.n > LAST(s.a^) THEN
            WITH temp = NEW(REF ARRAY OF Elem.T, 2 * NUMBER(s.a^)) DO
              FOR i := 0 TO LAST(s.a^) DO temp[i] := s.a[i] END;
              s.a := temp
            END
          END;
          s.a[s.n] := x;
          INC(s.n)
        END Push;

      PROCEDURE Pop(VAR s: T): Elem.T =
        BEGIN  DEC(s.n);  RETURN s.a[s.n]  END Pop;

    BEGIN
    END Stack.

To instantiate these generics to produce stacks of integers:

    INTERFACE Integer; TYPE T = INTEGER; END Integer.
    INTERFACE IntStack = Stack(Integer) END IntStack.
    MODULE IntStack = Stack(Integer) END IntStack.

Implementations are not expected to share code between different instances of a generic module, since this will not be possible in general.

Implementations are not required to typecheck uninstantiated generics, but they must typecheck their instances. For example, if one made the following mistake:

    INTERFACE String; TYPE T = ARRAY OF CHAR; END String.
    INTERFACE StringStack = Stack(String) END StringStack.
    MODULE StringStack = Stack(String) END StringStack.

everything would go well until the last line, when the compiler would attempt to compile a version of Stack in which the element type was an open array. It would then complain that the NEW call in Push does not have enough parameters.