Типы и подтипы

Такая штука как подтипы и приведение типов встречается повсюду, однако и тут есть некоторые нюансы, о которых лучше не забывать.

Подтип типа τ — это такой тип τ', значения которого можно безболезненно подставлять везде, где предполагается значение типа τ. Записывается это как

τ' <: τ

При этом τ называется супертипом для τ' .

Подтипы очень полезная в хозяйстве вещь: интуитивно понятно, например, что int <: float, то есть везде, где некая функция предполагает на входе действительное число, ей можно передать и целое. Еще очень широко подтипы используются нынче в ООП — когда тип (конкретный класс) "корова" является подтипом интерфейса "животное", другими словами, когда используется наследование интерфейса. Но тут есть уже очень много подводных камней, и к подтипам в ООП лучше вернемся попозже.

Логичное развитие идеи подтипов — это применение ее к параметризованым типам. В том числе ко всяким контейнерам.

Вопрос: если τ' <: τ, то следует ли из этого что List<τ'> будет подтипом List<τ>?

Если да, то тип List<T> называется ковариантным по параметру T, если наоборот (то есть List<τ> <: List<τ'>) — контравариантым.

Классический пример тут это параметризованный тип функции,

X → Y

то есть, она берет значение типа X в качестве аргумента, а возвращает Y. (X,Y - переменные типа, aka имена параметров шаблона/генерика).

Такой тип будет контравариантным по типу аргумента, и ковариантным по типу возвращаемого значения. И правда:

float → float <: int → float 

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

int → int <: int → float

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

Теперь вернемся к контейнерам. Возьмем некий шаблонный массив Array<T>. Пускай Cow <: Animal.

 function boogaga(Array<Animal> animals)
 {
   foreach (i in animals)
     i.go_home()
 }

С точки зрения этой функции, Array<Cow> похоже, вполне себе подтип Array<Animal>. И он таковым является в C#, Java и, в общем-то, C++. Однако, если наша функция захочет добавить еще один элемент в массив как animals.add(new Animal) — все сразу поломается, потому как где-то выше этот массив объявлен как Array<Cow>.

 function boogaga(Array animals)
 {
   animals.add(new Animal);
 }

 Array<Cow> cows;
 boogaga(cows);                         
 foreach(i in cows)
   i.sayMoo(); //  у Animal нет метода sayMoo!

 

Зачем тогда делать массивы ковариантными — это удобно для всяких операций сортировок и поиска, и других операций, навроде первой функции boogaga. А чтобы избежать подобных ошибок, при добавлении в массив элемента не того типа (Animal вместо Cow) в Java и C# при выполнении программы вылетит специальный эксепшен.

Что касается C++, то тут, как обычно, все хуже. Из-за того что типы указателей неявно конвертятся в массивы и наоборот. Очевидно, что Cow * есть подтип Animal * — но благодаря неявным преобразованиям, Cow[] будет подтипом Animal[], и это практически всегда будет приводить к ошибкам при вычислении смещений на элементы массива. см. C++ FAQ Lite.

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

Немножко ссылок по теме:

• Лекция про subtyping с примерами из java
• Туториал по Scala: "Scala By Example". Язык Scala примечателен тем, что там, при объявлении параметризованого типа (шаблона) можно явно указать его ковариантность, а также явно задать условие типа "параметр шаблона должен быть подтипом(супертипом) типа τ'".
• Книжка "Foundations of Object-Oriented Programming Languages: Types and Semantics" by Kim B. Bruce — частично доступна онлайн.
• Книжка "Types and Programming Languages" by Benjamin C. Pierce — к сожалению, легально доступной онлайн нет.