Тип пересечения - Intersection type

В теория типов, тип перекрестка могут быть присвоены значениям, которым можно присвоить как тип ${\displaystyle \sigma }$ и тип ${\displaystyle \tau }$. Этому значению можно присвоить тип пересечения ${\displaystyle \sigma \cap \tau }$ в система типов перекрестков.^[1]Обычно, если диапазоны значений двух типов перекрываются, то значение, принадлежащее пересечение из двух диапазонов можно назначить тип пересечения этих двух типов. Такое значение можно безопасно передавать в качестве аргумента функциям, ожидающим либо двух типов. например, в Ява класс Булево реализует как Сериализуемый и Сопоставимый интерфейсы. Следовательно, объект типа Булево можно безопасно передавать функциям, ожидающим аргумент типа Сериализуемый и функциям, ожидающим аргумента типа Сопоставимый.

Типы пересечения составные типы данных. Похожий на виды продукции, они используются для присвоения объекту нескольких типов, однако типы продуктов назначаются кортежи, так что каждому элементу кортежа назначается определенный компонент типа продукта. Для сравнения, базовые объекты типов пересечения не обязательно являются составными. Ограниченная форма типов пересечений: типы уточнения.

Типы пересечений полезны для описания перегруженные функции.^[2] Например, если номер => номер - это тип функции, принимающей число в качестве аргумента и возвращающей число, и нить => нить - это тип функции, принимающей строку в качестве аргумента и возвращающей строку, то пересечение этих двух типов может использоваться для описания (перегруженных) функций, которые выполняют одно или другое, в зависимости от того, какой тип ввода им дан.

Современные языки программирования, в том числе Цейлон, Поток, Ява, Scala, Машинопись, и Пока (видеть сравнение языков с типами пересечения ), используйте типы пересечений, чтобы объединить спецификации интерфейса и выразить специальный полиморфизм.Дополнение параметрический полиморфизм типы пересечений могут использоваться, чтобы избежать загрязнения иерархии классов от сквозные проблемы и уменьшить шаблонный код, как показано на Пример TypeScript ниже.

В теоретический тип изучение типов пересечений называется дисциплина типа перекрестка.^[3]Примечательно, что завершение программы можно точно охарактеризовать с помощью типов пересечений.^[4]

Пример TypeScript

Машинопись поддерживает типы пересечений,^[5] улучшение выразительности системы типов и уменьшение размера потенциальной иерархии классов, продемонстрированное следующим образом.

Следующий программный код определяет классы Курица, Корова, и RandomNumberGenerator что у каждого есть метод производить возврат объекта любого типа Яйцо, Молоко, или же номер.Кроме того, функции есть яйцо и пить молоко требовать аргументы типа Яйцо и Молоко, соответственно.

учебный класс Яйцо { частный своего рода: "Яйцо" }учебный класс Молоко { частный своего рода: "Молоко" }// производит яйцаучебный класс Курица { производить() { возвращаться новый Яйцо(); } }// производит молокоучебный класс Корова { производить() { возвращаться новый Молоко(); } }// производит случайное числоучебный класс RandomNumberGenerator { производить() { возвращаться Математика.случайный(); } }// требуется яйцофункция есть яйцо(яйцо: Яйцо) {    возвращаться «Я съела яйцо».;}// требуется молокофункция пить молоко(молоко: Молоко) {    возвращаться «Я выпил немного молока».;}

Следующий программный код определяет ad hoc полиморфный функция AnimalToFood который вызывает функцию-член производить данного объекта животное.Функция AnimalToFood имеет два аннотации типов, а именно ((_: Курица) => Яйцо) и ((_: Корова) => Молоко), связанный через конструктор типа пересечения &.Конкретно, AnimalToFood при применении к аргументу типа Курица возвращает объект типа type Яйцо, и когда применяется к аргументу типа Корова возвращает объект типа type Молоко.В идеале, AnimalToFood не должны применяться к любому объекту, имеющему (возможно, случайно) производить метод.

// получая курицу, производит яйцо; давая корову, дает молокопозволять AnimalToFood: ((_: Курица) => Яйцо) & ((_: Корова) => Молоко) =    функция (животное: любой) {        возвращаться животное.производить();    };

