6.7 Generics

It is well known that generics in programming languages are closely aligned with textual substitution. In fact, a good way to understand the generic facility of a new programming language is to ask oneself the question "In what way does this generic facility differ from simple text substitution?" The differences, if any, typically have to do with the difference in scoping between textual and intelligent substitution and whether the generic code is shared or copied by the implementation. In most cases the differences are quite minor.

Because generic facilities are so closely aligned with text substitution, it is possible to use FunnelWeb's parameterized macros to provide generics in programming languages that do not support generics. Simply write a FunnelWeb macro whose parameters are the parameters of the generic and whose body is the generic object.

The following FunnelWeb file gives an example of a fully worked Vax Pascal generic set package implemented using FunnelWeb parameterized macros. The package was written by Barry Dwyer of the Computer Science Department of the University of Adelaide in 1987 and was emailed to me on 11 November 1987. The generic package provides a set abstraction implemented using linked lists. Note the clever use of the instantiation parameters in type, function, and procedure names.

@$@<Generic Set Module@>@(@2@)==@{@-
@! @1 is the base type, @2 is the set type.
[inherit ('@1'), environment ('@2')]

module @2;

type  @2 = ^@2Record;
      @2Record = record
         Member: @1;
         Next: @2;
         end;

procedure Null@2 (var Result: @2);
begin new (Result);
Result^.Member := (- MaxInt)::@1;
Result^.Next := nil end;

function IsNull@2 (S: @2): boolean;
begin
IsNull@2 := S^.Member::integer = - MaxInt
end;

procedure ForEach@1 (S: @2; procedure DoIt (i: @1));
var   ThisS, NextS: @2;
begin ThisS := S;
while ThisS^.Member::integer <> - MaxInt do
   begin NextS := ThisS^.Next;
   DoIt (ThisS^.Member);
   ThisS := NextS end;
end;

function First@1 (S: @2): @1;
begin First@1 := S^.Member end;

function Is@1InSet (i: @1; S: @2): boolean;
   procedure TestEquals (j: @1);
   begin if Equal@1 (i, j) then Is@1InSet := true; end;
begin
Is@1InSet := false;
ForEach@1 (S, TestEquals);
end;

function Includes@2 (S1, S2: @2): boolean;
var Result: boolean;
   procedure TestIfInS1 (i: @1);
   begin
   if Result then
      if not Is@1InSet (i, S1) then
         Result := false;
   end;
begin Result := true;
ForEach@1 (S2, TestIfInS1);
Includes@2 := Result end;

function Disjoint@2s (S1, S2: @2): boolean;
var Result: boolean;
   procedure TestIfInS1 (i: @1);
   begin
   if Result then
      if Is@1InSet (i, S1) then
         Result := false;
   end;
begin Result := true;
ForEach@1 (S2, TestIfInS1);
Disjoint@2s := Result end;

function Equal@2 (S1, S2: @2): boolean;
begin
Equal@2 := Includes@2 (S1, S2) and
           Includes@2 (S2, S1);
end;

procedure Insert@1 (i: @1; var S: @2);
var   This, Pred, Succ: @2;
begin
if not Is@1InSet (i, S) then
   begin
   Pred := nil; Succ := S;
   while Succ^.Member::integer > i::integer do
      begin Pred := Succ; Succ := Succ^.Next end;
   if Succ^.Member::integer < i::integer then
      begin
      new (This);
      This^.Next := Succ;
      This^.Member := i;
      if Pred <> nil then
         Pred^.Next := This
      else
         S := This;
      end;
   end;
end;

procedure Insert@1s (S1: @2; var S2: @2);
var   This, Pred, Succ: @2;
   procedure Add@1 (i: @1);
   begin Insert@1 (i, S2) end;
begin
ForEach@1 (S1, Add@1);
end;

procedure Remove@1 (i: @1; var S: @2);
var   Pred, This: @2;
begin
Pred := nil; This := S;
while not Equal@1 (This^.Member, i) do begin
   Pred := This; This := This^.Next end;
if Pred <> nil then
   Pred^.Next := This^.Next
else
   S := This^.Next;
Dispose (This);
end;

procedure Dispose@2 (var S: @2);
var   Old: @2;
begin
while S <> nil do
   begin
   Old := S;
   S := S^.Next;
   Dispose (Old)
   end;
end;

end.
@}

@O@<NaryTreeSet.pas@>==@{@-
  @<Generic Set Module@>@-
@(@"NaryTree@"@,@"NaryTreeSet@"@)@}
@O@<NaryTreeSetSet.pas@>==@{@-
  @<Generic Set Module@>@-
@(@"NaryTreeSet@"@,@"NaryTreeSetSet@"@)@}

A great advantage of the approach reflected in the above example is that it allows the programmer to construct a generic object in a language that does not supply generics, with complete typesafety.  This contrasts to the approach that might be used in a language such as C where the programmer might choose to construct a "generic" package by parameterizing a package with pointers to void. The resulting package is powerful but extremely untypesafe. Such a generic list package is used in the code of FunnelWeb itself and caused no end of problems, as the compiler had no way of telling if pointers to the correctly typed object were being handed to the correct list-object/function combination.

The major disadvantage of the text generic approach is that it causes the code of the generic object to be duplicated once for each instantiation. Depending on the number and size of the instantiations, this may or may not be acceptable.

Where the duplication of code is unacceptable, a hybrid approach may be taken. As in the C example, the programmer could write a single generic package using pointers to void or some other untypesafe mechanism. Then the programmer creates a FunnelWeb generic package whose functions do nothing more than call the functions of the untypesafe package, and whose types do nothing more than contain the types of the untypesafe package. This solution involves the use of untypesafe programming, but this is a one-off and if done carefully and correctly, the result can be a typesafe generic package involving minimal code duplication.