Reference Developer Tutorial 1 Introduction 2 Macros 3 Typesetting 4 Example 5 Hints 6 Examples 7 Webmaking SEARCH

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.

Webmaster Copyright © Ross N. Williams 1992,1999. All rights reserved.