Наконец, следующий программный код демонстрирует тип безопасный использование приведенных выше определений.

 1 вар курица = новый Курица(); 2 вар корова = новый Корова(); 3 вар randomNumberGenerator = новый RandomNumberGenerator(); 4  5 консоль.бревно(курица.производить()); //Яйцо { } 6 консоль.бревно(корова.производить()); //Молоко { } 7 консоль.бревно(randomNumberGenerator.производить()); //0.2626353555444987 8  9 консоль.бревно(AnimalToFood(курица)); //Яйцо { }10 консоль.бревно(AnimalToFood(корова)); //Молоко { }11 //console.log(animalToFood(randomNumberGenerator)); // ОШИБКА: аргумент типа 'RandomNumberGenerator' не может быть назначен параметру типа 'Cow'12 13 консоль.бревно(есть яйцо(AnimalToFood(курица))); // Я съел яйцо.14 //console.log(eatEgg(animalToFood(cow))); // ОШИБКА: аргумент типа 'Milk' не может быть назначен параметру типа 'Egg'15 консоль.бревно(пить молоко(AnimalToFood(корова))); // Я выпил молока.16 //console.log(drinkMilk(animalToFood(chicken))); // ОШИБКА: аргумент типа «Яйцо» не может быть назначен параметру типа «Молоко»

Приведенный выше программный код имеет следующие свойства:

• Строки 1–3 создают объекты. курица, корова, и randomNumberGenerator их соответствующего типа.
• Строки 5–7 печатают для ранее созданных объектов соответствующие результаты (предоставленные в виде комментариев) при вызове производить.
• Строка 9 (соответственно 10) демонстрирует типобезопасное использование метода. AnimalToFood применительно к курица (соотв. корова).
• Строка 11, если она не зафиксирована, приведет к ошибке типа во время компиляции. Хотя выполнение из AnimalToFood мог бы призвать производить метод randomNumberGenerator, то аннотация типа из AnimalToFood запрещает это. Это соответствует предполагаемому значению AnimalToFood.
• Строка 13 (соответственно 15) демонстрирует, что применение AnimalToFood к курица (соотв. корова) приводит к объекту типа Яйцо (соотв. Молоко).
• Строка 14 (соответственно 16) демонстрирует, что применение AnimalToFood к корова (соотв. курица) не приводит к объекту типа Яйцо (соотв. Молоко). Следовательно, если раскомментировать строку 14 (соответственно, 16), это приведет к ошибке типа во время компиляции.

Сравнение с наследованием

Приведенный выше минималистичный пример можно реализовать с помощью наследование, например, путем получения классов Курица и Корова из базового класса ЖивотноеОднако в более крупных условиях это может быть невыгодно. Введение новых классов в иерархию классов не обязательно оправдано для сквозные проблемы, а может быть, вообще невозможно, например, при использовании внешней библиотеки. Вообразимо, приведенный выше пример можно было бы расширить следующими классами:

• класс Лошадь что не имеет производить метод;
• класс Овца что есть производить метод возврата Шерсть;
• класс Свинья который имеет производить метод, который можно использовать только один раз, возвращая Мясо.

Для этого могут потребоваться дополнительные классы (или интерфейсы), указывающие, доступен ли метод создания, возвращает ли метод производства пищу и можно ли повторно использовать метод создания. В целом это может загрязнить иерархию классов.

Сравнение с утиным набором текста

Приведенный выше минималистский пример уже показывает, что утка печатать менее подходит для реализации данного сценария. RandomNumberGenerator содержит производить метод, объект randomNumberGenerator не должен быть веским аргументом в пользу AnimalToFoodПриведенный выше пример может быть реализован с использованием утиного ввода, например, путем введения нового поля аргументForAnimalToFood в классы Курица и Корова означает, что объекты соответствующего типа являются допустимыми аргументами для AnimalToFoodОднако это не только увеличило бы размер соответствующих классов (особенно с введением большего количества методов, подобных AnimalToFood), но также является нелокальным подходом по отношению к AnimalToFood.

Сравнение с перегрузкой функций

Приведенный выше пример можно реализовать с помощью перегрузка функции, например, реализовав два метода AnimalToFood(животное: Курица): Яйцо и AnimalToFood(животное: Корова): МолокоВ TypeScript такое решение практически идентично приведенному примеру. Другие языки программирования, такие как Ява, требуют различных реализаций перегруженного метода. Это может привести либо к дублирование кода или же шаблонный код.

Сравнение с шаблоном посетителя

Приведенный выше пример можно реализовать с помощью шаблон посетителя. Это потребовало бы, чтобы каждый класс животных реализовал принимать метод, принимающий объект, реализующий интерфейс ЖивотноеПосетитель (добавление нелокальных шаблонный код ).Функция AnimalToFood будет реализовано как посещение способ реализации ЖивотноеПосетительК сожалению, связь между входным типом (Курица или же Корова) и тип результата (Яйцо или же Молоко) было бы трудно представить.

Ограничения

С одной стороны, типы пересечений может использоваться для локального аннотирования различных типов функции без введения новых классов (или интерфейсов) в иерархию классов. С другой стороны, этот подход требует все возможные типы аргументов и типы результатов должны быть указаны явно.Если поведение функции может быть точно указано с помощью унифицированного интерфейса, параметрический полиморфизм, или же утка печатать, то многословный характер типов пересечений неблагоприятен, поэтому типы пересечений следует рассматривать как дополнительные к существующим методам спецификации.

