Generic code... is it worth it?

[Jose E. Marchesi]

> Good morning Jose and list;
>
> I haven't edited the comments down so this is getting a bit long...
>
> On Mon, Dec 1, 2025 at 4:02 AM Jose E. Marchesi <jemarch@gnu.org> wrote:
>
>>
>> Hi Chris.
>>
>> > Jose and list,
>> >
>> > 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).
>> >>
>> >
>> > Where I'm coming from...
>> >
>> >    1. I am no kind of language designer / implementer; rather, I am a
>> >    language user, so my attitude to computer languages comes from using
>> them
>> >    for day to day coding purposes:
>>
>> Well that's actually the perspective that matters most IMO.  Language
>> designers and implementers sometimes have funny ideas, not necessarily
>> rooted in practical experience.
>>
>> >       1. At school in the 1970s I learned FORTRAN, IBM 360 assembly
>> >       language and PL/I reasonably well, PL/360, Algol W, Pascal and
>> > Algol 68 to
>> >       the point where I could write reasonable code in them;
>> >       2. In my working life, I used FORTRAN with a macro processor for
>> >       quite a long time, then Pascal (after I ported the MTS Pascal
>> compiler to
>> >       OS/VS1, continuing when I moved to our first Unix machine in 1984);
>> >       3. In the 1980s, I wrote a lexical scanner and recursive descent
>> >       parser for a kind of "parameter definition language" in Pascal;
>> >       4. In my first 20 years working on Unix, SunOS and Solaris, I
>> learned
>> >       three fundamental lessons:
>> >          1. I was OK with C but I really hated its lack of guardrails;
>> >          2. Even though Pascal was quite restrictive (seriously - array
>> >          bounds as a part of the type definition?) over the course of
>> time, its
>> >          strong typing, array bounds checking and other guardrails
>> > caught a lot of
>> >          my programming errors before I ever ran the code;
>> >          3. I could do a surprising amount of work with very compact awk
>> >          programs, especially given its support for regular expressions
>> and
>> >          associative arrays;
>>
>> All interesting observations.
>>
>> >       5. I started using Java in 1997 and have been a huge fan ever
>> since,
>> >       and increasingly use Groovy especially for scripting;
>> >       6. In the early 2000s, I ported my (still useful) parameter
>> >       definition language scanner / parser to Java;
>> >       7. I have tried LISP, Go, Python, Julia, Scala and probably a few
>> >       others, all of which I try to avoid whenever possible;
>> >       8. I also try to avoid JavaScript as much as possible, though I
>> will
>> >       certainly use it in preference to BASIC (that is to say, I would
>> rather
>> >       code complicated stuff in Google Sheets using JavaScript than in
>> Excel
>> >       using Visual Basic);
>> >       9. I have never bothered to learn any C++, Haskell, ocaml, Rust,
>> >       Perl, matlab, octave, Modula-2, Oberon, etc etc;
>> >    2. It's fair to say that in my 47 years of "life as a programmer",
>> Java
>> >    (and Groovy) have completely erased any interest I have in Pascal or
>> any of
>> >    its descendants, but I still have a very soft spot for Algol 68.
>>
>> Ok, so if I understand properly, Java offers you a good balance between
>> restrictedness (guardrails) and flexibility.
>>
>
> That's my perspective, reached over a good long time of hands-on.
>
> Java 1.4 had a class called Vector which implemented a kind of grow-able
> array of Object.
>
> Because users of Vector could add instances of any subclass of Object to
> the Vector instance, they sometimes did, often inadvertently.

Ok, so that Object is what plays the role of void* pointer in C.
Basically its existence in the language makes it possible to write
pretty generic code without having to replicate code.

> Java 1.5 introduced various growable collections, one of my favourites
> being HashMap.  So if you declare
>
> var myHashMap = new HashMap<String,MyDataStructure>()
>
> the compiler will fail if I try to add an entry whose value is other than
> an instance of MyDataStructure, for example
>
> myHashMap.add("second day of advent",LocalDate.of(2025,12,1))

