Хабрахабр

Теория программирования: Вариантность

Поэтому, даже если вы думаете, что знаете, что такое "вариантность", постарайтесь взглянуть на проблематику свежим взглядом. Здравствуйте, меня зовут Дмитрий Карловский и я… хочу поведать вам о фундаментальной особенности систем типов, которую зачастую или вообще не понимают или понимают не правильно через призму реализации конкретного языка, который ввиду эволюционного развития имеет много атавизмов. А продолжим без воды, чтобы даже профи было полезно для структурирования своих знаний. Начнём мы с самых основ, так что даже новичок всё поймёт. Потом будут разобраны подходы уже нескольких реальных языков. Примеры кода будут на псевдоязыке похожем на TypeScript. А если же вы разрабатываете свой язык, то данная статья поможет вам не наступить на чужие грабли.

а вдруг там лис?

Описывая тип параметра мы задаём ограничение на множество типов, которые можно нам передать. Параметр — это то, что мы принимаем. Несколько примеров :

// параметр функции
function log( id : string | number ) // параметр конструктора
class Logger { constructor( readonly id : Natural ) {}
} // шаблонный параметр
class Node< Id extends Number > { id : Id
}

В момент передачи аргумент всегда имеет какой-то конкретный тип. Аргумент — это то, что мы передаём. Несколько примеров: Тем не менее, при статическом анализе конкретный тип может быть не известен из-за чего компилятор оперирует опять же ограничениями на тип.

log( 123 ) // конкретный тип
new Logger( promptStringOrNumber( 'Enter id' ) ) // конкретный тип известен только в рантайме
new Node( 'root' ) // явно некорректный тип, ошибка компиляции

Подтип — это частный случай надтипа. Типы могут могут образовывать иерархию. Например, тип Natural является подтипом Integer и Positive. Подтип может образовываться путём сужения множества возможных значений надтипа. А тип Prime является подтипом всех вышеперечисленных. И все трое одновременно являются подтипами Real. В то же время типы Positive и Integer являются пересекающимися, но ни один из них не является сужением другого.

image

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

image

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

abstract class Animal {}
abstract class Pet extends Animal {}
class Cat extends Pet {}
class Dog extends Pet {}
class Fox extends Animal {} class AnimalCage { content : Animal }
class PetCage extends AnimalCage { content : Pet }
class CatCage extends PetCage { content : Cat }
class DogCage extends PetCage { content : Dog }
class FoxCage extends AnimalCage { content : Fox }

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

image

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

function touchPet( cage : PetCage ) : void { log( `touch ${cage.content}` )
} touchPet( new AnimalCage ) // forbid
touchPet( new PetCage ) // allow
touchPet( new CatCage ) // allow
touchPet( new DogCage ) // allow
touchPet( new FoxCage ) // forbid

image

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

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

function pushPet( cage : PetCage ) : void { const Pet = random() > .5 ? Cat : Dog cage.content = new Pet
} pushPet( new AnimalCage ) // allow
pushPet( new PetCage ) // allow
pushPet( new CatCage ) // forbid
pushPet( new DogCage ) // forbid
pushPet( new FoxCage ) // forbid

image

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

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

function replacePet( cage : PetCage ) : void { touchPet( cage ) pushPet( cage )
} replacePet( new AnimalCage ) // forbid
replacePet( new PetCage ) // allow
replacePet( new CatCage ) // forbid
replacePet( new DogCage ) // forbid
replacePet( new FoxCage ) // forbid

image

Если мы передадим ей клетку с любым животным, то она не сможет передать её в функцию touchPet, которая не умеет работать с лисами (дикое животное просто откусит палец). Функция replacePet наследует ограничения у тех функций, которые она внутри себя использует: у touchPet она взяла ограничение на надтип, а у pushPet — ограничение на подтип. А если передадим клетку с кошкой, то не получится вызвать уже pushPet.

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

function enshurePet( cage : PetCage ) : void { if( cage.content instanceof Pet ) return pushPet( cage )
} replacePet( new AnimalCage ) // allow
replacePet( new PetCage ) // allow
replacePet( new CatCage ) // allow
replacePet( new DogCage ) // allow
replacePet( new FoxCage ) // forbid

image

Тогда она проверит, что в клетке находится питомец, иначе положит внутрь случайного питомца. В неё можно передать клетку с животным. А можно передать и, например, клетку с кошкой, тогда она просто ничего не сделает.

Зачастую потому, что про вариантность часто объясняют на примере обобщённых контейнеров. Некоторые считают, что вариантность как-то связана с обобщениями. Однако, во всём повествовании у нас до сих пор не было ни единого обобщения — сплошь конкретные классы:

class AnimalCage { content : Animal }
class PetCage extends AnimalCage { content : Pet }
class CatCage extends PetCage { content : Cat }
class DogCage extends PetCage { content : Dog }
class FoxCage extends AnimalCage { content : Fox }

