Structural vs. Nominal Type Systems

Iā€™ve been interested in type systems lately. You hear a lot about static vs. dynamic type systems, and how static is clearly better. I would agree with that.

But there is another way to divide them up ā€”Ā structural vs. nominal type systems.

Structural Typing

In a structural type system, two types are compatible if they have the same structure. TypeScript is the quintessential example of a structural type system.

// TypeScript
type Country = {
name: string;
population: number;
};
type State = {
name: string;
population: number;
};
// a country can be assigned to a state
const x: Country = { name: "Sweden", population: 4 };
const sweden: State = x;
// we can pass a state to an argument of type Country
function travel(country: Country) {
console.log(`We are going to ${country.name}`);
}
const norway: State = { name: "Norway", population: 5 };
travel(norway); // We are going to Norway

But structural typing can have problems ā€”Ā sometimes slippery boundaries are not ideal.

// TypeScript
// Don't do this
type Inches = number;
type Centimeters = number;
// function definition far far away
function calculateSomething(distance: Centimeters) {
/* todo */
}
const distance: Inches = 5;
// the linter: that looks great to me! šŸ˜ˆ
calculateSomething(distance);

You can mitigate this by giving each type a ā€œbrandā€.

// TypeScript
type Inches = {
_unit: "inches"; // this is a brand
value: number;
};
type Centimeters = {
_unit: "centimeters"; // this is a brand
value: number;
};
const distance: Inches = { value: 5, _unit: "inches" };
function calculateSomething(distance: Centimeters) {
/* todo */
}
// error: type Inches is not assignable to type Centimeters
calculateSomething(distance);

And now weā€™ve stumbled into nominal typing.

Nominal Typing

In a nominal type system, types are only compatible if they have the same name (or ā€œtagā€, or ā€œbrandā€).

They are stricter than structural type systems ā€”Ā in fact, nominal typing is a subset of structural typing. Note that our above example was doing nominal typing in one of the most structural type systems out there, TypeScript.

Hereā€™s our original example in Kotlin,Ā a great example of a nominal type system.

// Kotlin
data class Country(val name: String, val population: Int)
data class State(val name: String, val population: Int)
val x = Country(name="Sweden", population=4)
// error: type mismatch: inferred type is Country but State was expected
val sweden: State = x
fun travel(country: Country) {
val name = country.name
print("We are going to $name")
}
val norway = State(name="Norway", population=5)
// error: type mismatch: inferred type is State but Country was expected
travel(norway)

Letā€™s review some definitions.

Subtyping

Subtyping is about substitutability. Type S is a subtype of type T if S can be used in a place where T is expected.

In our original TypeScript example, State is a subtype of Country, and Country is a subtype of State.

When subtyping goes both ways, we say the types are equivalent. Often times the relationship only goes one way though.

// TypeScript
type User = {
id: string;
};
type Auth0User = {
id: string;
auth0UserId: string;
};
function getUserInfoFromDatabase(user: User) {}
function getUserInfoFromAuth0(auth0User: Auth0User) {}
const michael: Auth0User = { id: "239ruepi", auth0UserId: "23jlkj23" };
// no problem
getUserInfoFromDatabase(michael);
const idris: User = { id: "2u3r0wfj" };
// error: Argument of type User is not assignable to parameter of type Auth0User
getUserInfoFromAuth0(idris);

We can use Auth0User in place of User, making Auth0Usera subtype of User.

We cannot use User in place of Auth0User, meaning User is not a subtype of Auth0User.

Nominal Subtypes

In a nominal type system, a type is only a subtype of another if it is declared to be so in its definition. Structural subtyping is intrinsic, while nominal subtyping is declarative [3].

Iā€™m going to repeat that for emphasis.

Structural subtyping is intrinsic, while nominal subtyping is declarative.

Letā€™s look at a subtype example in our nominal type system of the day, Kotlin.

// Kotlin
open class User(val id: String)
class Auth0User(id: String, auth0UserId: String): User(id) // declare subtype relationship
fun getUserInfoFromDatabase(user: User) {}
fun getUserInfoFromAuth0(auth0User: Auth0User) {}
val michael = Auth0User(id="239ruepi", auth0UserId="23jlkj23")
getUserInfoFromDatabase(michael) // all good
val idris = User(id="2u3r0wfj")
// error: type mismatch: inferred type is User but Auth0User was expected
getUserInfoFromAuth0(idris)

What about Go?

Go is another language Iā€™m fond of, and itā€™s not as black and white as TypeScript and Kotlin.

Letā€™s take a look at the Country example in Go.

// Go
package main
type Country struct {
name string
population int
}
type State struct {
name string
population int
}
func main() {
x := Country{name: "Sweden", population: 4}
var norway State
// error: cannot use x as State value in assignment
norway = x
}

Itā€™s the same for passing arguments to a function.

func travel(country Country) {
fmt.Printf("We are going to %s", country.name)
}
norway := State{name: "Norway", population: 5}
// error: Cannot use variable norway (of type State) as Country value
travel(norway)

So, nominal, right? Not quite.

If we donā€™t use a named type in our function definition, then it matches based on structure.

func travel(country struct {
name string
population int
}) {
fmt.Printf("We are going to %s", country.name)
}
// can pass variables with type Country or State into this

In Go,

  • two types are either identical or different (no subtyping)
  • a named type is always different from any other type
  • otherwise, theyā€™re identical if their underlying structures are equivalent

Go also defines the notion of assignability (which sounds a lot like ā€œsubstitutabilityā€). One type is assignable to another if:

  • theyā€™re the same named type
  • they have the same underlying structure, and at least one of them is not a named type
  • one is an interface type that the other implements

So Go is a mixed bag. It is structurally typed in general, but then it has this thing called named types, which is the definition of nominal typing. Not to mention using them is an extremely common way to write Go.

Final Questions

How does duck-typing relate to structural typing?

Citing this answer, duck typing is a runtime phenomenon emerging from the semantics of dynamically typed languages.

TypeScript is structurally typed. JavaScript is duck-typed.

Iā€™m not a huge fan of duck typing, because Iā€™m not a huge fan of dynamic type systems. Structural typing is like a static version of duck typing. And that makes it better.

Do nominal types maintain type information at runtime?

Consider our TypeScript branding example.

1
// TypeScript
2
type Inches = {
3
_unit: "inches"; // this is a brand
4
value: number;
5
};

That _unit brand is going nowhere at runtime, because we have to do this.

1
// TypeScript
2
const distance: Inches = { value: 5, _unit: "inches" };

What about in Kotlin? In short, yes.

Kotlin has the notion of runtime type information, which is avaliable for some of its types, namely classes, interfaces, objects, and functions. Check out this section of the spec.

The key exception is generics. Those types are erased.

In Summary

  • Nominal typing is a subset of structural typing. In structural typing, type compatibility is decided on the structure of types. In nominal typing, itā€™s decided by name. You can achieve this in TS with branding.
  • TypeScript is structurally typed.
  • Kotlin is nominally typed.
  • Type relationships are sometimes managed through subtyping. One type is a subtype of another if it can be substituted in its place. Go does not do subtyping; the closest thing it has is assignability.

Resources

  1. Effective TypeScript
  2. Wikipedia
  3. Integrating Nominal and Structural Subtyping
  4. Nominative and Structural Typing
  5. Comparison of Programming Languages by Type Systems
  6. Kotlin Language Specification, Type System
  7. Programmer dictionary: Class vs Type vs Object
  8. Why doesnā€™t Go have variance in its type system?

Wow! You read the whole thing. People who make it this far sometimes want to receive emails when I post something new.

I also have an RSS feed.