company_banner

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

Автор оригинала: Tristan Hume
  • Перевод

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

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

Обзор


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



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


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

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

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

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

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

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

Упаковка


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

type Stack struct {
  values []interface{}
}

func (this *Stack) Push(value interface{}) {
  this.values = append(this.values, value)
}

func (this *Stack) Pop() interface{} {
  x := this.values[len(this.values)-1]
  this.values = this.values[:len(this.values)-1]
  return x
}

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

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


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

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

Решить обе проблемы можно добавлением в систему типов функциональности дженериков, при этом используя основной метод упаковки так же, как раньше в ходе исполнения кода. Этот подход часто называют затиранием типов (type erasure), потому что типы в системе дженериков «затираются» и под капотом становятся одним типом (как Object).

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

List v = new ArrayList();
v.add("test"); // A String that cannot be cast to an Integer
Integer i = (Integer)v.get(0); // Run time error

List<String> v = new ArrayList<String>();
v.add("test");
Integer i = v.get(0); // (type error) compilation-time error

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


OCaml ещё дальше развивает идею унифицированного представления. Здесь нет примитивных типов, которым нужно дополнительное размещение упаковки (как int должен превратиться в Integer, чтобы попасть в ArrayList в Java), потому что всё уже упаковано или представлено целочисленным значением размером с указатель, то есть всё поместилось в одно машинное слово. Но когда сборщик мусора смотрит на данные, хранящиеся в структурах дженериков, ему нужно отличать указатели от чисел, поэтому числа маркируются с помощью одного бита, помещённого туда, где у правильно выровненных указателей не бывает одного бита, оставляя диапазоны размером только 31 или 63 бита.

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

let first (head :: tail) = head
(* inferred type: 'a list -> 'a *)

Приведённый тип можно назвать «функцией из списка элементов типа '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, в чьих компиляторах такой поддержки нет.

В языке С можно использовать препроцессор и определять структуру данных в макросе или заголовке, многократно вставляя его с разными #define. В Go есть скрипты наподобие genny, которые упрощают генерирование кода.

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

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


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

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

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


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

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


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

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

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

-- using AST construction functions
genFn :: Name -> Q Exp
genFn f = do
  x <- newName "x"
  lamE [varP x] (appE (varE f) (varE x))

-- using quotation with $() for splicing
genFn' :: Name -> Q Exp
genFn' f = [| \x -> $(varE f) x |]

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

Шаблоны


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

template <class T> T myMax(T a, T b) {
  return (a>b?a:b);
}

template <class T> struct Pair {
  T values[2];
};

int main() {
  myMax(5, 6);
  Pair<int> p { {5,6} };
  // This would give us a compile error inside myMax
  // about Pair being an invalid operand to `>`:
  // myMax(p, p);
}

К проблемам системы шаблонов можно отнести то, что если вы добавили в свою библиотеку шаблонную функцию и пользователь создал её экземпляр с неправильным типом, то в библиотеке может возникнуть загадочная ошибка компилирования. Это очень похоже на то, что может происходить с библиотеками в динамически типизированных языках, когда пользователь передаёт неправильный тип. В D есть интересное решение этой проблемы, аналогичное тому, что делают популярные библиотеки в динамических языках: для проверки валидности типов используются вспомогательные функции, и если они сбоят, сообщения об ошибках ясно указывают на это. Вот пример на D; обратите внимание на if в сигнатуре и более удобный синтаксис (! применяется для предоставления параметров шаблонов):

// We're going to use the isNumeric function in std.traits
import std.traits;

// The `if` is optional (without it you'll get an error inside like C++)
// The `if` is also included in docs and participates in overloading!
T myMax(T)(T a, T b) if(isNumeric!T) {
    return (a>b?a:b);
}

struct Pair(T) {
  T[2] values;
}

void main() {
  myMax(5, 6);
  Pair!int p = {[5,6]};
  // This would give a compile error saying that `(Pair!int, Pair!int)`
  // doesn't match the available instance `myMax(T a, T b) if(isNumeric!T)`:
  // myMax(p, p);
}

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

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


У шаблонов в D есть ряд расширений, позволяющие использовать оценку функций на этапе компилирования (compile time function evaluation) и static if, чтобы, по сути, шаблоны работали как функции, которые берут на этапе компилирования набор параметров и возвращают не-дженерик runtime-функции. Это превращает шаблоны в систему метапрограммирования с полным набором возможностей, и, насколько я понимаю, современные шаблоны в С++ имеют такие же возможности, но менее понятные механизмы.

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

