CS SYD - Ad-hoc polymorphism erodes type-safety

This blogpost explains and argues the claim that Ad-hoc polymorphism (Type-classes in Haskell/Scala/Purescript, Traits in Rust, Interfaces in Go/Java) makes code less type-safe.

In other words: ad-hoc polymorphism makes it so that sometimes, after a refactor, code that is wrong and would not type-check without it, now still type-checks.

Time to write a blog post

I've been digging into Rust for a while now and noticed that Rust code tends to use Traits even more than Haskell uses type-classes. I was surprised by this because I've been hearing so much about how Rust code's type safety is amazing.

My tweet that reads 'The traits (type classes) erode type-safety message doesn't seem to have reached Rust yet.'

Some responders seemed surprised by this idea, and I thought this was common knowledge but could not find any blog posts about it either. I figured maybe it was worth writing out, and some people agreed, so here we are:

My tweet that polls whether this blog post would be interesting.

Intro to polymorphism

Parametric polymorphism

Haskell and Rust both support parametric polymorphism, which means you can write code like this:

-- In Haskell:
reverse :: [a] -> [a]

// In Rust:
fn reverse<A>(v: Vec<A>) -> Vec<A> {...}

In this example, the reverse function can reverse a list/vector of any values that all have the same type. If the function does not use any properties of the parameter type in its implementation, we say the function uses parametric polymorphism.

Ad-hoc polymorphism

Haskell and Rust also both support ad-hoc polymorphism. This is like parametric polymorphism, but additional constraints can be put onto the type parameter. For example, there are functions like these:

-- In Haskell:
length :: Foldable t => t a -> Int

// In Rust:
fn count<I>(iter: I) -> usize where I: Iterator {...}

We say that these functions use ad-hoc polymorphism because they are polymorphic but also require the type to have certain specialised behaviour defined for them. In the Haskell case, any Foldable can have its length computed (by folding a constant function over its elements). In the Rust case, any Iterator can have its count computed (by counting its elements one by one). In both cases: if there's no way to iterate over elements, which we can tell by the absence of a Foldable instance/Iterator trait, these functions cannot compute the number of elements.

Another example of ad-hoc polymorphism involves functions that have to do with displaying values as text:

-- In Haskell:
show :: Show a => a -> String

// In Rust:
fn to_string<A>(value: A) -> String where A: ToString {...}

Type safety

I found these two definitions on wikipedia

In computer science, type safety and type soundness are the extent to which a programming language discourages or prevents type errors.

A type error is an unintended condition[a] which might manifest in multiple stages of a program's development.

Preventing type-errors is important when you first write code, but also when you later refactor the code. Haskell is famously excellent for refactoring code: As long as you get the code to type-check again, it probably* still does what you want.

In this blog post I will focus on semantic type-safety during refactors. By semantic type-safety, I mean "preventing code that still type-checks but silently does the wrong thing because of a type error".

Eroding type safety

The central claim of this blog post is:

Using ad-hoc polymorphism can cause code to silently do the wrong thing after a refactor because of a type error, in a way that monomorphic code would not have.

To show this, we will use an example of code in both Rust and Haskell. For each we will show two versions: one monomorphic, and one with ad-hoc polymorphism. We then show that when this code is refactored (in the same way), the version with monomorphic code will no longer type-check and the version with ad-hoc polymorphism will now silently do the wrong thing.

Before

Suppose a server has an allow-list setting of which clients are allowed to contact it. We show the number of allowed clients to the server administrator in an admin panel. We might have a settings type as follows:

-- In Haskell:
data Settings
    = Settings
    { settingAllowList :: [ClientIdentifier]
    , [...]
    }

// In Rust:
struct Settings {
    allow_list: Vec<ClientIdentifier>
}

Somewhere else in the code, we show the length of the list to the administrator by calling the counting function we saw above:

-- In Haskell:

-- With a function that is monomorphic in the collection type
allowListSize :: Settings -> Int
allowListSize = GHC.OldList.length . settingAllowList

-- With ad-hoc polymorphism:
allowListSize :: Settings -> Int
allowListSize = length . settingAllowList

// Rust

// With a function that is monomorphic in the collection type:
fn allow_list_count(settings: Settings) -> usize {
    Vec::len(settings.allow_list)
}

// With ad-hoc polymorphism:
fn allow_list_count(settings: Settings) -> usize {
    settings.allow_list.into_iter().count()
}

So far so good. This code type-checks, runs, and does what we want.

Note that this function may be very far removed from the type that it works on. It could be all the way down in the same file, in a different file, or even in a different library or project entirely.

Refactor

Now we are asked to make it possible to turn the allow list off. I.e. make it possible for any client to contact the server.

We can't put all possible client identifiers in this list, because we don't know them all. We also cannot use the empty list to represent "turned off", because the empty list means that no clients may contact the server. Instead we decide to use Maybe/Option to let us represent "turned off" with Nothing/None.

So we refactor the settings type:

-- In Haskell:
data Settings
    = Settings
    { settingAllowList :: Maybe [ClientIdentifier]
    , [...]
    }

// In Rust:
struct Settings {
    allow_list: Option<Vec<ClientIdentifier>>
}

Suppose we do not consider changing the counting function because it is far away and not on our mind. (As you will see below, you should not have to consider this anyway.)

After

Now let's look at the counting function and what's happened to it in both scenarios.

In Haskell, the allowListSize function using a monomorphic length now fails to compile:

ghci> GHC.OldList.length (Just ["foo", "bar"])

<interactive>:6:21: error:
    • Couldn't match expected type: [a0]
                  with actual type: Maybe [String]

In contrast, the allowListSize function using an ad-hoc polymorphic length still compiles but now only ever returns 0 (turned off) or 1 (turned on):

ghci> length Nothing
0
ghci> length (Just ["foo","bar"])
1

In rust, the allow_list_count function using a monomorphic len now fails to compile:

error[E0308]: mismatched types
  --> src/example.rs:10:28
   = note: expected reference `&Vec<_, _>`
                   found enum `Option<Vec<&str>>`

In rust, the allow_list_count function using an ad-hoc polymorphic count still compiles but now only ever returns 0 (turned off) or 1 (turned on):

println!("{}", Some(vec!["foo", "bar"]).into_iter().count());   // Prints 1
println!("{}", None::<Option<Vec<String>>>.into_iter().count());   // Prints 0

Note that this problem is not specific to Foldable/Iterator, or Data.Foldable.length, GHC.OldList.length/len,count, but can occur for with every class/trait that has more than one instance/impl.

Conclusion and alternatives

It is useful for the sake of future maintenance to stick with monomorphic functions where possible. (You can make a function monomorphic with explicit type annotations or type applications.) The compiler will tell you about all the places you need to make a judgement call, instead of silently doing possibly the wrong thing. Alternatively/additionally, tests can also catch these problems earlier.