Nominal for Storing, Structural for Manipulating

20 Nov, 2024

Something that comes up sometimes in programming languages is the difference between nominal and structural type systems.
While I'm definitely not the first to talk about this, something that is remarkable to me is that, in my opinion, this is something nearly every programming language gets wrong.

But let's start from the top

What's In a Name

If you're coming from a language like Java, Kotlin, Haskell, OCaml or Rust (or most other languages really), nominal types are what you would probably just think of as "types".

In a language like this, a type needs to be defined in a type declaration where it is given a name that acts as its sole source of identity, without any regard for its implementation. Even if two separate types happen to share the same implementation, they are deemed unequal because they have different names.

For example, if I were to define two java classes

class A {
    int x;
}
class B {
    int x;
}

or two OCaml records

type a = {
    x : int
}
type b = {
    x : int
}

a function accepting an A will not accept a B, because even though their implementations are entirely identical, A and B are not the same type.

There is a reason why this is the default in most languages: it's great for data abstraction and error messages and generally makes for fewer surprises than the alternative.

But it can be a bit restrictive sometimes. For example, let's say you want to define a function that performs some internal database query and can return either one result, many results or an error. In a purely nominative type system, you need to explicitly define this type.

data QueryResult a
    = One a
    | Many (List a)
    | Error QueryError
performQuery :: Query a -> QueryResult a

Not only is this annoying to define, it's also annoying to use! When a user sees the type of performQuery in your docs or in their editor, all they see is QueryResult a. They don't see the cases it has until they hover over it (if you have a good LSP¹) or manually look up its definition (if you don't). If you've ever used a library that makes extensive use of these kinds of one-off nominal types, you will know what I mean.

Additionally, nominal types are quite inflexible. If you have something of type QueryResult a, you have to assume that it could really be any of those three cases. With nominal types, there is no in-between because the implementation is not relevant for the type: "Something that could be One or an Error but not Many" is not a valid type because it doesn't have a name.

Structural Types

If instead, you are coming from TypeScript, you will be used to the other end of the spectrum: structural types! While a structural type might have a name, it is treated more like a type alias and is not actually part of its identity.

Two structural types are equal if and only if their definitions are equal.

For example, replicating the example from before in TypeScript

class A {
    x : number = 0
}
class B {
    x : number = 0
}

const x : A = new B()

will show that you can actually assign something of type B to a context where an A is expected now, even though these are separate classes with separate names that just happen to share the same implementation!

And often times this is exactly what you want! Anonymous, row polymorphic records are a popular feature for a reason and polymorphic variants solve all the problems from the nominal types section above.

But they also have their downsides. For one, structural types make data abstraction impossible because they always expose their entire definition: that's the whole point! They're also terrible for error messages since the compiler often simply cannot know that you didn't actually want it to spell out your Person type as a record with 27 fields.

A slightly more subtle issue is that the interface a nominal type provides is often technically not quite accurate. If your function takes a Player, you probably only want it to be valid for records that are actual valid players but if you represent Player as a structural record, it will accept anything that has, say, an id, name and health field (which Enemy might happen to contain as well!)

Therefore, the vast majority of programming languages primarily stick to nominal types and sometimes provide very limited, separate support for structural records or variants.

However, for Polaris, I went with a slightly different approach.

¿Por Qué No Los Dos?

If structural types are so great for specifying and manipulating a types' definition and nominal types are so great for restricting types to their name, why don't we take just those aspects and combine them?

In Polaris, all records and variants are row-polymorphic, structural records and polymorphic variants, whereas nominal types are implemented through lightweight newtype wrappers.

What this means is that all nominal variants and records are really just nominal wrappers over structural variants or records.

For example, a binary tree might be implemented as

data Tree(a) =
  < Empty
  , Branch({ left : Tree(a), value : a, right : Tree(a) })
  >

Here data defines a newtype (as opposed to type which would define a type alias) and the syntax on the right of the definition specifies the type of a polymorphic variant with an Empty and a Branch constructor, where the Branch constructor itself takes an argument of an anonymous, structural record type.

Now, because this is a nominal newtype, its constructor can be hidden to the outside to make the type abstract, error messages will only mention Tree(a) and if someone else were to define their own Tree type, they couldn't accidentally pass it to any of your functions even if they used the exact same definition. Values of type Tree essentially behave exactly as if Tree were a nominal variant in Haskell or OCaml.

That is, until the newtype is unwrapped. At that point, it reveals its underlying structural variant that now suddenly gets all the benefits of structural types for free.

One advantage of this is that in case you do actually want to be able to pass that Tree type someone else wrote to your functions, you don't need any messy conversion functions! Because they have the same (exposed) implementation, all you need to do is swap out the newtype.

let convertTree : forall a. TheirTree(a) -> Tree(a)
let convertTree(theirTree) = Tree(theirTree!)

(Polaris uses postfix ! for "unwrap expressions" that make unwrapping mostly unintrusive.)

But that's not all. Because they're not tied to a single name, structural types can be manipulated much more flexibly than nominal types.

To demonstrate this, let's look at yet another language: Gleam!✨

The Gleam team recently released a cool new feature which they call "Variant inference". What this means is that when matching on a variant, Gleam will keep track of which variants have already been exhausted and which ones have been matched by the current case to narrow down the type of a constructor for use in record updates or accessors.²

This is a great feature that is the result of a lot of careful effort the Gleam implementors put into the user experience of their language.

But what if I told you that Polaris already supported this before Gleam? And even better: because of the way Polaris' type system works, its implementation is more powerful, simpler and more consistent than Gleam's!

Matching on a variant in Polaris refines the type of the scrutinee after each match so that exhausted branches will not show up in the next case.

For example, if we pattern match on our Tree from before like this

let f : Tree(String) -> ()
let f(tree) = match tree! {
    Empty -> ()
    rest -> ...
}

The type of rest is only < Branch({ left : Tree(String), value : String, right : Tree(String) }) > because the Empty case has already been handled.

This is more powerful than Gleam's approach, because this information is not just something the compiler keeps track of to make the coverage checker smarter; it's actually part of rest's type, which it can persist even accross function boundaries!

It's also simpler because nothing else needs to be aware of this: after the type is adjusted, the result is still just a regular, albeit slightly smaller, polymorphic variant type.

Now, nearly all of this would have been possible in TypeScript. However, unlike TypeScript, Polaris achieves it without giving up any of the benefits of nominal types.