Обобщенное программирование

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

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

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

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

Выбранный подход по синтаксису более всего похож на реализованный в языке Julia (т.е. нет отдельного синтаксиса для шаблонов), но позволяет определять конкретные специалиазции как в C++, Rust во время компиляции, а для динамической типищации используется динамическая диспетчеризация выбора конкретной релиазции, что похоже на применения обощеного программирования в Pyton с использованиям C/C++ библиотек.

Имена функций подчиняются общим правилами именования объектов, поэтому её имя является единой “точкой входа” для выбора конкретной реализации машинного кода (динамиечская диспетчеризация), но при отсуствии нужной специалиазции она не генерируется, а выбирается наиболее подходящая из специализированных ранее. Но такой подход не мешает динамически создавать специалиазаии, если среда выполнения поддерживает JIT компиляцию.

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

Модель обощеного программирования

Каждая функция языка имеет как миниму две части машинного кода.

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

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

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

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

Примеры

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

    # Типы аргументов не проверяются (функцию можно вызвать с любыми типами)
    def max_val(a, b):
        if a > b:
            return a
        else:
            return b

    # Одна функция и проверка типов аргументов производится в ранатайме 
    # как и обработка возможных ошибок из-за несовместимых типов
    max_val(3, 5)
    max_val(3.0, 5.0)
    max_val("a","b")

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

    // Проверка типов во время компиляции
    template<typename T>
    T max_val(T a, T b) {
        return a > b ? a : b;
    }

    // Во время выполнения нет информации о типах
    // Отдельная реализация для каждого типа данных
    // и применения манглинга имен для выбора нужной функции 
    max_val<int>(3, 5);          // генерирует: int max_val(int, int)
    max_val<double>(3.0, 5.0);   // генерирует: double max_val(double, double)
    max_val<std::string>("a","b");// генерирует: string max_val(string, string)

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

    # Типы аргументов не проверяются (функцию можно вызвать с любыми типами)
    @max_val(a, b: Any) := {
        @if( a > b) {
            return a;
        }
        return b;
    };

    # Одна функция и проверка типов аргументов производится в ранатайме 
    # как и обработка возможных ошибок из-за несовместимых типов
    max_val(3, 5)
    max_val(3.0, 5.0)
    max_val("a","b")

Однако при конкретизации обработываемых типов, реализация приближается к используемой в C++

    # Обработываемые типы данных
    :MaxTypes := <Integer, Double, Any>;
    # Проверка типов происходит во время компиляции
    max_val( a:MaxTypes, b:MaxTypes):MaxTypes := {
        @if( a > b) {
            @return a;
        }
        @return b;
    };

    # Для специалиазций создаются отдельные реализации для каждого типа
    max_val(3, 5);      #  вызывается int max_val(int, int)
    max_val(3.0, 5.0);  #  вызывается double max_val(double, double)

    # Для остальных тьипов вызывается специалиазции Any,
    # у которой присуствует информации о типах данных
    # Проверка типов аргументов производится в ранатайме 
    # как и обработка возможных ошибок из-за несовместимых типов
    max_val("a","b");

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

    # Типы аргументов не проверяются (функцию можно вызвать с любыми типами)
    @max_val(a, b) := {
        @if( a > b) {
            return a;
        }
        return b;
    };

    # Одна функция и проверка типов аргументов производится в ранатайме 
    # как и обработка возможных ошибок из-за несовместимых типов
    array := :Int32[100](... rand() ...); # заполнение тензора значениями функции rand() 
    max := array[0];
    index := 1;
    while(index < len(array)){
        max = max_val(max, array[index]); # Вызов функции max_val с типизированными аргументами
        # функция не только можен быть типизирована автоматически, но и в случае аггресивной 
        # оптимизации копидлятор может полностью раскрыть вызов функции в инлайн код
        index += 1;
    }
    @print(max);