Обобщенное программирование – обзор реализаций

В большинстве сильно типизированных языков поддерживается обобщенное программирование. Круг проблем, которые решаются на этих языках, один и тот же, но сами проблемы решались в разное время разными способами, и у каждого из этих способов были свои «за» и «против». Мы рассмотрим историю реализаций обобщенного программирования, чтобы вы могли распробовать его как инженер. Наилучшего подхода не существует, любой подход – это всегда компромисс, при котором одними преимуществами жертвуют ради других. Мы рассмотрим три популярных языка, обогативших нашу индустрию новыми подходами: C++, Java, C#(.Net). Для каждого из рассматриваемых языков мы ответим на следующие вопросы:

• Как дженерики на самом деле работают под капотом?

• Как происходила миграция на дженерики?

• Вариантность.

• «За» и «Против».

Если у вас не так много опыта работы с обобщенным программированием в целом – почитайте это введение в обобщенное программирование.

Не стану сравнивать языки в попытках понять, какой из них лучше – на самом деле, все они отличные! Здесь я хочу показать, как различные предусловия (дизайн языка и среды выполнения, экосистема и даже рыночная конкуренция) повлияли на то, как именно дженерики были реализованы в разных языках.

C++

В C++ разработчик контролирует все аспекты использования памяти: можно выделять объекты в стеке или куче, именно вы отвечаете за высвобождение памяти, вы даже можете сами разработать собственный инструмент для выделения памяти из кучи. Решения о том, как будет выделяться память, принимаются прямо на месте использования:

class Product {
    private:
        double price;
    public:
        Product(double price): price(price) { }
        void printPrice() {
            std::cout << "my price is " << price << "\n";
        }
    };
 
   int main()
   {
        Product stackAllocatedProduct(1.5);
        stackAllocatedProduct.printPrice();
        Product* heapAllocatedProduct = new Product(2.5);
        heapAllocatedProduct->printPrice();
        return 0;
    }

В C++ методы вызываются двумя разными способами. Если метод объявляется при помощи ключевого слова virtual, то вызов его осуществляется через таблицу виртуальных методов. Другие методы вызываются напрямую, то есть, компилятор вставляет вызов функции прямо в машинный код, указывая адрес этой функции.

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

Для поддержки обобщенного программирования в C++ используется возможность под названием Template, добавленная в язык давным-давно – в 1986 году.

namespace generic {
    template <typename T>
    T max(T first, T second) {
        if (second > first) {
            return second;
        }
        return first;
    }
}

Под капотом

Слово Template («шаблон») позволяет понять, как именно данная языковая возможность работает под капотом. Реализованная функция служит просто шаблоном для компилятора, который генерирует новые функции для шаблона любого типа, какой применяется с этим компилятором.

Так, если воспользоваться функцией max таким образом:

cout << "int " << generic::max(1, 2) << ", char " << generic::max('a', 'b');

то компилятор сгенерирует 2 функции: для типов int и char.

template<> int max<int>(int first, int second) {
    if (second > first) {
        return second;
    }
    return first;
}
template<> char max<char>(char first, char second) {
    if (second > first) {
        return second;
    }
    return first;
}

Миграция на дженерики

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

Шаблоны как языковая возможность не ломают имеющегося кода; если вы перекомпилируете ваш код с помощью компилятора, поддерживающего шаблоны, то он и после этого должен работать. Основная проблема при миграции заключается в том, как перенести библиотеки, чтобы они могли работать как со старыми, так и с новыми компиляторами. К счастью, в старые добрые времена разработчики не очень хорошо умели переиспользовать код. В 1992 году состоялся первый релиз STL (стандартной библиотеки шаблонов), где использование обобщенного кода было необходимым. А библиотечный код основан на шаблонах. Поэтому мне кажется, что миграция никогда не представляла особенной проблемы.

Преимущества

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

Кроме того, шаблоны очень гибкие. Внутри шаблона можно использовать попросту что угодно; код будет работать, если приспособлен для работы с шаблонным параметром.

Недостатки