Зависимый тип перекрестка

А зависимый тип перекрестка, обозначенный ${\displaystyle (x:\sigma )\cap \tau }$, это зависимый тип в котором тип ${\displaystyle \tau }$ может зависеть от термина переменной ${\displaystyle x}$.^[6]В частности, если срок ${\displaystyle M}$ имеет зависимый тип пересечения ${\displaystyle (x:\sigma )\cap \tau }$, то член ${\displaystyle M}$ имеет обе тип ${\displaystyle \sigma }$ и тип ${\displaystyle \tau [x:=M]}$, куда ${\displaystyle \tau [x:=M]}$ - это тип, который получается в результате замены всех вхождений термин переменная ${\displaystyle x}$ в ${\displaystyle \tau }$ по сроку ${\displaystyle M}$.

Пример Scala

Scala поддерживает объявления типов ^[7] как члены объекта. Это позволяет типу члена объекта зависеть от значения другого члена, который называется зависимый от пути тип.^[8]Например, следующий текст программы определяет черту Scala. Свидетель, который можно использовать для реализации одноэлементный образец.^[9]

черта Свидетель {  тип Т  вал ценить: Т {}}

Вышеупомянутая черта Свидетель объявляет член Т, которому можно присвоить тип как его значение, а член ценить, которому может быть присвоено значение типа Т. Следующий текст программы определяет объект booleanWitness как пример вышеупомянутой черты Свидетель.Предмет booleanWitness определяет тип Т в качестве Булево и ценность ценить в качестве истинный. Например, выполнение Система.из.println(booleanWitness.ценить) отпечатки истинный на консоли.

объект booleanWitness расширяет Свидетель {  тип Т = Булево  вал ценить = истинный}

Позволять ${\displaystyle \langle {\textsf {x}}:\sigma \rangle }$ быть типом (в частности, тип записи ) объектов, имеющих член ${\displaystyle {\textsf {x}}}$ типа ${\displaystyle \sigma }$. В приведенном выше примере объект booleanWitness может быть назначен зависимый тип пересечения ${\displaystyle (x:\langle {\textsf {T}}:{\text{Type}}\rangle )\cap \langle {\textsf {value}}:x.{\textsf {T}}\rangle }$Рассуждения заключаются в следующем. Предмет booleanWitness есть член Т которому присвоен тип Булево как его ценность. Булево это тип, объект booleanWitness имеет тип ${\displaystyle \langle {\textsf {T}}:{\text{Type}}\rangle }$.Кроме того, объект booleanWitness есть член ценить которому присвоено значение истинный типа Булево.Поскольку ценность booleanWitness.Т является Булево, предмет booleanWitness имеет тип ${\displaystyle \langle {\textsf {value}}:{\textsf {booleanWitness.T}}\rangle }$.В целом объект booleanWitness имеет тип пересечения ${\displaystyle \langle {\textsf {T}}:{\text{Type}}\rangle \cap \langle {\textsf {value}}:{\textsf {booleanWitness.T}}\rangle }$.Поэтому, представляя самосылку как зависимость, объект booleanWitness имеет зависимый тип пересечения ${\displaystyle (x:\langle {\textsf {T}}:{\text{Type}}\rangle )\cap \langle {\textsf {value}}:x.{\textsf {T}}\rangle }$.

В качестве альтернативы приведенный выше минималистичный пример можно описать с помощью зависимые типы записей.^[10]По сравнению с зависимыми типами пересечений, зависимые типы записей представляют собой строго более специализированную концепцию теории типов.^[6]

Пересечение типовой семьи

An пересечение семейства типов, обозначенный ${\displaystyle \bigcap _{x:\sigma }\tau }$, это зависимый тип в котором тип ${\displaystyle \tau }$ может зависеть от термина переменной ${\displaystyle x}$.^[6]В частности, если срок ${\displaystyle M}$ имеет тип ${\displaystyle \bigcap _{x:\sigma }\tau }$, то для каждый срок ${\displaystyle N}$ типа ${\displaystyle \sigma }$, период, термин ${\displaystyle M}$ имеет тип ${\displaystyle \tau [x:=N]}$Это понятие также называют скрытый Тип Пи,^[11] отмечая, что аргумент ${\displaystyle N}$ не сохраняется на уровне семестра.

Сравнение языков с типами пересечения