Обобщения нужны лишь, чтобы уменьшить копипасту. Сделано это было, чтобы показать, что проблемы вариантности никак с обобщениями не связаны. Например, код выше можно переписать через простое обобщение:

class Cage<Animal> { content : Animal }

И теперь можно создавать экземпляры любых клеток:

const animalCage = new Cage<Animal>()
const petCage = new Cage<Pet>()
const catCage = new Cage<Cat>()
const dogCage = new Cage<Dog>()
const foxCage = new Cage<Fox>()

Обратите внимание, что сигнатуры у всех четырёх ранее приведённых функций совершенно одинаковые:

( cage : PetCage )=> void

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

Например, модификаторы in и out в C#: Поэтому в современных языках есть средства для явного указания какие у параметра ограничения на типы.

interface ICageIn<in T> { T content { set; } } // contravariant generic parameter
interface ICageOut<out T> { T content { get; } } // covariant generic parameter
interface ICageInOut<T> { T content { get; set; } } // invariant generic parameter

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

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

function getPets( input : PetCage ) : [ Pet , Pet ] { return [ input.content , new Cat ]
}

Такая функция эквивалентна функции, принимающей помимо одного входного параметра, ещё и два выходных.

function getPets( input : PetCage , output1 : PetCage , output2 : PetCage ) : void { output1.content = input.content output2.content = new Cat
}

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

image

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

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

class PetCage { pushPet() : void { const Pet = random() > .5 ? Cat : Dog this.content = new Pet } }

function pushPet( this : PetCage ) : void { const Pet = random() > .5 ? Cat : Dog this.content = new Pet
}

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

function fillPetCage( cage : PetCage ) { cage.pushPet()
}

image

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

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

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

С изменяемыми же всё сложнее, так как следующие две ситуации являются взаимоисключающими для принципа LSP:

  1. У класса A есть подкласс B, где поле B::foo является подтипом A::foo.
  2. У класса A есть метод, который может изменить поле A::foo.

Соответственно, остаётся лишь три пути:

  1. Запретить объектам при наследовании сужать типы своих полей. Но тогда в клетку для кота вы сможете засовывать и слона.
  2. Руководствоваться не LSP, а вариантностью каждого параметра каждой функции в отдельности. Но тогда придётся много думать и объяснять компилятору где какие ограничения на типы.
  3. Плюнуть на всё и уйти в монастырь функциональное программирование, где все объекты неизменяемые, а значит параметры их принимающие ковариантны объявленному типу.

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

abstract class Animal { is! : 'cat' | 'dog' | 'fox' }
abstract class Pet extends Animal { is! : 'cat' | 'dog' } class Cat extends Pet { is! : 'cat' }
class Dog extends Pet { is! : 'dog' }
class Fox extends Animal { is! : 'fox' } class Cage<Animal> { content! : Animal } function pushPet( cage : Cage<Pet> ) : void { const Pet = Math.random() > .5 ? Cat : Dog cage.content = new Pet
} pushPet( new Cage<Animal>() ) // forbid to push Pet to Animal Cage :-(
pushPet( new Cage<Cat>() ) // allow to push Dog to Cat Cage :-(

Чтобы решить эту проблему приходится помогать компилятору довольно нетривиальным кодом:

function pushPet< PetCage extends Cage<Animal>
>( cage: Cage<Pet> extends PetCage ? PetCage : never
): void { const Pet = Math.random() > .5 ? Cat : Dog cage.content = new Pet
} pushPet( new Cage<Animal>() ) // allow :-)
pushPet( new Cage<Pet>() ) // allow :-)
pushPet( new Cage<Cat>() ) // forbid :-)
pushPet( new Cage<Dog>() ) // forbid :-)
pushPet( new Cage<Fox>() ) // forbid :-)

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


class Animal {}
class Pet extends Animal {} class Cat extends Pet {}
class Dog extends Pet {}
class Fox extends Animal {} class Cage< Animal > { content : Animal } function touchPet( cage : { +content : Pet } ) : void { console.log( `touch ${typeof cage.content}` )
} function pushPet( cage: { -content: Pet } ): void { const Pet = Number((0: any)) > .5 ? Cat : Dog cage.content = new Pet
} function replacePet( cage : { content : Pet } ) : void { touchPet( cage ) pushPet( cage )
} touchPet( new Cage<Animal> ) // forbid :-)
touchPet( new Cage<Pet> ) // allow :-)
touchPet( new Cage<Cat> ) // allow :-)
touchPet( new Cage<Dog> ) // allow :-)
touchPet( new Cage<Fox> ) // forbid :-) pushPet( new Cage<Animal> ) // allow :-)
pushPet( new Cage<Pet> ) // allow :-)
pushPet( new Cage<Cat> ) // forbid :-)
pushPet( new Cage<Dog> ) // forbid :-)
pushPet( new Cage<Fox> ) // forbid :-) replacePet( new Cage<Animal> ) // forbid :-)
replacePet( new Cage<Pet> ) // allow :-)
replacePet( new Cage<Cat> ) // forbid :-)
replacePet( new Cage<Dog> ) // forbid :-)
replacePet( new Cage<Fox>) // forbid :-)

