Nominal Typing Done Wrong
Published:
When implementing a type system, a question is constantly asked: under what circumstance should we consider two types equal to each other? Two common styles to approach the problem are structural and nominal typing. In essence, structural typing adds a bunch of congruence rules saying that if all components of the two types are equal, then the two types are equal; meanwhile, nominal typing ensures that types have names, and two type are equal only if they have the same name. As we shall see, they have different merits and are usually implemented in different ways. When coming up with a new language, language designers have the freedom of picking different type equality policies for different parts of the language in question. Though it’s possible to mix both styles without breaking the static semantics, it’s commonly believed that a consistent style can help avoid confusion. Under such assumption, we can roughly divide languages into two kinds: those embracing a structural type system, and those using a nominal one. Then an interesting observation is that I see more languages in real life adopt nominal typing than those structural. In fact, it’s hard to think of many languages with a structural type system: OCaml, Scala, Dhall, Typescript, and perhaps Go’s interface and Elm’s record (sorta). (Un)surprisingly, almost all imperative language’s type systems are nominal, with Rust as a representitive. My conjecture for the reason behind the phenomena is that nominal type systems are easier to implement and comprehend.