Structural type system

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

In structural typing, an element is considered to be compatible with another if, for each feature within the second element's type, a corresponding and identical feature exists in the first element's type. Some languages may differ on the details, such as whether the features must match in name. This definition is not symmetric, and includes subtype compatibility. Two types are considered to be identical if each is compatible with the other.

For example, OCaml uses structural typing on methods for compatibility of object types. Go uses structural typing on methods to determine compatibility of a type with an interface. C++ template functions exhibit structural typing on type arguments. Haxe uses structural typing, but 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 added features, such as members not present in the base type, or stronger invariants.

A distinction exists between structural substitution for inferred and non-inferred polymorphism. Some languages, such as Haskell, do not substitute structurally in the case where an expected type is declared (i.e., not inferred), e.g., only substitute for functions that are signature-based polymorphic via type inference.^[1] Then it is not possible to accidentally subtype a non-inferred type, although it may still be possible to provide an explicit conversion to a non-inferred type, which is invoked implicitly.

構造的サブタイピングは、アドホックな型やプロトコルの作成を可能にするため、名義的サブタイピングよりも柔軟性が高いと言えるでしょう。特に、既存の型の定義を変更することなく、その型のスーパータイプとなる型を作成することが可能です。しかし、プログラマーが閉じた抽象化を作成したい場合には、これは望ましくないかもしれません。

構造型付けと命名型付けの欠点の一つは、異なる目的で個別に定義された2つの型が、偶然にも同じ特性（例えば、どちらも整数のペアで構成されている）を持つ場合、構造が同一であるという理由だけで、型システムによって同じ型とみなされてしまう可能性があることです。これを回避する一つの方法は、用途ごとに代数的なデータ型を一つずつ作成することです。

1990年、Cookらは、構造型付けされたオブジェクト指向言語では継承はサブタイピングではないことを証明した。 ^{[ 2 ]}

構造型に基づいて2つの型が互換性があるかどうかをチェックすることは、簡単な操作ではなく、たとえば、以前にチェックした型のスタックを維持する必要があります。^{[ 3 ]}

型が期待される構造と一致しない場合、エラーメッセージは名目上の型付けの場合よりも長くなります。

OCamlにおけるオブジェクトは、そのメソッドの名前と型によって構造的に型付けされる。

オブジェクトは、クラス名を経由せずに直接作成できます（直接オブジェクト）。クラスは、オブジェクトを作成するための機能のみを提供します。

# 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 >

ここでは、OCaml 対話型ランタイムが便宜上、オブジェクトの推論された型を出力します。その型 ( ) は、そのメソッドによってのみ定義されます。言い換えれば、x の型は、名前ではなく、メソッド型 "get_x : int" と "set_x : int -> unit" によって定義されます。 ^{[ 4 ]}< get_x : int; set_x : int -> unit >  

同じメソッドとメソッドの型を持つ別のオブジェクトを定義するには：

#lety=objectmethodget_x=2methodset_xy=Printf.printf"%d\n"yend;;valy:<get_x:int;set_x:int->unit>=<obj>

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.

One can define a function that invokes a method:

#letset_to_10a=a#set_x10;;valset_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 it can be used on object x:

#set_to_10x;;-:unit=()

Another object can be made that happens to have that method and method type; the other methods are irrelevant:

#letz=objectmethodblahblah=2.5methodset_xy=Printf.printf"%d\n"yend;;valz:<blahblah:float;set_x:int->unit>=<obj>

The "set_to_10" function also works on it:

#set_to_10z;;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:

#typesimpler_obj=<get_x:int>;;typesimpler_obj=<get_x:int>

The 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 x can be coerced 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.

• Pierce, Benjamin C. (2002). "19.3". Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.

• NominativeAndStructuralTyping at WikiWikiWeb