Generics
In many applications, we don't need inheritance/implementation; instead, we require generic implementations of class logic that can work with multiple data types. Interfaces may not be suitable here, as we might want to use generic classes with types that are not under our control, such as types from libraries.
Types of Generics
In programming languages, there are generally three ways to implement generics:
- Monomorphization (a term coined in the Rust community), as seen in C++ or Rust. During compilation, all parameterized instances are effectively created through copy-pasting and replacing with the required type wherever specializations are found to be included in the assembly. This approach benefits from compile-time optimizations and results in highly efficient executables.
- Type erasure, as in Java. As an intermediate step, for each specialization where the parameterized type is encountered, it is replaced with the Object class. Whenever a variable of that type is used, casts are performed to use methods and fields of that type. This approach was useful in Java primarily to provide backward compatibility with non-generic versions and because the implementation was lightweight. However, it is an inefficient approach due to the casts. Another issue is that generics using primitives are not allowed, as they don't inherit from Object, and there must be additional classes to encapsulate them. Lastly, parametric polymorphism is restricted to a single specialization of the generic class (e.g., a function cannot have an overload with List<Integer> and List<String> at the same time).
- Reification, as in C#. Specializations do not exist at compile time; only the generic class or method exists at compile-time. Specializations are created at runtime, meaning they are concretized/reified at runtime. Even though some efficiency is lost due to the overhead of the framework creating the type, this approach allows the runtime creation of object instances for a specialization that hasn't been explicitly declared by the programmer. Thus, reification of generic classes offers runtime flexibility for various applications without suffering from the same issues as type erasure.
Using Generics
A class or method can be made generic by parameterizing it with a list of parameters enclosed in <>. The placeholders are used to represent the concrete types that will be used. A class or method parameterized with concrete types is referred to as a specialization.
Below is an example of how a generic array list can be implemented.
/* This is a simple example of a generic class parameterized with a single parameter for generics; there can be more.
* This class represents an array list, a list that has an array behind it, the capacity of which doubles when exceeded during insertion.
*/
public class ArrayList<T>
{
private T[] _buffer = Array.Empty<T>(); // We can use the generic parameter anywhere, including variable declarations; here, the buffer stores list elements.
public int Length { get; private set; } // The list has a length that will be monitored during insertion and deletion.
public int Capacity => _buffer.Length; // The capacity of the list is the length of the buffer.
public void Add(T item) // We can use the generic parameter T to use it as a function parameter.
{
if (Length == Capacity) // If the buffer is completely occupied, we need to increase its size.
{
var tmp = new T[Capacity != 0 ? Capacity * 2 : 1]; // A new buffer with double length is created.
Array.Copy(_buffer, tmp, Length); // The content of the old buffer is copied to the new one.
_buffer = tmp; // The buffer is replaced.
}
_buffer[Length++] = item; // Add the new element and increment the list's length.
}
public T RemoveAt(int index) // We can use the generic parameter T to use it as the return type of a function.
{
var item = _buffer[index]; // First, read the element to be removed.
Array.Copy(_buffer, index + 1, _buffer, index, Length - index - 1); // Move the content after the removed element one position forward.
_buffer[--Length] = default!; // Remove the last element; if it's a reference type, this prevents it from lingering in the buffer and being recycled.
if (Length != Capacity / 4 || Length == 0) // Decrement the list's length and return the result if the length is not one-fourth of the capacity.
{
return item;
}
var tmp = new T[Capacity / 2]; // Otherwise, create a new buffer with half the capacity to reduce memory usage.
Array.Copy(_buffer, tmp, Length); // Copy the content of the old buffer to the new one.
_buffer = tmp; // Replace the buffer.
return item;
}
public T this[int index] => _buffer[index]; // Here, an indexing operator is created, and we can access an element as if accessing an array.
}
Constaints
When using generic parameters, we cannot make assumptions about the data type because we don't know what type will be used. However, we can use constraints to restrict which types can be used for specializing the type.
/* We can impose multiple constraints for all parameters using the "where" keyword.
* Here, we require that type T be a value type, U be a reference type that implements IComparer<T>,
* and U has a default constructor.
*/
public class ConstraintExample<T, U> where T : struct where U : class, IComparer<T>, new()
{
// ...
}
Covariance and Contravariance
In several languages like Java, for generic classes that inherit from other classes or implement generic interfaces, direct conversion is not possible. For example, even if a class like Integer inherits from the Object class, an IList<Integer> cannot be directly converted to an IList<Object>. In C#, in certain cases, such conversions and their reversals can be achieved through the concepts of covariance and contravariance. In Java, this is possible only under specific circumstances and not as directly as in the mentioned example.
If we have an interface where a generic parameter T appears only in the return types of methods (these types can also be generic and parameterized by T), T can be a covariant parameter, denoted as out T. In this case, an interface parameterized with a derived class can be converted to an interface parameterized with the parent class. Conversely, if T appears only in the parameter types of methods, T is contravariant, denoted as in T. In this case, an interface parameterized with a class can be converted to an interface parameterized with a derived class of that class. In essence, covariance maintains the direction of conversion from the derived class to the base class when the interface is parameterized, while contravariance reverses it.
To illustrate, let's consider the following example:
// This is just a base class meant to be inherited.
public class BaseClass
{
protected readonly string Str;
public BaseClass(string str) => Str = str;
public bool IsOddLength => Str.Length % 2 == 1;
public override string ToString() => $"{nameof(BaseClass)}({Str})";
}
// Through this class, we will demonstrate the concept of generic interfaces.
public class DerivedClass : BaseClass
{
public DerivedClass(string str) : base(str + "!")
{
}
public override string ToString() => $"{nameof(DerivedClass)}({Str})";
}
/* We define an interface for a predicate, where the predicate represents a function
* that takes an input and returns a boolean value. This interface is contravariant
* because T only appears in the function parameters of this interface.
*/
public interface IPredicate<in T>
{
public bool Test(T test);
}
/* We define an interface for a reader, where the reader represents a function
* that takes a string and returns an object of type T. This interface is covariant
* because T only appears in the return types of the functions of this interface.
*/
public interface IReader<out T>
{
public T Read(string str);
}
/* Here we implement the interface parameterized with the base class to allow it
* to be converted to the interface parameterized with the derived class.
*/
public class Predicate : IPredicate<BaseClass>
{
public bool Test(BaseClass test) => test.IsOddLength;
}
/* Here we implement the interface parameterized with the derived class to allow it
* to be converted to the interface parameterized with the base class.
*/
public class Reader : IReader<DerivedClass>
{
public DerivedClass Read(string str) => new DerivedClass(str);
}
IReader<DerivedClass> derivedClassReader = new Reader();
// We can convert the interface here in the direction of converting the derived class to the base class using covariance.
IReader<BaseClass> baseClassReader = derivedClassReader;
IPredicate<BaseClass> baseClassPredicate = new Predicate();
// We can convert the interface here in the direction of converting the derived class to the base class using contravariance.
IPredicate<DerivedClass> derivedClassPredicate = baseClassPredicate;
Console.WriteLine("Testing {0}<{1}> results in {2}", nameof(IPredicate<BaseClass>), nameof(BaseClass), baseClassPredicate.Test(new BaseClass(TestString)));
Console.WriteLine("Testing {0}<{1}> results in {2}", nameof(IPredicate<DerivedClass>), nameof(DerivedClass), derivedClassPredicate.Test(new DerivedClass(TestString)));
Console.WriteLine("Reading {0}<{1}> results in {2}", nameof(IReader<DerivedClass>), nameof(DerivedClass), derivedClassReader.Read(TestString));
Console.WriteLine("Reading {0}<{1}> results in {2}", nameof(IReader<BaseClass>), nameof(BaseClass), baseClassReader.Read(TestString));
The reason why these conversions work is simple. In the example, in covariance, the return type can be converted from the derived class to the base class. Therefore, if we use the function that returns the derived class, we also have a function that returns the base class directly, as the conversion to the base class can be done after the return. In contravariance, if the parameter received by the function is of the base class type, we implicitly have a function that accepts the derived type, as the conversion can be done before applying the parameter from the derived class to the base class.
It's important to note that these rules that determine whether an interface is covariant or contravariant through a parameter can be reversed when dealing with combinations of covariance and contravariance. For example, if the Test function in IPredicate were to take another contravariant interface instead of T, IPredicate would become covariant. Similarly, if the Read function in IReader were to return a contravariant interface in T instead of T itself, IReader would become contravariant. Essentially, covariance and contravariance result in contravariance, double covariance or double contravariance results in covariance.