Generics as super-functions

This post is the beginning of a series in which we will look at generics more closely, we will consider their implementation details across various languages, and we will explore their potential in solving problems we have today (with static analysis in mind).

As usual, we will use C# as for our examples because its generics syntax will be self-explanatory to developers familiar with C++, Java, Rust, etc. Also, for the purposes of this post we will use the terms “function” and “method” interchangeably.

A look at NDepend

Earlier this year, the developers of NDepend were kind enough to grant me free of charge a license for their tool. They invited me to try it and consider writing something about it.

So this post will be a brief pause from the usual content of my blog, as we will be taking a quick look at some of the functionality of this software. I’ve also opted to include a few screenshots from the NDepend site, because I preferred them to the ones I took myself.

Undefined behavior can literally erase your hard disk

It is no secret that C and C++ are chock-full of pitfalls of undefined behavior. The C++ standard describes it as:

behavior for which this International Standard imposes no requirements

Modern compilers, with optimizations on, often assume that undefined behavior is never invoked in the program and try to make sense of the code under that assumption. When a program actually does invoke undefined behavior, this conflicts with the assumption under which the compiler generated code, often resulting in strange, or even outright paradoxical results. (I like to call those cases “paranormal behavior”, but it still hasn’t caught on.)

Changing an object's type at runtime in C#

In most statically typed languages, an object’s type is set in stone once the object has been completely constructed. While the object can subsequently be cast to various types, it can never change its runtime type — many aspects of type systems and features (such as virtual dispatch) depend on this.

In this post, we will see how we can use unsafe code in C# to bypass the type system and change a .NET object’s runtime type. Then, we will see an unusual case where it would be neat to have this. Needless to say, don’t try this in real code.

Implementing multiple dispatch polymorphism

As we saw previously, many popular OOP languages support subtype polymorphism with single dispatch. This means that the dynamic resolution of a polymorphic call happens with respect to one argument only: the this reference.

The problem with this limitation is that it’s completely arbitrary. In a well-written program, there is no natural tendency for polymorphism to be useful only in one dimension. Quite the contrary – if a program is written with best OOP practices in mind (e.g. one responsibility per class), chances are that the need for multidimensional polymorphism, also called multiple dispatch, will eventually arise.

Implementing single dispatch polymorphism

Many object-oriented languages have support for subtype polymorphism with single dispatch over the this argument.

To implement polymorphic calls, they need a way of accessing information about which override should be selected at runtime. At least for compiled languages, the most obvious way to store this information is in the form of function pointers. The structure that contains these function pointers is called a dispatch table.

Applications of substructural typing

In a previous writing, we mentioned a family of types called substructural types. A type is substructural if it disallows any of the three structural rules: contraction (the ability to use a variable more than once), weakening (the ability to leave a variable unused), and exchange (the ability to reorder usages of two variables with respect to their declaration order).

In this writing, we will look at several problems that substructural type systems can help us solve at compile time, in ways that common unrestricted type systems are simply unable to do.

Structural rules and substructural logics

There is a family of unusual type systems called substructural type systems. Many programmers have never encountered them, while other have encountered them without realizing what they are or what’s the idea behind them.

We will try to shed some light on where substructural type systems come from, by giving a quick tour of their theoretical background, which comes from sequent calculus. To keep this short enough, we will go only over the parts that are useful for examining type systems.

Creating a ref alternative in C#

C# has two keywords called ref and out. They are not exactly the same, but they both offer the ability to pass a reference to a local variable or a field. At the binary level, what is passed is essentially a pointer.

This feature is useful, but it has certain technical limitations. We will explore the possibility of constructing an alternative that does not suffer from the same limitations.

Using the new() constraint is a symptom of the XY problem

C# allows you to write generic code with a few constraints that can’t be expressed through the type hierarchy alone. For example, you can require that a generic type parameter only accepts types that are structs, or reference types, or non-abstract types that have a public default constructor:

1
2
3
4
5
6
7
public void M<T1, T2, T3>()
    where T1 : struct
    where T2 : class
    where T3 : new()
{
    /* code */
}

That last case is what we’re interested in for this post.