Making Illegal States Unrepresentable

I have opinions on this

Okay so the saying is "make illegal states unrepresentable". The meaning is that we should structure programs in a way it such that a bad thing, the "illegal state", is not even a sensible construct in our system. The usual example is from F# for fun and profit:

Let’s look at our Contact type. Thanks to the previous refactoring, it is quite simple:

type Contact = 
{
   Name: Name;
   EmailContactInfo: EmailContactInfo;
   PostalContactInfo: PostalContactInfo;
}

Now let’s say that we have the following simple business rule: “A contact must have an email or a postal address”. Does our type conform to this rule?

The answer is no. The business rule implies that a contact might have an email address but no postal address, or vice versa. But as it stands, our type requires that a contact must always have both pieces of information.

[...]

If we think about the business rule carefully, we realize that there are three possibilities:

• A contact only has an email address
• A contact only has a postal address
• A contact has both a email address and a postal address

Once it is put like this, the solution becomes obvious – use a union type with a case for each possibility.

type ContactInfo = 
  | EmailOnly of EmailContactInfo
  | PostOnly of PostalContactInfo
  | EmailAndPost of EmailContactInfo * PostalContactInfo

type Contact = 
{
  Name: Name;
  ContactInfo: ContactInfo;
}

Now there's no way to have a Contact that breaks the business rules.

It's a concept I find very helpful. But if you look for examples online almost everything either "let's prevent dividing-by-zero" or "let's enumerate the cases in a data type". We can more creative than that! Some examples of "illegal states unrepresentable" that I found useful but have not seen anyone else talk about online:

Let's say we have a set of elements that can be partitioned into disjoint sets. Elements can belong to either set but the sets must be disjoint: no element can be shared between them. This is a fairly common thing you see in business domains.

// arbitrary pseudocode
Person {
  friends: set Person,
  enemies: set Person,
}

If we are mutating an instance of this we'd need to constantly make sure that we don't have the same element in both sets. Or we could also remove the possibility of collision by replacing all the sets with a single mapping:

Person {
  relationships: {
    $Person_entity: friend_or_enemy
  }
}

Since keys can't be duplicated we can't have an element having two distinct values at once. We made the illegal state unrepresentable.

Another example: we have a list of entities each with a position. We want to guarantee that no two entities collide by having the same position. Instead of encoding the positions of each entity, we can encode what entity is at a given position:

// instead of
Entity {
  position: Position
}

// we instead do
Position {
  occupied_by: optional Entity
}

I do a lot of these kind of "inversions" when I write specifications. We turn a derived quality into a base one and vice versa.¹ It prevents the collision from happening. But this gets considerably more difficult if we add an additional requirement, such as making sure that areas don't overlap. We can not longer invert the relationship, as each entity now occupies a set of positions.

Which brings me to my next thought on representable states, what I'm going to call constructive vs. predicative data.²

Let's jump back to the address example. Saying "every contact must have either an email or postal address" is predicative: we take a universe of representable contacts and use a predicate to select a subset of the universe, the set of all valid contacts. Saying "every contact is EmailOnly, PostalOnly, or EmailAndPost" is constructive: we're building up the set of all valid contacts from base rules. Illegal states are unrepresentable because these rules only generate valid contacts. The universe of contacts is the exact same as the universe of valid contacts.

This feels very similar to the imperative vs. declarative spectrum, where constructive and predicative are imperative and declarative respectively. What fascinates me is that the benefits are inverted. Speaking in a very broad terms here "declarative" code is usually "more correct" and "more elegant", as is constructive-style representations. But as domain gets messier codebases tend to drift towards a more imperative style. The most elegant representations of problems don't take perturbations to those problems very well. Similarly, it's much easier write a bunch of overlapping predicates that it is to nurture a construction that happens to properly represent your valid states. But the overlapping predicates by definition act on a universe of possible states much bigger the set of valid states, leaving more room for your code to reach an illegal state.

To see what I mean here, take the contact example and add some new requirements. First try to guarantee the requirements a constructive way, and then try to guarantee them by writing a function that tests whether or not a given contact satisfies all of the requirements:

• In addition to email and postal you have a phone number. We distinguish between an work phone, home phone, and mobile phone. You may have any combination of those three types, but all of them count as "phone numbers".
• If you don't have email you need both postal office and at least one phone number. If you don't have email or postal office you need two different types of phone number.
• You must provide a secret question unless that all three of the email, postal, phone number. In that case a secret question is optional.

(Predicative data is more composable, like declarative code, but is further from the spec, like imperative code. Probably some deeper things going on here.)

That's all I got. Have a great weekend!

¹ hot tip to anybody writing a Minizinc spec: write both representations as variables and connect them with a channel constraint. This lets you use the optimum representation for predicates. It's often a significant optimization.

² Predicative, not predictive.

If you're reading this on the web, you can subscribe here. Updates are once a week. My main website is here.

My new book, Logic for Programmers, is now in early access! Get it here.