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

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

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

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

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

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

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

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

Предполагать 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>);
• вариант, если ковариантный, контравариантный или бивариантный;
• инвариантный или нонвариантный , если не вариант.

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

Примеры С#

Например, в 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 (контравариантный) атрибут (ноль или более) его параметров типа. Вышеуказанные интерфейсы объявлены как IEnumerable<out T>, Action<in T>, и IList<T>. Типы с более чем одним параметром типа могут указывать разные отклонения для каждого параметра типа. Например, тип делегата Func<in T, out TResult> представляет функцию с контравариантным входным параметром типа T и ковариантное возвращаемое значение типа TResult. Компилятор проверяет, что все типы определены и используются согласованно с их аннотациями, и в противном случае сигнализирует об ошибке компиляции.

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

Массивы

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

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

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

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

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

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

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

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

boolean equalArrays(Object[] a1, Object[] a2);
void shuffleArray(Object[] a);

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

Таким образом, и Java, и C# относятся к типам массивов ковариантно. Например, в Java String[] является подтипом Object[]и в С# string[] является подтипом object[].

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

// a is a single-element array of String
String[] a = new String[1];

// b is an array of Object
Object[] b = a;

// Assign an Integer to b. This would be possible if b really were
// an array of Object, but since it really is an array of String,
// we will get a java.lang.ArrayStoreException.
b[0] = 1;

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

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

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

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

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

Типы функций

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

Эти языки также должны указывать, когда один тип функции является подтипом другого, то есть когда безопасно использовать функцию одного типа в контексте, который ожидает функцию другого типа. Безопасно заменить функцию f на функцию g , если f принимает более общий тип аргумента и возвращает более конкретный тип, чем g . Например, функции типа animal -> cat, cat -> cat, и animal -> animal можно использовать везде, где cat -> 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})}}$

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