fn Stack(comptime T: type) type {
    return struct {
        items: []T,
        len: usize,

        const Self = @This();
        pub fn push(self: Self, item: T) {
            // ...
        }
    };
}

В Zig для этого применяется один и тот же язык при компилировании и выполнении, с разделением функций на основе параметров, помеченных comptime. В языке Terra на метауровне используется отдельный, но аналогичный язык. Terra — это диалект Lua, здесь можно создавать низкоуровневые С-образные инлайны функций, а затем с помощью Lua API манипулировать ими на метауровне, как и примитивами quoting и splicing:

function MakeStack(T)
    local struct Stack {
        items : &T; -- &T is a pointer to T
        len : int;
    }
    terra Stack:push(item : T)
        -- ...
    end
    return Stack
end

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

Дженерики в Rust


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

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

fn my_max<T: PartialOrd>(a: T, b: T) -> T {
    if a > b { a } else { b }
}

struct Pair<T> {
    values: [T; 2],
}

fn main() {
    my_max(5,6);
    let p: Pair<i32> = Pair { values: [5,6] };
    // Would give a compile error saying that
    // PartialOrd is not implemented for Pair<i32>:
    // my_max(p,p);
}

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

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


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

На самом деле, я не знаю ни одного языка, который работает таким образом, это просто идея, которая пришла ко мне во время написания статьи, как естественное расширение этой таксономии, на что я и надеялся благодаря этому упражнению! Я надеюсь, что эта статья даст вам более четкое представление о системах дженериков в разных языках, и о том, как они могут вписаться в единую таксономию. Также надеюсь, что этот текст побудит вас задуматься о том, в каком направлении в рамках пространства идей мы можем найти новые классные языки программирования.
Mail.ru Group
1 016,66
Строим Интернет
Поделиться публикацией

Похожие публикации

Комментарии 14

    +4
    Это круто, спасибо. Хотя конечно нужно знать устройство компиляторов, чтобы понимать о чем речь в статье. Было бы идеально дополнить иллюстрациями и примерами «псевдокода» на Си (как «лингва франка») некоторых структур данных, используемых в дженериках с упаковкой. Т.е. просто нарисовать как оно устроено в памяти.
      +1

      Не очень понятен момент про Swift. Чем witness-таблица отличается от тайп-классов? Witness-таблица это как vtable, но указатель на неё не хранится в объекте, а передаётся?
      Если так, то что делать с типами более высокого порядка, например:


      zip(a: Pair<List<T>, List<U>>) -> List<Pair<U, V>>

      Создавать witness-таблицы на лету?

        +1
        Шикарная статья, наконец понял разницу между impl Trait и dyn Trait в расте :)
          +9

          Забавно, что в статье про дженерики не описаны, собственно, хаскелевские дженерики, являющиеся куда более приятной альтернативой упомянутому в статье TH. Да и вообще это, наверное, представитель ещё одного подхода к метапрограммированию.

            +1

            И ещё Data.Data тогда уж можно упомянуть. Забавно, что в одном языке есть три разных подхода для программирования дженериков :)

            +7

            Реализация дженериков от C# зря попала в ветку "упаковки" — это не соответствует действительности.

              +5

              C# для всех ссылочных типов использует одну реализацию.
              Для типов-значений делает копию кода на каждый используемый тип.
              Поэтому язык можно отнести в обе ветви.

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


              есть третий способ — это векторные инструкции, если заморачиваемся с производительностью. Если нет, то можно динамический тип. Вообще это такой галоп по сабжу что согласен, надо по разработке компиляторов нормально почитать
                +3

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

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

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

                      0
                      Ничего удивительного при таких метаниях, в общем-то.
                    0

                    По-моему, разнообразие метапрограммирования в C# не полностью отражено на иллюстрации в начале статьи.


                    • ArrayList — недженериковая коллекция, в которую можно боксить что угодно, потом приводить
                    • List<FooClass> — дженериковая коллекция, машинный код один для всех классов
                    • List<dynamic> — дженериковая коллекция, тот же IL, тот же машинный код, но каждое обращение к объекту "динамическое" (с утиной типизацией), внутри кэшированные отражения
                    • List<BarStruct> — дженериковая коллекция, тот же IL, но машинный код под каждую структуру отдельный, боксинга нет
                    • Шаблоны на T4 — не совсем встроено в язык, но идёт в комплекте, скажем так

                    Есть ещё варианты, но это так, из коробки.

                      0
                      Рекомендую посмотреть на дженерики в языке Julia (там это называется multiple dispatch).

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

                      Самое читаемое