Но шаблоны не очень популярны в мире C++. Многие разработчики не пользуются этой возможностью, так как у шаблонов слишком много недостатков:

• Шаблоны замедляют компиляцию;

• При работе с ними компилятор выдает совершенно бесполезные сообщения об ошибках;

• Переиспользовать двоичный файл дженерика нельзя – можно только исходный код;

• Пока не попробуешь – не знаешь, будет ли работать обобщенный код;

• Код разбухает.

Разбухание кода (code bloat) – это ситуация, когда после компиляции у вас получается гораздо более крупный исполняемый файл, чем вы ожидали. Всякий раз, применяя новый обобщенный параметр, вы получаете новый сгенерированный класс или функцию, их код хранится на диске и должен загружаться в оперативную память во время выполнения  .

Вариантность

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

Но со времен C++ 17 библиотека std поддерживает ко- и контравариантность при помощи функции std::function. Производители функций ковариантны, а потребители функций – контравариантны.

Java

Система типов Java основана на ссылочных и значимых типах. Любой объект – это ссылочный тип, он выделяется в куче, а работаете вы с ним по ссылке. Значимые типы – это примитивы данных, выделяемые в стеке (локальная переменная) или в куче (поле класса). В Java существует всего 8 значимых типов: byte, short, int, long, float, double, char и boolean. Поэтому, работая с Java, вы большую часть времени работаете со ссылочными типами. Разработчики могут только лишь выделять объекты. Как именно выделяются объекты, и как память от них высвобождается – зависит от среды выполнения. Код Java компилируется в байт-код Java, который интерпретируется виртуальной машиной Java (JVM) на действующем устройстве.

В первом релизе Java дженерики еще не поддерживались. Как люди жили без дженериков? Можно приводить объекты к одному и тому же базовому классу или интерфейсу, а потом передавать их к функции.

static Comparable unsafeMax(Comparable first, Comparable second) {
    if (second.compareTo(first) > 0) {
        return second;
    }
    return first;
}

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

Под капотом

Дженерики в Java реализовывались с расчетом на использование во время компиляции: в байт-коде дженериков нет. На уровне байт-кода работа идет просто с Object. Но при использовании дженериков компилятор проверяет типы, поэтому вам не требуется заниматься явным их приведением. Процесс, при котором компилятор не оставляет среде исполнения никакой информации о дженериках, называется  стиранием типов.

static <T extends Comparable<T>> T max(T first, T second) {
    if (second.compareTo(first) > 0) {
        return second;
    }
    return first;
}

static void main(String[] args) {
    Integer first = 5;
    Integer second = 7;
    Integer dangerResult = (Integer) unsafeMax(first, second);
    Integer result = max(first, second);
}

В примерах выше у нас 2 реализации функции max: обобщенная (max) и необобщенная (unsafeMax). Как видите, на уровне байт-кода Java Bytecode они одинаковые.

Если при виде такого байт-кода Java вам становится страшно, изучите его по следующему 47-минутному видео на youtube.

Вот как функция max вызывает Comparable<T>.compareTo:

static max(Ljava/lang/Comparable;Ljava/lang/Comparable;)Ljava/lang/Comparable;
    ALOAD 1
    ALOAD 0
    INVOKEINTERFACE java/lang/Comparable.compareTo (Ljava/lang/Object;)I (itf)

А вот как unsafeMax вызывает Comparable.compareTo:

static unsafeMax(Ljava/lang/Comparable;Ljava/lang/Comparable;)Ljava/lang/Comparable;
    ALOAD 1
    ALOAD 0
    INVOKEINTERFACE java/lang/Comparable.compareTo (Ljava/lang/Object;)I (itf)

А вот как они вызываются в функции main:

L2
    ALOAD 1
    ALOAD 2
    INVOKESTATIC Main.unsafeMax (Ljava/lang/Comparable;Ljava/lang/Comparable;)Ljava/lang/Comparable;
    CHECKCAST java/lang/Integer
    ASTORE 3
