A structural type system (or property-based type system) is a major class of type system
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
, in which type compatibility and equivalence are determined by the type's structure, 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
Nominative type system
In computer science, a nominal or nominative type system is a major class of type system, in which compatibility and equivalence of data types is determined by explicit declarations and/or the name of the types. Nominative systems are used to determine if types are equivalent, as well as if a type...
, where comparisons are based on explicit declarations or the names of the types, and duck typing
Duck typing
In computer programming with object-oriented programming languages, duck typing is a style of dynamic typing in which an object's current set of methods and properties determines the valid semantics, rather than its inheritance from a particular class or implementation of a specific interface...
, in which only the part of the structure accessed at runtime is checked for compatibility.
In structural typing, an object or term is considered to be compatible with another type if for each feature within the second type, there must be a corresponding and identical feature in the first 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 such types are considered to be identical if each is compatible with the other.
As an example, OCaml uses structural typing on methods for compatibility of object types. Go
Go (programming language)
Go is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
uses structural typing on methods to determine compatibility of a type with an interface. C++ template functions exhibit structural typing on type arguments. HaXe
HaXe
haXe is a versatile open-source high-level multiplatform programming language described on its website as a "universal language".It can produce:* Flash applications and games* Multi-platform client-side web applications* Apache CGI web applications...
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).
There is a distinction 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. 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.
In computer science, a nominal or nominative type system is a major class of type system, in which compatibility and equivalence of data types is determined by explicit declarations and/or the name of the types. Nominative systems are used to determine if types are equivalent, as well as if a type...
, as it permits the creation of ad hoc types and protocol
Protocol (object-oriented programming)
In object-oriented programming, a protocol or interface is a common means for unrelated objects to communicate with each other. These are definitions of methods and values which the objects agree upon in order to cooperate....
s; 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
Algebraic data type
In computer programming, particularly functional programming and type theory, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped datum is an argument to the constructor...
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 > =
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 > =
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.
One 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 =
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 > =
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 =
# (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.
WikiWikiWeb is a term that has been used to refer to four things: the first wiki, or user-editable website, launched on 25 March 1995 by Ward Cunningham as part of the Portland Pattern Repository ; the Perl-based application that was used to run it, also developed by Cunningham, which was the first...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
