Ковариантность и контравариантность (информатика)

Многие системы типов языков программирования поддерживают подтипирование . Например, если тип является подтипом , то выражение типа должно быть заменяемым везде, где используется выражение типа . CatAnimalCat Animal

Дисперсия — это то, как подтипирование между более сложными типами соотносится с подтипированием между их компонентами. Например, как список s должен Catсоотноситься со списком Animals? Или как функция, которая возвращает, Cat должна соотноситься с функцией, которая возвращает Animal?

В зависимости от дисперсии конструктора типа отношение подтипирования простых типов может быть либо сохранено, либо обращено, либо проигнорировано для соответствующих сложных типов. Например, в языке программирования OCaml "список Cat" является подтипом "списка Animal", поскольку конструктор типа списка является ковариантным . Это означает, что отношение подтипирования простых типов сохраняется для сложных типов.

С другой стороны, "функция от Animal до String" является подтипом "функции от Cat до String", поскольку конструктор типа функции контравариантен в типе параметра . Здесь отношение подтипирования простых типов меняется на противоположное для сложных типов.

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

Чтобы сохранить простоту системы типов и позволить создавать полезные программы, язык может рассматривать конструктор типа как инвариантный, даже если можно было бы безопасно считать его вариантным, или рассматривать его как ковариантный, даже если это может нарушить безопасность типов.

Формальное определение

Предположим, Aчто и Bявляются типами, а I<U>обозначает применение конструктора типа I с аргументом типа U. В системе типов языка программирования правило типизации для конструктора типа Iследующее:

ковариантным , если он сохраняет порядок типов (≤) , который упорядочивает типы от более конкретных к более общим: Если A ≤ B, то I<A> ≤ I<B>;
контравариантным, если он меняет этот порядок на противоположный: Если A ≤ B, то I<B> ≤ I<A>;
бивариантный , если оба из них применимы (т.е. если A ≤ B, то I<A> ≡ I<B>); ^[1]
вариант, если он ковариантный, контравариантный или бивариантный;
инвариантный или невариантный, если не вариантный.

В статье рассматривается, как это применимо к некоторым распространенным конструкторам типов.

Примеры на C#

Например, в C# , если Catявляется подтипом Animal, то:

IEnumerable<Cat>является подтипом . Подтипирование сохраняется, поскольку является ковариантным по .IEnumerable<Animal>IEnumerable<T>T
Action<Animal>является подтипом . Подтипирование является обратным, поскольку является контравариантным для .Action<Cat>Action<T>T
Ни один из них не является подтипом другого, поскольку инвариантен относительно .IList<Cat>IList<Animal>IList<T>T

Дисперсия универсального интерфейса C# объявляется путем помещения атрибута out(ковариантный) или in(контравариантный) в (ноль или более) его параметров типа. ^[2]^{: 144} Вышеуказанные интерфейсы объявляются как , , и . Типы с более чем одним параметром типа могут указывать различные дисперсии для каждого параметра типа. Например, тип делегата представляет функцию с контравариантным входным параметром типа и ковариантным возвращаемым значением типа . ^[3]^[2]^{: 145} Компилятор проверяет, что все типы определены и используются в соответствии с их аннотациями, и в противном случае сигнализирует об ошибке компиляции.IEnumerable<out T>Action<in T>IList<T>Func<in T, out TResult>TTResult

Правила типизации для вариативности интерфейса обеспечивают безопасность типов. Например, an представляет функцию первого класса, ожидающую аргумент типа , ^[2]^{: 144} и функция, которая может обрабатывать любой тип животных, всегда может быть использована вместо функции, которая может обрабатывать только кошек.Action<T>T

Массивы

Типы данных только для чтения (источники) могут быть ковариантными; типы данных только для записи (приемники) могут быть контравариантными. Изменяемые типы данных, которые действуют как источники и приемники, должны быть инвариантными. Чтобы проиллюстрировать это общее явление, рассмотрим тип массива . Для типа Animalмы можем создать тип , который является «массивом животных». Для целей этого примера этот массив поддерживает как чтение, так и запись элементов.Animal[]

У нас есть возможность рассматривать это как:

ковариант: a — это ;Cat[]Animal[]
контравариант: an есть a ;Animal[]Cat[]
инвариант: an не является a и a не является an .Animal[]Cat[]Cat[]Animal[]

Если мы хотим избежать ошибок типа, то только третий вариант безопасен. Очевидно, что не каждый может рассматриваться как , поскольку клиент, читающий из массива, будет ожидать , но может содержать , например . Так что контравариантное правило небезопасно.Animal[]Cat[]CatAnimal[]Dog

И наоборот, a нельзя рассматривать как . Всегда должно быть возможно поместить a в . С ковариантными массивами это не может быть гарантированно безопасным, поскольку резервное хранилище может быть фактически массивом кошек. Поэтому ковариантное правило также небезопасно — конструктор массива должен быть инвариантным . Обратите внимание, что это проблема только для изменяемых массивов; ковариантное правило безопасно для неизменяемых (только для чтения) массивов. Аналогично, контравариантное правило было бы безопасным для массивов только для записи.Cat[]Animal[]DogAnimal[]

Ковариантные массивы в Java и C#

Ранние версии Java и C# не включали дженерики, также называемые параметрическим полиморфизмом . В таких условиях создание инвариантных массивов исключает полезные полиморфные программы.

