Nominal Subtying Considered Bad: Findler, Flatt and Felleisen

March 14, 2006

I came across the following words in a paper about using casts:

“Nominal subtyping forces programmers to explicitly state all of the subtyping relationships in the program. This limits component reuse, because programmers cannot anticipate all of the contexts in which a particular class might be used. In contrast, structural subtyping implicitly allows any type with appropriate structure to be used in a given context.

Language designers choose nominal type systems because they are easy to understand and easy to implement. A programmer doesn’t need to investigate the structure of an interface I to find out whether an instance o of a class C can have type I; it suffices to check whether the definition of C mentions I as an implemented interface (or whether the superclasses and superinterfaces mention I). A compiler writer, in turn, can build a class graph and an interface graph and type check expressions and statements by comparing points in a graph.

Nominal typing, however, is also a known obstacle to software reuse. In particular, a programmer can only compose two objects if the creators of the two respective classes used the same (nominal) types. Unfortunately, in a world of software components where third-party programmers compose existing pieces of software, the implementor of a class cannot possibly anticipate all possible types for an object. Hence, programmers resort to casts and have invented adapter patterns to bridge the gap between third- party components.

One way to overcome this problem is to switch to a structural type system. The research community has long recognized this shortcoming of nominal subtype systems and that structural subtype systems do not suffer from this flaw. Some modern research languages like LOOM , OCaml, OML, PolyTOIL, and Moby adopt structural subtype systems. Their designs demonstrate how their structural subtype systems empower their user communities to reuse classes in unanticipated situations.”

This is very well stated. The authors go on to describe an implementation of a limited form of subtyping via contracts for an enriched Java.

Read the rest of their paper here: Semantic Casts, Contracts and Structural Subtyping in a NominalWorld, Robert Bruce Findler, Matthew Flatt, and Matthias Felleisen.

Advertisements