Английская Википедия:Intersection type

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description Шаблон:Type systems In type theory, an intersection type can be allocated to values that can be assigned both the type <math>\sigma</math> and the type <math>\tau</math>. This value can be given the intersection type <math>\sigma \cap \tau</math> in an intersection type system.[1] Generally, if the ranges of values of two types overlap, then a value belonging to the intersection of the two ranges can be assigned the intersection type of these two types. Such a value can be safely passed as argument to functions expecting either of the two types. For example, in Java the class Шаблон:Code implements both the Шаблон:Code and the Шаблон:Code interfaces. Therefore, an object of type Шаблон:Code can be safely passed to functions expecting an argument of type Шаблон:Code and to functions expecting an argument of type Шаблон:Code.

Intersection types are composite data types. Similar to product types, they are used to assign several types to an object. However, product types are assigned to tuples, so that each tuple element is assigned a particular product type component. In comparison, underlying objects of intersection types are not necessarily composite. A restricted form of intersection types are refinement types.

Intersection types are useful for describing overloaded functions.[2] For example, if Шаблон:TS-lang is the type of function taking a number as an argument and returning a number, and Шаблон:TS-lang is the type of function taking a string as an argument and returning a string, then the intersection of these two types can be used to describe (overloaded) functions that do one or the other, based on what type of input they are given.

Contemporary programming languages, including Ceylon, Flow, Java, Scala, TypeScript, and Whiley (see comparison of languages with intersection types), use intersection types to combine interface specifications and to express ad hoc polymorphism. Complementing parametric polymorphism, intersection types may be used to avoid class hierarchy pollution from cross-cutting concerns and reduce boilerplate code, as shown in the TypeScript example below.

The type theoretic study of intersection types is referred to as the intersection type discipline.[3] Remarkably, program termination can be precisely characterized using intersection types.[4]

TypeScript example

TypeScript supports intersection types,[5] improving expressiveness of the type system and reducing potential class hierarchy size, demonstrated as follows.

The following program code defines the classes Шаблон:TS-lang, Шаблон:TS-lang, and Шаблон:TS-lang that each have a method Шаблон:TS-lang returning an object of either type Шаблон:TS-lang, Шаблон:TS-lang, or Шаблон:TS-lang. Additionally, the functions Шаблон:TS-lang and Шаблон:TS-lang require arguments of type Шаблон:TS-lang and Шаблон:TS-lang, respectively. 

class Egg { private kind: "Egg" }
class Milk { private kind: "Milk" }

// produces eggs
class Chicken { produce() { return new Egg(); } }

// produces milk
class Cow { produce() { return new Milk(); } }

// produces a random number
class RandomNumberGenerator { produce() { return Math.random(); } }

// requires an egg
function eatEgg(egg: Egg) {
    return "I ate an egg.";
}

// requires milk
function drinkMilk(milk: Milk) {
    return "I drank some milk.";
}

The following program code defines the ad hoc polymorphic function Шаблон:TS-lang that invokes the member function Шаблон:TS-lang of the given object Шаблон:TS-lang. The function Шаблон:TS-lang has two type annotations, namely Шаблон:TS-lang and Шаблон:TS-lang, connected via the intersection type constructor Шаблон:TS-lang. Specifically, Шаблон:TS-lang when applied to an argument of type Шаблон:TS-lang returns an object of type type Шаблон:TS-lang, and when applied to an argument of type Шаблон:TS-lang returns an object of type type Шаблон:TS-lang. Ideally, Шаблон:TS-lang should not be applicable to any object having (possibly by chance) a Шаблон:TS-lang method. 

// given a chicken, produces an egg; given a cow, produces milk
let animalToFood: ((_: Chicken) => Egg) & ((_: Cow) => Milk) =
    function (animal: any) {
        return animal.produce();
    };

Finally, the following program code demonstrates type safe use of the above definitions. 

var chicken = new Chicken();
var cow = new Cow();
var randomNumberGenerator = new RandomNumberGenerator();

console.log(chicken.produce()); // Egg { }
console.log(cow.produce()); // Milk { }
console.log(randomNumberGenerator.produce()); //0.2626353555444987

console.log(animalToFood(chicken)); // Egg { }
console.log(animalToFood(cow)); // Milk { }
//console.log(animalToFood(randomNumberGenerator)); // ERROR: Argument of type 'RandomNumberGenerator' is not assignable to parameter of type 'Cow'

