Как дженерики реализованы в современном компиляторе?

Я имею в виду, как нам перейти от какого-то шаблона T add(T a, T b) ...к сгенерированному коду? Я подумал о нескольких способах достижения этой цели: мы храним обобщенную функцию в AST как, Function_Nodeа затем каждый раз, когда мы ее используем, мы сохраняем в исходном узле функции свою копию со всеми типами, Tзаменяемыми типами, которые являются использовался. Например, add<int>(5, 6)будет хранить копию универсальной функции addи заменять все типы T в копии на int.

Так это будет выглядеть примерно так:

struct Function_Node {
    std::string name; // etc.
    Type return_type;
    std::vector<std::pair<Type, std::string>> arguments;
    std::vector<Function_Node> copies;
};

Затем вы можете сгенерировать код для них, и когда вы посещаете Function_Nodeсписок копий copies.size() > 0, вы вызываете visitFunctionвсе копии.

visitFunction(Function_Node& node) {
    if (node.copies.size() > 0) {
        for (auto& node : nodes.copies) {
            visitFunction(node);
        }
        // it's a generic function so we don't want
        // to emit code for this.
        return;
    }
}

Будет ли это хорошо работать? Как современные компиляторы подходят к этой проблеме? Я думаю, что, возможно, другим способом сделать это было бы то, что вы могли бы вставить копии в AST, чтобы он проходил через все семантические фазы. Я также подумал, что, возможно, вы могли бы сгенерировать их в немедленной форме, например, в MIR Rust или Swifts SIL.

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

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

Как дженерики реализованы в современном компиляторе?

Я предлагаю вам прочитать исходный код современного компилятора, если вы хотите узнать, как работает современный компилятор. Я бы начал с проекта Roslyn, который реализует компиляторы C # и Visual Basic.

В частности, я обращаю ваше внимание на код в компиляторе C #, который реализует символы типа:

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Symbols

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

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Binder/Semantics/Conversions

Я изо всех сил пытался сделать последний легко читаемым.

Я подумал о нескольких способах достижения этого: мы храним обобщенную функцию в AST как Function_Node, а затем каждый раз, когда мы ее используем, мы сохраняем в исходном узле функции свою копию со всеми типами T, замененными типами. которые используются.

Вы описываете шаблоны , а не дженерики . C # и Visual Basic имеют фактические дженерики в своих системах типов.

Вкратце, они работают так.

• Мы начнем с установления правил для того, что формально составляет тип во время компиляции. Например: intэто тип, параметр типа Tэто тип, для любого типа тип Xмассива X[]также является типом и так далее.

• Правила для дженериков включают замену. Например, class C with one type parameterэто не тип. Это шаблон для создания типов. class C with one type parameter called T, under substitution with int for T это тип.

• Правила, описывающие отношения между типами - совместимость при присваивании, способ определения типа выражения и т. Д. - разрабатываются и реализуются в компиляторе.

• Разработан и реализован язык байт-кода, который поддерживает универсальные типы в своей системе метаданных.

• Во время выполнения JIT-компилятор превращает байт-код в машинный код; он отвечает за создание соответствующего машинного кода с учетом общей специализации.

Так, например, в C #, когда вы говорите,

class C<T> { public void X(T t) { Console.WriteLine(t); } }
...
var c = new C<int>(); 
c.X(123);

затем компилятор проверяет C<int>, что аргумент intявляется допустимой заменой T, и генерирует метаданные и байт-код соответственно. Во время выполнения дрожание обнаруживает, C<int>что создается в первый раз, и динамически генерирует соответствующий машинный код.

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

<T extends Addable> T add(T a, T b) { … }

можно скомпилировать, проверить тип и вызвать так же, как

Addable add(Addable a, Addable b) { … }

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

$T1 add($T1 a, $T1 b)

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

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

VTable для аргументов общего типа можно избежать, если универсальная функция не выполняет никаких операций над типом, а только передает их другой функции. Например, функция Haskell call :: (a -> b) -> a -> b; call f x = f xне должна была бы блокировать xаргумент. Однако для этого требуется соглашение о вызовах, которое может проходить через значения, не зная их размера, что в любом случае существенно ограничивает его указателями.

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

1. Примените шаблон к предоставленным аргументам шаблона. Например, вызов template<class T> T add(T a, T b) { … }as add<int>(1, 2)даст нам реальную функцию int __add__T_int(int a, int b)(или какой-либо другой подход к именованию).

2. Если код для этой функции уже был сгенерирован в текущем модуле компиляции, продолжайте. В противном случае, сгенерируйте код, как если бы функция int __add__T_int(int a, int b) { … }была написана в исходном коде. Это включает в себя замену всех вхождений аргумента шаблона его значениями. Это, вероятно, преобразование AST → AST. Затем выполните проверку типа сгенерированного AST.

3. Скомпилируйте вызов, как если бы исходный код был __add__T_int(1, 2).

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

Что это значит для вашего компилятора и / или языка? Вы должны тщательно продумать, какие дженерики вы хотите предложить. Стирание типов при отсутствии вывода типов - самый простой из возможных подходов, если вы поддерживаете коробочные типы. Специализация шаблонов кажется довольно простой, но обычно включает искажение имен и (для нескольких блоков компиляции) существенное дублирование в выходных данных, поскольку шаблоны создаются на сайте вызовов, а не на сайте определения.

Подход, который вы показали, по сути является C ++ - подобным шаблонным подходом. Тем не менее, вы сохраняете специализированные / созданные экземпляры шаблонов как «версии» основного шаблона. Это вводит в заблуждение: концептуально они не одинаковы, и разные экземпляры функции могут иметь совершенно разные типы. Это усложнит ситуацию в долгосрочной перспективе, если вы также допустите перегрузку функций. Вместо этого вам потребуется понятие набора перегрузки, содержащего все возможные функции и шаблоны, которые имеют общее имя. За исключением разрешения перегрузки, вы можете рассматривать различные созданные шаблоны как полностью отдельные друг от друга.