Дженерики что это программирование

Модели дженериков и метапрограммирования: Go, Rust, Swift, D и другие

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

Я считаю дженерики интересным вариантом, потому что они являются простым частным случаем общей задачи метапрограммирования: написания программ, способных генерировать классы других программ. В доказательство я покажу, как три разных и абсолютно общих метода метапрограммирования могут считаться разнонаправленными расширениями в пространстве систем дженериков: динамических языков вроде Python, процедурных систем макросов вроде Template Haskel и поэтапной компиляции вроде Zig и Terra.

Обзор

Я нарисовал блок-схему всех описанных в статье систем, чтобы вы представляли её содержимое и как взаимосвязаны эти системы:

Основные идеи

Допустим, мы пишем на языке без систем дженериков, и хотим сделать структуру данных стека дженериков (generic stack data structure), которая работает с данными любых типов. Проблема в том, что каждая функция и определение типа будет работать только с данными одного размера и скопированными одним способом, и, в целом, работающими похоже.

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

Упаковка означает складывание всего подряд в унифицированные «коробки», которые работают одинаково. Обычно это делают так: данные кладут в кучу (heap), а указатели на них размещают в структуре данных. Можно сделать указатели на все типы, которые будут работать одинаково, так что один и тот же код будет работать с данными любых типов! Однако это приводит к повышению потребления памяти, динамическому поиску и промахам кэша. В языке С это соответствует тому, что ваша структура данных хранит указатели void* и просто кэширует данные в и из void* (если данные не в куче, он их там размещает).

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

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

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

Упаковка

Начнём с примера базовой упаковки в Go:

Также упаковка используется в C ( void* ), Go ( interface<> ), до-дженериковой Java ( Object ) и до-дженериковом Objective-C ( id ).

Упакованные дженерики с затиранием типов

У основного метода упаковки есть недостатки:

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

Выведенные упакованные дженерики с унифицированным представлением

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

Приведённый тип можно назвать «функцией из списка элементов типа ‘a во что-то с типом ‘a ». Это обозначает, что возвращаемый тип будет таким же, как тип списка, и при это может быть любым типом.

Интерфейсы

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

Интерфейсные таблицы виртуальных методов

Если мы хотим предоставлять функции, специфические для типов, придерживаясь стратегии упаковки ради унифицированной работы со всем подряд, то достаточно иметь унифицированный способ находить подобные функции, которые нам нужно получить от объекта. Такой подход называется «таблицами виртуальных методов» (vtables, virtual method tables), хотя никто не пользуется полным названием. Он реализован так: на нулевом смещении в каждом объекте дженерик-структуры расположен указатель на таблицы указателей функций с консистентной схемой. В этих таблицах дженерик-код ищет указатели на функции, специфические для типов, индексируя определённые указатели на фиксированных смещениях.

Так реализованы типы interface в Go и объекты dyn trait в Rust. Когда вы приводите тип к интерфейсному типу того, что он реализует, для интерфейса создаётся обёртка, содержащая указатель на исходный объект и указатель на vtable функций, специфических для типов. Но для этого требуется дополнительный уровень косвенной адресации указателей и другая схема. Поэтому сортировка в Go использует интерфейс для контейнера с методом Swap, а не берёт слайс интерфейса Comparable, потому что это потребовало бы размещения в памяти совершенного нового слайса интерфейсных типов, который сортировался бы вместо исходного слайса!

Объектно-ориентированное программирование

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

Кроме предоставления дополнительных возможностей, встраивание vtable в каждый объект решает проблему необходимости конструировать новые интерфейсные типы с косвенной адресацией (indirection). В отличие от Go, в Java функция сортировки может применять интерфейс Comparable к типам, которые она реализует.

Рефлексия

Если у вас есть таблицы виртуальных типов, то вам не будет сложно заставить компилятор генерировать и таблицы других типов информации, например, имён полей, типов и мест (locations). Это позволит обращаться ко всем данным этого типа с помощью кода, который может просматривать все данные любых других типов. Такое поведение можно использовать для добавления в язык «рефлексии», позволяющей реализовать сериализацию и красивое отображение произвольных типов. У рефлексии, как у расширения парадигмы упаковки, есть недостаток: для неё достаточно лишь одной копии кода, но при этом нужно выполнять много динамических поисков, что снижает скорость сериализации.

Языки, использующие рефлексию для сериализации и прочих функций: Java, C# и Go.

Динамически типизированные языки

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

Вы можете сказать: «Но ведь динамические языки работают не так, они просто реализуют всё с помощью хэш-таблиц!». Хэш-таблицы — лишь хорошая структура данных для создания редактируемых таблиц с информацией о типах. К тому же так работают некоторые интерпретаторы, например, CPython. В высокопроизводительном JIT, скажем, V8, много таблиц виртуальных типов и информации о рефлексии (reflection info). В V8 скрытые классы (vtables и информация о рефлексии) и структура объектов аналогичны тем, что вы можете увидеть в Java VM, с возможностью заменять объекты новыми таблицами виртуальных типов в ходе исполнения. Это не совпадение, потому что совпадений не бывает: создатель V8 раньше работал над высокопроизводительной Java VM.

