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

Многие языков программирования системы типов поддерживают подтипирование . Например, если тип 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#

Например, в 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метод на элементах. Реализация не зависит от точного типа элемента, хранящегося в массиве, поэтому должна быть возможность написать одну функцию, которая будет работать со всеми типами массивов. Легко реализовать функции типа:

логическое   значение  равных массивов (  Object  []   a1  ,   Object  []   a2  ); 
  void   shuffleArray  (  Объект  []   a  ); 

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

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

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

// 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  >   логическое   значение  равных массивов (  T  []   a1  ,   T  []   a2  ); 
  <  T  >   void   shuffleArray  (  T  []   a  ); 

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

Типы функций

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

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

класс   CatShelter   расширяет   AnimalShelter   { 

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

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

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

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

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

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

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

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

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

класс   CatShelter   расширяет   AnimalShelter   { 

     void   putAnimal  (  ковариантное   -кошка   животное  )   { 
         // ... 
     } 
 } 

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

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

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

интерфейс   AnimalInterface   {} 


 интерфейс   DogInterface   расширяет   AnimalInterface   {} 


 класс   Dog   реализует   DogInterface   {} 


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


 class   PetDog   расширяет   Pet 
 { 
     public   function   __construct  (  DogInterface   $dog  ) 
     { 
         родитель  ::  __construct  (  $ собака  ); 
      } 
 } 

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

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

интерфейс   Comparable   { 

     int   CompareTo  (  Object   o  ); 
  } 

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

класс   RationalNumber   реализует   Comparable   { 
     int   numerator  ; 
      int   знаменатель  ; 
     ... 
 
     public   int   CompareTo  (  Objectother  ​  )   { 
         RationalNumberotherNum   RationalNumber   =   (  )  ;  other   // 
          вернуть   целое число  .   сравнить  (  числитель   *   другоеNum  .  знаменатель  , 
                                другоеNum  .  числитель   *   знаменатель  ); 
      } 
 } 

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

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

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

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

class   Shelter  <  T   расширяет   Animal  >   { 

     T   getAnimalForAdoption  ()   { 
         // ... 
     } 

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

    
 class   CatShelter   расширяет   Shelter  <  Cat  >   { 

     Cat   getAnimalForAdoption  ()   { 
         // .. . 
     } 

     void   putAnimal  (  -кошка   Животное  )   { 
         // ... 
     } 
 } 

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

класс   RationalNumber   реализует   Comparable  <  RationalNumber  >   { 

     int   numerator  ; 
      int   знаменатель  ; 
     ... 
         
     public   int   CompareTo  (  RationalNumberotherNum   )   //   { 
         return   Integer  .   сравнить  (  числитель   *   другоеNum  .  знаменатель  ,  
                                другоеNum  .  числитель   *   знаменатель  ); 
      } 
 } 

Еще одна языковая особенность, которая может помочь, — это множественная отправка . Одна из причин, по которой бинарные методы неудобно писать, заключается в том, что при вызове типа 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) в параметре типа.

интерфейс   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> интерфейс.

интерфейс   IList  <T> ​  { 
 Insert 
     void   (  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] сорт.

запечатанный   абстрактный   класс   List  [  +  A  ]   расширяет   AbstractSeq  [  A  ]   { 
     def   head  :   A 
     def   Tail  :   List  [  A  ] 

     /** Добавляет элемент в начало этого списка.   */ 
     def   ::  [  B   >:   A  ]   (  x  :   B  ):   List  [  B  ]   = 
         new   scala  .   коллекция  .   неизменный  .   ::  (  x  ,   это  ) 
     /** ... */ 
 } 

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

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

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

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

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

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

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

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

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

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

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

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

 модуля  тип   S   = 
     сигнатуры 
         тип   ключа 
         тип   (+  '  a  )   t 
         val   пусто  :   '  at   val 
         mem   :  a   key   ->   '  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>, то программа проверки типов примет

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

потому что тип X как известно, является подтипом 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   расширяет   Comparable  <  T  >>   T   max  (  Collection  <  T  >   coll  ); 

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

<  T   расширяет   сопоставимое  <?    супер   T  >>   T   max  (  Коллекция  <T> ​  coll   )  ; 

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

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

<  T   расширяет   сопоставимое  <?    супер   T  >>   T   max  (  Коллекция  <?   расширяет   T  >   кол  ); 

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

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

Один из способов оценить, полезна ли дополнительная гибкость, — это посмотреть, используется ли она в существующих программах. Обзор большого набора 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> выдаст ошибку типа

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

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

Этимология

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

См. также

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

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

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