Articles

Why not use Structural Subtyping?

Modern programming languages generally use what is known as a [[Nominal typing|Nominal type system]].  This means types are associated with explicit names and subtyping relationships are explicit in the code (e.g. via extends or implements). This approach has the advantage of being relatively simple to implement; however, at the same time, it is quite restrictive because the way types are structured is essentially fixed.

An alternative (and far less common) approach is to use a [[Structural type system]]. In this case, types are not associated with explicit names and subtyping relationships are not declared explicitly. Rather, types are defined by their structure and subtyping is implicit between types of related structure. Consider this simple example:

define Point as { int x, int y }
define Point3D as { int x, int y, int z }

Whilst there is no explicit connection between Point and Point3D, there is an implicit one — namely, that Point3D is a subtype of Point. This means we can pass Point3D instances into variables of type Point, without any need for casting. Likewise, we can define an implicit super type of Point:

define RealPoint as { real x, real y }

These definitions may be spread across different files, different libraries or different programs — i.e. there is no connection between them other than their structure. In fact, we might even have a different name for the same type:

define XYpoint as { int x, int y }

In a structural type system, there is no difference at all between Point and XYpoint — they are the exactly same type.

The advantages of structural subtyping seem fairly evident to me. For example, suppose you’re working with some library and want to pass your types directly into its functions. In a nominal type system, this can be a real problem unless (by chance) we can inherit or implement types from the library. In a structural type system, this is easy as we just need to make sure our types have the right fields! (Of course, encapsulation is an issue here, as we may not know exactly what fields are required).

Here’s another take on the benefits of structural subtyping. So, my question is: why don’t more languages employ structural subtyping? Scala is probably the best example of one that (at least, to some degree) does — see here and here. Also, there is the “M Programming Language” (see here, here and here for more), which has excellent support for structural subtyping.

Finally, there has been a fair amount of academic research on structural subtyping in the context of languages like Java:

  • Integrating Nominal and Structural Subtyping“, Donna Malayeri and Jonathan Aldrich. In Proceedings of ECOOP, 2008. [PDF]
  • Whiteoak: Introducing structural typing into Java“, Joseph (Yossi) Gil and Itay Maman. In Proceedings of OOPSLA, 2008. [PDF]

