DISCOVERY

February 3rd, 2019

Variance with C# Generics

C#

Object Oriented Programming

Polymorphism

Variance

Variance amongst generics in programming languages is a topic that interests me. Generics in Java are always invariant, however C# isn't as restrictive, making it fun to explore. Since variance is an advanced topic, this article starts with the basic concepts of variance. Once the basics are understood, I'll explain variance in C# generics.

Variance is a form of polymorphism. Therefore, we need to understand the different forms of polymorphism to understand variance.

Polymorphism

Something that is polymorphic can exist in many different forms. In computer science, polymorphism is when an entity can take the form of multiple different types1. A type is a blueprint for a value, the same way a class is a blueprint for an object2.

Polymorphism comes in many different forms. When Christopher Strachey first defined polymorphism in a Computer Science context, he said there were two main forms of polymorphism: ad-hoc and parametric3. Nowadays its agreed upon that the two main forms of polymorphism are ad-hoc and universal, with parametric falling under universal4.

Main Polymorphism Forms

Ad-hoc Polymorphism

Ad-hoc Polymorphism is when a function or method works with arguments of multiple different types. Therefore it can be said that the function arguments are polymorphic. Depending on the argument types, the behavior of the function can be completely different5. The most common forms of Ad-hoc polymorphism are function overloading and operator overloading.

Universal Polymorphism

Universal polymorphism consists of symbols that accept an infinite number of different types6. Acceptable types can exist within a certain range or encompass the entire languages type system. The most common forms of universal polymorphism are inclusion polymorphism and parametric polymorphism. A synonym for inclusion polymorphism is variance . An example of parametric polymorphism is generics.

When using generics, we deal with universal polymorphism. While generics are an implementation of parametric polymorphism, variance means the same thing as inclusion polymorphism.

Universal Polymorphism Implementations

Generics

Generic types expose type parameters which are filled in by creators and consumers of the type instances. Type parameters are symbols that accept a range of different types. For example, in C# the syntax <...> is used next to the class identifier to define a generic type. For example, the List class is defined List<T>, where T is the type parameter. Instances of the type fill in the type parameter with any type argument, such as new List<int>(); or new List<string>();.

Variance

Variance describes the relationship between a compile time type and its assigned runtime type. Variance also limits the valid relationships between compile time and runtime types. There are three forms of variance: covariance, contravariance, and invariance. Types are covariant when the runtime type can be a subtype or the same type as the compile time type. Types are contravariant when the runtime type can be a supertype or the same type as the compile time type. Types are invariant when the compile time type and runtime type must be the same type. When types are invariant, different types have no relationship to one another. When types are contravariant or covariant, clear relationships between different types are declared.

In C#, non-generic types follow covariance. Therefore, the assigned value of a variable declaration can be a subtype or the same type as the declared type. For example, object myObj; can be assigned to the same type (object()) or a subtype ("a string literal").

object myObj1 = new object(); object myObj2 = "a string literal";

By default, generics in C# are invariant. Therefore the compile time and runtime type parameters must be the same.

// valid List<string> list1 = new List<string>(); // ERROR: invalid List<object> list2 = new List<string>();

This behavior is the same as Java. However, C# provides us with the flexibility to give generics variance.

As of C# 4.0, generic type parameters can be made covariant or contravariant with interfaces7. To make a type parameter covariant, it must be marked with the out modifier. To make a type parameter contravariant, it must be marked with the in modifier8. I defined an interface with one contravariant type parameter and one covariant type parameter.

public interface ICovariant<in TK, out TV> { TV Get(TK key); TV Pop(TK key); }

The TK type parameter is contravariant and the TV type parameter is covariant. Contravariant types with the in modifier can only be passed in to a method and can't be returned by a method. Covariant types with the out modifier can only be returned by a method and can't be used as a method argument.

With ICovariant defined, I created a class VariantMap which implements ICovariant.

public class VariantMap<TK, TV> : ICovariant<TK, TV> {}

Finally I proved that TK is contravariant and TV is covariant.

// Program.cs // Map that uses variance ICovariant<string, object> variantMap = new VariantMap<object, string>(("Andy", "Jarombek")); Assert(variantMap.Get("Andy").Equals("Jarombek")); Assert(variantMap.Pop("Andy").Equals("Jarombek")); var contents = new List<(object, int)> {("Andy", 23), (0, 0)}; // Another map that uses variance ICovariant<object, Int32> variantMap2 = new VariantMap<object, int>(contents); Assert(variantMap2.Get(0).Equals(0)); Assert(variantMap2.Get("Andy").Equals(23));

You can check out the full VariantMap, ICovariant and Program code on GitHub. In my repository there is also an InvariantMap class which uses invariant generic type parameters.

Variance may seem like a complex topic, but it's a fundamental piece of the programming languages we interact with every day. For more information on variance make sure to check out my article about Generics and Variance in Java.

[1] "Polymorphism (computer_science)", https://en.wikipedia.org/wiki/Polymorphism_(computer_science)

[2] Joseph Albahari & Ben Albahari, C# 7.0 in a Nutshell (Beijing: O'Reilly, 2018), 21

[3] Christopher Strachey, "Fundamental Concepts in Programming Languages," Higher-Order and Symbolic Computation (2000), 37, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.332.3161&rep=rep1&type=pdf

[4] "Java Polymorphism", https://javapapers.com/core-java/java-polymorphism/

[5] "Ad hoc polymorphism", https://en.wikipedia.org/wiki/Ad_hoc_polymorphism

[6] "Universal Polymorphism", https://en.wikibooks.org/wiki/Introduction_to_Programming_Languages/Universal_Polymorphism

[7] Albahari., 132

[8] Albahari., 133