Generic code... is it worth it?

[Jose E. Marchesi]

Hello people!

So mnabipoor and I spent some time this weekend musing about generic
code in general and Algol 68 in particular.  We looked at Lindsey's
sketch for modals published in the Algol Bulletin 37 and discussed its
many problems and implementation difficulties.  We also did a little
survey of the techniques used by other programming languages to deal
with generic code, monomorphization, and what not, and how well Algol 68
suites itself to them (spoiler: not very well).

To us, it is quite obvious that people is clearly willing to pay an
_enormous_ toll for the generic programming capabilities in their
programming languages of choice: incredibly complicated implementations,
kilometric unreadable diagnostics that are basically useless,
unavoidable and shameful gigantismus in the resulting programs, the
consequential dependency on tools that really should not be necessary,
like multi-threaded linkers... and many more unpleasantries.

Then we asked ourselves the (also obvious) question: once the blood
(fat) price is paid, what do they use the expensive goodies for?  In the
vast majority of cases this is to implement stacks, lists, vectors, hash
tables and other generic data structures, and also sorting routines, in
comfort.

This brought us to the next question: if your programming language of
choice, whatever it is, provides good enough mechanisms to realize these
concepts in a reasonable and convenient way, do you really need the
generic programming features on top of them, considering how expensive
they are?  Is it worth it?

Let's start with sorting.  Sorting is a pretty generic operation,
because the whole business only depends on an ordered set or domain and
the ordering relationship between the elements in the set.  It really
doesn't matter what you are sorting, apart from given two elements of
the set, being able to determine which one is bigger or lesser or equal.

Suppose then that we write the following module:

  module QSort =
  def
      pub proc qsort = (int left, right,
                        proc(int,int)int cmp, proc(int,int)void swap) void:
      begin
            proc partition = int:
            begin int pivot = right;
                  int i := left - 1, j := left;
                  while j <= right - 1
                  do if cmp (j, pivot) <= 0
                     then i +:= 1;
                          swap (i, j)
                     fi;
                     j +:= 1
                  od;
                  swap (i + 1, right);
                  i + 1
            end;

            if left < right
            then int pi = partition;
                 qsort (left, pi - 1, cmp, swap);
                 qsort (pi + 1, right, cmp, swap)
            fi
      end;

      skip
  fed

The `qsort' routine takes an interval of indexes, that define the set of
elements, a comparator routine that knows how to compare elements given
their indexes, and a swapping routine that knows how to swap the
elements given their indexes.  This is how qsort can be used to sort a
multiple of ints (similar examples coul be written to sort other kind of
multiples, or elephans, or whatever):

  access QSort
  begin [5]int list := (5,1,100,-2,1);

        qsort (LWB list, UPB list,
               (int a, b) int: (list[a] > list[b] | 1 |: list[a] < list[b] | -1 | 0),
               (int a, b) void: (int t = list[a]; list[a] := list[b]; list[b] := t));

        { Check the multiple values are indeed sorted.  }
        for i from LWB list to UPB list - 1
        do assert (list[i] <= list[i+1]) od
  end;

So given the perfectly generic definition of `qsort', it takes only
three lines of perfectly clear and concise code in order to put it to
good use.  With no macros, with no templates.  Of course, this is
because of Algol 68's sheer expressiveness and nice abstractions.  But
it is Algol 68 we are talking about.

Then there are lists, vectors, hash tables, and the like "generic" data
structures... the typical favorite applications of generic code
features.  Suppose we have a module that implement supercomplicated and
genius-level hashing functions:

  module Hash =
  def
      pub int hash_table_size := 1008;

      pub proc hash_string = (string s) int:
      begin bits hash;
            for i to UPB s
            do hash := BIN (ABS hash * 613 + ABS s[i]) od;
            hash := hash AND BIN (ABS (BIN 1 SHL 30) - 1);
            ABS hash %* hash_table_size
      end;

      skip
  fed

Then we could use them to build our own hash tables:

  access Hash
  begin mode Bucket = struct (string s, int i, ref Bucket n);
        ref Bucket no_bucket = nil;
        [hash_table_size]Bucket table;

        proc put = (ref[]Bucket t, string s, int v) void:
           (get (t, s) = -1 | int h = hash_string (s); t[h] := (s, v, n of t[h]));

        proc get = (ref[]Bucket t, string s) int:
           (ref Bucket p := t[hash_string (s)];
            while (p :/=: no_bucket) andth (s of p /= s) do p := n of p od;
            (p :/=: no_bucket | i of p | -1));

        put (table, "one", 1);
        put (table, "two", 2);
        assert (get (table, "one") = 1);
        assert (get (table, "two") = 2)
  end

So we have implemented a perfectly functional hash table data structure
in nine lines of code not counting empty lines (this table is on the
stack, using the heap would require adding a couple of `heap' keywords
but no additional lines).  Again, it could be argued this is easy
because of Algol 68's expressive power.  But again, it is Algol 68 we
are talking about.

So yes, we could add modals to the language, implemented as templates or
a more sophisticated and less gross solution like Swift does.

But, is the price to pay for it _really_ worth it?
Would really love to hear people's opinions about this..

Salud!