19 comments to Why not use Structural Subtyping?

  • The way you describe this sounds more like “duck typing”. Duck typing is something like “does it have the right methods?” whereas structural subtyping is “does it have the right components?”.

    The problem is that a 3D point should NOT be used in place of a 2D point. They are really different things.

    Imagine you have an “area” function expecting a circle, which is represented by {point center; real radius}. You pass it an ellipse represented by {point center; real minor_axis; real major_axis}. Clearly the function will return the wrong result, and the type system won’t protect you.

  • Hey Jeff,

    So, yeah, it is like duck typing. The main difference being that it is statically enforced. Sorry, I don’t follow your ellipse example [as ellipse is not a structural subtype of circle]. Assuming the ellipse record has a radius field, then really the issue is about what the area function is supposed to do. The name of the function you’re describing should be: areaOfCircle() — since this is what it’s doing. If we want to distinguish between ellipses and circles, then we need some field to separate them, and a method which then selects on that field. (actually, this is one of the awkward things of structural subtyping — you often end up using fields to distinguish different types).

  • The main reason is that structural width subtyping can be a fair bit more expensive at runtime than nominal subtyping with single inheritance. Structural depth subtyping is, however, usually pretty easy.

    One argument in favor of the existence of nominal subtyping is that it gives you easy to use mnemonics (Although, yes, you can use type aliases), and a way to capture laws and interface contracts that aren’t visible in the type.

    If you are interested in structural subtyping, there is a particularly elegant implementation in Matthias Blume’s MLPolyR, and a slightly less elegant version baked into Ocaml. Duality usually leads from open records to open variants, which are exploited in both of those type system, although they are not yet present in Scala.

  • Hi Edward,

    Ah, your point about width subtyping is very interesting. The issue is basically that you sacrifice the abilty for constant-time lookup of fields, since you can’t tell exactly which slot a given field occupies. Kind of like the interface problem in Java (e.g. [1]), right?

    I also agree with your comment about hidden invariants. However, the rise and prevalence of dynamic languages makes me feel that this problem may be overstated … ?

    Ah, I’d forgotten about O’Caml … yes I’ll have to take a look at that!

  • You should check out haxe:
    http://www.haxe.org
    http://haxe.org/doc/intro

    It is ecmascript based, and performs the compile-time structural subtyping you are describing. The key feature is that haxe can compile to other targets and vm’s, including swf bytecode and javascript. It’s a solid option if you want to use advanced static compilation features for dynamic web languages.
    http://haxe.org/manual/2_types

  • Hey cool — thanks!! I haven’t heard of haXe before, and it looks very interesting. I think structural subtyping is really well-suited to typing dynamic languages …

  • Tom

    The link for Nominal type system on wikipedia doesn’t exist, but http://en.wikipedia.org/wiki/Nominal_typing does.

  • Ta — should be fixed now.

  • Eli

    You might want to read this paper to see what’s being done to bring structural subtyping into more prominent use, and what’s been holding it back.

  • Matt

    I can see using a 2D point where a 3D point is expected by just assuming that the z component is zero, but I can’t imagine any situation where using a 3D where a 2D point is required by just ignoring the z component makes sense. You normally would have to do some kind of projection from the 3D to the 2D space.

  • Well, that’s pretty much exactly what you’re doing — projecting away the Z component.

    But, the point of the example is more to illustrate the mechanism of structural subtyping, rather than to think about when it does and does not make sense. In a dynamically typed language, like JavaScript, you can do exactly this sort of thing (and it’s considered pretty useful). The downside, however, is that in JavaScript you get no guarantees of safety at all — so the code can fail at any point. However, with structural subtyping, you get back the safety whilst keeping all the flexibility …

  • david allan finch

    Excellent, I have always want to assign fruit to a 3DPoint.

    define Bag as { int apples, int oranges }

    Not everything that has wings and flies is a duck sometimes its classification or other non specified information makes the structures not the same.

  • Mascara adds structural typing to JavaScript. It really shines when you want to gradually add type annotations to existing duck-typed code, without having to rewrite everything.

    Structural typing is also a necessity when typing code which uses object literals to define instances, as is often the case in JavaScript.

    Nominal typing might be cleaner if you develop code from scratch, but when integrating with untyped/duck-typed code, structural typing is very convenient, and can work as a first step towards nominal typing.

  • OCaml has a nominal type system enhanced with polymorphic variants and object classes, which use row types for structural subtyping. The diagnostic messages produced by the OCaml compilers for all type errors, not just the structural subtyping errors, can be a bit… oblique.

    My take on the type-classes vs. structural subtyping discussion is that A) one or the other is a good idea, but not both; and B) whichever one you pick is going to leave people missing the other. It’s not clear which one is really the winner, but there are a lot of people who have picked a favorite and would rather not see the debate continue.

  • Hi David,

    “Excellent, I have always want to assign fruit to a 3DPoint”

    Well, I guess you’re not a fan of duck typing either. The issue is really about what is more important: flexibility or safety. Traditional languages, like Java, er on the side of safety (which is nice), but this causes problems when interoperating with existing code. If the programmer of that existing code made a bad job of structuring their data, or it is not extensible etc, then you’re stuck with it. Structural typing aims to hit a sweet spot between both.

  • Hi Olav,

    Thanks for the pointer to Mascara — I haven’t come across that before!! I competely agree that it’s really useful for typing previously untyped code…

  • Hi J Woodyatt,

    “It’s not clear which one is really the winner, but there are a lot of people who have picked a favorite and would rather not see the debate continue.”

    Hmmm, interesting. Type classes came up in the comments section on reddit. I’m not entirely familiar with them, although I was aware of some similarity. I need to go check them out — thanks!!

  • [...] Case Against Structural Subtyping … ? By Dave, on January 26th, 2011 My previous post on structural subtyping generated quite a few comments over on reddit.  There were a lot of mixed opinions as to the pros [...]

  • [...] typing, rather than nominal typing, and I’ve blogged about this quite a bit already (see [1][2][3][4]).  Over the weekend, I finally found time to work through all my thoughts and turn them [...]

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>