Например, рассмотрим написание функции для перемешивания массива или функции, которая проверяет два массива на равенство, используя метод Object. equalsдля элементов. Реализация не зависит от точного типа элемента, хранящегося в массиве, поэтому должно быть возможно написать одну функцию, которая работает со всеми типами массивов. Легко реализовать функции типа:

boolean equalArrays ( Объект [] a1 , Объект [] a2 ); void shuffleArray ( Объект [] a );

Однако если бы типы массивов рассматривались как инвариантные, то было бы возможно вызывать эти функции только для массива точно такого типа . Например, нельзя было бы перетасовать массив строк.Object[]

Поэтому и Java, и C# обрабатывают типы массивов ковариантно. Например, в Java является подтипом , а в C# является подтипом .String[]Object[]string[]object[]

Как обсуждалось выше, ковариантные массивы приводят к проблемам с записью в массив. Java ^[4]^{: 126} и C# решают эту проблему, помечая каждый объект массива типом при его создании. Каждый раз, когда значение сохраняется в массиве, среда выполнения проверяет, что тип времени выполнения значения равен типу времени выполнения массива. Если есть несоответствие, выдается ArrayStoreException(Java) ^[4]^{: 126} или ArrayTypeMismatchException(C#):

// a — это одноэлементный массив строк String [ ] a = new String [ 1 ] ;    // b — массив объектов Object [ ] b = a ;   // Присвоить целое число b. Это было бы возможно, если бы b действительно был // массивом Object, но поскольку это действительно массив String, // мы получим java.lang.ArrayStoreException. b [ 0 ] = 1 ;

В приведенном выше примере можно безопасно читать из массива (b). Только попытка записи в массив может привести к проблемам.

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

С добавлением дженериков Java ^[4]^{: 126–129} и C# теперь предлагают способы записи такого рода полиморфных функций без опоры на ковариацию. Функциям сравнения массивов и тасования можно задать параметризованные типы

< T > boolean equalArrays ( T [] a1 , T [] a2 ); < T > void shuffleArray ( T [] a );

В качестве альтернативы, чтобы обеспечить доступ метода C# к коллекции только для чтения, можно использовать интерфейс вместо передачи ему массива .IEnumerable<object>object[]

Типы функций

