Привет, любители дженериков и типобезопасности.

Я давно хотел написать статью о Generics & Variance, но не мог начать. На эту тему уже написано так много замечательных статей и видео, что я не мог придумать, как добавить какую-то ценность. Но здесь я делаю попытку. Если вы эксперт, вы можете проверить содержимое ниже, или если вы новичок, вы можете просто получить несколько новых выводов. Давайте начнем.

Дженерики, какие они?

Концепция Generics была впервые применена в языке программирования под названием ML (Meta Language) в 1973 году. Этот подход позволил программистам писать общие функции, которые различаются только типами, с которыми эти функции работают. Это помогло уменьшить дублирование кода. Например:

// Standard ML
// A generic swap function
fun swap (y, x) = (x, y)

Здесь функция swap относится к типу 'a * 'b -> 'b * 'a. Этот, казалось бы, странный синтаксис используется для описания универсальных типов в ML и других похожих языках. 'a - это переменная типа, обозначающая любой возможный тип. Это может быть Int, Float, String или любой конкретный тип, определенный во время использования или создания экземпляра. Аналогичная функция в Java и Swift будет:

// Java
public <A, B> Pair<B, A> swap(Pair<A, B> pair) {
    return Pair.create(pair.second, pair.first);
}
// Swift
func swap<A, B>(_ pair: (A, B)) -> (B, A) {
    return (pair.1, pair.0)
}

Здесь Pair<A,B> во фрагменте кода Java - это общий тип, который может содержать любые два типа. A & B называются параметрами типа. До Generics нам нужно было бы написать IntPair, StringPair, int_swap, string_swap отдельно для каждого уникального типа.

Эти неопределенные параметризованные типы называются Generics в C #, Java, Rust, Swift, TypeScript и некоторых других. Они известны как Параметрический полиморфизм в таких языках, как ML, Haskell, Scala и Шаблоны в C ++.

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

Дженерики - как они работают под капотом?

Вот несколько преимуществ написания универсального кода:

  1. Более строгая проверка типов во время компиляции.
  2. Позволяет писать код, применимый ко многим типам с одинаковым базовым поведением. Например: List<T>.
  3. Оптимизированный код.

Проницательный читатель сразу же усомнится в третьем пункте в приведенном выше списке. Оптимизировано? В каком смысле? Этот момент требует некоторой корректировки. Его следует указать как оптимизированный байтовый код. Но давайте сначала разберемся с первыми двумя пунктами.

Рассмотрим эти два фрагмента кода ниже (на Java).

// Java
List<String> words = new ArrayList<>();
words.add("Hello ");
words.add("world!");
String s = words.get(0) + words.get(1);
System.out.println(s); // Hello World
// Java
List words = new ArrayList();
words.add("Hello ");
words.add("world!");
String s = ((String)words.get(0)) + ((String)words.get(1))
System.out.println(s); // Hello World

Эти фрагменты создают абсолютно идентичный байт-код. Фактически компилятор Java преобразует 1-й фрагмент кода, используя Generics, во 2-й фрагмент. Компилятор следит за тем, чтобы List<String> содержал только список String во время компиляции, поэтому мы не сталкиваемся с проблемами во время выполнения. Поскольку компилятор заботится об автоматическом преобразовании типов, он предотвращает любые ClassCastException, которые могут быть брошены во время выполнения. Таким образом повышается безопасность типов. Также существует вопрос о том, что List<T> читается как List of T. Для такого метода, как size() on List, все, что нам нужно, - это количество элементов, а не базовый тип этих элементов. Таким образом, лучшая абстракция, свободная от информации о конкретном типе. Эта уловка, используемая компилятором Java, называется Стирание типа.

Мономорфизация.

Есть еще один способ работы компиляторов с универсальным кодом. Их можно скомпилировать для создания отдельных специализированных версий общих функций. Запутались?. Возьмем очень простой пример на Rust.

// Rust
fn print_hash<T: Hash>(t: &T) {
    println!("The hash is {}", t.hash())
}
print_hash(&true);      // instantiates T = bool
print_hash(&12_i64);    // instantiates T = Int64