L3
    ALOAD 1
    ALOAD 2
    INVOKESTATIC Main.max (Ljava/lang/Comparable;Ljava/lang/Comparable;)Ljava/lang/Comparable;
    CHECKCAST java/lang/Integer
    ASTORE 4
L4

На уровне байт-кода – никакой разницы.

Миграция на дженерики

Дженерики как отдельная возможность появились в релизе Java 5 в сентябре 2004 года. К тому времени язык Java существовал уже более 8 лет. Много (реально, очень много!) кода было написано с тех пор, как язык Java стал популярен.

Компания Sun не контролировала ни всех, ни даже большинства библиотек в экосистеме Java, поэтому было понятно, что на миграцию потребуется определенное время, и миграция всех библиотек одновременно не произойдет. Например, если вы – разработчик библиотеки, то некоторые пользователи библиотеки обновятся до новой Java и захотят, чтобы вы предоставили обобщенный API. Другие же пользователи заняты разработкой колоссального приложения, и на обновление этого приложения до новой Java потребуются годы, но и эти пользователи хотят получать от вас патчи и усовершенствования. Если нужно поддержать все вышеупомянутые возможности в одной библиотеке, то именно миграционная возможность становится первым ограничением по требованиям:

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

 Чтобы добиться совместимости с уже написанным необобщенным кодом, инженеры Sun реализовали дженерики через стирание типов и добавили в качестве еще одной возможности сырые типы.

При помощи сырых типов разработчики могут использовать обобщенный код так, как будто он необобщенный. Например, ArrayList вместо ArrayList<T> будет трактоваться компилятором как ArrayList<Object>.

Среда выполнения Java (JRE) поставляется в комплекте с множеством полезных пакетов. Многие встроенные классы были переписаны с расчетом на предоставление обобщенного API, например, ArrayList стал ArrayList<T>.

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

Подробнее о том, почему Sun остановилась на стирании типов, написано в блоге Нила Гафтера.

Вариантность

Java поддерживает вариантность на уровне языка при помощи так называемых масок (wildcards).

Чтобы воспользоваться инвариантностью, укажите неограниченную маску, например, T<?>. Это значит, что о типе можно не беспокоиться, а использовать обобщенный объект точно как обычный Object:

static void printItems(List<?> list) {
    for (Object item : list) {
        System.out.println(item);
    }
}

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

class A {}
class B extends A {}
class C extends B {}
class D extends B {}

Если вы хотите использовать ковариантность, то должны указать верхнюю границу, например, extends T:

List<? extends B> listOfB;
listOfB = new ArrayList<C>(); // нормально
listOfB = new ArrayList<D>(); // нормально
listOfB = new ArrayList<A>(); // ошибка компиляции

У List есть много методов, некоторые из них производят, а другие потребляют обобщенные значения. Когда вы указываете  extends T, вы можете использовать только производители методов:

B b = listOfB.get(0); // нормально
listOfB.add(new B()); // ошибка компиляции

Если вы хотите использовать контравариантность, то должны указать нижнюю границу, например, super T:

List<? super B> listOfB;
listOfB = new ArrayList<A>(); // нормально
listOfB = new ArrayList<C>(); // не скомпилируется

Указав super T, вы можете использовать только потребители методов:

listOfB.add(new D()); // нормально
B b = listOfB.get(0); // не скомпилируется

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

За

Как вы помните, со всеми недостатками шаблонов C++, упомянутыми нами выше, удалось справиться. Компилятор производит только одну функцию или класс для всех возможных обобщенных параметров, в то время как все обобщенные типы являются Object, так что:

• Вы можете использовать обобщенный код из двоичных файлов (байт-кода);

• Сообщения об ошибках компиляции поступают не из сгенерированного кода, поэтому они понятны;

• Поддержка ко- и контравариантности;

• Легкость валидации: если код работает с одним типом, то будет работать и со всеми остальными.

Против

Но сохраняются и некоторые недостатки.

• Обобщенный код работает только со ссылочными типами. Таким образом, вы не сможете использовать Map<integer>, а только Map<Integer>. Т.e., чтобы передать integer в обобщенный код, вам нужно заключить в рамки объект Integer;