Языки с функциями первого класса имеют типы функций , такие как «функция, ожидающая Cat и возвращающая Animal» (написанные в синтаксисе OCaml или в синтаксисе C# ).cat -> animalFunc<Cat,Animal>

Эти языки также должны указывать, когда один тип функции является подтипом другого, то есть когда безопасно использовать функцию одного типа в контексте, который ожидает функцию другого типа. Безопасно заменить функцию g функцией f , если f принимает более общий тип аргумента и возвращает более конкретный тип, чем g . Например, функции типа , , и могут использоваться везде, где ожидалось a . (Можно сравнить это с принципом надежности коммуникации: «будьте либеральны в том, что вы принимаете, и консервативны в том, что вы производите».) Общее правило таково:animal -> catcat -> catanimal -> animalcat -> animal

(P_{1}\rightarrow R_{1})\leq (P_{2}\rightarrow R_{2})

если и .

P_{1}\geq P_{2}

R_{1}\leq R_{2}

Используя обозначение правила вывода, то же самое правило можно записать так:

{\frac {P_{1}\geq P_{2}\quad R_{1}\leq R_{2}}{(P_{1}\rightarrow R_{1})\leq (P_{2}\rightarrow R_{2})}}

Другими словами, конструктор типа → контравариантен по типу параметра (входа) и ковариантен по типу возврата (выхода) . Это правило было впервые формально сформулировано Джоном К. Рейнольдсом [ ^5] и далее популяризировано в статье Луки Карделли ^[6] .

При работе с функциями, которые принимают функции в качестве аргументов , это правило можно применять несколько раз. Например, применяя правило дважды, мы видим, что если . Другими словами, тип ковариантен в позиции . Для сложных типов может быть сложно мысленно проследить, почему данная специализация типа является или не является типобезопасной, но легко вычислить, какие позиции являются ко- и контравариантными : позиция ковариантна, если она находится слева от четного числа стрелок, применяемых к ней. $((P_{1}\to R)\to R)\leq ((P_{2}\to R)\to R)$ $P_{1}\leq P_{2}$ $((A\to B)\to C)$ $A$

Наследование в объектно-ориентированных языках

Когда подкласс переопределяет метод в суперклассе, компилятор должен проверить, что переопределяющий метод имеет правильный тип. Хотя некоторые языки требуют, чтобы тип точно соответствовал типу в суперклассе (инвариантность), также безопасно с точки зрения типа разрешить переопределяющему методу иметь "лучший" тип. Согласно обычному правилу подтипирования для типов функций, это означает, что переопределяющий метод должен возвращать более конкретный тип (ковариантность возвращаемого типа) и принимать более общий аргумент (контравариантность типа параметра). В нотации UML возможности следующие (где Class B является подклассом, который расширяет Class A, который является суперклассом):

Дисперсия и переопределение метода: обзор
Подтипирование типа параметра/возвращаемого значения метода.
Инвариантность . Сигнатура переопределяющего метода неизменна.
Ковариантный возвращаемый тип . Отношение подтипирования имеет то же направление, что и отношение между ClassA и ClassB.
Контравариантный тип параметра . Отношение подтипирования находится в противоположном направлении к отношению между ClassA и ClassB.
Ковариантный тип параметра . Не типобезопасен.

Для конкретного примера предположим, что мы пишем класс для моделирования приюта для животных . Мы предполагаем, что Catэто подкласс Animal, и что у нас есть базовый класс (используя синтаксис Java)

класс  Приют для животных {  Animal getAnimalForAdoption () { // ... } void putAnimal ( Animal Animal ) { //... } }

Теперь вопрос: если мы создадим подкласс AnimalShelter, какие типы нам разрешено присваивать getAnimalForAdoptionи putAnimal?

Ковариантный метод возвращает тип

В языке, который допускает ковариантные типы возвращаемых данных , производный класс может переопределить getAnimalForAdoptionметод для возврата более конкретного типа:

класс  CatShelter расширяет AnimalShelter {    Cat getAnimalForAdoption () { return new Cat (); } }

Среди основных ОО-языков Java , C++ и C# (начиная с версии 9.0 ^[7] ) поддерживают ковариантные возвращаемые типы. Добавление ковариантного возвращаемого типа было одной из первых модификаций языка C++, одобренных комитетом по стандартам в 1998 году. ^[8] Scala и D также поддерживают ковариантные возвращаемые типы.

Контравариантный метод параметрического типа

Аналогично, безопасно с точки зрения типа разрешить переопределяющему методу принимать более общий аргумент, чем метод в базовом классе:

класс  CatShelter расширяет AnimalShelter { void putAnimal ( Object animal ) { // ... } }

Только несколько объектно-ориентированных языков на самом деле позволяют это (например, Python при проверке типов с помощью mypy). C++, Java и большинство других языков, поддерживающих перегрузку и/или затенение, интерпретировали бы это как метод с перегруженным или затененным именем.

Однако Sather поддерживал как ковариантность, так и контравариантность. Соглашение о вызовах для переопределенных методов ковариантно с параметрами out и возвращаемыми значениями и контравариантно с нормальными параметрами (с режимом в ).

Тип параметра ковариантного метода

Пара основных языков, Eiffel и Dart ^[9], позволяют параметрам переопределяющего метода иметь более конкретный тип, чем метод в суперклассе (ковариация типа параметра). Таким образом, следующий код Dart будет проверять тип, putAnimalпереопределяя метод в базовом классе:

класс CatShelter расширяет AnimalShelter {     void putAnimal ( ковариантное животное Cat ) { // ... } }

Это небезопасно с точки зрения типа. Приведя a CatShelterк an AnimalShelter, можно попытаться поместить собаку в приют для кошек. Это не соответствует CatShelterограничениям параметров и приведет к ошибке времени выполнения. Отсутствие безопасности типов (известное как «проблема catcall» в сообществе Eiffel, где «cat» или «CAT» — это измененная доступность или тип) является давней проблемой. На протяжении многих лет для ее исправления предлагались различные комбинации глобального статического анализа, локального статического анализа и новых языковых возможностей ^[10]^[11], и они были реализованы в некоторых компиляторах Eiffel.

Несмотря на проблему безопасности типов, разработчики Eiffel считают ковариантные типы параметров критически важными для моделирования требований реального мира. ^[11] Приют для кошек иллюстрирует распространенное явление: это своего рода приют для животных, но с дополнительными ограничениями , и кажется разумным использовать наследование и ограниченные типы параметров для его моделирования. Предлагая такое использование наследования, разработчики Eiffel отвергают принцип подстановки Лисков , который гласит, что объекты подклассов всегда должны быть менее ограниченными, чем объекты их суперкласса.

Еще один пример основного языка, допускающего ковариацию в параметрах методов, — это PHP в отношении конструкторов классов. В следующем примере метод __construct() принимается, несмотря на то, что параметр метода ковариантен параметру родительского метода. Если бы этот метод был чем-то иным, чем __construct(), возникла бы ошибка:

интерфейс  AnimalInterface  {}интерфейс  DogInterface  расширяет  AnimalInterface  {}класс  Dog  реализует  DogInterface  {}класс  Pet {  public  function  __construct ( AnimalInterface  $animal )  {} }класс  PetDog  расширяет  Pet {  public  function  __construct ( DogInterface  $dog )  {  parent :: __construct ( $dog );  } }

Другим примером, где ковариантные параметры кажутся полезными, являются так называемые бинарные методы, т. е. методы, где ожидается, что параметр будет того же типа, что и объект, для которого вызывается метод. Примером является compareToметод: проверяет, находится ли до или после в некотором порядке, но способ сравнения, скажем, двух рациональных чисел будет отличаться от способа сравнения двух строк. Другие распространенные примеры бинарных методов включают проверки равенства, арифметические операции и операции над множествами, такие как подмножество и объединение.a.compareTo(b)ab

В старых версиях Java метод сравнения был указан как интерфейс Comparable:

интерфейс  Сопоставимый {  int compareTo ( Объект o ); }

Недостатком этого является то, что метод указан для приема аргумента типа Object. Типичная реализация сначала приведет этот аргумент к нижнему типу (выдавая ошибку, если он не соответствует ожидаемому типу):

class  RationalNumber implements Comparable { int numerator ; int denominator ; // ... public int compareTo ( Object other ) { RationalNumber otherNum = ( RationalNumber ) other ; return Integer.comparable ( numerator * otherNum .denominator , otherNum . numerator * denominator ) ; } }

В языке с ковариантными параметрами аргументу to compareToможно было бы напрямую задать желаемый тип RationalNumber, скрывая приведение типа. (Конечно, это все равно привело бы к ошибке времени выполнения, если бы compareToзатем был вызван, например, для a String.)

Избегание необходимости использования ковариантных типов параметров

Другие возможности языка могут обеспечить очевидные преимущества ковариантных параметров, сохраняя при этом заменяемость Лисков.

В языке с дженериками (он же параметрический полиморфизм ) и ограниченной квантификацией предыдущие примеры можно записать безопасным с точки зрения типов способом. ^[12] Вместо определения AnimalShelterмы определяем параметризованный класс . (Одним из недостатков этого является то, что реализатор базового класса должен предвидеть, какие типы необходимо будет специализировать в подклассах.)Shelter<T>

класс  Shelter < T расширяет Animal > {    Т getAnimalForAdoption () { // ... }     void putAnimal ( T животное ) { // ... } }      класс  CatShelter расширяет Shelter < Cat > {    Кошка getAnimalForAdoption () { // ... }     void putAnimal ( Животное -кошка ) { // ... } }

Аналогично, в последних версиях Java Comparableинтерфейс был параметризован, что позволяет опускать приведение типов безопасным для типов способом:

класс  RationalNumber реализует Comparable < RationalNumber > {    int числитель ; int знаменатель ; // ... public int compareTo ( RationalNumber otherNum ) { return Integer.compar ( numberator * otherNum.denominator , otherNum . numerator * denominator ) ; } }

Другая функция языка, которая может помочь, — это множественная диспетчеризация . Одна из причин, по которой бинарные методы неудобно писать, заключается в том, что в вызове типа , выбор правильной реализации действительно зависит от типа выполнения как и , но в традиционном ОО-языке учитывается только тип выполнения . В языке с множественной диспетчеризацией в стиле Common Lisp Object System (CLOS) метод сравнения можно записать как универсальную функцию, где оба аргумента используются для выбора метода.a.compareTo(b)compareToaba

Джузеппе Кастанья ^[13] заметил, что в типизированном языке с множественной диспетчеризацией универсальная функция может иметь некоторые параметры, которые управляют диспетчеризацией, и некоторые «оставшиеся» параметры, которые не управляют. Поскольку правило выбора метода выбирает наиболее конкретный применимый метод, если метод переопределяет другой метод, то переопределяющий метод будет иметь более конкретные типы для управляющих параметров. С другой стороны, для обеспечения безопасности типов язык все равно должен требовать, чтобы оставшиеся параметры были по крайней мере такими же общими. Используя предыдущую терминологию, типы, используемые для выбора метода во время выполнения, являются ковариантными, в то время как типы, не используемые для выбора метода во время выполнения метода, являются контравариантными. Обычные языки с одной диспетчеризацией, такие как Java, также подчиняются этому правилу: для выбора метода используется только один аргумент (объект-получатель, переданный методу в качестве скрытого аргумента this), и действительно, тип thisболее специализирован внутри переопределяющих методов, чем в суперклассе.

Кастанья предполагает, что примеры, где ковариантные типы параметров превосходят (в частности, бинарные методы), следует обрабатывать с использованием множественной диспетчеризации; которая является естественно ковариантной. Однако большинство языков программирования не поддерживают множественную диспетчеризацию.

Резюме дисперсии и наследования

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

Общие типы

В языках программирования, которые поддерживают generics (также известные как параметрический полиморфизм ), программист может расширить систему типов новыми конструкторами. Например, интерфейс C#, например, позволяет создавать новые типы, например или . Тогда возникает вопрос, какова должна быть дисперсия этих конструкторов типов.IList<T>IList<Animal>IList<Cat>

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

Аннотации дисперсии декларации-сайта

Наиболее популярными языками с аннотациями вариативности на месте объявления являются C# и Kotlin (использующие ключевые слова outи in), а также Scala и OCaml (использующие ключевые слова +и -). C# допускает аннотации вариативности только для типов интерфейсов, тогда как Kotlin, Scala и OCaml допускают их как для типов интерфейсов, так и для конкретных типов данных.

Интерфейсы

В C# каждый параметр типа универсального интерфейса может быть помечен как ковариантный ( out), контравариантный ( in) или инвариантный (без аннотации). Например, мы можем определить интерфейс итераторов только для чтения и объявить его ковариантным (out) в его параметре типа.IEnumerator<T>

интерфейс IEnumerator < out T > { T Current { get ; } bool MoveNext (); }

При таком объявлении IEnumeratorбудет рассматриваться как ковариантный по своему параметру типа, например, является подтипом .IEnumerator<Cat>IEnumerator<Animal>

Проверка типов обеспечивает, чтобы каждое объявление метода в интерфейсе упоминало параметры типа только способом, соответствующим аннотациям in/ out. То есть параметр, который был объявлен ковариантным, не должен встречаться ни в одной контравариантной позиции (где позиция контравариантна, если она встречается под нечетным числом контравариантных конструкторов типов). Точное правило ^[14]^[15] заключается в том, что возвращаемые типы всех методов в интерфейсе должны быть допустимы ковариантно , а все типы параметров метода должны быть допустимы контравариантно , где допустимый S-ly определяется следующим образом:

Неуниверсальные типы (классы, структуры, перечисления и т. д.) допустимы как ко-, так и контравариантно.
Параметр типа Tявляется ковариантно допустимым, если он не был отмечен in, и контрвариантно допустимым, если он не был отмечен out.
Тип массива является допустимым S-ly, если является. (Это связано с тем, что в C# есть ковариантные массивы.)A[]A
Универсальный тип является допустимым S-ly, если для каждого параметра ,G<A1, A2, ..., An>Ai
- Ai является допустимым S-ly, а i- й параметр to Gобъявлен ковариантным, или
- Ai является допустимым (не S)-ly, а i- й параметр to Gобъявлен контравариантным, или
- Ai действителен как ковариантно, так и контравариантно, а i -й параметр to Gобъявлен инвариантным.

В качестве примера того, как применяются эти правила, рассмотрим интерфейс. IList<T>

интерфейс IList < T > { void Insert ( int index , T item ); IEnumerator < T > GetEnumerator (); }

Тип параметра Tдолжен Insertбыть допустимым контравариантно, т. е. параметр типа Tне должен быть помечен out. Аналогично, тип результата должен быть допустимым ковариантно, т. е. (поскольку является ковариантным интерфейсом), тип должен быть допустимым ковариантно, т. е. параметр типа не должен быть помечен . Это показывает, что интерфейс не может быть помечен ни как ко-, ни как контравариантный.IEnumerator<T>GetEnumeratorIEnumeratorTTinIList

В общем случае общей структуры данных, такой как IList, эти ограничения означают, что outпараметр может использоваться только для методов, извлекающих данные из структуры, и inпараметр может использоваться только для методов, помещающих данные в структуру, отсюда и выбор ключевых слов.

Данные

C# допускает аннотации вариативности для параметров интерфейсов, но не для параметров классов. Поскольку поля в классах C# всегда изменяемы, параметризованные с вариантами классы в C# не были бы очень полезны. Но языки, которые делают акцент на неизменяемых данных, могут хорошо использовать ковариантные типы данных. Например, во всех Scala , Kotlin и OCaml неизменяемый тип списка является ковариантным: является подтипом .List[Cat]List[Animal]

Правила Scala для проверки аннотаций дисперсии по сути такие же, как и в C#. Однако есть некоторые идиомы, которые применяются, в частности, к неизменяемым структурам данных. Они проиллюстрированы следующим (выдержкой из) определением класса .List[A]

запечатанный абстрактный класс List [ + A ] расширяет AbstractSeq [ A ] { def head : A def tail : List [ A ]             /** Добавляет элемент в начало этого списка. */ def :: [ B >: A ] ( x : B ): List [ B ] = new scala . collection . immutable . :: ( x , this ) /** ... */ }

Во-первых, члены класса, имеющие вариантный тип, должны быть неизменяемыми. Здесь headимеет тип A, который был объявлен ковариантным ( +), и действительно headбыл объявлен как метод ( def). Попытка объявить его как изменяемое поле ( var) будет отклонена как ошибка типа.

Во-вторых, даже если структура данных неизменяема, она часто будет иметь методы, где тип параметра встречается контравариантно. Например, рассмотрим метод ::, который добавляет элемент в начало списка. (Реализация работает путем создания нового объекта класса с похожим названием , :: класса непустых списков.) Наиболее очевидным типом для него будет

def :: ( x : A ): Список [ A ]

Однако это будет ошибкой типа, поскольку ковариантный параметр Aпоявляется в контравариантной позиции (как параметр функции). Но есть трюк, чтобы обойти эту проблему. Мы даем ::более общий тип, который позволяет добавлять элемент любого типа, B если только Bявляется супертипом A. Обратите внимание, что это зависит от Listковариантности, поскольку this имеет тип , и мы рассматриваем его как имеющий тип . На первый взгляд может быть неочевидно, что обобщенный тип является правильным, но если программист начнет с более простого объявления типа, ошибки типа укажут место, которое необходимо обобщить.List[A]List[B]

Вывод дисперсии

Можно разработать систему типов, в которой компилятор автоматически выводит наилучшие возможные аннотации дисперсии для всех параметров типов данных. ^[16] Однако анализ может стать сложным по нескольким причинам. Во-первых, анализ нелокален, поскольку дисперсия интерфейса Iзависит от дисперсии всех интерфейсов, которые Iупоминаются. Во-вторых, для получения уникальных наилучших решений система типов должна допускать бивариантные параметры (которые одновременно являются ко- и контрвариантными). И, наконец, дисперсия параметров типа, вероятно, должна быть преднамеренным выбором проектировщика интерфейса, а не чем-то, что просто происходит.

По этим причинам ^[17] большинство языков делают очень мало выводов дисперсии. C# и Scala вообще не выводят никаких аннотаций дисперсии. OCaml может выводить дисперсию параметризованных конкретных типов данных, но программист должен явно указать дисперсию абстрактных типов (интерфейсов).

Например, рассмотрим тип данных OCaml, Tкоторый оборачивает функцию

тип  ( ' а ,  ' б )  t  =  T  из  ( ' а  ->  ' б )

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

тип  (- ' a ,  + ' b )  t  =  T  из  ( ' a  ->  ' b )

Явные аннотации в OCaml становятся полезными при указании интерфейсов. Например, стандартный интерфейс библиотеки для таблиц ассоциаций включает аннотацию, говорящую о том, что конструктор типа карты является ковариантным в типе результата.Map.S

 тип  модуля S  =  тип sig  тип  ключа  (+ ' a ) t значение пусто : ' a t значение mem : ключ -> ' a t -> bool ... конец

Это гарантирует, что eg является подтипом .cat IntMap.tanimal IntMap.t

Аннотации дисперсии использования на месте (подстановочные знаки)

Одним из недостатков подхода с декларацией на месте является то, что многие типы интерфейсов должны быть сделаны инвариантными. Например, мы видели выше, что IListнеобходимо было сделать инвариантным, поскольку он содержал Insertи GetEnumerator. Чтобы раскрыть больше вариативности, разработчик API мог бы предоставить дополнительные интерфейсы, которые предоставляют подмножества доступных методов (например, «список только для вставки», который предоставляет только Insert). Однако это быстро становится громоздким.

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

Java предоставляет аннотации вариативности места использования через подстановочные знаки , ограниченную форму ограниченных экзистенциальных типов . Параметризованный тип может быть создан с помощью подстановочного знака ?вместе с верхней или нижней границей, например или . Неограниченный подстановочный знак типа эквивалентен . Такой тип представляет для некоторого неизвестного типа , который удовлетворяет границе. ^[4]^{: 139} Например, если имеет тип , то средство проверки типов приметList<? extends Animal>List<? super Animal>List<?>List<? extends Object>List<X>XlList<? extends Animal>

Животное а = л . получить ( 3 );

поскольку известно, что тип Xявляется подтипом Animal, но

л . добавить ( новое животное ());

будет отклонен как ошибка типа, поскольку an Animalне обязательно является X. В общем случае, если задан некоторый интерфейс , ссылка на an запрещает использование методов из интерфейса , где встречается контравариантно в типе метода. И наоборот, если бы был тип , можно было бы вызвать , но не .I<T>I<? extends T>TlList<? super Animal>l.addl.get

В то время как не-wildcard параметризованные типы в Java являются инвариантными (например, нет отношения подтипирования между и ), wildcard типы могут быть сделаны более конкретными, указав более узкую границу. Например, является подтипом . Это показывает, что wildcard типы ковариантны в своих верхних границах (и также контравариантны в своих нижних границах ). Всего, учитывая wildcard тип, такой как , есть три способа сформировать подтип: специализировав класс , указав более узкую границу или заменив wildcard определенным типом (см. рисунок). ^[4]^{: 139}List<Cat>List<Animal>List<? extends Cat>List<? extends Animal>C<? extends T>CT?

Применяя две из трех вышеупомянутых форм подтипирования, становится возможным, например, передать аргумент типа методу, ожидающему . Это вид выразительности, который является результатом ковариантных типов интерфейса. Тип действует как тип интерфейса, содержащий только ковариантные методы , но реализатору не нужно было определять его заранее.List<Cat>List<? extends Animal>List<? extends Animal>List<T>List<T>

В общем случае обобщенной структуры данных IListковариантные параметры используются для методов, извлекающих данные из структуры, а контравариантные параметры — для методов, помещающих данные в структуру. Мнемоника для Producer Extends, Consumer Super (PECS) из книги Effective Java Джошуа Блоха дает простой способ запомнить, когда использовать ковариантность и контравариантность. ^[4]^{: 141}

Подстановочные знаки гибки, но есть и недостаток. Хотя дисперсия на месте использования означает, что разработчикам API не нужно учитывать дисперсию параметров типа для интерфейсов, вместо этого им часто приходится использовать более сложные сигнатуры методов. Распространенный пример касается интерфейса Comparable. ^[4]^{: 66} Предположим, мы хотим написать функцию, которая находит самый большой элемент в коллекции. Элементы должны реализовать метод compareTo, ^[4]^{: 66} поэтому первая попытка может быть

< T extends Comparable < T >> T max ( Collection < T > coll );

Однако этот тип недостаточно общий — можно найти максимум a , но не a . Проблема в том, что он не реализует , а вместо этого (лучший) интерфейс . В Java, в отличие от C#, не считается подтипом . Вместо этого тип должен быть изменен:Collection<Calendar>Collection<GregorianCalendar>GregorianCalendarComparable<GregorianCalendar>Comparable<Calendar>Comparable<Calendar>Comparable<GregorianCalendar>max

< T extends Comparable <? super T >> T max ( Collection < T > coll );

Ограниченный подстановочный знак передает информацию, которая вызывает только контравариантные методы из интерфейса. Этот конкретный пример разочаровывает, поскольку все методы в контравариантны, так что это условие тривиально истинно. Система на месте объявления могла бы справиться с этим примером с меньшим беспорядком, аннотируя только определение .? super TmaxComparableComparableComparable

Метод maxможно изменить еще больше, используя верхний ограниченный подстановочный знак для параметра метода: ^[18]

< T extends Comparable <? super T >> T max ( Collection <? extends T > coll );

Сравнение аннотаций Declaration-site и Use-site

Аннотации вариативности использования на месте обеспечивают дополнительную гибкость, позволяя большему количеству программ проверять тип. Однако их критиковали за сложность, которую они добавляют языку, что приводит к сложным сигнатурам типов и сообщениям об ошибках.

Один из способов оценить, полезна ли дополнительная гибкость, — посмотреть, используется ли она в существующих программах. Исследование большого набора библиотек Java ^[16] показало, что 39% аннотаций с подстановочными знаками можно было бы напрямую заменить аннотациями на месте объявления. Таким образом, оставшиеся 61% — это показатель мест, где Java выигрывает от наличия системы на месте использования.

В языке с декларацией на месте библиотеки должны либо предоставлять меньше вариативности, либо определять больше интерфейсов. Например, библиотека Scala Collections определяет три отдельных интерфейса для классов, которые используют ковариацию: ковариантный базовый интерфейс, содержащий общие методы, инвариантную изменяемую версию, которая добавляет методы с побочными эффектами, и ковариантную неизменяемую версию, которая может специализировать унаследованные реализации для использования структурного обмена. ^[19] Такая конструкция хорошо работает с аннотациями на месте декларации, но большое количество интерфейсов влечет за собой издержки сложности для клиентов библиотеки. И изменение интерфейса библиотеки может быть не вариантом — в частности, одной из целей при добавлении дженериков в Java было поддержание обратной совместимости с двоичными кодами.

С другой стороны, подстановочные знаки Java сами по себе сложны. В презентации на конференции ^[20] Джошуа Блох критиковал их как слишком сложные для понимания и использования, заявляя, что при добавлении поддержки замыканий «мы просто не можем позволить себе еще одни подстановочные знаки ». Ранние версии Scala использовали аннотации варианта использования на месте, но программисты обнаружили, что их трудно использовать на практике, в то время как аннотации объявления на месте оказались очень полезными при проектировании классов. ^[21] Более поздние версии Scala добавили экзистенциальные типы и подстановочные знаки в стиле Java; однако, по словам Мартина Одерски , если бы не было необходимости во взаимодействии с Java, то они, вероятно, не были бы включены. ^[22]

Росс Тейт утверждает ^[23] , что часть сложности подстановочных знаков Java обусловлена решением кодировать вариантность места использования с помощью формы экзистенциальных типов. Первоначальные предложения ^[24]^[25] использовали специальный синтаксис для аннотаций вариантов, записывая вместо более многословного .List<+Animal>List<? extends Animal>

Поскольку подстановочные знаки являются формой экзистенциальных типов, их можно использовать не только для дисперсии. Такой тип, как ("список неизвестного типа" ^[26] ), позволяет передавать объекты в методы или сохранять их в полях без точного указания параметров типа. Это особенно ценно для таких классов, где большинство методов не упоминают параметр типа.List<?>Class

Однако вывод типа для экзистенциальных типов является сложной проблемой. Для разработчика компилятора подстановочные знаки Java вызывают проблемы с завершением проверки типов, выводом аргументов типов и неоднозначными программами. ^[27] В общем случае невозможно решить , является ли программа Java, использующая обобщения, хорошо типизированной или нет, ^[28] поэтому любой проверке типов придется перейти в бесконечный цикл или истечь по времени для некоторых программ. Для программиста это приводит к сложным сообщениям об ошибках типа. Тип Java проверяет подстановочные знаки, заменяя подстановочные знаки новыми переменными типа (так называемое преобразование захвата ). Это может затруднить чтение сообщений об ошибках, поскольку они ссылаются на переменные типа, которые программист не записал напрямую. Например, попытка добавить a Catк a приведет к ошибке типаList<? extends Animal>

метод List.add (capture#1) неприменим (фактический аргумент Cat не может быть преобразован в capture#1 путем преобразования вызова метода)где capture#1 — это новая переменная типа: захват#1 расширяет Животное из захвата ? расширяет Животное

Поскольку аннотации как на месте объявления, так и на месте использования могут быть полезны, некоторые системы типов предоставляют обе. ^[16]^[23]

Этимология

Эти термины происходят из понятия ковариантных и контравариантных функторов в теории категорий . Рассмотрим категорию, объекты которой являются типами, а морфизмы представляют отношение подтипа ≤. (Это пример того, как любое частично упорядоченное множество может рассматриваться как категория.) Тогда, например, конструктор типа функции берет два типа p и r и создает новый тип p → r ; таким образом, он переводит объекты в в объекты в . По правилу подтипирования для типов функций эта операция меняет ≤ для первого параметра и сохраняет его для второго, поэтому это контравариантный функтор в первом параметре и ковариантный функтор во втором. $C$ $C^{2}$ $C$

Смотрите также

Ссылки

^ Это происходит только в патологическом случае. Например, I<T> = int: любой тип может быть помещен в for Tи результатом все равно будет int.
^ abc Скит, Джон (23 марта 2019 г.). C# in Depth . Мэннинг. ISBN 978-1617294532.
^ Func<T, TResult> Делегат - Документация MSDN
^ abcdefgh Блох, Джошуа (2018). «Effective Java: Programming Language Guide» (третье изд.). Addison-Wesley. ISBN 978-0134685991.
^ Рейнольдс, Джон К. (1981). Сущность Алгола. Симпозиум по алгоритмическим языкам. Северная Голландия.
^ Карделли, Лука (1984). Семантика множественного наследования (PDF) . Семантика типов данных (Международный симпозиум София-Антиполис, Франция, 27–29 июня 1984 г.). Конспект лекций по информатике. Том 173. Springer. С. 51–67. doi :10.1007/3-540-13346-1_2. ISBN 3-540-13346-1.
Более длинная версия: — (февраль 1988 г.). «Семантика множественного наследования». Информация и вычисления . 76 (2/3): 138–164. CiteSeerX 10.1.1.116.1298 . doi :10.1016/0890-5401(88)90007-7.
^ Торгерсен, Мэдс. «C# 9.0 в записи».
^ Эллисон, Чак. «Что нового в стандартном C++?».
^ "Исправление распространенных проблем с типами". Язык программирования Dart .
^ Бертран Мейер (октябрь 1995 г.). "Статическая типизация" (PDF) . OOPSLA 95 (Объектно-ориентированное программирование, системы, языки и приложения), Атланта, 1995 г.
^ ab Howard, Mark; Bezault, Eric; Meyer, Bertrand; Colnet, Dominique; Stapf, Emmanuel; Arnout, Karine; Keller, Markus (апрель 2003 г.). "Типовая ковариация: компетентные компиляторы могут перехватывать все свистки" (PDF) . Получено 23 мая 2013 г.
^ Франц Вебер (1992). "Получение эквивалента корректности классов и системной корректности - как получить правильную ковариацию". TOOLS 8 (8-я конференция по технологии объектно-ориентированных языков и систем), Дортмунд, 1992. CiteSeerX 10.1.1.52.7872 .
^ Кастанья, Джузеппе (май 1995 г.). «Ковариантность и контравариантность: конфликт без причины». Труды ACM по языкам и системам программирования . 17 (3): 431–447. CiteSeerX 10.1.1.115.5992 . doi :10.1145/203095.203096. S2CID 15402223.
^ Липперт, Эрик (3 декабря 2009 г.). "Точные правила валидности дисперсии" . Получено 16 августа 2016 г.
^ "Раздел II.9.7". ECMA International Standard ECMA-335 Common Language Infrastructure (CLI) (6-е изд.). Июнь 2012 г.
^ abc Altidor, John; Shan, Huang Shan; Smaragdakis, Yannis (2011). «Укрощение джокеров: объединение вариативности определения и места использования». Труды 32-й конференции ACM SIGPLAN по проектированию и реализации языков программирования (PLDI'11) . ACM. стр. 602–613. CiteSeerX 10.1.1.225.8265 . doi :10.1145/1993316.1993569. ISBN 9781450306638.
^ Липперт, Эрик (29 октября 2007 г.). «Ковариантность и контравариантность в C#, часть седьмая: зачем нам вообще нужен синтаксис?» . Получено 16 августа 2016 г.
^ Bloch 2018, стр. 139–145, Глава §5, пункт 31: Используйте ограниченные подстановочные знаки для повышения гибкости API.
^ Одерски, Марин; Спун, Лекс (7 сентября 2010 г.). "The Scala 2.8 Collections API" . Получено 16 августа 2016 г.
^ Блох, Джошуа (ноябрь 2007 г.). "The Closures Controversy [видео]". Презентация на Javapolis'07. Архивировано из оригинала 2014-02-02.{{cite web}}: CS1 maint: location (link)
^ Одерски, Мартин; Зенгер, Маттиас (2005). "Масштабируемые абстракции компонентов" (PDF) . Труды 20-й ежегодной конференции ACM SIGPLAN по объектно-ориентированному программированию, системам, языкам и приложениям (OOPSLA '05) . ACM. стр. 41–57. CiteSeerX 10.1.1.176.5313 . doi :10.1145/1094811.1094815. ISBN 1595930310.
↑ Веннерс, Билл; Соммерс, Фрэнк (18 мая 2009 г.). «Цель системы типов Scala: беседа с Мартином Одерски, часть III» . Получено 16 августа 2016 г.
^ ab Tate, Ross (2013). "Mixed-Site Variance". FOOL '13: Неформальные материалы 20-го Международного семинара по основам объектно-ориентированных языков . CiteSeerX 10.1.1.353.4691 .
^ Игараси, Ацуси; Вироли, Мирко (2002). «О подтипировании на основе дисперсии для параметрических типов». Труды 16-й Европейской конференции по объектно-ориентированному программированию (ECOOP '02) . Конспект лекций по информатике. Том 2374. С. 441–469. CiteSeerX 10.1.1.66.450 . doi :10.1007/3-540-47993-7_19. ISBN 3-540-47993-7.
^ Торуп, Крестен Краб; Торгерсен, Мадс (1999). «Унификация обобщенности: объединение преимуществ виртуальных типов и параметризованных классов». Объектно-ориентированное программирование (ECOOP '99) . Конспект лекций по информатике. Том 1628. Springer. С. 186–204. CiteSeerX 10.1.1.91.9795 . doi :10.1007/3-540-48743-3_9. ISBN 3-540-48743-3.
^ "Учебники Java™, Generics (обновлено), Unbounded Wildcards" . Получено 17 июля 2020 г. .
^ Тейт, Росс; Леунг, Алан; Лернер, Сорин (2011). «Укрощение подстановочных знаков в системе типов Java». Труды 32-й конференции ACM SIGPLAN по проектированию и реализации языков программирования (PLDI '11) . стр. 614–627. CiteSeerX 10.1.1.739.5439 . ISBN 9781450306638.
^ Григоре, Раду (2017). «Java generics are turing complete». Труды 44-го симпозиума ACM SIGPLAN по принципам языков программирования (POPL'17) . стр. 73–85. arXiv : 1605.05274 . Bibcode : 2016arXiv160505274G. ISBN 9781450346603.

Внешние ссылки

Невероятные приключения в кодировании: серия статей о проблемах реализации, связанных с ко/контравариантностью в C#
Contra Vs Co Variance (обратите внимание, что эта статья не обновлена для C++)
Замыкания для языка программирования Java 7 (v0.5)
Теория ковариантности и контравариантности в C# 4