Компилятор Java будет иметь только одну копию функции print_hash, но компилятор Rust фактически создает две копии этой функции, по одной для каждого конкретного типа аргумента. В чем преимущество? Преимущество в том, что компилятор может оптимизировать код в соответствии с конкретным типом на картинке. Это означает, что любой вызов print_hash будет встроен в место вызова; прямой статический диспетчерский вызов соответствующей реализации, сохраняющий любое косвенное обращение при вызове функции. Это называется Мономорфизация - преобразование полиморфного кода в мономорфный код.

// Compiled Code
__print_hash_bool(&true);
__print_hash_i64(&12_i64);

Если преимущества кажутся минимальными, рассмотрите типы: Array<Bool> & Array<Int>. Компилятор создает специализированные копии: Array_Bool & Array_Int для Bool и Int соответственно. Компилятор теперь может разметить память в соответствии с размером Bool & Int, встроить их (когда это возможно) и сэкономить место. Каждый метод на Array аналогичным образом генерирует специализированный код, сохраняющий косвенное обращение к вызовам методов. Следовательно, общий код работает так же быстро и эффективно, как если бы вы вручную написали специализированный код. Как это для сравнения: ArrayList<Boolean> в Java, в зависимости от реализации, использует как минимум в 16 раз больше памяти, чем в Rust.

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

Безопасность универсального типа

Если вы добрались сюда, значит, вы уже знаете, что такое безопасность типов (время компиляции). Всегда хорошо ловить ошибки еще до запуска программы. Обобщения помогают нам писать безопасный для повторного использования код. Рассмотрим пример из книги Эффективная Java:

// Java
// 1
private final Collection stampsUntyped = ... ;
stampsUntyped.add(new Coin())

// 2
private final Collection<Stamp> stampsTyped = ... ;
stampsTyped.add(new Coin())
                    ^
                    Type Mismatch

Есть два способа создать коллекцию марок.

В 1 у нас есть необработанная коллекция, то есть она может содержать что угодно. Есть вероятность, что мы могли бы добавить к нему экземпляр класса Coin. Он будет успешно скомпилирован и выйдет из строя во время выполнения, когда мы получим stamp из коллекции.

В разделе 2 у нас есть Generic collection, где общий параметр определен как Stamp. Это хорошо. Это типобезопасный вариант. Мы не можем добавить экземпляр Coin в коллекцию штампов. Компилятор приходит нам на помощь и не дает скомпилировать этот код.

Представьте, что кто-то помещает java.util.Date экземпляр в коллекцию, которая должна содержать только java.sql.Date экземпляров. Параметризованные типы предотвратят это во время компиляции.

Если вы используете необработанные типы, вы теряете все преимущества безопасности и выразительности Generics.

___________________________________________________________________

Вопрос :
В чем разница между List и List<Object>?
(Не волнуйтесь, мы ответим на этот вопрос в ближайшее время.)

___________________________________________________________________

Подождите, нам всегда нужна безопасность типов?

Рассмотрим этот фрагмент кода (снова из Effective Java Book):

// Java
static int numElementsInCommon(Set s1, Set s2) {
    int result = 0;
    for (Object o1 : s1)
        if (s2.contains(o1))
            result++;
    return result;
}

Этот метод numElementsinCommon вычисляет количество общих элементов между двумя наборами. Нет необходимости делать эти входные Наборы универсальными, поскольку мы только получаем доступ и сравниваем элементы друг друга. Кажется, нам не всегда нужна безопасность типов.

Но можем ли мы сделать это лучше с помощью Generics? Если да, то лучше как?
Ответ - да, можем, используя подстановочный знак (?). Это НЕ вопросительный знак. В Java это называется подстановочным знаком.

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

Принцип подтипа и замены (SP)

Подтипирование должно показаться знакомой или известной территорией, и это действительно так. Это ключевая особенность объектно-ориентированных языков, таких как Java, которую мы используем слишком часто. Когда мы extend или implement определенный Тип, более конкретный тип (то есть дочерний / подтип) может поместиться в более крупный контейнер (то есть родительский / супертип). Например:

  • Целое число - это подтип числа.
  • Double - это подтип числа.
  • Строка - это подтип объекта.
  • String [] - это подтип Object [].
  • ArrayList - это подтип списка.

Здесь и далее мы будем обозначать A -> B как A is a subtype of B и A !-> B как A is NOT a subtype of B.

И Принцип замещения говорит:

Если S -> T, это означает, что любой термин типа S можно безопасно использовать в контексте, где ожидается термин типа T.