Язык	Активно развивается	Парадигма (ы)	Положение дел	Функции
C #	да[12]	Функциональный Императив Объектно-ориентированный	Под обсуждением[13]	?
Цейлон	да[14]	Объектно-ориентированный	Поддерживается[15]	Уточнение типа Состав интерфейса Подтип по ширине
F #	да[16]	Функциональный Императив Объектно-ориентированный	Под обсуждением[17]	?
Поток	да[18]	Функциональный Императив Объектно-ориентированный Сценарии	Поддерживается[19]	Уточнение типа Состав интерфейса
Форсайт	Нет	Императив	Поддерживается[20]	Пересечение типов функций Распределительное, ко- и контравариантное определение подтипов функций
Ява	да[21]	Императив Объектно-ориентированный	Поддерживается[22]	Уточнение типа Состав интерфейса Подтип по ширине
Scala	да[23]	Функциональный Императив Объектно-ориентированный	Поддерживается[24][25]	Уточнение типа Состав черт Подтип по ширине
Машинопись	да[26]	Функциональный Императив Объектно-ориентированный Сценарии	Поддерживается[5]	Пересечение произвольного типа Состав интерфейса Подтип по ширине и глубине
Пока	да[27]	Функциональный Императив	Поддерживается[28]	?

Рекомендации

1. Барендрегт, Хенк; Коппо, Марио; Дезани-Чианкаглини, Мариангиола (1983). «Лямбда-модель фильтра и полнота присвоения типов». Журнал символической логики. 48 (4): 931–940. Дои:10.2307/2273659. JSTOR  2273659.
2. Палсберг, Йенс (2012). «Перегрузка NP-Complete». Логика и семантика программы. Конспект лекций по информатике. 7230. С. 204–218. Дои:10.1007/978-3-642-29485-3_13. ISBN  978-3-642-29484-6.
3. Хенк Барендрегт; Вил Деккерс; Ричард Статман (20 июня 2013 г.). Лямбда-исчисление с типами. Издательство Кембриджского университета. стр. 1–. ISBN  978-0-521-76614-2.
4. Гилезан, Сильвия (1996). «Сильная нормализация и типизация с типами пересечений». Журнал формальной логики Нотр-Дам. 37 (1): 44–52. Дои:10.1305 / ndjfl / 1040067315.
5. «Типы пересечений в TypeScript». Получено 2019-08-01.
6. Копылов, Алексей (2003). «Зависимое пересечение: новый способ определения записей в теории типов». 18-й симпозиум IEEE по логике в компьютерных науках. LICS 2003. Компьютерное общество IEEE. С. 86–95. CiteSeerX  10.1.1.89.4223. Дои:10.1109 / LICS.2003.1210048.
7. «Объявления типов в Scala». Получено 2019-08-15.
8. Амин, Нада; Грюттер, Самуэль; Одерский, Мартин; Rompf, Tiark; Штуки, Сандро (2016). «Сущность зависимых типов объектов». Список успехов, которые могут изменить мир - эссе, посвященные Филиппу Вадлеру по случаю его 60-летия. Конспект лекций по информатике. 9600. Springer. С. 249–272. Дои:10.1007/978-3-319-30936-1_14.
9. «Синглтоны в бесформенной библиотеке Scala». Получено 2019-08-15.
10. Поллак, Роберт (2000). «Зависимо типизированные записи для представления математической структуры». Доказательство теорем в логиках высокого порядка, 13-я Международная конференция. TPHOLs 2000. Springer. С. 462–479. Дои:10.1007/3-540-44659-1_29.
11. Пень, Аарон (2018). «От реализуемости к индукции через зависимое пересечение». Анналы чистой и прикладной логики. 169 (7): 637–655. Дои:10.1016 / j.apal.2018.03.002.
12. «Руководство по C #». Получено 2019-08-08.
13. «Обсуждение: типы Union и Intersection в C Sharp». Получено 2019-08-08.
14. "Eclipse Ceylon: Добро пожаловать на Цейлон". Получено 2019-08-08.
15. «Типы пересечений на Цейлоне». Получено 2019-08-08.
16. «Фонд программного обеспечения F #». Получено 2019-08-08.
17. "Добавить типы пересечений к F Sharp". Получено 2019-08-08.
18. "Flow: средство проверки статического типа для JavaScript". Получено 2019-08-08.
19. «Синтаксис типа пересечения в потоке». Получено 2019-08-08.
20. Рейнольдс, Дж. К. (1988). Эскизный проект языка программирования Forsythe.
21. «Программное обеспечение Java». Получено 2019-08-08.
22. "IntersectionType (Java SE 12 и JDK 12)". Получено 2019-08-01.
23. «Язык программирования Scala». Получено 2019-08-08.
24. «Составные типы в Scala». Получено 2019-08-01.
25. «Типы пересечений в точках». Получено 2019-08-01.
26. «TypeScript - масштабируемый JavaScript». Получено 2019-08-01.
27. «В то время как: язык программирования с открытым исходным кодом с расширенной статической проверкой». Получено 2019-08-01.
28. "Спецификация языка Whyy" (PDF). Получено 2019-08-01.