These are more like "generics", which I think require some sort of
templating.  Another way to support generic code.

>
>
>
>> >> 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.
>> >>
>> >
>> > I've never looked "under the covers" at the way Java handles generics,
>> but
>> > I can say I've used them a LOT and I really appreciate the strong
>> > compile-time type checking they give me.  In particular, I have:
>> >
>> >    1. written many 10s of data management applications using generics
>> >    together with hash maps, to map String keys to some kind of data
>> structure;
>> >    2. occasionally run into a situation where I can use generics to give
>> >    myself generic classes that can be applied to several different data
>> >    structure configurations while ensuring maximal code reuse;
>> >    3. more recently but still fairly often, written applications that use
>> >    Streams to process structured data, requiring me to follow the use of
>> >    generics to code up my own BinaryOperator, Comparator and other bits
>> of
>> >    machinery that enable the application of Stream classes to processing
>> data
>> >    streams;
>> >    4. also more recently but still fairly often, using Function and
>> >    generics to code up lambdas.
>> >
>> > I have not ever spent solid time studying the way Java implements streams
>> > to the point where I can critique it for needless complexity or any other
>> > overwrought unpleasantness, but I can say that:
>> >
>> >    1. doing real stuff with Stream in Java requires some learning, both
>> of
>> >    the paradigm and the way it is implemented in
>> (strongly-statically-typed)
>> >    Java;
>> >    2. once that threshold is passed, the resulting code doesn't feel
>> >    clumsy, fragile nor laden with technical debt / bad code smells.
>> >
>> > So, while I bet your comment above, ie that there are some pretty
>> unwieldy
>> > generics implementations "out there", based on my significant personal
>> > experience with generics in Java, it is possible to implement them in
>> such
>> > a way as to be really useful and that doesn't produce a lot of
>> > complexity.
>>
>> As far as I understand it, Java is dynamic enough to admit an
>> implementation of generics via a "neutral" run-time object, which I
>> think is called Object.  It plays a similar role than void* in C.  The
>> operations on "neutral" objects is usually restricted: you can move them
>> around, etc. What is nice of that approach is that you don't need to
>> actually instantiate different copies of the same generic
>> routines/packages/etc: what people refer to as "monomorphization".
>>
>
> Every class in Java inherits from Object, or inherits from a class that
> inherits from another class that inherits from Object, or...
>
> Maybe I don't understand you though, but I don't see this as being related
> to the utility of generics in Java.  Here's a really simple declaration
> using generics, from the official Java documentation:
>
> public class Box<T> {
>     // T stands for "Type"
>     private T t;
>
>     public void set(T t) { this.t = t; }
>     public T get() { return t; }
> }
>
> Then an instance of Box might be declared as:
>
> var foo = new Box<LocalDate>();
>
> foo.set(LocalDate.of(2025,12,1));
>
> I think I can imagine something like this in Algol 68 without stretching
> too hard
>
> mode Box<T> = struct (T t);
>
> Box<int> foo;
> t of foo := 42
>
> Combined with modules, this "feels" like it could get pretty interesting,
> though to be completely transparent, I have not really tried to sketch out
> much more than this.

The difference between Object (or Lindsey's restricted modals, which are
basically names, or void*) and generics or templates, is in the
implementation.

>>
>> But then I think something called Java generics also got added at some
>> point, and this one is probably based on monomorphization, i.e. in
>> replicating code.  The interpreted nature of Java may alleviate the
>> problem of templated code replication, but in languages primarily
>> compiled ahead-of-time, like C or Algol 68, I don't see a way to
>> implement generic via monomorphization without making copies of each
>> specialized instance in each compilation unit.
>>
>
> Not sure the interpreted vs compiled argument is valid here - Java is
> compiled ahead of time, into code for the Java Virtual Machine.  Those
> instructions are interpreted and often compiled right down to machine code
> as "Just in time".

The difference is that when you compile code JVM ahead of time, you can
accompany the compiled code with the associated IR that gave origin to
the compiled code.