Теперь вы помните название этой статьи. Я знаю, что это долгий вопрос, но пора начать наш путь к самому интересному - Дисперсия. Давайте рассмотрим эту иерархию классов ниже для дальнейшего обсуждения. Все примеры будут на Java.

// Java
public class Animal {
    String name;
    int troubleMakerRating;
    
    Animal(String name) {
        this.name = name;
        this.troubleMakerRating = new Random().nextInt();
    }
}

public class Dog extends Animal {
    Dog(String name) {
        super(name);
    }
}

public class Cat extends Animal {
    Cat(String name) {
        super(name);
    }
}

Есть класс Animal. Dog & Cat расширьте Animal, потому что собака - это животное, а кошка это животное. У каждого Animal есть name и troubleMakerRating. Итак, в соответствии с принципом замещения (SP), если у нас есть коллекция Animals, можно добавить в нее экземпляр Dog или Cat:

List<Animal> animals = new ArrayList<Animal>();
animals.add(new Animal("Some Lion"));
animals.add(new Dog("German Shepherd"));
animals.add(new Cat("RagDoll"));

Здесь подтипы представлены в двух формах:
1. Добавление в список разрешено, потому что Dog/Cat is a subtype of Animal.
2. Операция присваивания разрешена, потому что ArrayList is a subtype of List.

Итак, если Dog -> Animal, ArrayList -> List кажется вполне разумным, что ArrayList<Dog> -> List<Animal>. Запишем это в коде:

List<Animal> animals = new ArrayList<Dog>();

Попробуйте скомпилировать приведенный выше фрагмент кода. Не будет. Компилятор выдает Incompatible Types. Компилятор не позволяет нам заменять List<Animal> на ArrayList<Dog>, потому что это небезопасно.

List<Animal> animals = new ArrayList<Dog>(); // Compilation ERROR !!
animals.add(new Cat("Birman"));

Если в первой строке не было ошибки компиляции, то в соответствии с принципом замены было бы допустимо добавить экземпляр Cat в список животных, который на самом деле является списком Dog, а кошки и собаки не подходят. Проблемы будут видны во время выполнения, когда мы анализируем список животных, думая, что все они собаки, но выскакивает кошка. Помните правило: Ошибка времени компиляции - это хорошо, ошибка времени выполнения - это плохо. Вот почему принцип замещения здесь не применяется. то есть ArrayList<Dog> !-> List<Animal>.

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

void printNames(Collection<Animal> animals) {
    animals.forEach(animal -> System.out.println(animal.name));
}
List<Dog> myDogs = new ArrayList<>();
myDogs.add(new Dog("German Shepherd"));
myDogs.add(new Dog("Bulldog"));
myDogs.add(new Dog("Pug"));

printNames(myDogs); // Compilation ERROR !! Incompatible Types

Функция printNames принимает список животных и печатает их имена. Итак, у нас должна быть возможность повторно использовать функцию для вывода имен из списка собак. В конце концов, функция printNames только обращается к животным из списка, а не пытается писать в него. Но работа компилятора - быть в безопасности, поэтому он выдает ошибки на printNames(myDogs). Над умным компилятором !!

А что, если нам нужно сравнить двух собак с помощью универсального компаратора для животных:

// 1
void printNameOfMostTroubleMakerDog(List<Dog> dogs,
                                    Comparator<Dog> comparator) {

    Dog maxTroubleMaker = dogs.get(0);
    for (int i = 1; i < dogs.size(); i++) {
        if (comparator.compare(maxTroubleMaker, dogs.get(i)) > 0) {
            maxTroubleMaker = dogs.get(i);
        }
    }
    System.out.println(maxTroubleMaker.name 
            + " is the most trouble making Dog.");
}
// 2
Comparator<Animal> troubleMakerComparator = Comparator.comparingInt(animal -> animal.troubleMakerRating);
// 3 - Compilation ERROR !! Incompatible Types
printNameOfMostTroubleMakerDog(myDogs, troubleMakerComparator)
  1. printNameOfMostTroubleMakerDog берет список собак и печатает название собаки, вызывающей наибольшие проблемы, на основе входного компаратора.
  2. Мы создаем многоразовый troubleMakerComparator, который сравнивает рейтинг нарушителей порядка каждого животного.
  3. Он не компилируется, потому что printNameOfMostTroubleMakerDog ожидает Comparator<Dog>, но мы передаем Comparator<Animal>.

