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

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

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

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

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

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

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

Формальное определение [ править ]

В системе типа в виде языка программирования , правила набора текста или конструктор типа:

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

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

Примеры 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]IEnumerable<out T>Action<in T>IList<T>Func<in T, out TResult>TTResult

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

Массивы [ править ]

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

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

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

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

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

С C # вы можете поиграть с этим, используя ключевое слово dynamic поверх array / collection / generics с утиной типизацией , intellisense таким образом теряется, но работает.

Ковариантные массивы в Java и C # [ править ]

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

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

логическое  equalArrays ( Object []  a1 ,  Object []  a2 ); void  shuffleArray ( Object []  a );

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

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

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

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

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

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

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

< T >  логическое  equalArrays ( T []  a1 ,  T []  a2 ); < T >  void  shuffleArray ( T []  a );

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

Типы функций [ править ]

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

Эти языки также должны указывать, когда один тип функции является подтипом другого, то есть когда безопасно использовать функцию одного типа в контексте, который ожидает функцию другого типа. Можно безопасно заменить функцию f функцией g, если f принимает аргумент более общего типа и возвращает более конкретный тип, чем g . Например, функции типа , и могут использоваться везде, где ожидалось. (Это можно сравнить с принципом устойчивости коммуникации: «будьте либеральны в том, что вы принимаете, и консервативны в том, что вы производите».) Общее правило таково:Animal -> CatCat -> CatAnimal -> AnimalCat -> Animal

${\ Displaystyle (P_ {1} \ rightarrow R_ {1}) \ leq (P_ {2} \ rightarrow R_ {2})}$если и .${\ Displaystyle P_ {1} \ geq P_ {2}}$${\ Displaystyle R_ {1} \ leq R_ {2}}$

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

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

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

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

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

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

• Вариант и переопределение метода: обзор
• Подтип параметра / типа возвращаемого значения метода.

• Инвариантность . Сигнатура замещающего метода не изменилась.

• Ковариантный возвращаемый тип . Отношение подтипов находится в том же направлении, что и отношение между ClassA и ClassB.

• Контравариантный тип параметра . Отношение подтипов противоположно отношению между ClassA и ClassB.

• Ковариантный тип параметра . Не безопасный тип.

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

class  AnimalShelter  { Животное  getAnimalForAdoption ()  {  // ...  }  void  putAnimal ( Животное  животное )  {  // ...  } }

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

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

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

class  CatShelter  extends  AnimalShelter  { Cat  getAnimalForAdoption ()  {  вернуть  новый  Cat ();  } }

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

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

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

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

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

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

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

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

class  CatShelter  extends  AnimalShelter  { void  putAnimal ( ковариантный  Кот-  животное )  {  // ...  } }

Это небезопасно. Повышающей Кастинг CatShelterАнь AnimalShelter, можно попытаться поместить собаку в кошки приюта. Это не соответствует CatShelterограничениям параметров и приведет к ошибке выполнения. Отсутствие безопасности типов (известное как «проблема перехвата» в сообществе Eiffel, где «кошка» или «CAT» - это измененная доступность или тип) было давней проблемой. За прошедшие годы для исправления этой проблемы были предложены различные комбинации глобального статического анализа, локального статического анализа и новых языковых функций ^{[7] [8],} и они были реализованы в некоторых компиляторах Eiffel.

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

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

интерфейс  AnimalInterface  {}интерфейс  DogInterface  расширяет  AnimalInterface  {}класс  Dog  реализует  DogInterface  {}class  Pet {  общедоступная  функция  __construct ( AnimalInterface  $ animal )  {} }класс  PetDog  расширяет  Pet {  общедоступная  функция  __construct ( DogInterface  $ dog )  {  parent :: __construct ( $ dog );  } }

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

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

interface  Comparable  { int  compareTo ( Объект  o ); }

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

класс  RationalNumber  реализует  Comparable  {  int  numerator ;  int  знаменатель ;  // ...  public  int  compareTo ( объект  другой )  {  RationalNumber  otherNum  =  ( RationalNumber ) другой ;  вернуть  целое число . compare ( числитель  *  другое число . знаменатель ,  другое число . числитель  *  знаменатель );  } }

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

Отсутствие необходимости в ковариантных типах параметров [ править ]

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

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

class  Shelter < T  extends  Animal >  { T  getAnimalForAdoption ()  {  // ...  } void  putAnimal ( T  животное )  {  // ...  } } class  CatShelter  extends  Shelter < Cat >  { Кошка  getAnimalForAdoption ()  {  // ...  } void  putAnimal ( Кошка-  животное )  {  // ...  } }

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

class  RationalNumber  реализует  Comparable < RationalNumber >  { int  числитель ;  int  знаменатель ;  // ...  public  int  compareTo ( RationalNumber  otherNum )  {  вернуть  целое число . compare ( числитель  *  другое число . знаменатель ,  другое число . числитель  *  знаменатель );  } }

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

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

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

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

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

Общие типы [ править ]

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

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

Аннотации отклонения от места объявления [ править ]

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

Интерфейсы [ править ]

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

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

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

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

• Неуниверсальные типы (классы, структуры, перечисления и т. Д.) Действительны как ко-, так и контравариантно.
• Параметр типа Tдействителен ковариантно, если он не был отмечен in, и действителен контравариантно, если он не был отмечен out.
• Тип массива допустим S-ly, если есть. (Это потому, что в C # есть ковариантные массивы.)A[]A
• Базовый тип действует S-LY , если для каждого параметра ,G<A1, A2, ..., An>Ai
  • Ai является допустимым S-ly, а i- й параметр Gобъявлен ковариантным, или
  • Ai действителен (не S) -y, а i- й параметр 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 ]  =  новый  scala . сбор . неизменяемый .: :( x ,  this )  / ** ... * / }

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

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

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

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

Вывод дисперсии [ править ]

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

По этим причинам ^[14] большинство языков делают очень мало выводов о дисперсии. 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

 тип  модуля S  =  sig  type  key  type  (+ ' a )  t  val  empty :  ' a  t  val  mem :  key  ->  ' a  t  ->  bool  ...  end

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

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

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

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

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

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

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

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

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

В то время как параметризованные типы без подстановочных знаков в Java являются инвариантными (например, между подстановочными знаками и нет отношения ), подстановочные типы можно сделать более конкретными, указав более жесткие границы. Например, это подтип . Это показывает, что типы подстановочных знаков ковариантны по своим верхним границам (а также контравариантны по своим нижним границам ). В целом, с учетом типа подстановочного знака, например , есть три способа сформировать подтип: путем специализации класса , путем указания более жесткой границы или путем замены подстановочного знака определенным типом (см. Рисунок).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) из книги Джошуа Блоха « Эффективная Java » дает простой способ запомнить, когда использовать ковариацию и контравариантность.

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

< T  расширяет  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  расширяет  Comparable <?  super  T >>  T  max ( Коллекция < T >  coll );

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

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

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

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

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

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

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

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

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

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

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

Происхождение термина ковариация [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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