console.log(eatEgg(animalToFood(chicken))); // I ate an egg.
//console.log(eatEgg(animalToFood(cow))); // ERROR: Argument of type 'Milk' is not assignable to parameter of type 'Egg'
console.log(drinkMilk(animalToFood(cow))); // I drank some milk.
//console.log(drinkMilk(animalToFood(chicken))); // ERROR: Argument of type 'Egg' is not assignable to parameter of type 'Milk'

The above program code has the following properties:

Comparison to inheritance

The above minimalist example can be realized using inheritance, for instance by deriving the classes Шаблон:TS-lang and Шаблон:TS-lang from a base class Шаблон:TS-lang. However, in a larger setting, this could be disadvantageous. Introducing new classes into a class hierarchy is not necessarily justified for cross-cutting concerns, or maybe outright impossible, for example when using an external library. Imaginably, the above example could be extended with the following classes:

This may require additional classes (or interfaces) specifying whether a produce method is available, whether the produce method returns food, and whether the produce method can be used repeatedly. Overall, this may pollute the class hierarchy.

Comparison to duck typing

The above minimalist example already shows that duck typing is less suited to realize the given scenario. While the class Шаблон:TS-lang contains a Шаблон:TS-lang method, the object Шаблон:TS-lang should not be a valid argument for Шаблон:TS-lang. The above example can be realized using duck typing, for instance by introducing a new field Шаблон:TS-lang to the classes Шаблон:TS-lang and Шаблон:TS-lang signifying that objects of corresponding type are valid arguments for Шаблон:TS-lang. However, this would not only increase the size of the respective classes (especially with the introduction of more methods similar to Шаблон:TS-lang), but is also a non-local approach with respect to Шаблон:TS-lang.

Comparison to function overloading

The above example can be realized using function overloading, for instance by implementing two methods Шаблон:TS-lang and Шаблон:TS-lang. In TypeScript, such a solution is almost identical to the provided example. Other programming languages, such as Java, require distinct implementations of the overloaded method. This may lead to either code duplication or boilerplate code.

Comparison to the visitor pattern

The above example can be realized using the visitor pattern. It would require each animal class to implement an Шаблон:TS-lang method accepting an object implementing the interface Шаблон:TS-lang (adding non-local boilerplate code). The function Шаблон:TS-lang would be realized as the Шаблон:TS-lang method of an implementation of Шаблон:TS-lang. Unfortunately, the connection between the input type (Шаблон:TS-lang or Шаблон:TS-lang) and the result type (Шаблон:TS-lang or Шаблон:TS-lang) would be difficult to represent.

Limitations

On the one hand, intersection types can be used to locally annotate different types to a function without introducing new classes (or interfaces) to the class hierarchy. On the other hand, this approach requires all possible argument types and result types to be specified explicitly. If the behavior of a function can be specified precisely by either a unified interface, parametric polymorphism, or duck typing, then the verbose nature of intersection types is unfavorable. Therefore, intersection types should be considered complementary to existing specification methods.

Dependent intersection type

A dependent intersection type, denoted <math>(x : \sigma) \cap \tau</math>, is a dependent type in which the type <math>\tau</math> may depend on the term variable <math>x</math>.[6] In particular, if a term <math>M</math> has the dependent intersection type <math>(x : \sigma) \cap \tau</math>, then the term <math>M</math> has both the type <math>\sigma</math> and the type <math>\tau[x := M]</math>, where <math>\tau[x := M]</math> is the type which results from replacing all occurrences of the term variable <math>x</math> in <math>\tau</math> by the term <math>M</math>.

Scala example

Scala supports type declarations [7] as object members. This allows a type of an object member to depend on the value of another member, which is called a path-dependent type.[8] For example, the following program text defines a Scala trait Witness, which can be used to implement the singleton pattern.[9] 

trait Witness {
  type T
  val value: T {}
}

The above trait Witness declares the member T, which can be assigned a type as its value, and the member value, which can be assigned a value of type T. The following program text defines an object booleanWitness as instance of the above trait Witness. The object booleanWitness defines the type T as Boolean and the value value as true. For example, executing System.out.println(booleanWitness.value) prints true on the console. 

object booleanWitness extends Witness {
  type T = Boolean
  val value = true
}