Компилятор должен был это позволить. Если Comparator<Animal> может сравнивать двух животных, он определенно может сравнивать двух собак.

Теперь возникает вопрос: если мы знаем, что некоторые из замен, подобных приведенным выше, безопасны, не можем ли мы передать это и компилятору? Если бы на каждый вопрос был дан ответ «Нет», в этой статье не было бы нужды. 😛
Не забывайте подстановочные знаки (?). Да, мы собираемся их использовать сейчас.

Дисперсия

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

Есть четыре возможных варианта:

  • Ковариация: сохраняет порядок отношений подтипов. т.е.
    если A -> B, то Box<A> -> Box<B>
  • Контравариантность: меняет порядок следования подтипов. т.е.
    если A -> B, то Box<B> -> Box<A>
  • Двувариантность: если применимы оба вышеперечисленного. т.е.
    если A -> B, то Box<A> -> Box<B> & Box<B> -> Box<A>
  • Инвариантность: ни Ковариация, ни Контравариантность не применимы.

Чтобы решить проблему подстановки, с которой мы столкнулись при использовании printNames & printNameOfMostTroubleMakerDog, мы будем использовать ковариацию и контравариантность соответственно.

Ковариация

Если каким-то образом ArrayList<Dog> становится подтипом List<Animal>, printNames функция становится повторно используемой для любого списка, который содержит типы, расширяющие Animal. Вот как мы это делаем:

void printNames(Collection<? extends Animal> animals) {
    ...
}

printNames(myDogs); // Compiles cleanly

Теперь printNames(myDogs); проверяет типы и компилирует. Обратите внимание на изменение подписи. printNames больше не принимает Collection<Animal>, а Collection<? extends Animal>. Когда мы используем ? extends, мы в основном сообщаем компилятору, что набор элементов, тип которых имеет верхнюю границу с Animal, принимается функцией printNames.

Это делает две вещи:

  1. Это составляет List<Dog> -> Collection<Animal>. Это называется ковариацией.
  2. И внутри printNames мы можем НЕ добавлять какие-либо элементы в коллекцию, но мы можем анализировать или получать доступ к элементам вне списка. Мы не можем добавить, потому что возможно, что этот список может быть списком собак (однородный список) или списком некоторых животных (разнородный список). Поскольку мы не уверены, что такое базовый список, компилятор не разрешает никаких добавлений в коллекцию.

Мы также можем использовать подстановочные знаки при объявлении переменных. Бывший:

1|  List<Dog> dogs = new ArrayList<Dog>();
2|  dogs.add(new Dog("PitBull"));
3|  dogs.add(new Dog("Boxer"));
4|  List<? extends Animal> animals = dogs;
5|  animals.add(new Cat("Sphynx Cat")); // Compilation ERROR !!

Без ? extends 4-я строка вызвала бы ошибку компиляции, потому что List<Dog> !-> List<Animal>, но пятая сработала бы, потому что Cat -> Animal. С ? extends 4-я строка компилируется, потому что теперь List<Dog> -> List<Animal>, но 5-я не компилируется, потому что вы не можете добавить Cat к List<? extends Animal>, так как это может быть список другого подтипа Animal.

Другой способ понять: когда мы extend, существует по крайней мере тип с верхней границей, поэтому мы знаем, какой тип мы получаем из коробки. Так что GET разрешен, потому что это самый безопасный вариант для компилятора.

Общее полезное правило:
если структура содержит элементы с типом формы ? extends E, мы можем ПОЛУЧИТЬ элементы из структура, но мы НЕ МОЖЕМ ВСТАВИТЬ в нее элементы.

Контравариантность

Точно так же, чтобы решить проблему с компаратором, мы изменяем функцию printNameOfMostTroubleMakerDog, чтобы включить подстановочный знак и сделать ее ? super Dog. то есть:

void printNameOfMostTroubleMakerDog(List<Dog> dogs,
                               Comparator<? super Dog> comparator) {
    ...
}
...
// Compiles Cleanly
printNameOfMostTroubleMakerDog(myDogs, troubleMakerComparator);