In GCC we don't have that luxury, unless we emit the GCC IR (gimple) as
well as the pre-compiled object code.  At the moment that is done in
LTO, but not further.  That is necessary, for example, to determine the
size of the objects should the generic code want to allocate them in the
stack.

> I believe, though I can't point to proof of my belief, that behaviour
> (methods) code lives in the class definition, not in the instance
> definitions.
>
> In any case, Algol 68 already supports declaring procedures as elements of
> structures, so right now we can 1) declare a structured mode with a proc
> field 2) create a name of that mode and 3) assign a value (ie a procedure
> body) to the proc field.

Yes, that is doable and usable with Lindsey's restricted modals.

>>
>> Algol 68's type system doesn't have such a "neutral" object.  Lindsey's
>> proposal for modals speak of "restricted modals" in which the modal is
>> only accepted in `ref MODE' and `ref[]MODE' contexts.  In this approach,
>> the name becomes this "neutral" object.  This is very much
>> non-orthogonal, but the alternative would be templating aka
>> monomorphization.
>>
>
> As I said above, I don't see the "neutral object" concept as being part of
> what makes Java generics work.  Clearly however the fact that Object has a
> method that calculates hash code and all subclasses of Object inherit that
> behaviour (and may override it) makes it easy to rely on a hash function
> always being at hand.
>
> But I think if we defined a structured mode that included an operator
> field, we could then assign an operator to that field to handle the hashing
> for that specific mode of the key.
>
>>
>> > 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.
>> >>
>> >
>> > Don't forget user interfaces!
>>
>> In what sense?
>>
>
> Again, using Java as an example, much of the Java Swing UI makes use of
> generics; for example combo box models, list models, cell renderers etc etc.

Ok.

