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

Здравствуйте, меня зовут Дмитрий Карловский и я… хочу поведать вам о фундаментальной особенности систем типов, которую зачастую или вообще не понимают или понимают не правильно через призму реализации конкретного языка, который ввиду эволюционного развития имеет много атавизмов. Поэтому, даже если вы думаете, что знаете, что такое «вариантность», постарайтесь взглянуть на проблематику свежим взглядом. Начнём мы с самых основ, так что даже новичок всё поймёт. А продолжим без воды, чтобы даже профи было полезно для структурирования своих знаний. Примеры кода будут на псевдоязыке похожем на 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. И все трое одновременно являются подтипами Real. А тип Prime является подтипом всех вышеперечисленных. В то же время типы 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

Функция replacePet наследует ограничения у тех функций, которые она внутри себя использует: у touchPet она взяла ограничение на надтип, а у pushPet — ограничение на подтип. Если мы передадим ей клетку с любым животным, то она не сможет передать её в функцию touchPet, которая не умеет работать с лисами (дикое животное просто откусит палец). А если передадим клетку с кошкой, то не получится вызвать уже 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 { content : Animal }

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

const animalCage = new Cage()
const petCage = new Cage()
const catCage = new Cage()
const dogCage = new Cage()
const foxCage = new Cage()

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

( cage : PetCage )=> void

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

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

interface ICageIn { T content { set; } } // contravariant generic parameter
interface ICageOut { T content { get; } } // covariant generic parameter
interface ICageInOut { 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 { content! : Animal }

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

pushPet( new Cage() ) // forbid to push Pet to Animal Cage :-(
pushPet( new Cage() ) // allow to push Dog to Cat Cage :-(

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

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

pushPet( new Cage() ) // allow :-)
pushPet( new Cage() ) // allow :-)
pushPet( new Cage() ) // forbid :-)
pushPet( new Cage() ) // forbid :-)
pushPet( new Cage() ) // 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 ) // forbid :-)
touchPet( new Cage ) // allow :-)
touchPet( new Cage ) // allow :-)
touchPet( new Cage ) // allow :-)
touchPet( new Cage ) // forbid :-)

pushPet( new Cage ) // allow :-)
pushPet( new Cage ) // allow :-)
pushPet( new Cage ) // forbid :-)
pushPet( new Cage ) // forbid :-)
pushPet( new Cage ) // forbid :-)

replacePet( new Cage ) // forbid :-)
replacePet( new Cage ) // allow :-)
replacePet( new Cage ) // forbid :-)
replacePet( new Cage ) // forbid :-)
replacePet( new Cage) // forbid :-)

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

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

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

using System;

abstract class Animal {}
abstract class Pet : Animal {}
class Cat : Pet {}
class Dog : Pet {}
class Fox : Animal {}

interface ICageIn { T content { set; } }
interface ICageOut { T content { get; } }
interface ICageInOut { T content { get; set; } }

class Cage : ICageIn, ICageOut, ICageInOut { public T content { get; set; } }

public class Program {

    static void touchPet( ICageOut cage ) {
        Console.WriteLine( cage.content );
    }

    static void pushPet( ICageIn cage ) {
        cage.content = new Dog();
    }

    static void replacePet( ICageInOut cage ) {
        touchPet( cage as ICageOut );
        pushPet( cage as ICageIn );
    }

    void enshurePet( Cage cage ) {
        if( cage.content is Pet ) return;
        pushPet( cage as ICageIn );
    }

    public static void Main() {

        var animalCage = new Cage();
        var petCage = new Cage();
        var catCage = new Cage();
        var dogCage = new Cage();
        var foxCage = new Cage();

        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 { public T content; }

public class Main
{
    static void touchPet( Cage cage ) {
        System.out.println( cage.content );
    }

    static void pushPet( Cage cage ) {
        cage.content = new Dog();
    }

    static void replacePet(Cage cage ) {
        touchPet( cage );
        pushPet( cage );
    }

    void enshurePet( Cage cage ) {
        if( cage.content instanceof Pet ) return;
        pushPet( cage );
    }

    public static void main(String[] args) {

        Cage animalCage = new Cage();
        Cage petCage = new Cage();
        Cage catCage = new Cage();
        Cage dogCage = new Cage();
        Cage foxCage = new Cage();

        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 :-)
    }
}

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

© Habrahabr.ru