К сожалению, мне не удалось найти способа более удобно задавать вариантность не описывая типы всех полей явно. Бивариантность тут невыразима. Например, как-то так:

function pushPet( cage: Contra< Cage<Pet> , 'content' > ): void { const Pet = Number((0: any)) > .5 ? Cat : Dog cage.content = new Pet
}

Однако, впоследствии в нём были добавлены in и out модификаторы параметров, что позволило компилятору правильно проверять типы передаваемых аргументов. C# изначально проектировался без какого-либо понимания вариантности. К сожалению, использовать эти модификаторы опять же не очень удобно.

using System; abstract class Animal {}
abstract class Pet : Animal {}
class Cat : Pet {}
class Dog : Pet {}
class Fox : Animal {} interface ICageIn<in T> { T content { set; } }
interface ICageOut<out T> { T content { get; } }
interface ICageInOut<T> { T content { get; set; } } class Cage<T> : ICageIn<T>, ICageOut<T>, ICageInOut<T> { public T content { get; set; } } public class Program { static void touchPet( ICageOut<Pet> cage ) { Console.WriteLine( cage.content ); } static void pushPet( ICageIn<Pet> cage ) { cage.content = new Dog(); } static void replacePet( ICageInOut<Pet> cage ) { touchPet( cage as ICageOut<Pet> ); pushPet( cage as ICageIn<Pet> ); } void enshurePet( Cage<Pet> cage ) { if( cage.content is Pet ) return; pushPet( cage as ICageIn<Pet> ); } public static void Main() { var animalCage = new Cage<Animal>(); var petCage = new Cage<Pet>(); var catCage = new Cage<Cat>(); var dogCage = new Cage<Dog>(); var foxCage = new Cage<Fox>(); touchPet( animalCage ); // forbid :-) touchPet( petCage ); // allow :-) touchPet( catCage ); // allow :-) touchPet( dogCage ); // allow :-) touchPet( foxCage ); // forbid :-) pushPet( animalCage ); // allow :-) pushPet( petCage ); // allow :-) pushPet( catCage ); // forbid :-) pushPet( dogCage ); // forbid :-) pushPet( foxCage ); // forbid :-) replacePet( animalCage ); // forbid :-) replacePet( petCage ); // allow :-) replacePet( catCage ); // forbid :-) replacePet( dogCage ); // forbid :-) replacePet( foxCage ); // forbid :-) } }

Если же параметр не обобщённый, то беда. К Java возможность переключения вариантности была добавлена довольно поздно и лишь для обобщённых параметров, которые сами-то появились сравнительно недавно.

abstract class Animal {}
abstract class Pet extends Animal {}
class Cat extends Pet {}
class Dog extends Pet {}
class Fox extends Animal {} class Cage<T> { public T content; } public class Main
{ static void touchPet( Cage<? extends Pet> cage ) { System.out.println( cage.content ); } static void pushPet( Cage<? super Pet> cage ) { cage.content = new Dog(); } static void replacePet(Cage<Pet> cage ) { touchPet( cage ); pushPet( cage ); } void enshurePet( Cage<Pet> cage ) { if( cage.content instanceof Pet ) return; pushPet( cage ); } public static void main(String[] args) { Cage<Animal> animalCage = new Cage<Animal>(); Cage<Pet> petCage = new Cage<Pet>(); Cage<Cat> catCage = new Cage<Cat>(); Cage<Dog> dogCage = new Cage<Dog>(); Cage<Fox> foxCage = new Cage<Fox>(); touchPet( animalCage ); // forbid :-) touchPet( petCage ); // allow :-) touchPet( catCage ); // allow :-) touchPet( dogCage ); // allow :-) touchPet( foxCage ); // forbid :-) pushPet( animalCage ); // allow :-) pushPet( petCage ); // allow :-) pushPet( catCage ); // forbid :-) pushPet( dogCage ); // forbid :-) pushPet( foxCage ); // forbid :-) replacePet( animalCage ); // forbid :-) replacePet( petCage ); // allow :-) replacePet( catCage ); // forbid :-) replacePet( dogCage ); // forbid :-) replacePet( foxCage ); // forbid :-) }
}

Надеюсь изложенный материал помог вам лучше понять ограничения на типы, и как они реализованы в разных языках. На этом пока всё. Возможно именно вы разработаете язык, в котором всё это будет реализовано и удобно, и типобезопасно. Где-то лучше, где-то хуже, где-то никак, но в целом — так себе. А пока присоединяйтесь к нашему телеграм чату, где мы иногда обсуждаем теоретические концепции языков программирования.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть