Do I Really Understand Generics?

You never really know something until you teach it to someone else. - John C Maxwell

I’ve had a couple moments where I could not for the life of me explain generics to another developer. This reminded me of the quote that I started this post with, and filled me no end of self doubt. Do I really understand this tool that I’m using everyday? Am I just not great at explaining things? Am I having a recurrence of imposter syndrome after all these years?

After going to the wellness room to meditate and calm down, I started thinking: “What do I think generics are? How do I model them? Is that a good way to explain this concept?”

To answer the first question, I think without looking it up that generics are a way of making code that can handle multiple types. I remember being introduced to this using linked lists in Java during my freshman year of undergraduate studies. Instead of having a node with reference to an object and relying on the calling application logic to decide how to cast from object to the appropriate type, we can have a type parameter and have code that should work for all types.

We can do:

class LinkedListNode<T>
{
     public T Data { get; set; }
     public LinkedListNode<T> Next { get; set; }
}

Instead of:

class LinkedListNode
{
     public object Data { get; set; }
     public LinkedListNode Next { get; set; }
}

This allows us to lean on the compiler and the run time to sort out the type of Data when invoke it’s getter, and that makes our lives much easier. Unfortunately, I’ve found that this explanation didn’t work well. The developer in question has spent most of their career writing in JavaScript and is now transitioning into TypeScript and C#. In JavaScript, you don’t have this problem arrays. The following is valid:

var a = ['foo', {'a': 'b', 'c':'d'}, 42];

Without having things lined up conceptually, I started thinking about my second question. In my head, I tend to model generics with a little bit of lambda calculus. Lambda is after all a binding operation much like ∀ and ∃. We use lambda to bind symbols all the time in modern code:

   ((x) => x + 1)(42) // Should return 43 as a value in the REPL
   (42) => 42 + 1     // We can think of 42 being bound for x by the lambda
   42 + 1             // The resulting expression after binding
   43                 // Simplified

We can then think about LinkedListNode<T> as a lambda like (T) => LinkedListNode<T>. We can then simplify this expression to get various LinkedListNode types:

   ((T) => LinkedListNode<T>)(int)
   (int) => LinkedListNode<int>
   LinkedList<int>

   ((T) => LinkedListNode<T>)(double)
   (double) => LinkedListNode<double>
   LinkedList<double>

   ((T) => LinkedListNode<T>)(string)
   (string) => LinkedListNode<string>
   LinkedList<string>

We can think of the generics as giving us all of these types as we use them. That we bind the type parameter on the fly to create new types and use them (more on this later). This explanation feels really comfortable and intuitive to me. But I feel like it might be too esoteric to use on a day to day basis especially invoking lambda calculus. I tried to do something similar without the extra lambda syntax to explain what was happening as one generic method invoked another generic method, but it didn’t seem like it made sense to my audience at the time.

Then that left me with the thought: “Yeah I can model this behavior using lambdas, but is any of this being done at run time? Is this actually how it works?”

Coincidentally, I encountered another explaination of how Generics works while reading the Rust book. Rust uses a technique called monomorphism, which from what I understand means that if you have List<T> and your program only uses int as T, then the compiler will generated the code for just lists of ints. This of course is not how I would assume C# works, since you can use System.Reflection to interrogate type parameters of generic types loaded from other assemblies.

I would really like to follow this up with a deeper dig into how the C# generics work under the hood, but at the time of this writing I’ve struggeled too long trying to get ILSpy working on Linux. I might need to spend some time myself working on how to extract IL from the arbitrary DLLs that I’ve been creating. Hopefully, once I get that working, I can circle back to this topic.