The previous post glossed over some features of C# that make functional programming difficult. Here they are explicitly addressed. Let’s call them warts. These warts make it difficult to reason about code and thus to write correct code.
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.
There will be a post some time in the future explaining how to implement a
‘nothing’ value that provides compile time guarantees and preserves
parametricity. For now, null is outlawed from Functional Friday. The
functions written here will neither consume nor produce the null pointer.
The function, DieIfNull will help ensure this by throwing an uncatchable
exception if any of its arguments are null.
namespace FunctionalFriday.UnWart
{
public static class UnNull
{
public static void DieIfNull(object arg1, params object[] args)
{
if (ReferenceEquals(arg1, null)
|| args.Any(x => ReferenceEquals(x, null)))
{
throw new MissingMethodException("Don't use null.");
}
}
}
}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.
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 : IToStringOr, to use the previous post’s type class encoding:
string Mystery<T, TToString>(T x, TToString str)
where TToString : IToString<T>Needless to say, methods on object will not be used on Functional Friday in a way that breaks parametricity.
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.
There are ways to have ‘mutable’ state in a program without mutating variable or field values. There will be a post on it in the future. For now, mutation is also banned from Functional Friday.
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) // guaranteedWith 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(
",",
File.ReadLines("C:\\Windows\\win.ini").Take(x));
}For now, side effect use will be restricted to Console.Write for
displaying examples. Yet another future post will explore how to get the
effect of side effects without losing the usefulness of equational
reasoning.
Five warts are enough for one day.