При работе с функциями, которые принимают функции в качестве аргументов , это правило можно применять несколько раз. Например, применив правило дважды, мы видим, что $((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 возможности следующие (где класс B — это подкласс, расширяющий класс A, который является суперклассом):

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

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

class AnimalShelter {

    Animal getAnimalForAdoption() {
        // ...
    }
    
    void putAnimal(Animal animal) {
        //...
    }
}

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

Тип возвращаемого значения ковариантного метода

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

class CatShelter extends AnimalShelter {

    Cat getAnimalForAdoption() {
        return new Cat();
    }
}

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

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

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

class CatShelter extends AnimalShelter {
    void putAnimal(Object animal) {
        // ...
    }
}

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

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

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

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

class CatShelter extends AnimalShelter {

    void putAnimal(covariant Cat animal) {
        // ...
    }
}

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

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

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

interface AnimalInterface {}


interface DogInterface extends AnimalInterface {}


class Dog implements DogInterface {}


class Pet
{
    public function __construct(AnimalInterface $animal) {}
}


class PetDog extends Pet
{
    public function __construct(DogInterface $dog)
    {
        parent::__construct($dog);
    }
}

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

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

interface Comparable {

    int compareTo(Object o);
}

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

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

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

Устранение необходимости в ковариантных типах параметров

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

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

class Shelter<T extends Animal> {

    T getAnimalForAdoption() {
        // ...
    }

    void putAnimal(T animal) {
        // ...
    }
}

    
class CatShelter extends Shelter<Cat> {

    Cat getAnimalForAdoption() {
        // ...
    }

    void putAnimal(Cat animal) {
        // ...
    }
}

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

class RationalNumber implements Comparable<RationalNumber> {

    int numerator;
    int denominator;
    // ...
         
    public int compareTo(RationalNumber otherNum) {
        return Integer.compare(numerator * otherNum.denominator, 
                               otherNum.numerator * denominator);
    }
}

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

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

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

Краткое изложение дисперсии и наследования

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

	Тип параметра	Тип возврата
C++ (с 1998 г.), Java (начиная с J2SE 5.0 ), D , C# (начиная с C# 9).	Инвариант	Ковариантный
С# (до C# 9)	Инвариант	Инвариант
Сатер	Контравариантный	Ковариантный
Эйфелева	Ковариантный	Ковариантный

Общие типы

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

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

Аннотации отклонений на сайте объявления

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

Интерфейсы

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

interface IEnumerator<out T>
{
    T Current { get; }
    bool MoveNext();
}

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

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

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

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

interface IList<T>
{
    void Insert(int index, T item);
    IEnumerator<T> GetEnumerator();
}

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

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

Данные

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

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

sealed abstract class List[+A] extends AbstractSeq[A] {
    def head: A
    def tail: List[A]

    /** Adds an element at the beginning of this list. */
    def ::[B >: A] (x: B): List[B] =
        new scala.collection.immutable.::(x, this)
    /** ... */
}

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

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

def :: (x: A): List[A]

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

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

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

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

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

type ('a, 'b) t = T of ('a -> 'b)

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

type (-'a, +'b) t = T of ('a -> 'b)

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

module type S =
    sig
        type key
        type (+'a) t
        val empty: 'a t
        val mem: key -> 'a t -> bool
        ...
    end

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

Использование аннотаций отклонений на сайте (подстановочные знаки)

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

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

Java предоставляет аннотации отклонений в зависимости от места использования посредством подстановочных знаков — ограниченной формы ограниченных экзистенциальных типов . Параметризованный тип может быть создан с помощью подстановочного знака. ? вместе с верхней или нижней границей, например List<? extends Animal> или List<? super Animal>. Неограниченный подстановочный знак, например List<?> эквивалентно List<? extends Object>. Такой тип представляет List<X> для какого-то неизвестного типа X что удовлетворяет границе. Например, если l имеет тип List<? extends Animal>, то программа проверки типов примет

Animal a = l.get(3);

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

l.add(new Animal());

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

Подтипы подстановочных знаков в Java можно визуализировать в виде куба.

Хотя параметризованные типы без подстановочных знаков в Java являются инвариантными (например, между List<Cat> и List<Animal>), типы подстановочных знаков можно сделать более конкретными, указав более жесткую границу. Например, List<? extends Cat> является подтипом List<? extends Animal>. Это показывает, что типы подстановочных знаков ковариантны в своих верхних границах (а также контравариантны в своих нижних границах ). В общей сложности, учитывая тип подстановочного знака, например C<? extends T>, существует три способа формирования подтипа: путем специализации класса C, задав более жесткую границу Tили заменив подстановочный знак ? определенного типа (см. рисунок).

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

В общем случае общей структуры данных IListковариантные параметры используются для методов, извлекающих данные из структуры, а контравариантные параметры — для методов, помещающих данные в структуру. Мнемоника Producer Extends, Consumer Super (PECS) из книги Эффективная Java» « Джошуа Блоха дает простой способ запомнить, когда использовать ковариацию и контравариацию.

Подстановочные знаки являются гибкими, но есть один недостаток. Хотя вариативность в зависимости от места использования означает, что разработчикам API не нужно учитывать разницу параметров типа в интерфейсах, вместо этого им часто приходится использовать более сложные сигнатуры методов. Типичный пример включает в себя Comparable интерфейс. Предположим, мы хотим написать функцию, которая находит самый большой элемент в коллекции. Элементы должны реализовать compareTo метод, так что первая попытка может быть

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

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

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

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

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

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

Сравнение аннотаций сайта объявления и сайта использования

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

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

В языке сайта объявлений библиотеки должны либо предоставлять меньшую вариативность, либо определять больше интерфейсов. Например, библиотека Scala Collections определяет три отдельных интерфейса для классов, использующих ковариантность: ковариантный базовый интерфейс, содержащий общие методы, инвариантную изменяемую версию, которая добавляет методы с побочными эффектами, и ковариантную неизменяемую версию, которая может специализировать унаследованные реализации для использования структурных делиться. Этот дизайн хорошо работает с аннотациями сайтов объявлений, но большое количество интерфейсов влечет за собой сложность для клиентов библиотеки. А изменение интерфейса библиотеки может быть невозможным — в частности, одной из целей при добавлении дженериков в Java было обеспечение обратной двоичной совместимости.

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

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

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

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

method List.add (capture#1) is not applicable
  (actual argument Cat cannot be converted to capture#1 by method invocation conversion)
where capture#1 is a fresh type-variable:
  capture#1 extends Animal from capture of ? extends Animal

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

Этимология

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

См. также

• Полиморфизм (информатика)
• Наследование (объектно-ориентированное программирование)
• Принцип замены Лискова

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

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