>
>>
>> > And then please consider: if you eliminate data structures, sorting,
>> > and user interfaces, you have eliminated a great deal of what
>> > programmers actually do!
>>
>> No no, I wasn't implying these use cases are not important.  On the
>> contrary, I was pointing out _these_ are the use cases to support.
>>
>
> Ok! my misunderstanding.
>
>>
>> > I think it's worthwhile considering what generics do, at a higher level:
>> > they abstract away a lot of the "how" details, in the same way functional
>> > programming proponents talk about the big advantage of functional
>> > programming as putting the programmer in the position of always working
>> on
>> > "what"  and not having to worry overmuch about the "how".
>> >
>> > Going back to the simple example of hash tables - both Python and Groovy
>> > provide a really compact way of initializing a hash map, adding elements,
>> > looking things up... for instance in Groovy:
>> >
>> > def myHashMap = ['am': 0, 'pm': 12]
>> >
>> > Looking at that, I can assume that if I look up the value for key 'am' I
>> > will get a time offset of 0 hours, whereas for the key 'pm', I will get a
>> > time offset of 12 hours.
>> >
>> > But Groovy won't complain, neither at compile time nor run time, if I try
>> > to look up an integer key, whereas in Java
>> >
>> > Map<String,Integer> myHashMap = Map.of("am",0,"pm",12);
>> >
>> > if I subsequently code
>> >
>> > var foo = myHashMap.get(42);
>> >
>> > the compiler will reject it.
>> >
>> >>
>> >> 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?
>> >>
>> >
>> > That depends on how much extra work (and potential bugginess) that is
>> > introduced by not having them.
>> >
>> >>
>> >> 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.
>> >>
>> >
>> > Ok so far, but if you had generics, you could use THE SAME qsort routine
>> to
>> > sort on string keys, date keys, etc.  Yes, you can get some way toward
>> this
>> > thanks to Algol 68 providing you with operator overloading so that you
>> > could define a COMPARE operator that works on int, another that works on
>> > real, another on string, another on Date and so forth, which is probably
>> a
>> > good enough solution in this case, since indexes and keys tend to be
>> > simple-ish types.
>> >
>> > But if your COMPARE operator for date only works on year/month/day and
>> > someone wants to include hours/minutes/seconds, they are going to have to
>> > get at your code so they can add their own COMPARE operator for
>> date-time,
>> > or maybe date-time-with-timezone...
>> >
>> > I think, anyway - maybe I'm missing something.
>>
>> Hm I am a bit lost.
>>
>> To recap: the example shows how you can use the same implementation of
>> the quicksort algorithm in a generic way, without resorting to
>> particular generic programming artifacts like templates or run-time
>> checked neutral objects.
>>
>> The cmp procedure has to be tailored to the nature of the elements being
>> sorted.  In a language with templates the user provides a sort method or
>> similar for the objects being sorted.  In the example above the user
>> provides the same logic as a routine argument to `qsort'.  What is the
>> difference?
>>
>> Your
>
>     pub proc qsort = (int left, right,
>                          proc(int,int)int cmp, proc(int,int)void swap) void:
>
> if done with generics might look like
>
>     pub proc qsort = (T left, right,
>                         proc(T,T)int cmp, proc(T,T)void swap) void:
>
> where T represents a type variable.  The code itself is the same, it's just
> the mode of the elements of the array and the mode of the arguments to the
> procedures that are parametrized, so that the programmer has to declare the
> mode of the actual mode parameter as part of a declaration using the
> parametrized mode.  Does that make sense?

Yes of course.  Now if inside qsort, compiled separately, you do:

   T foo;

what generator do you use?  How does the generator know how much memory
to allocate, and how to fill in sub-values with their own static and
dynamic parts, etc?

That's the difficulty: you need full type information at the time you
compile the generic code, and that you have at the time you generate
code that links with it, but not before.

Restricted modals, like in:

  pub proc qsort = (mode X, ref[]X list, proc(ref X, ref X)int cmp) void
  
will work provided X only appears in a context 'ref X' or 'ref[]X'.
Which is all we may need, I'm not saying otherwise.

>
>
>> > 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.
>> >>
>> >
>> > Again, I agree BUT you're only allowing string keys above, and operator
>> > overloading is only going to take you as far as however many key types
>> you
>> > can conceive of when you're implementing the hash tables in the first
>> > place, not providing a way for me to easily add my own type of key.
>>
>> Well, that depends on what "easily" is supposed to mean.
>>
>> You know more than me on that topic, but I would say what is difficult
>> about hashing is not the glu-ing of the data structure, which can be
>> done very easily in decent languages as shown in the example.  It is the
>> hashing functions themselves.
>>
>
> I'm going to decline to show you the "hashing bruises" vs the "hash table
> bruises"...

:)

> But I see op HASH as being a straightforward, already implemented way of
> defining a hashing function for every mode that I want to use as a key -
> int, string, Date, etc.
>
> So if I want to hash on Datetime, I can write a HASH operator for that.  I
> *think* that, with generics, I could assign that hash operator to a field
> in a structure.
>
> But really, awk has taught me that I can live with int and string keys.
> It's the wide range of values that  throw me for a loop (see below).

>
>>
>> So the Hashes module can focus on providing good hash functions, and
>> then the user can roll her own hash tables very easily.
>>
>> > As an aside, the problem is worse on the value side.  I guess your hash
>> > table of string -> integer could map to another table of integer ->
>> > mystructure, with this second table living outside the hash table end of
>> > things; but maintaining two data structures for the price of one is
>> pretty
>> > antithetical to "concentrating on the 'how' versus the 'what'".
>>
>> That is a very good point.
>>
>> >>
>> >> 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!
>> >>
>> >
>> > Maybe the first question to ask is, "is there a really minimal modal kind
>> > of thing that could be easily added to the language that deals with the
>> > most obvious use cases for modals"?
>>
>> That would be the restricted modals sketched by Lindsey I think.
>>
>
> I need to read that and play with it a bit.  As you correctly point out
> above, if I can figure out how to use them to support multi-mode hash
> tables, I've probably shown that they're more than ample.
>
> Thanks, I hope my long-winded comments above haven't put everyone to sleep
> yet.