Generic code... is it worth it?

[chris hermansen]

I'm getting too wordy in my old age, nevertheless...

On Sun, Nov 30, 2025 at 12:35 PM Jose E. Marchesi <jemarch@gnu.org> wrote:

>
> 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..


 Let's say I write a library that has the ability to manage what Java calls
"Map".  In Java, this means a mapping from a "key" to a "value".  In other
words, I can create a key and use it to retrieve a value associated with
that key.

By the way I think of this as a fundamental need of computing.

Thinking about this in Algol 68, we can define

mode Key = ....
mode Value = ...

I'm not sure about this, but maybe, if we were building a Map module, we
could leave the definition - definition after use - to the application
programmer.  That programmer, according to their needs, could define Key as
a union of int, string, date and whatever values need to be looked up, and
Value as a union of whatever values need to be retrieved.  This would be
cool.  Is it possible? I kind of think so but I'm not certain.

That is, the module that defines all of the Map functionality DOES NOT
DEFINE either mode Key or mode Value; but the application programmer must,
before using either of those modes (and anything to do with Map).

If this were possible, it would mostly do what I like to do in Java, except
that it would not protect me from storing a (String,Foo) key-value pair in
a (Date,Bar) map; or so I think... because in my application,

mode Key = union (String, Date, ...)
mode Value = (Foo, Bar, ...)

That is to say, each instance of Map x would be able to store any / all of
those modes.

What I think of as "real modals" would instead allow me to declare maps of
String → Foo and Date → Bar and not be able to put entries of one into the
other (in my carelessness / confusion).

That is, with "real modals" I would expect to be able to declare something
as

mode Foo = ...;
mode StringFooMap = Map<String,Foo>;
mode Bar = ...;
mode DateBarMap = Map<Date,Bar>;

and later on

StringFooMap x, y z;
DateBarMap a, b, c;

rather than unioning all the various key modes together and all the various
value modes together.

Reaching back to your perspective that this would cause massive ugliness
in... something in the compiler?... you might well be right; but it would
certainly make my intent more obvious, and I suppose it would make my code
more bullet-proof as well.

I hope this adds clarity to the reasons why I think modals are a Good Thing
(as long as they're well done).

-- 
Chris Hermansen · clhermansen "at" gmail "dot" com

C'est ma façon de parler.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/algol68/attachments/20251130/d3744600/attachment.htm>