C#: Functional warts

Navigation   notoc

Blog   notoc nav

Introduction   notoc

Some features of C# make functional programming difficult. Let’s call them warts.

Warts make it difficult to reason about code and thus to write correct code.

Wart 1: null

Tony Hoare invented the null pointer and later apologised for doing so:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

Null breaks parametricity. In the presence of null an implementation of the following type cannot assume that x is always a value of type T because the domain of T in C# includes all values of type T and the null pointer.

string Mystery<T, TJsonShow>(T x) where TJsonShow : IJsonShow<T>

Null breaks more than parametricity. It makes it difficult to reason in a principled way about monomorphic functions too. An implementation of the type string Mystery(string x) cannot assume that x is a string because the set of inhabitants of the string type in C# includes null.

Wart 2: reflection

Reflection breaks parametricity. Reflection enables recovering type information at runtime. With that capability, a type like Mystery below cannot provide the guarantees that parametric types should give.

string Mystery<T, TEq>(T x, T y, TEq eq)
    where TEq : IEqualityComparer<T>

Without reflection, Mystery is guaranteed to only ever call the IEqualityComparer methods on eq. With reflection, Mystery can do just about anything, like the following crazy implementation does.

string Mystery<T, TEq>(T x, T y, TEq eq)
    where TEq : IEqualityComparer<T>
    if (x is int) return "x is an int";
    if (x is string) return ((string) x).ToUpper();
    return eq.Equals(x, y).ToString();

Trivially, default(T) also breaks parametricity by enabling construction of values outside the presence of a new() constraint. It does this from type information gained at runtime, hence, reflection.

Wart 3: object methods

Object methods break parametricity. In C# every type inherits from object. This means methods on object are callable on values of parametric type parameters, even when that makes no sense.

For example. Every value except null has a ToString method, which means this function has an implementation that uses its argument.

string Mystery<T>(T x)

Without object methods (and any of the other warts in this post), there is only one kind of implementation of Mystery: one that returns a constant string without touching x.

string Mystery<T>(T x)
    return "asdf";

With object methods, implementations like the following are possible.

string Mystery<T>(T x)
    return x.ToString();

This second implementation is problematic because it is defined on any T, including types for which ToString does not make sense. It should really be typed something like the following, where the interface IString provides the ToString method.

string Mystery<T>(T x)
    where T : IToString

Or, to use the previous post’s type class encoding:

string Mystery<T, TToString>(T x, TToString str)
    where TToString : IToString<T>

Wart 4: mutation

Mutation interferes with equational reasoning. Variables in mathematics are immutable. In the function f(x) = x * x, x is called a variable, not because the equation can mutate its value, but because the equation can be evaluated for different values of x. Evaluate f(3): f(3) = 3 * 3 => f(3) = 9. Evaluate f(a + 2): f(a + 2) = (a + 2) * (a + 2) => f(a + 2) = a^2 + 4a + 4. Once the value of x is known it can be substituted wherever x appears. If x were mutable and the implementation of f mutated it, evaluation by substitution would not work; instead the equation would have to be run or stepped through to work out what it was doing.

Programs that avoid mutation are easier to reason about. A trivial example is equality. Assuming immutability, if x == y now, x == y always. With mutation, if x == y now, there is no guarantee that in n clock cycles x != y because one or both of them was mutated in the meantime. An equality relation between mutable values is somewhat nonsensical.

Another example is validation. Let bool IsValid<T>(T x) be a function that determines whether a T is valid according to some specification. If x is immutable a true return value from IsValid(x) guarantees that x is valid forever: x can be used anywhere a valid T is required. If x is mutable there is no such guarantee, and if x is mutable and more than one thread has access to it, all bets are off.

Wart 5. side effects

Similar to mutation, side effects mess with equational reasoning. Without mutation and side effects, string Mystery(int x) will always return the same for any value of x.

Mystery(3) == Mystery(3) // guaranteed

With side effects this guarantee vanishes. For example, none of the following implementations fulfill the above guarantee because their return value depends on external state which may change between calls.

string Mystery1(int x)
    return DateTime.Now.AddSeconds(x).ToString();

string Mystery2(int x)
    return string.Join(

Five warts are enough for one day.