9 апреля 2014 в 12:06

Вариантность в программировании из песочницы

До сих пор не можете спать, пытаясь осмыслить понятия ковариантности и контравариантности? Чувствуете, как они дышат вам в спину, но когда оборачиваетесь ничего не находите? Есть решение!


Меня зовут Никита, и сегодня мы попытаемся заставить механизм в голове работать корректно. Вас ожидает максимально доступное рассмотрение темы вариантности в примерах. Добро пожаловать под кат.



Брифинг


Вариантность в данном посте разбирается безотносительно к какому-либо языку программирования. Примеры в разделе практики написаны на псевдоязыке (он чудом оказался похож на C#) и поэтому не обязаны компилироваться вашим любимым компилятором. Приступим.


Хитрости терминологии


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


Термины ковариантность и ковариация эквивалентны (по крайней мере в программировании). Более того, термины контравариантность и контравариация также эквивалентны. Так, например, термины ковариантность и контравариантность используется в Википедии и у Троелсена (в переводе). А термины ковариация и контравариация встречаются, например, на MSDN и у Скита (в переводе).


В английском языке всё проще — covariance и contravariance.


Теория


Вариантность — перенос наследования исходных типов на производные от них типы. Под производными типами понимаются контейнеры, делегаты, обобщения, а не типы, связанные отношениями "предок-потомок". Различными видами вариантности являются ковариантность, контравариантность и инвариантность.


Ковариантность — перенос наследования исходных типов на производные от них типы в прямом порядке.
Контравариантность — перенос наследования исходных типов на производные от них типы в обратном порядке.
Инвариантность — ситуация, когда наследование исходных типов не переносится на производные.


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


Вот и всё, что нужно знать. Конечно, тем кто первый раз сталкивается с вариантностью, трудно вникнуть. Поэтому рассмотрим конкретные примеры.


Практика


Для чего всё это?

Вся суть вариантности состоит в использовании в производных типах преимуществ наследования. Известно, что если два типа связаны отношением "предок-потомок", то объект потомка может храниться в переменной типа предка. На практике это значит, что мы можем использовать для каких-либо операций объекты потомка вместо объектов предка. Тем самым, можно писать более гибкий и короткий код для выполнения действий поддерживаемых разными потомками с общий предком.


Исходная иерархия и производные типы

Для начала опишем иерархию типов, которой будем оперировать. Вверху иерархии у нас находится Device (устройство), потомками которого являются Mouse (мышь), Keyboard (клавиатура). У Mouse в свою очередь тоже есть потомки — WiredMouse (проводная мышь), WirelessMouse (беспроводная мышь).



Все любят контейнеры. На их примере наиболее просто объяснить, что подразумевается под производными типами. Если говорить о списках как производных типах, то для типа Device производным будет
List<Device> (список устройств). Аналогично, для типа Keyboard производным будет List<Keyboard> (список клавиатур). Думаю, если и были сомнения, то теперь их нет.


Классическая ковариантность

Ковариантность также легче изучать на примере контейнеров. Для этого выделим часть иерархии (ветвь) — Keyboard : Device (клавиатура является устройством, клавиатура частный случай устройства). Опять возьмём списки и построим ковариантную производную ветвь — List<Keyboard> : List<Device> (список клавиатур является частным случаем списка устройств). Как видим, наследование передалось в прямом порядке.



Рассмотрим пример кода. Есть функция, которая принимает список устройств List<Device> и совершает над ними какие-то манипуляции. Как вы уже догадались, в эту функцию можно передать список клавиатур List<Keyboard>:


void DoSmthWithDevices(List<Device> devices) { /* действия с элементами списка */ }
...
List<Keyboard> keyboards = new List<Keyboard> { /* заполнение списка */ };
DoSmthWithDevices(keyboards);

Классическая контравариантность

Каноническим для изучения контравариантности является рассмотрение её на основе делегатов. Допустим, у нас есть обобщённый делегат:


delegate void Action<T>(T something);

Для исходного типа Device производным будет Action<Device>, а для KeyboardAction<Keyboard>. Полученные делегаты могут представлять функции, которые выполняют какие-то действия над устройством или мышью соответственно. Для ветви Keyboard : Device построим производную контравариантную ветвь — Action<Device> : Action<Keyboard> (действие над устройством является частным случаем действия над клавиатурой — звучит странно, но так и есть). Если можно нажать клавишу на клавиатуре, то это не значит, что и на устройстве можно нажать её (оно может не иметь понятия о том, что такое клавиша). Но если можно подключить устройство, то можно этим же способом (методом, функцией) подключить и клавиатуру. Как видим, наследование передалось в обратном порядке.



Из выше сказанного логично, что если функция может выполнить, что-то над устройством, то она может выполнить это и над клавиатурой. Это значит, мы можем передать объект делегата Action<Device> в функцию, принимающую объект делегата Action<Keyboard>. Рассмотрим в коде:


void DoSmthWithKeyboard(Action<Keyboard> actionWithKeyboard) { /* выполнение actionWithKeyboard над клавиатурой */ }
...
Action<Device> actionWithDevice = device => device.PlugIn();
DoSmthWithKeyboard(actionWithDevice);

Немного инвариантности

Если производные типы инвариантны к исходным типам, то для ветви Keyboard : Device не образуется ни ковариантной (List<Keyboard> : List<Device>), ни контравариантной (Action<Device> : Action<Keyboard>) ветви. Это значит, что нет никакой связи между производными типами. Как видим, наследование не переносится.



А что если?


Неочевидная ковариантность

Делегаты типа Action<T> могут быть ковариантны. Это значит, что для ветви Keyboard : Device образуется ковариантная ветвь — Action<Keyboard> : Action<Device>. Таким образом, в функцию, принимающую объект делегата Action<Device>, можно передавать объект делегата Action<Keyboard>.


void DoSmthWithDevice(Action<Device> actionWithDevice) { /* выполнение actionWithDevice над устройством */ }
...
Action<Keyboard> actionWithKeyboard = keyboard => ((Device)keyboard).PlugIn();
DoSmthWithDevice(actionWithKeyboard);

Неочевидная контравариантность

Контейнеры могут быть контравариантны. Это значит, что для ветви Keyboard : Device образуется контравариантная ветвь — List<Device> : List<Keyboard>. Таким образом, в функцию, принимающую List<Keyboard>, можно передавать List<Device>:


void FillListWithKeyboards(List<Keyboard> keyboards) { /* заполнение списка клавиатур  */ }
...
List<Devices> devices = new List<Devices>();
FillListWithKeyboards(devices);

Сакральный смысл

Рассмотренные выше экзотические виды вариантности имеют, разве что, академическую ценность. Сложно придумать реальную задачу, которая легче решается при наличии такого рода возможностей. Стоит запомнить, что ковариантность и контравариантность могут вызывать ошибки времени выполнения. Для их устранения требуется вводить определённые ограничения. Компиляторы, как правило, такие ограничения не вводят.


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

Если производный тип ковариантен, то для обеспечения безопасности контейнер должен быть read only. В противном случае, остаётся возможность записать в List<Keyboard> объект неверного типа (Device, Mouse и другие) через приведение к List<Device>:


List<Device> devices = new List<Keyboard>();
devices.Add(new Device()); // ошибка времени выполнения

Если производный тип контравариантен, то для обеспечения безопасности контейнер должен быть write only. В противном случае, остаётся возможность считывания из List<Device> объекта неверного типа (Keyboard, Mouse и других) через приведение к соответствующему списку (List<Keyboard>, List<Mouse> и другим):


List<Keyboard> keyboards = new List<Device>();
keyboards.Add(new Keyboard());
keyboards[0].PressSpace(); // ошибка времени выполнения

Двойные стандарты для делегатов

Разумным для делегатов является ковариантность для выходного значения и контравариантность для входных параметров (исключая передачу по ссылке). В случае соблюдения данных условий ошибок времени выполнения не возникает.


Дебрифинг


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


UDP


Возможно более правильным определением вариантности является предложенное Эриком Липпертом. Спасибо Alex_sik за ссылку на статью.


Совместимость присваивания, assignment compatibility — это возможность присвоить значение более частного типа совместимой переменной более общего типа.
Вариантность — это сохранение совместимости присваивания исходных типов у производных типов.
Ковариантность — это сохранение совместимости присваивания исходных типов у производных в прямом порядке.
Контравариантность — это сохранение совместимости присваивания исходных типов у производных в обратном порядке.

Никита @Accetone
карма
14,0
рейтинг 0,0
Пользователь
Самое читаемое Разработка

Комментарии (22)

  • 0
    А можно какой-нибудь осмысленный пример контравариантности?
    • +2
      В разделе «Классическая ковариантность», вроде, неплохой пример. В любом случае, можно рассмотреть ещё один.

      class Fruit
      {
          public void Eat()
          {
              Console.WriteLine("You ate fruit!");
          }
      }
      
      class Orange : Fruit {}
      
      class Program
      {
          static void Main(string[] args)
          {
              // создаём объект делегата, который принимает фрукт и возвращает void
              Action<Fruit> actionWithFruit = fruit => fruit.Eat();
      
              // создаём список из трёх апельсинов
              List<Orange> oranges = new List<Orange> { new Orange(), new Orange(), new Orange() };
      
              // по факту мы должны передать в метод ForEach объект делгата Action<Orange>,
              // который принимает апельсин и возвращает void, но благодаря контравариантности 
              // можем передать Action<Fruit> т.е. записываем в переменную типа Action<Orange> объект типа Action<Fruit>
              // контравариантность переварачивает порядок наследования
              // Orange : Fruit => Action<Fruit> : Action<Orange>
              // Fruit fruit = new Orange();
              // Action<Orange> action = new Action<Fruit>(fruit => fruit.Eat());
              oranges.ForEach(actionWithFruit);
          }
      }
      


      Скажите, если нужно пояснить код или что-то осталось неясным, буду рад помочь.
      • 0
        Да, так стало понятнее, спасибо. Вроде бы то же самое, что и в статье, но с дополнительными объяснениями лучше. Теперь, когда ясна теория, очень хотелось бы узнать про эти штуки применительно к конкретным языкам, ибо никогда особо над этим не задумывался. Например, этот код в C# компилируется?
        • 0
          Ковариантность и контрваирантность, например, активно используются компилятором C# для выведения типов, при работе с делегатами.
          Довольно подробно эта тема освещена у Джона Скита. SergeyT написал хорошую рецензию на эту книгу.
        • 0
          Например, этот код в C# компилируется?

          Нет, не скомпилируется, по крайней мере при помощи Mono C# Compiler. Пруф.

        • +1
          С# / .Net Framework

          Массивы ковариантны / 2.0 и выше
          Fruit[] fruits = new Orange[10];
          

          Обобщённые коллекции инвариантны
          List<Fruit> fruits = new List<Orange>(); // ошибка времени компиляции
          

          Обобщённые интерфейсы ковариантны / 4.0 и выше
          IEnumerable<Orange> oranges = new List<Orange>();
          IEnumerable<Fruit> fruits = oranges;
          

          Группа методов ковариантна по выходному значению и котнравариантна по входным аргументам / 2.0 и выше
          // творим из фрукта апельсин ;) 
          static Orange Upgrade(Fruit fruit) { return new Orange(); }
          
          // обобщённый тип делегата для указания на методы 
          // принимающие TIn и возвращающие TOut
          delegate TOut Func<TIn, TOut>(TIn smth);
          
          static void Main(string[] args)
          {
              // это обычно т.к. Upgrade принимает Fruit и возвращает Orange
              // а делегат как раз указывает на такие функции
              Func<Fruit, Orange> action = Upgrade;
          
              // используется и ковариантность и контравариантность т.к.
              // Upgrade принимает Fruit и возвращает Orange
              // а делегат указывает на функции принимающие Orange и возвращающие Fruit 
              Func<Orange, Fruit> action2 = Upgrade;
          }
          

          Объекты делегатов ковариантны по выходному значению и котнравариантны по входным аргументам / 4.0 и выше
          Func<Fruit, Orange> action = fruit => new Orange();
          Func<Orange, Fruit> action2 = action;
          

          Приведённый мной код (комментарий с дополнительным примером) компилируется начиная с .Net Framework 4.0 и выше.
        • 0
          Извините, насчёт обобщённых интерфейсов перепутал.

          Обобщённые интерфейсы ковариантны по выходному значению и котнравариантны по входным аргументам / 4.0 и выше

          interface IMagic<in TIn, out TOut>
          {
              TOut DoMagic(TIn smth);
          }
          
          class Magic : IMagic<Fruit, Orange>
          {
              public Orange DoMagic(Fruit smth)
              {
                  return new Orange();
              }
          }
              
          class Program
          {
              static void Main(string[] args)
              {
                  // это обычно т.к. Magic реализует интерфейс IMagic<Fruit, Orange>
                  IMagic<Fruit, Orange> i1 = new Magic();
          
                  // используется и ковариантность и контравариантность т.к. записываем
                  // IMagic<Fruit, Orange> в IMagic<Orange, Fruit>
                  IMagic<Orange, Fruit> i2 = new Magic();
              }
          }
          
  • +1
    Просто оставлю это здесь: What's the difference between covariance and assignment compatibility?
    У Эрика Липперта целый цикл статей на эту тему был.

    ИМХО «перенос наследования» как то коряво звучит, а может она даже и неправильна (да, да, так написано в Википедии). Версия Липперта мне нравится больше: «Универсальный тип I ковариантен (in Т), если конструкция с аргументами ссылочного типа сохраняет направление возможности присваивания».
  • 0
    Стоит запомнить, что ковариантность и контравариантность могут вызывать ошибки времени выполнения. Для их устранения требуется вводить определённые ограничения. Компиляторы, как правило, такие ограничения не вводят.


    Не знаю как в C#гипотетическом языке, в Scala компилятор заставит сделать все 100% типобезопасно
    • 0
      Со 100% я погорячился, конечно. Все мутабельные коллекции в Scala инвариантны.
    • +1
      Здесь речь идёт не о инвариантности для обеспечения типобезопасности. Говорится, что, если поддерживается ковариантность или контравариантность, тех же коллекций, то компилятор, как правило, не проверяет корректно ли вы ей пользуетесь. Так компилятор может пропустить (не выдать ошибку времени компиляции) этот кусок кода:

      List<Device> devices = new List<Keyboard>();
      devices.Add(new Device()); // ошибка времени выполнения
      

      Это, вроде как очевидно, но я решил всё таки упомянуть.

      Спасибо за комментарий.
      • 0
        Я хотел сказать что в вашем примере инвариантность List по T вызвала бы ошибку компиляции и до ошибки в рантайме бы не дошло.

        Было бы здорово увидеть этот пример в статье, возможно даже в с участием обычных массивов Java, которые ковариантны и позволяют вот так прострелить себе колено.

        Тут, в общем, проблема не в вариантности, а в мутабельности. Для иммутабельных коллекций продвинутая система типов может гарантировать отсутствие ошибок времени выполнения.
        • 0
          В том примере с List предполагается, что контейнеры ковариантны. Это и позволяет «выстрелить себе в ногу» и в комментарии написано, что ошибка будет во время выполнения. Фактически этот пример эквивалентен примеру с массивами в Java (аналогичная ситуация с массивами в C#), только ваш основан на реально существующем языке и его возможностях.

          Или вы имеете в виду, что стоило вставить пример, когда коллекции инвариантны и при этом код не будет компилироваться?

          Если я правильно понимаю, то неизменяемость (иммутабельность) не связана с типобезопасностью. Чуть что поправьте.

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

          Предположим, что у нас List<T> является неизменяемым типом. Это не запрещает, приведя List<Keyboard> к List<Device>, записать в список объект типа Mouse, что вызовет ошибку времени выполнения.

          Для разрешения такой ситуации необходимо накладывать ограничения на операцию добавления в коллекцию. Либо совсем убирать добавление (read only) либо разрешать добавлять объекты текущего типа (Device) и его предков (Object). Получается мы можем добавить такое ограничение и для изменяемого (мутабельного) типа, что сделает его типобезопасным.
  • 0
    Простите, я правильно понимаю, что в теории любой тип в любом месте может ко/контр/ин-вариантен, но на практике конкретные языки и конкретные компиляторы накладывают ограничения? В своем проекте очень остро столкнулся с проблемой того, что аргументы методов в c# могут быть только контрвариантны
    • 0
      Да, в теории всё так, как вы поняли. Но правильнее будет сказать, что компиляторы не реализуют возможности ковариантности и контравариантности, вместо накладывания ограничений.

      А насчёт контравариантности аргументов методов в С#, можете привести краткий пример того как у вас работает и как вы хотите что бы работало?
      • 0
        У меня есть интерфейс
        public interface ISolver<out TInputData,out TAnswerData>
        {
                TAnswerData Solve(TInputData data);
        }
        


        И вот в таком виде он не скомпилируется, потому что компилятор ожидает контравариантный параметр. А хочу я очень простого — передавать наследников в качестве аргумента метода Solve, например, я хотел бы сделать такую реализацию:
        public class BinomSolver : ISolver<BinomTaskData,BinomAnswerData>
            {
                public override BinomAnswerData Solve(SolverDataBase input)
                {
                    var data = GetParameter(input);
                    var discrim = Math.Pow(data.B, 2) - 4 * data.A * data.C;
                    var x1 = (-data.B + Math.Sqrt(discrim)) / (2 * data.A);
                    var x2 = (-data.B - Math.Sqrt(discrim)) / (2 * data.A);
                    return new BinomAnswerData(x1, x2);
                }
        
            }
        

        • 0
          Пардон, несколько неправильно скопировал код, в реализации метод принимает BinomTaskData, конечно же. Такая хотелка, но сделать так у меня не получилось, пришлось выделывать костыли
        • 0
          Если я правильно понял, то:

          public interface ISolver<in TInputData, out TAnswerData>
          {
              TAnswerData Solve(TInputData data);
          }
          
          • 0
            Да, вы правильно поняли, но вообще говоря, это ограничение компилятора, если бы шарп поддерживал полномасштабную вариантность, можно было бы в качестве аргумента задать out-параметр. У Липперта, кажется, был пост, почему c# team сделали именно так, но, увы, я его потерял, возможно, вы поясните. В любом случае, когда я впервые столкнулся с in/out-параметры, я был уверен, что их можно использовать повсеместно и с помощью ключевых слов лишь делать «подсказки» разработчикам и компилятору, но увы :)
            • 0
              Для того, что бы вы могли передавать наследников в Solve ковариация и контравариация не нужна вовсе (она и не используется). Указывание in и out в обобщённом интерфейсе дают другие возможности. In — делает параметр типа контравариантным, out — ковариантным.

              class Fruit : IMagic<Fruit>
              {
                  public void DoMagic(Fruit smth) { Console.WriteLine("Hello from fruit!"); }
              }
              
              class Orange : Fruit { }
              
              interface IMagic<in T>
              {
                  void DoMagic(T smth);
              }
              
              static void Main(string[] args)
              {
                  var f = new Fruit();
                          
                  // не контравариация, пользуемся возможностью приведения потомка к предку
                  f.DoMagic(new Orange());
              
                  // контравариация, записываем IMagic<Fruit> в IMagic<Orange>
                  // т.е. в обратном порядке к возможностям исходных
                  // Fruit и Orange (Orange o = new Fruit();)
                  IMagic<Orange> magic = f as IMagic<Fruit>;
              
                  magic.DoMagic(new Orange());
              }
              

              Код выведет два раза "Hello from fruit!". И вот тот второй раз следует рассмотреть. Мы привели в конечном итоге Fruit к IMagic<Orange>. Вызываем метод DoMagic передавая ему Orange, но по факту вызывается метод котрый принимает Fruit и это типобезопасно т.к. допустимо преобразование из Orange в Fruit.

              Предположим, что входной аргумент будет ковариантен (параметр out):

              class Fruit {}
              
              class Orange : Fruit, IMagic<Orange>
              {
                  public void DoMagic(Orange smth) { Console.WriteLine("Hello from orange!"); }
              }
              
              interface IMagic<out T>
              {
                  void DoMagic(T smth);
              }
              
              static void Main(string[] args)
              {
                  // ковариация, записываем IMagic<Orange> в IMagic<Fruit>
                  // т.е. в прямом порядке к возможностям исходных
                  // Fruit и Orange (Orange o = new Fruit();)
                  IMagic<Fruit> magic = new Orange() as IMagic<Orange>;
              
                  magic.DoMagic(new Fruit());
              }
              

              Приведя Orange к IMagic<Fruit> (а это было бы возможно т.к. параметр типа ковариантен), есть возможность вызвать метод DoMagic и передать ему либо Fruit либо Orange (т.к. он приводим к Fruit). По факту будет вызыватся DoMagic, который требует Orange и передача ему Fruit вызовет ошибку времени выполнения.

              Обобщённые интерфейсы ковариантны по выходному значению и котнравариантны по входным аргументам начиная с .Net Framework 4.0. Поддержка для выходных значений контравариантности не типобезопасна. Поддержка для входных аргументов ковариантности также не типобезопасна. В C# поддерживается концепция максимальной типобезопасности (исключением являются массивы).
              • 0
                Спасибо за развернутый ответ, я Вас понял. По поводу передачи наследников — безусловно, но чтобы работать с конкретным ожидаемым типом надо делать приведение типа и хотелось, чтобы это делал компилятор. Понятно, что при этом нарушается типобезопасность и, признаться, даже не знаю, что лучше, делать as или пользоваться такими костылями, как ковариантность в параметре.

                А не могли Вы меня просветить, в языках с более «слабой» типобезопасностью ко- и контр-вариантность реализованы повсеместно?
                • 0
                  Не могу сказать, не ознакомлен. Знаю про C# в .Net Framework и написал всё что нужно в комментариях выше.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.