• Обобщенные параметры недоступны во время выполнения по причине стирания типов;

• Этот пункт по-своему следует из предыдущего, но его стоит упомянуть в ряду недостатков. Массивы плохо сочетаются с дженериками. Например, нельзя создать обобщенный массив вида  new E[];

Что касается использования значимых типов и материализованных дженериков, должен упомянуть, что большая часть нашей индустрии (имею в виду бекенд-разработку, где язык  Java исключительно популярен) в самом деле, не страдает от их отсутствия. Но есть те, кто страдают. Есть проект valhalla – это эксперимент, призванный привнести значимые типы и материализованные дженерики в Java. Подробнее об этом можно почитать в данной статье.

И добавлю еще несколько слов о массивах и дженериках. Массивы в Java ковариантны, и все проверки типов происходят во время выполнения:

Object[] objectArray = new Long[1];
objectArray[0] = "secretly I'm a String"; // Выбрасывает ArrayStoreException

Нельзя создавать массивы вроде new E[], так как массивы проверяются во время исполнения, а с дженериками используется стирание типов. Oracle не удалось изменить массивы в Java 5, поэтому в Java плохо смешивать массивы с дженериками. Подробнее об этом рассказано в книге Джошуа Блоха «Эффективное программирование на Java».

C# (.Net)

Язык C# похож на Java, но это не случайно, и у их сходства есть своя история. В начале 2000-х одним из основных продуктов Microsoft была операционная система Windows. Легко вообразить, насколько можно было бы поднять производительность труда разработчиков при помощи комбинации язык + среда выполнения, как в Java, а также одновременно повысить качество программ для Windows. А еще Microsoft хотела внедрить более качественную интеграцию с ОС Windows. Поэтому они взялись менять JVM, и компании Sun (к тому времени уже приобретенной Oracle) это не понравилось, поэтому она стала запрещать изменения, вносимые Microsoft. Тогда Microsoft решила создать свою собственную платформу. К тому времени уже были очевидны все недостатки Java и ошибки, допущенные при его проектировании, поэтому Microsoft попробовала исправить их в зародыше. Подробнее о том, почему Microsoft создала C#.

Система типов C# позволяет разработчику создавать одновременно и собственные значимые (struct), и собственные ссылочные (class) типы. Значимые типы могут выделяться в стеке или куче, а ссылочные – только в куче. Среда выполнения .Net, именуемая CLR, отвечает за выделение и очистку памяти. Компилятор C# производит промежуточный язык (IL), который затем компилируется в машинный код на работающем устройстве.

C# поддерживает дженерики, начиная с версии 2.0 – то есть, с сентября 2005 года, 3 года спустя после выхода C# 1.0.

public static T max<T>(T first, T second) where T: IComparable<T> {
    if (second.CompareTo(first) > 0) {
        return second;
    }
    return first;
}

public static void Main() {
    var maxValue = max(3, 4);
}

Под капотом

У Microsoft не было особого выбора, учитывая поддержку собственных значимых типов и вскрывшихся недостатков стирания типов в Java – им пришлось поддерживать дженерики во время выполнения. И они это сделали.

(полная версия следующего кода на промежуточном языке приведена на .Net fiddle):