Let <math>\langle \textsf{x} : \sigma \rangle</math> be the type (specifically, a record type) of objects having the member <math>\textsf{x}</math> of type <math>\sigma</math>. In the above example, the object booleanWitness can be assigned the dependent intersection type <math>(x : \langle \textsf{T} : \text{Type} \rangle) \cap \langle \textsf{value} : x.\textsf{T} \rangle</math>. The reasoning is as follows. The object booleanWitness has the member T that is assigned the type Boolean as its value. Since Boolean is a type, the object booleanWitness has the type <math>\langle \textsf{T} : \text{Type} \rangle</math>. Additionally, the object booleanWitness has the member value that is assigned the value true of type Boolean. Since the value of booleanWitness.T is Boolean, the object booleanWitness has the type <math>\langle \textsf{value} : \textsf{booleanWitness.T} \rangle</math>. Overall, the object booleanWitness has the intersection type <math>\langle \textsf{T} : \text{Type} \rangle \cap \langle \textsf{value} : \textsf{booleanWitness.T} \rangle</math>. Therefore, presenting self-reference as dependency, the object booleanWitness has the dependent intersection type <math>(x : \langle \textsf{T} : \text{Type} \rangle) \cap \langle \textsf{value} : x.\textsf{T} \rangle</math>.

Alternatively, the above minimalistic example can be described using dependent record types.[10] In comparison to dependent intersection types, dependent record types constitute a strictly more specialized type theoretic concept.[6]

Intersection of a type family

An intersection of a type family, denoted <math display="inline">\bigcap_{x : \sigma} \tau</math>, is a dependent type in which the type <math>\tau</math> may depend on the term variable <math>x</math>. In particular, if a term <math>M</math> has the type <math display="inline">\bigcap_{x : \sigma} \tau</math>, then for each term <math>N</math> of type <math>\sigma</math>, the term <math>M</math> has the type <math>\tau[x := N]</math>. This notion is also called implicit Pi type,[11] observing that the argument <math>N</math> is not kept at term level.

Comparison of languages with intersection types

Language Actively developed Paradigm(s) Status Features
C# Шаблон:Yes[12] Шаблон:Maybe[13] Additionally, generic type parameters can have constraints that require their (monomorphized) type-arguments to implement multiple interfaces, whereupon the runtime type represented by the generic type parameter becomes an intersection-type of all listed interfaces.
Ceylon Шаблон:No[14] Шаблон:Yes[15]
  • Type refinement
  • Interface composition
  • Subtyping in width
F# Шаблон:Yes[16] Шаблон:Maybe[17] Шаблон:Dunno
Flow Шаблон:Yes[18] Шаблон:Yes[19]
  • Type refinement
  • Interface composition
Forsythe Шаблон:No Шаблон:Yes[20]
  • Function type intersection
  • Distributive, co- and contravariant function type subtyping
Java Шаблон:Yes[21] Шаблон:Yes[22]
  • Type refinement
  • Interface composition
  • Subtyping in width
PHP Шаблон:Yes[23] Шаблон:Yes[24]
  • Type refinement
  • Interface composition
Scala Шаблон:Yes[25] Шаблон:Yes[26][27]
  • Type refinement
  • Trait composition
  • Subtyping in width
TypeScript Шаблон:Yes[28] Шаблон:Yes[5]
  • Arbitrary type intersection
  • Interface composition
  • Subtyping in width and depth
Whiley Шаблон:Yes[29] Шаблон:Yes[30] Шаблон:Dunno

References

Шаблон:RefList

Шаблон:Data types

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite journal
  2. ↑ Шаблон:Cite book
  3. ↑ Шаблон:Cite book
  4. ↑ Шаблон:Cite journal
  5. ↑ 5,0 5,1 Шаблон:Cite web
  6. ↑ 6,0 6,1 Шаблон:Cite conference
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite book
  9. ↑ Шаблон:Cite web
  10. ↑ Шаблон:Cite conference
  11. ↑ Шаблон:Cite journal
  12. ↑ Шаблон:Cite web
  13. ↑ Шаблон:Cite web
  14. ↑ Шаблон:Cite web
  15. ↑ Шаблон:Cite web
  16. ↑ Шаблон:Cite web
  17. ↑ Шаблон:Cite web
  18. ↑ Шаблон:Cite web
  19. ↑ Шаблон:Cite web
  20. ↑ Reynolds, J. C. (1988). Preliminary design of the programming language Forsythe.
  21. ↑ Шаблон:Cite web
  22. ↑ Шаблон:Cite web
  23. ↑ Шаблон:Cite web
  24. ↑ Шаблон:Cite web
  25. ↑ Шаблон:Cite web
  26. ↑ Шаблон:Cite web
  27. ↑ Шаблон:Cite web
  28. ↑ Шаблон:Cite web
  29. ↑ Шаблон:Cite web
  30. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Intersection_type&oldid=15430773