Infinite Negative Utility

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:

class Cat {
  void speak() {
    System.out.println("meow");
  }
}

class Dog {
  void speak() {
    System.out.println("woof");
  }
}

Both Cat and 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:

class cat = object
  method speak = print_endline "meow"
end
class dog = object
  method speak = print_endline "woof"
end

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:

let hear_what_it_has_to_say obj =
  let () = obj#speak in ()

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 function¹:

# hear_what_it_has_to_say;;
- : < speak : unit;  .. >  ->  unit = <fun>

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 unit.

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!

let () = hear_what_it_has_to_say (new cat)
(* prints "meow" *)
let () = hear_what_it_has_to_say (new dog)
(* prints "woof" *)

Notice that at no point in the above code did I indicate that cat or 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.

Row Polymorphism

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.²

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 dog and cat had the same interface, but we could define a new object that features a different, larger interface:

class cow = object
  method speak = print_endline "moo"
  method num_stomachs = 4
end

Our cow class now has a method that neither cat nor 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 cat and dog. After all, it still fits the interface!

let () = hear_what_it_has_to_say (new cow)
(* prints "moo" *)

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:

let ecce_orator obj =
  let () = obj#speak in obj

Here's the type that OCaml infers for this:

# ecce_orator;
- : (< speak : unit; .. > as 'a) -> 'a = <fun>

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.³

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:

class Cat
  def speak() puts "meow" end
end

class Cow
  def speak() puts "moo" end
  def num_stomachs() 4 end
end

def hear_what_it_has_to_say(obj)
  obj.speak
end

hear_what_it_has_to_say(Cat.new)
hear_what_it_has_to_say(Cow.new)

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.