.method public hidebysig static !!T  max<(class [mscorlib]System.IComparable`1<!!T>) T>(!!T first,
                                                                                          !!T second) cil managed
  {
    IL_000a:  callvirt   instance int32 class [mscorlib]System.IComparable`1<!!T>::CompareTo(!0)

После компиляции получаем на промежуточном языке код, в котором относительно дженериков действительно все то же, что и в C#.

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

Все оптимизации применяются на уровне генерации машинного кода. В большинстве случаев приходится работать со ссылочными типами. Под капотом все ссылки относятся к одному и тому же типу данных; это адрес в памяти, то есть, просто число. Таким образом, CLR генерирует одну обобщенную реализацию для всех ссылочных типов. Работает как и в Java, но на уровень ниже, там, где находится машинный код.

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

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

Миграция на дженерики

Как и в языках Java и C++, дженерики (как языковая возможность) не ломают существующий код, поэтому основную сложность здесь представляет неодновременная миграция библиотек и приложений на ту версию языка, что поддерживает дженерики.

Microsoft предоставила большую часть инфраструктуры и “готовые” решения, поэтому для C#-разработчиков миграция на сторонние библиотеки не была первоочередной задачей. Поэтому Microsoft могла себе позволить делать коренные изменения прямо во время выполнения. Миграция библиотек происходила без коренных изменений, были добавлены новые API с поддержкой дженериков.

var notGenericList = new System.Collections.ArrayList();
var genericList = new System.Collections.Generic.List<object>();

Вариантность

C# поддерживает как ко- так и контравариантность с применением вариантности на месте объявления. Есть 2 ключевых слова: in и out , помечающих обобщенные параметры как контра- и ковариантные. Давайте опробуем их, переписав примеры из объяснений ковариантности и контравариантности.

class Flower {  }
class Rose: Flower { }
class Daisy: Flower { }

interface FlowerShop<out T> where T: Flower {
    T getFlower();
}

class RoseShop: FlowerShop<Rose> {
    public Rose getFlower() {
        return new Rose();
    }
}

class DaisyShop: FlowerShop<Daisy> {
    public Daisy getFlower() {
        return new Daisy();
    }
}

Обобщенные параметры в FlowerShop<T> помечены как out. Это значит, что FlowerShop<T> может производить лишь значения типа T, то есть, тут можно без опаски использовать ковариантность:

static FlowerShop<Flower> tellMeShopAddress() {
    return new RoseShop();
}

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

interface PrettyGirl<in TFavoriteFlower> where TFavoriteFlower: Flower {
    void takeGift(TFavoriteFlower flower);
}

class AnyFlowerLover: PrettyGirl<Flower> {
    public void takeGift(Flower flower) {
        Console.WriteLine("I like all flowers!");
    }
}

Поэтому здесь безопасно использовать контравариантность:

PrettyGirl<Rose> girlfriend = new AnyFlowerLover();
girlfriend.takeGift(new Rose());

Вариантность поддерживается на уровне CLR: общеязыковая среда выполнения CLI поддерживает ковариантность и контравариантность обобщенных параметров, но только в сигнатурах интерфейсов и классов-делегатов.

Достоинства

C#, как и многие языки до него, пытался устранить недостатки предшественников. Предшественником, а также основным конкурентом C# был Java, поэтому разработчики C# приложили массу усилий, чтобы решить присущие Java проблемы с устройством дженериков:

• Обобщенный код доступен для всех значимых типов;

• Некоторые считают, что вариантность на месте объявления лучше, чем на месте использования;

• Обобщенные типы являются материализуемыми, т.e. тип обобщенного параметра доступен во время выполнения.

Другая серьезная причина, по которой .Net поддерживает значимые типы в обобщенном коде – это работа со struct. Было бы очень странно разрешать пользователю создавать собственные значимые типы, но не разрешать использовать struct в обобщенном коде.

Недостатки

• При работе со значимыми типами код может разбухать;

• Некоторые считают, что вариантность удобнее применять на месте использования;

Заключение

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

C++ дает разработчику полную свободу в управлении памятью, генерация кода как подход – это обычное дело при разработке на C и C++. Поэтому я считаю, что шаблоны по-настоящему хороши именно при работе с  C++: они быстрые (только во время выполнения), их легко понять, а подход к ним в С++ наиболее гибок в сравнении с аналогичными подходами из других рассмотренных языков.

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

Дженерики в C# (.Net), как и сам язык – самые «молодые» из всех. Чтобы преуспеть в сфере, где некая проблема уже решена, необходимо решать ее гораздо лучше, чем конкуренты. Прямым конкурентом C# является Java. Создатели C# максимально постарались сделать свой язык привлекательным. Поэтому дженерики у них получились своеобразными, не такими, какие рассчитаны на работу с моделью памяти, применяемой в Java и библиотечной экосистемой Java.

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

Обязательно обратите внимание на весеннюю распродажу.