Structural type system

A structural type system (or property-based type system) is a major class of type system, in which type compatibility and equivalence are determined by the type's structure, and not through explicit declarations. Structural systems are used to determine if types are equivalent, as well as if a type is a subtype of another. It contrasts with nominative systems, where comparisons are based on explicit declarations or the names of the types, and duck typing, in which only the part of the structure accessed at runtime is checked for compatibility.

In structural typing, two objects or terms are considered to have compatible types if the types have identical structure. Depending on the semantics of the language, this generally means that for each feature within a type, there must be a corresponding and identical feature in the other type. Some languages may differ on the details (such as whether the features must match in name).

ML, Whiteoak and Objective Caml are examples of structurally-typed languages. HaXe uses structural typing, although classes are not structurally subtyped.

In languages which support subtype polymorphism, a similar dichotomy can be formed based on how the subtype relationship is defined. One type is a subtype of another if and only if it contains all the features of the base type (or subtypes thereof); the subtype may contain additional features (such as members not present in the base type, or stronger invariants).

Structural subtyping is arguably more flexible than nominative subtyping, as it permits the creation of ad hoc types and interfaces; in particular, it permits creation of a type which is a supertype of an existing type T, without modifying the definition of T. However this may not be desirable where the programmer wishes to create closed abstractions.

A pitfall of structural typing versus nominative typing is that two separately defined types intended for different purposes, each consisting of a pair of numbers, could be considered the same type by the type system, simply because they happen to have identical structure. One way this can be avoided is by creating one algebraic data type for one use of the pair and another algebraic data type for the other use.

Example

Objects in OCaml are structurally typed by the names and types of their methods.

Objects can be created directly ("immediate objects") without going through a nominative class. Classes only serve as functions for creating objects.

 # let x =
     object
       val mutable x = 5
       method get_x = x
       method set_x y = x <- y
     end;;
 val x : < get_x : int; set_x : int -> unit > = <obj>

Here the OCaml interactive runtime prints out the inferred type of the object for convenience. You can see that its type (< get_x : int; set_x : int -> unit >) is purely defined by its methods.

Let's define another object, which has the same methods and types of methods:

 # let y =
     object
       method get_x = 2
       method set_x y = Printf.printf "%d\n" y
     end;;
 val y : < get_x : int; set_x : int -> unit > = <obj>

You can see that OCaml considers them the same type. For example, the equality operator is typed to only take two values of the same type:

 # x = y;;
 - : bool = false

So they must be the same type, or else this wouldn't even type-check. This shows that equivalence of types is structural.

I can define a function that invokes a method:

 # let set_to_10 a = a#set_x 10;;
 val set_to_10 : < set_x : int -> 'a; .. > -> 'a = <fun>

The inferred type for the first argument (< set_x : int -> 'a; .. >) is interesting. The .. means that the first argument can be any object which has a "set_x" method, which takes an int as argument.

So we can use it on object x:

 # set_to_10 x;;
 - : unit = ()

We can make another object that happens to have that method and method type; the other methods are irrelevant:

 # let z =
     object
       method blahblah = 2.5
       method set_x y = Printf.printf "%d\n" y
     end;;
 val z : < blahblah : float; set_x : int -> unit > = <obj>

The "set_to_10" function also works on it:

 # set_to_10 z;;
 10
 - : unit = ()

This shows that compatibility for things like method invocation is determined by structure.

Let us define a type synonym for objects with only a "get_x" method and no other methods:

 # type simpler_obj = < get_x : int >;;
 type simpler_obj = < get_x : int >

Our object x is not of this type; but structurally, x is of a subtype of this type, since x contains a superset of its methods. So we can coerce x to this type:

 # (x :> simpler_obj);;
 - : simpler_obj = <obj>
 # (x :> simpler_obj)#get_x;;
 - : int = 10

But not object z, because it is not a structural subtype:

 # (z :> simpler_obj);;
 This expression cannot be coerced to type simpler_obj = < get_x : int >;
 it has type < blahblah : float; set_x : int -> unit > but is here used with type
   < get_x : int; .. >
 The first object type has no method get_x

This shows that compatibility for widening coercions are structural.

References

• Benjamin C. Pierce, Types and programming languages, MIT Press 2002, ISBN 0262162091, section 19.3

External links

• c2.com: Nominative and structural typing