Wednesday, August 15, 2007

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

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

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

τ' <: τ

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

Подтипы очень полезная в хозяйстве вещь: интуитивно понятно, например, что 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.

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

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

4 comments:

migmit said...

Чего-то я не понял.
1) Согласно теоркатегору, фонктор Hom (он же (->)) ковариантен по типу возвращаемого значения и контравариантен по типу аргумента. Тут используется другая терминология?
2) int -> float <: int -> int выглядит ОЧЕНЬ сомнительно.
3) ВСЕ параметризованные типы ковариантны??? В том числе тип (->)?

lrrr said...

Насчет (1) и (2) - спасибо, сейчас поправлю.
Я, правда, мягко говоря, не силен в теории категрий -- можно поподробнее про аналогию между понятием ковариантности функторов в ТК и ковариантности типов? Типы могут ведь быть не только ковариантными и контравариантными?

Насчет (3) я тоже наверное погорячился. С Хаскелем что-то все не так просто.

Но если под подтипами понимать интстансы type classes, а параметризованные типы -- то что можно через data объявить -- вроде
все ковариантно, нет?

migmit said...

По поводу ТК - попробую сформулировать.
Итак, наша категория состоит из
а) объектов - типов данных
б) морфизмов - функций с аргументами одного типа и значениями другого.
Отношение <:, на самом деле, позволяет выделить некое "дефолтное" отображение, своего рода "автоматическое преобразование", скажем, int -> float.
Соответственно, если функтор F ковариантен, то он переводит это отображение в F(int) -> F(float). Ну и, коль скоро F не просто функтор в категорном смысле, но вещь довольно специфическая, вводящая новый тип, мы можем просто договориться, что дефолтное отображение F(int) -> F(float) - это и есть то, что получается применением F к дефолтному же отображению int -> float. Неоднозначности не возникает. Аналогично с контравариантностью.
По поводу Хаскеля - я не очень понимаю, где там подтипы. Скажем, int не является подтипом float, его надо явно приводить. По-моему, там вообще подтипов нет. Есть подтипы в O'Haskell, но в нём я сам плаваю.

lrrr said...

Ага, мысль ясна, но по-моему в этой модели не укладывается тот факт что функций типа int -> float может быть несколько.

Насчет подтипов в Хаскеле -- наверное можно считать подтипами instances классов типов, т.е. Int <: Num. Я в общем про них думал когда про подтипы в Хаскеле упоминал.

Плюс к этому, их можно реализовать через параметризованые типы:
data Boo x = Boo Int Int x
Если создать новый тип где вместо x будет какая-то конкретная структура, то получается вроде как подтип Boo. Это уже из Олега Киселева, Haskell's Overlooked Object System -- там это подробнее описано.