Emulating first-class polymorphism

Last time, we talked about universally quantified types and the challenge of passing a generic function to a non-generic function. The best way to do this is with a non-generic interface that contains one or more generic methods. This allows us to limit the scope of the type variables to each method. In our case, we can define an interface that represents operations on generic lists:

interface IListOperations
{
    int GetWeight<T>(IList<T> items);   // scope of T is limited to GetWeight
    // ... other methods with other type variables
}

At the moment, we only have one such operation, GetWeight, but we could add more in the future. We can then modify our SumWeights function to take an IListOperations:

static int SumWeights(
    IList<int> ints,
    IList<string> strs,
    IListOperations listOps)
    => listOps.GetWeight(ints) + listOps.GetWeight(strs);

This technique is a bit more verbose than a plain function, but it effectively supports universally quantified function types. (Shout out to @costinmanda for digging into this problem in the comments!)

Deserialization challenge

Now let's switch to a different, more unusual, problem. Imagine that we have a file that contains a list of serialized objects, all of the same type. For example, we might store a list of circles like this:

MyNamespace.Shapes.Circle
Origin=(3,4), Radius=5
Origin=(-2,3), Radius=7
...

And we might store rectangles like this:

MyNamespace.Shapes.Rectangle
TopLeft=(0,3), BottomRight=(3,0)
TopLeft=(1,1), BottomRight=(4,-3)
...

The file format itself doesn't really matter, so don't get hung up on why it's not CSV, JSON, or XML. What's important is that we can use the format to store a list of values of any relevant type.¹

How would you design an API to deserialize the contents of such a file? You might start with something like this:

static IList<T> DeserializeList<T>(string path)
{
   // implementation
}

var circles = DeserializeList<Circle>("Circles.txt);
var rectangles = DeserializeList<Rectangle>("Rectangles.txt");

This works great, but only if you know the type contained in each file ahead of time. What if you need to be able to deserialize an arbitrary file without knowing the type of objects it contains at compile-time?

var values = DeserializeList<???>("Arbitrary.txt");

We could potentially use obj as the type variable, so that values is of type IList<obj>:

IList<obj> values = DeserializeList<obj>("Arbitrary.txt");

The problem with this approach is that an IList<obj> (or a non-generic IList) could contain a mixture of different types of objects. We don't want to lose the fact that all the values in a given file are in fact of the same type. Is there a way to represent this in C#?

Existentially quantified types

Ideally, we'd want to write the signature of DeserializeList like this:

static ∃T.IList<T> DeserializeList(string path)   // not legal C#
{
   // implementation
}

We've introduced ∃T., which means "there exists a type T", so ∃T.IList<T> is a generic list containing items of some unspecified type. We call ∃T.IList<T> an existentially quantified type. Note that we no longer pass a type parameter to DeserializeList at all, since there's no way to know the actual type that T represents at compile-time.

Obviously, existential types are not directly supported by C#. But is there a way to emulate them using universal types instead? The answer is yes, but the solution is not at all obvious. We'll cover it next time.

1. Note that the first line of the file contains the name of the stored type. We can use this metadata to dynamically instantiate the type at runtime (via reflection or some other mechanism). ↩