Something I’ve felt for a long time is that structural types are underused and underappreciated in modern programming languages. They’re not unheard of: plenty of programming languages feature them in prominent or less-than-prominent ways! But I’m always surprised that they don’t show up more prominently.
In particular, I feel that structural types combine about 95% of what I want out of dynamic duck typing with about 95% of what I want out of static type-checking: and honestly, that’s a good amount of both! This post is intended to be a quick example of what structural types looks like and why I sometimes point to them as the static answer to duck typing.
Structural Types vs. Nominal Types
If you’re familiar with Java, you know what nominal types look like. Consider the following (contrived) example in Java:
Dog are classes that, from a programmer’s point of view, implement the same interface: both of them have a zero-argument method
speak that prints something. However, as written, I can’t easily write a function that accepts either a
Cat or a
Dog and statically rejects other objects which don’t have a
speak method. From Java’s point of view, these are completely different types, regardless of the set of methods they expose. Why? Because they’re named different things! I could manually tell Java that they implement a shared interface, but there are no language features that can work over objects of the same “shape” without explicitly indicating that they share that shape.
The OCaml language has a different approach to objects. I can define analogous classes in OCaml like this:
However, OCaml has a crucial difference in how it treats the types of objects: OCaml cares more about the interface than the name. Consider the function below:
If you’re used to curly-brace languages, then this syntax might be unfamiliar: the
# operator works like the
. operator in Java and other object-oriented languages, so the expression
obj#speak is the OCaml equivalent of
obj.speak() in most traditional object-oriented languages. If we load this function into an OCaml repl, we can observe the type that OCaml has inferred for this function1:
This again might be unfamiliar syntax, so the way to read this type is as follows:
hear_what_it_has_to_say is a function which takes an object whose type (represented as the stuff in the angle brackets) has a method called
speak which returns
unit (more or less like
void in Java or C++). The object may have other methods, which is what the
.. means. Finally, the function itself returns
In short, this function takes an argument that must be an object that has at least a
speak method which doesn’t return anything. This means I can call it with both a
cat and a
dog: after all, they both fit that description!
Notice that at no point in the above code did I indicate that
dog shared an interface: in fact, I didn’t define any interfaces at all! I simply created data that had a particular shape, and wrote code that assumed a particular shape, and put them together.
Sometimes when I talk about structural typing, I talk specifically about row types or row polymorphism. This is a particular implementation of structural typing which happens to be convenient and easy to reason about, although other approaches do exist.2
You’ve already seen an example of row polymorphism: OCaml’s object types! The
.. in the above type signature is what we would call a “row variable”, a stand-in for “the rest of the object”. In the above instance, both
cat had the same interface, but we could define a new object that features a different, larger interface:
cow class now has a method that neither
dog bothered to implement. However, we can still call our
hear_what_it_has_to_say method on it without trouble, even though its type is strictly larger than the types of both
dog. After all, it still fits the interface!
A powerful feature of row types is that we can give intermediate names to structures or parts of structures and use them accordingly. For example, I can write a function like the one above that calls a method and then returns the object it received:
Here’s the type that OCaml infers for this:
This types looks mostly like the one before, except that we give the object type a temporary alias (here it is
'a) which allows us to express that the return value of the function is exactly the same as what we got in: that is, if we were passed a
cat, we’ll get back a
cat with all its methods, if we were passed a
cow, we’ll get back a
cow with all its methods, and so forth. This is important, and is one of the things that separates systems like row typing from other approaches to structural types like structural subtyping.3
Why Does It Matter?
I said near the beginning that structural types give you 95% of what you want from duck typing and 95% of what you want from static typing. For a long time, I suspected that people who were fans of dynamic languages would start to find structurally-typed systems and use them to build new languages which could take advantage of static types while retaining the flexibility of dynamic systems that permit duck-typed interfaces. I recently found a newer language which is a perfect example of exactly this approach: the Crystal language. To demonstrate, here’s what the above OCaml snippets look like when translated into Crystal:
If you know Ruby, this program will look very familiar: it’s valid Ruby source! In particular, like the OCaml above, it’s a program that can call
hear_what_it_has_to_say on any object with a
speak method through the magic of duck typing! Amazingly, it’s also valid Crystal, and produces exactly the same output. There’s an important difference, though: if I were to ammend this program with a line like
hear_what_it_has_to_say(5), then the Crystal compiler gives me the following compile-time error:
Error in src/main.cr:19: instantiating 'hear_what_it_has_to_say(Int32)' hear_what_it_has_to_say(5) ^~~~~~~~~~~~~~~~~~~~~~~ in src/main.cr:12: undefined method 'speak' for Int32 obj.speak ^~~~~ Rerun with --error-trace to show a complete error trace.
This is a bit verbose and jargon-heavy, but what it’s telling us is that the literal
5 (which Crystal gives the type
Int32) doesn’t have a method called
speak, and therefore the program doesn’t type-check. Crystal is doing something very much like what OCaml does here, but it’s also doing it while presenting you with an interface that looks a lot like Ruby’s: it’s specifically designed to enable the use of duck typing while still preventing cases that would end up failing at runtime!
But You Said 95% Up At The Top
Okay, there are a few drawbacks to a system like this. One small cost relative to a more traditional nominally-typed system is performance: it’s difficult to implement this kind of type system without some kind of indirection, which is a small but nonetheless present cost. When a method is given an object which has a
speak method, it needs to know where the code for that method lives, which means I’ll need some kind of function pointer or vtable to point it to the appropriate code, or else I’ll have to replicate the method’s code with specializations for each data layout we use. In most problem domains, this won’t be a problem—but nonetheless, this sort of indirection wouldn’t necessarily be required in a system with more rigid types!
A slightly bigger cost is that structural systems like this have slightly weaker static guarantees than a more nominal system. In a Java-like setting, if I accidentally try to call
myCat.speka() instead of
myCat.speak(), then the compiler can immediately spot a problem right in the function definition:
Cat objects don’t have a
speka method! In the analogous OCaml function, however, I might not find the problem so easily: if I mistyped out
hear_what_it_has_to_say function above with a
speka method, then the function itself would have been fine: it just means that it takes an object that has a
speka method instead of what we intended! Our program as a whole still wouldn’t compile, but the error would only arise elsewhere, when we try to pass a
cat object to the method. In this case, we’re probably safe, but when you start to look at programs across module or compilation unit boundaries, you can start seeing that it’s possible for this sort of error to slip in unnoticed until later compilation units are presented with a nonsensical interface.
Finally, there’s the cost relative to traditional dynamic type systems: these structurally-typed systems are often less expressive than pure duck typing! OCaml’s approach, for example, doesn’t let you branch on whether or not an object has a given method, like Python’s
hasattr or Ruby’s
respond_to?: you either use the interface you’re given, or you don’t. Crystal does let you do this, but the type system becomes more complex and sporadically harder to reason about, and it will regularly (although it didn’t come up in my example above) simply give up inference and require the you to fill in the types that you want. Still, it’s not as straightforward as passing in a thing that implements the stuff you want and letting it quack.
Of course, in several of these cases, I’m also setting up a bit of an artificial divide: there’s nothing wrong with having a system that has features of structural and nominal typing! OCaml does, and this can be very powerful: we can have some parts of the program that work over types whose structure is inferred, and others that work over types whose structures is declared up-front, and both of these can happen in concert. Alternately, we can build gradually typed systems that allow full dynamic types and gradually use more static knowledge to move towards a system like this, for a full spectrum between flexibility and safety.
But even with the drawbacks as described, I contend that systems that use structural types as a modeling tool are a powerful middle step between dynamic and static languages, and they can definitely enable new powerful tools that allow the flexible experimentation of dynamically-typed languages while retaining many of the safety properties provided by statically-typed languages.
I added a tiny bit of extra whitespace to the actual output, for clarity’s sake.↩
The most notable other approach to structural typing is structural subtyping, which I’m not going to go over here, but which also exists in OCaml: the Real World OCaml book has a section on Subtyping Versus Row Polymorphism which explains it in a bit more detail. There are some situations where you might prefer row types, and some where you might prefer a proper subtyping system: it very much depends!↩
In particular, in a system with subtyping, I might have one type that’s a subtype of another: say, a
catwhich is a subtype of
animal. I can write a function which accepts an
animalas argument, and pass it a
cat, but once I’ve done that, I’ve casted that reference to a
catto a broader type, which means the type has lost some information! If that function returns the value it was given, it can’t return the
cat, it has to return the value it was given, and the type has no way of tying the full structure of the input type to the output type. That’s where row typing is a valuable tool!↩