Передача словаря

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

Такой подход используется в классах типов (type classes) в Haskell, хотя GHC позволяет с помощью инлайнинга и специализации выполнять какую-то мономорфизацию. В OCaml используется передача словаря с явным аргументом в виде модулей первого класса, но уже предложено добавить возможность сделать параметр неявным.

Witness-таблицы в Swift

Авторы Swift применили интересное решение: передача словаря, а также помещение в таблицу данных о размерах типов и способах их перемещения, копирования и освобождения позволяет предоставлять всю необходимую информацию для унифицированной работы с любыми типами без их упаковки. Таким образом Swift может реализовывать дженерики без мономорфизации и размещения в памяти в унифицированном представлении всех сущностей! Да, приходится расплачиваться за динамические поиски, как это свойственно всему семейству, использующему упаковку, на зато экономятся ресурсы на размещение в памяти, её потребление и непоследовательность кэша. Компилятор Swift также умеет с помощью функций, аннотированных как @inlinable, специализировать (мономорфизировать) и инлайнить дженерики внутри модуля или между модулями, чтобы избежать упомянутых расходов. Вероятно, применяется эвристическая оценка влияния на размер кода.

Это также объясняет, как Swift может реализовать ABI-стабильность, при этом позволяя добавлять и перераспределять поля в структуре, хотя авторы предоставляют атрибут @frozen для отказа от динамического поиска ради повышения производительности.

Интенсиональный анализ типов (Intensional Type Analysis)

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

Я не предостерегаю от использования языков, использующих этот подход, но похожим образом действуют компиляторы С++ и виртуальные машины Java, когда с помощью оптимизации на основе профилей выясняют, что определённое место вызова дженериков по большей части работает с объектами определённых типов. Компиляторы и ВМ заменяют места вызова проверками на каждый обычный тип, а затем статически деспетчеризируют эти типы, в качестве запасного варианта используя обычную динамическую диспетчеризацию. Поэтому алгоритм предсказания ветвления может прогнозировать, по какой ветке пойдёт код, и продолжит диспетчеризировать инструкции с помощью статических вызовов.

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

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

Генерирование исходного кода

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

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

Строковые миксины в D

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

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

Процедурные макросы Rust

Аналогичный пример, только с представлением в компиляторе лишь на одном этапе. Процедурные макросы Rust используют в качестве входных и выходных данных потоки токенов (token streams), предоставляя утилиты для преобразования этих потоков в строковые и обратно. Преимущество этого подхода в том, что потоки токенов могут сохранять информацию из исходного кода о расположениях. Код, написанный пользователем, макрос может вставлять в виде токенов напрямую из входных данных в выходные. И если этот код приведёт к ошибке компилирования в выходных данных макоса, компилятор выведет сообщение и точно укажет на файл, строку и колонку сломанной части кода. Но если сломанный код макрос генерирует, то сообщение об ошибке укажет на вызов макроса. Например, если вы используете макрос, который обёртывает функцию в журналирующих вызовах и допускает ошибку в реализации обёрнутой функции, то сообщение об ошибке укажет прямо на ошибку в файле, а не на код, сгенерированный макросом.

Макросы синтаксического дерева

Некоторые языки идут ещё дальше и предлагают средства использования и создания в макросах разных типов дерева абстрактного синтаксиса (Abstract Syntax Tree, AST). В качестве примеров можно назвать Template Haskell, макросы Nim, OCaml PPX и почти все Lisp.

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

Таким образом, во всех упомянутых мной языках есть в том или ином виде примитив «quote», которому вы даёте фрагмент кода на языке, а тот возвращает синтаксическое дерево. Эти примитивы могут сращивать значения синтаксического дерева с помощью подобия строковой интерполяции. Вот пример на Template Haskell:

Одним недостатком создания процедурных макросов на уровне синтаксического дерева, а не на уровне токенов, является в том, что типы синтаксического дерева часто меняются при добавлении новых языковых свойств. А типы токенов могут остаться совместимыми. К примеру, системе PPX в OCaml нужна специальная инфраструктура для миграции деревьев парсинга в/из языковой версии, используемой макросом. В Rust есть библиотеки, добавляющие утилиты parsing и quotation, поэтому вы можете писать процедурные макросы в том же стиле, что и в синтаксисе макросов синтаксических деревьев. А ещё в Rust есть экспериментальная библиотека, которая пытается реплицировать интерфейс, предоставляемые рефлексией!

Шаблоны

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

В C++20 есть «концепты», которые служат для той же цели, только их архитектура больше похожа на определение интерфейсов и ограничения типов.

Функции этапа компилирования

Есть языки, которые ещё дальше развивают концепцию «дженерики как функции этапа компилирования». Например, Zig:

Безумный уровень метапрограммирования в Terra позволяет реализовывать в виде простых функций оптимизирующие компиляторы для проблемно-ориентированных (domain specific) языков, или реализовывать интерфейсные и объектные системы Java и Go в библиотеке с маленьким количеством кода. И затем в Terra можно сохранить сгенерированный в ходе runtime код в виде объектных файлов, не содержащих зависимости.

Дженерики в Rust

Следующий тип мономорфизированных дженериков переносит генерирование кода в компиляторе ещё дальше, после проверки типов. Я упоминал, что тип внутрибиблиотечных ошибок, которые вы можете получить в С++, похожи на ошибки в динамически типизированном языке. Это следствие того, что в параметрах шаблонов, по сути, есть лишь один вид типов, как динамический язык. А значит мы можем решить проблему, добавив систему типов на метауровень и применяя много видов типов со статической проверкой на поддержку используемых вами операций. Так работают дженерики в Rust, и на уровне языка — в Swift и Haskell.

В Rust нужно в параметрах типов объявлять «границы признаков» (trait bounds). Trait — это как интерфейсы в других языках, они объявляют набор возможностей, предоставляемых типом. Компилятор Rust проверит, будет ли тело ваших дженерик-функций работать с любым типом, соответствующим границам признаков, и не позволит использовать возможности типов, которые не объявлены в этих границах. Поэтому пользователи дженерик-функций в Rust никогда не получают ошибок компиляции при создании экземпляров библиотечных функций. Кроме того, компилятору достаточно лишь один раз выполнить проверку типов для каждой дженерик-функции.

На уровне языка это очень похоже на такую разновидность системы типов, которая нужна для реализации дженериков с интерфейсной поддержкой с помощью упаковки дженериков. Поэтому Rust поддерживает оба варианта в рамках одной системы. В Rust 2018 даже появился унифицированный синтаксис, в котором параметр v: &impl SomeTrait получается мономорфизированным, а параметр v: &dyn SomeTrait использует упаковку. Это свойство позволяет компиляторам вроде GHC в Swift и Haskell использовать мономорфизацию в качестве оптимизации, даже хотя по умолчанию они применяют упаковку.

Мономорфизация машинного кода

Следующий логический шаг в моделях мономорфизированных дженериков — это перенести их в компиляторах на ещё более позднюю стадию, после бэкенда. Как мы копируем шаблоны исходного кода, которые аннотированы заглушками (placeholders) для дженерик-типов, так же мы можем генерировать машинный код с заглушками для частей, относящихся к определённым типам. А затем мы можем очень быстро наштамповать эти шаблоны с помощью memcpy и нескольких патчей, словно линковщик! Недостатком является то, что мономорфизированные копии нельзя оптимизировать по отдельности. Однако благодаря отсутствию оптимизации дубликатов компилирование может проходить гораздо быстрее. Мы даже можем превратить генератор кода в маленький JIT, который будет вставляться в бинарники и в ходе исполнения генерировать мономорфизированные копии, чтобы не раздувать размеры файлов.

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

Источник

Дженерики в TypeScript: разбираемся вместе

Всем привет! Команда TestMace публикует очередной перевод статьи из мира web-разработки. На этот раз для новичков! Приятного чтения.

Развеем пелену таинственности и недопонимания над синтаксисом и наконец подружимся с ним

Наверное, только матёрые разработчики Java или других строго типизированных языков не хлопают глазами, увидев дженерик в TypeScript. Его синтаксис коренным образом отличается от всего того, что мы привыкли видеть в JavaScript, поэтому так непросто сходу догадаться, что он вообще делает.

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

Дженерики в TypeScript

В документации TypeScript приводится следующее определение: «дженерики — это возможность создавать компоненты, работающие не только с одним, а с несколькими типами данных».

Здорово! Значит, основная идея состоит в том, что дженерики позволяют нам создавать некие повторно используемые компоненты, работающие с различными типами передаваемых им данных. Но как это возможно? Вот что я думаю.

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

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

Сделаем так, чтобы она работала с числами:

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

Посмотрите на вызов функции. Теперь-то синтаксис дженериков не должен вас пугать. T и U — это просто имена переменных, которые вы назначаете сами. При вызове функции вместо них указываются типы, с которыми будет работать данная функция.

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

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

Обратите особое внимание на второй вызов console.log на анимации выше — в него не передаётся тип. В этом случае TypeScript попытается вычислить тип по переданным данным.

Обобщённые классы и интерфейсы

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

Посмотрите на пример и попробуйте разобраться сами. Надеюсь, у вас получилось.

Если код сразу не понятен, попробуйте отследить значения type сверху вниз вплоть до вызовов функции. Порядок действий следующий:

Реальные случаи использования: выходим за рамки примитивных типов

Результатом выполнения данного кода будет:

Подведем итоги

Надеюсь, я помог вам разобраться с дженериками. Запомните, всё, что вам нужно сделать, — это всего лишь передать значение type в функцию 🙂

Если хотите ещё почитать про дженерики, я прикрепил далее пару ссылок.

Источник