Generics systems

entomy profile image Patrick Kelly ・6 min read

First, let me say what this isn't. This is not an explanation of how generics work, nor a tutorial on using generic subroutines/types/modules. There's plenty of fantastic tutorials on using generics in your language of choice, and I'm not going to replicate already splendid work.

Now, what this is, is a comparison of various generic systems used in many different programming languages. I've been wanting to cover this for a while, someone suggested a more limited form of this, I told them I would do it, and now I'm doing it.

So, as far as making things generic goes, there's three "levels" of code constructs that can be templated: subroutines, types, and modules. Exactly what is supported will vary with what programming language you are using. Since this blog has primarily been covering the .NET world, with C# in particular, let's look at that specifically.

C# supports two of these levels: subroutines and types. A generic subroutine, a.k.a. generic method, is simple, either being indiscriminate of the caller or dispatching on the caller, in either case making it so you can't have generic conditions on the caller. Generic extension methods can get around this issue in a satisfactory way and are —in my opinion— where generic subroutines are most powerful. The other side of this is generic types, which is straightforward in C#. You add the generic parameters to a class, interface, or struct, and the whole type is templated on that. For each permutation of types passed into the template, you get a unique type back, even if they share a common name and behavior. The only thing usable as generic parameters are types, and this is where the limitations of C#'s generics begins to show. More on what other possibilities exists later. Lastly we have generic constraints, which are used to limit or add requirements to the generic parameters, this are as follows: struct, class, notnull, unmanaged, new(), and lastly any type, which will require the constrained parameter be of or derived from that type. Pretty full featured. You can do a lot with this. And I in fact do a lot with this feature set.

But let's consider one of the major tripping points people have. This is a common criticism I see levied when people are proposing improvements to C#. Let's write some generic mathematics code.

T lcm<T>(T a, T b) where...? = abs(a * b) / gcd(a, b);

Uh oh. There's numerous problems with this.

Firstly, what do we even put down as the generic constraint? unmanaged gets us close, but includes to non-numeric types, like structs composed of other unmanaged types, including points and quaternions! Because of that, it's nowhere near specific enough for this purpose. But also, we can't use standard operators in a generic context either. And to make matters even worse, the compiler isn't going to know how to resolve abs() or gdc() either, unless they exist in the same module we're defining lcm(), which, probably is the case, but you can see how this would be problematic.

What are the ways around this?

If you must stick with C#, you must write unique methods for each numeric type. That's Byte, SByte, Int16, UInt16, Int32, UInt32, Int64, UInt64, Single, Double, and Decimal. Then the Big* variants if you need that, Complex and Quaternion if appropriate, and Vector* and Matrix* if appropriate.

Yeah, no. That's ridiculous. Are there other generics systems that address this better? Yes, plenty, and we don't even need to look far.

F#, despite being a CLR/CLS Compliant producer and consumer, adds its own extensions on top which aren't necessarily CLS Compliant. While it can easily consume C#/VB code, and it can potentially produce code that can be consumed from C#/VB, it can produce code that can't be consumed from C#/VB. And because of how F# works, a lot of those extensions are related to generics.

let inline lcd< ^a
    when ^a : (static member ( * ) : ^a * ^a -> ^a)
    and ^a : (static member ( / ) : ^a * ^a -> ^a)>
    (a:^a)(b:^a) = abs(a * b) / gcd(a)(b)

Honestly, I'm not in the mood to fully debug this one, so it's not copypasta and run, but it's close enough to show the point. Hey, maybe, I've even written enough of these that it runs first try.

The reason why this works is because instead of constraining it on a type, F# allows us to constrain on required members or static members. In this case, on required multiplication and division operators. This does assume abs() and gcd() are defined and able to be used in this context as well, but that's typically going to be the case when writing highly generic code in F#. We're constraining based on traits or properties of the types, just more explicitly than how languages like Rust handle traits.

F# then, unsurprisingly, supports a richer set of constraints, including null, not null, struct, not struct, enum<>, delegate<>, comparison, equality, unmanaged, (new : unit -> 'a), as well as the aformentioned member signatures available in both (member ...) and (static member ...) forms.

That's great right? Only I still find that extremely limited. See, I didn't start my development journey in the .NET world. I've seen things man. Some of them make you wonder what the language designers were thinking. Some of them though, are outright fantastic. Ada has both, not just across the language either. For generic systems Ada has both.

First, let's get the head scratcher out the way: Ada does not support inline instantiation of generics. This is the single biggest dumbfounding thing I've seen in any programming language out there. It makes it phenomenally difficult to provide unit testing frameworks, and effectively means you get the unit testing framework generators that generate a testing harness per project and... oh boy.

But I wouldn't be mentioning this without Ada's generics doing some fantastic things as well.

In case you're unfamiliar, here's Ada's type tree:

Ada's type tree

You'll notice it is in fact a tree, complete with a hierarchy. If you expect there's inheritance, then yes, there is. But not at all in the way you might be thinking. This isn't implemented through object inheritance. Rather, the only thing you can actually have access to in normal code is the leaves of this tree. The observant of you will notice I said normal code. You have access to this entire thing with generics.

Because of the sophistication with Ada's generic constraints (they call them generic formals), there's a need to break the constraints into categories. These are "generic formal objects", "generic formal types", and "generic formal subprograms". Generic formal types are as follows: type T (<>) is limited private, type T (<>) is private, type T is private, type T (<>) is abstract tagged limited private, type T (<>) is tagged limited private, type T (<>) is abstract tagged private, type T (<>) is tagged private, type T (<>) is new U, type T (<>) is abstract new U with private, type T (<>) is new U with private, type T is (<>), type T is range <>, type T is mod <>, type T is delta <>, type T is delta <> digits <>, type T is digits <>, type T is array (I) of E, type T is access O.

Whoa. That's a lot of dama... constraints, I mean constraints. Some of these constrain specifically to any integer type, like type T is range <>. But we can also advance in the hierarchy with things like type T is (<>), which covers any discrete type, including integers, modulars (unsigned), and enumeration types. It's not perfect however, there's no constraint for say "any numeric type". However, this was never meant for that level of genericity. Rather, these are simply common sets of building blocks to utilize. You can go further by adding subprogram constraints just like with F#'s member constraints.

    type T is private;
    with function "*"(A, B : T) return T is <>;
    with function "/"(A, B : T) return T is <>;
    with function abs(A : T) return T is <>;
    with function gcd(A, B : T) return T is <>;
function lcd(A, B : T) return T is (abs(a * b) / gcd(a, b));

Ignoring what the type T is private part is, because "nonlimited definite type" isn't going to mean much to non-Ada programmers, we clearly have a function that will work for anything with *, /, abs(), and gcd() available for it. Nice!

But there was another category of generic formals Ada has that I hadn't covered yet: generic formal objects. These are parameters which accept an object, that is, an instance of a type; not necessarily an object from the .NET world, but any instance.

    Object : Integer;
-- Something to be templated

So we can pass specific values to a generic just like with functions. If you're familiar at all with C++ templates, this should all be seeming remarkably familiar, and in fact Ada generics are similar, although there's some particularly major differences I won't be getting into. Where is this useful? All sorts of places, like fine grained control over containers/collections, regarding chunk sizes for collections which use chunks, growth factors for resizing arrays, and many other possibilities. Let your mind go wild.

I like C#. But it could really use some improvements to its generic system.


Editor guide