Теперь printNameOfMostTroubleMakerDog(myDogs, troubleMakerComparator) проверка типов. ? super Dog означает любой тип, нижняя граница которого - Dog, то есть любой тип, являющийся супертипом Dog. Итак, Animal и Object являются здесь допустимыми типами. Это также делает Comparator<Animal> подтипом Comparator<Dog> для этого метода. Это Контравариантность. Здесь должно быть какое-то следствие из принципа GET-PUT, который мы видели выше, и на самом деле он есть. Теперь мы можем ПОСТАВИТЬ элементы внутри такой структуры, но не можем ПОЛУЧИТЬ элементы, если это так. Для этого нам понадобится другой пример.

public static void add_N_DogsTo(List<? super Dog> someList,
                                 int count) {
    if (count == 0)
        return;

    for (int i = 0; i < count; i++)
        // Adding to the list is allowed
        someList.add(new Dog("Stray Dog " + i ));
    // Reading from the list is NOT allowed. Compilation ERROR !!                                     
    Animal d = someList.get(0); 
}

Если у нас есть функция для добавления 'N' собак в некоторый список, нижняя граница которого равна Dog, добавление разрешено, а чтение из списка - нет. Это связано с тем, что во время PUT у нас есть конкретный тип, который мы можем добавить, но во время команды GET мы никогда не сможем узнать тип выходного объекта. Это может быть Animal или Object.

Примечание: Object d = someList.get(0); работает, потому что в Java все расширяет Object. Так что всегда есть верхняя граница.

Другой способ понять это: когда мы super, существует по крайней мере тип с нижней границей, поэтому мы знаем, какой наименьший тип мы можем поместить в поле. Так что PUT разрешен, потому что это самый безопасный вариант для компилятора.

Общее полезное правило:
Если структура содержит элементы с типом формы ? super E, мы можем ВСТАВИТЬ элементы в структуру, но мы МОЖЕМ НЕ ПОЛУЧАТЬ элементы из него.

Уф .. Это было много, правда? Это было, но это все, ребята. Прежде чем мы расстаемся, давайте просто ответим на два вопроса, которые мы оставили висеть выше.

1). В чем разница между List и List<Object>?

  • List отказался от проверки общего типа, где List<Object> явно сообщил компилятору, что он способен хранить элементы типа Object, который в основном является всем в Java. Как это помогает? Прочтите следующий пункт:
  • List list = new List<String> возможно, но
    List<Object> list = new List<String> НЕ. Потому что универсальные шаблоны в Java инвариантны по причинам, уже обсуждавшимся в разделе «Принцип подтипов и подстановки».

2). Как улучшить следующий фрагмент кода, используя универсальные шаблоны, в которых безопасность типов не имеет значения?

// Java
static int numElementsInCommon(Set s1, Set s2) {
    int result = 0;
    for (Object o1 : s1)
        if (s2.contains(o1))
            result++;
    return result;
}

Чтобы повторить то, что я сказал выше, нам не нужно делать здесь общие наборы (т.е. Set<T>), потому что это только сравнение их элементов. Но что, если мы добавим сюда подстановочный знак:

// Java
static int numElementsInCommon(Set<?> s1, Set<?> s2) {
    int result = 0;
    for (Object o1 : s1)
        if (s2.contains(o1))
            result++;
    return result;
}

Что нам дает добавление подстановочного знака ?. Чем Set и Set<?> отличаются?
Мы действительно сделали эту функцию более безопасной в использовании. При использовании Set мы можем поместить любой элемент внутрь функции и изменить его содержимое, но поскольку универсальные шаблоны инвариантны в Java, компилятор запрещает нам добавлять что-либо внутри Set<?>. Это не значит, что мы не можем вызывать set.removeAll() или set.pop() внутри функции и не изменять ее содержимое. Также мы можем добавить null в коллекцию Set<?>. Но любая безопасность всегда выгодна.

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

Спасибо, что прочитали, ребята. Поделитесь 🗣 в своих кругах и аплодируйте 👏🏻 Если вам понравилось.

Если у вас есть какие-либо вопросы или у вас есть что добавить или исправить в этой статье, не стесняйтесь помещать их (без каламбура) в комментарии, и я верну вам (опять же, без каламбура 😛) как можно скорее .

Подпишитесь на Androidiots, чтобы увидеть больше такого потрясающего контента.