https://cs-syd.eu/posts/2023-08-25-ad-hoc-polymorphism-erodes-type-safety

CS SYD Logo
Services Blog About

Ad-hoc polymorphism erodes type-safety

ERT 8 min
Date 2023-08-25
polymorphism
haskell
rust

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 addition 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.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"]).iter().count());   // Prints 1
println!("{}",None::<Option<Vec<String>>>.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.

Know a technical team that could use strong technical leadership?

Hire me
Next
Outage postmortem
(c) CS SYD. Tom Sydney Kerckhove | Technical Leader | Speaker | Coach.
Tom Sydney Kerckhove Twitter Tom Sydney Kerckhove Github Tom Sydney
Kerckhove LinkedIn Tom Sydney Kerckhove YouTube Tom Sydney Kerckhove
Tiktok
contact