Концептуальное обобщённое программирование на C++

Основная информация

• ID статьи: 2510.08969
• Название: Concept-Based Generic Programming in C++
• Автор: Bjarne Stroustrup (Колумбийский университет)
• Классификация: cs.PL cs.SE
• Время публикации: 2025 год
• Ссылка на статью: https://arxiv.org/abs/2510.08969

Аннотация

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

Исследовательский контекст и мотивация

Проблемный контекст

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

Исследовательская мотивация

Основная мотивация данной статьи состоит в демонстрации того, как использовать концепции, введённые в C++20, для:

• Предоставления спецификаций интерфейсов со статической типобезопасностью
• Реализации типобезопасности с нулевыми накладными расходами
• Построения расширений пользовательских систем типов
• Сохранения единства обобщённого программирования и универсального программирования

Цели проектирования

Статья следует целям обобщённого программирования, предложенным Алексом Степановым: "наиболее универсальное, наиболее эффективное, наиболее гибкое представление концепций" и удовлетворяет следующим требованиям проектирования:

• Универсальность: Должна быть возможность выражения гораздо большего, чем можно представить
• Непоколебимая эффективность: Обобщённый код не должен иметь накладных расходов на время выполнения по сравнению с эквивалентным низкоуровневым кодом
• Интерфейс со статической типобезопасностью: Система типов должна быть достаточно гибкой, чтобы позволить проверку на этапе компиляции большинства аспектов интерфейсов, которые не зависят от значений времени выполнения

Основные вклады

1. Предложены методы программирования на основе концепций для типобезопасности: Демонстрируется, как использовать концепции для исключения сужающих преобразований и обеспечения проверки диапазонов при сохранении нулевых накладных расходов на время выполнения.
2. Построены практические расширения систем типов:
   • Реализован тип Number<T>, исключающий опасные сужающие преобразования
   • Разработан безопасный тип Span, обеспечивающий проверку диапазонов при доступе к массивам
   • Продемонстрировано применение концепций в проектировании алгоритмов
3. Предоставлена глубокая философия проектирования концепций: Подробно описаны решения проектирования концепций как функций времени компиляции, отношение к объектно-ориентированному программированию, выбор символического представления и другие ключевые соображения проектирования.
4. Продемонстрирована единство обобщённого программирования: Доказано, что обобщённое программирование является составной частью C++, а не изолированным подъязыком, и беспрепятственно интегрируется с другими языковыми особенностями (такими как лямбда-функции, вариадические шаблоны, статическая рефлексия).

Подробное описание методов

Основное определение концепций

Концепция представляет собой функцию (предикат), вычисляемую на этапе компиляции и способную принимать параметры типов:

template<typename T>
concept Num = integral<T> || floating_point<T>;

Методы исключения сужающих преобразований

Определение концепции для обнаружения сужения

template<typename T, typename U>
concept Can_narrow_to = 
    ! same_as<T, U>    // различные типы
    && Num<T> && Num<U>   // оба являются числовыми типами
    && ( 
        (floating_point<T> && integral<U>) // может потерять дробную часть
        || (numeric_limits<T>::digits > numeric_limits<U>::digits) // может произойти усечение
        || (signed_integral<T>!=signed_integral<U> && sizeof(T)==sizeof(U)) // может изменить знак
    );

Функция проверки во время выполнения

template<Num U, Num T>
constexpr bool will_narrow(U u) {
    if constexpr (!Can_narrow_to<T, U>)
        return false;  
    // проверка во время выполнения только при возможности сужения
    T t = u;
    return (t != u);
}

Реализация типа Number

template<Num T>
class Number {
    T val;
public:
    template<Num U>
    constexpr Number(const U u) : val{convert_to<T>(u)} { }
    
    operator T() { return val; }
};

Реализация безопасного доступа к диапазонам

Проектирование типа Span

template<class T>
class Span {
    T* p;
    unsigned n;
public:
    Span(Spanable auto& s) : p{data(s)}, n{size(s)} {}
    
    T& operator[](Number<unsigned> i) { 
        return p[check(i)]; 
    }
    
private:
    unsigned check(unsigned nn) {
        if (n <= nn) throw Span_range_error{};
        return nn;
    }
};

Применение концепций в алгоритмах

Функция сортировки с ограничениями концепций

template<typename R, typename Pred = ranges::less>
concept Sortable_range = 
    ranges::random_access_range<R>
    && sortable<ranges::iterator_t<R>, Pred>;

template<typename R, typename Pred = ranges::less>
requires Sortable_range<R,Pred>
void sort(R& r, Pred p = {}) {
    sort(r.begin(), r.end(), p);
}

Технические инновации

1. Паттерны использования (Use Patterns)

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

template<typename T, typename U = T>
concept equality_comparable = requires(T a, U b) {
    {a==b} -> Boolean;
    {a!=b} -> Boolean;
    {b==a} -> Boolean;
    {b!=a} -> Boolean;
}

Преимущества этого подхода:

• Обработка смешанной арифметики
• Обработка неявных преобразований
• Обеспечение стабильности интерфейса

2. Концепции как функции

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

• Возможность запроса свойств типа ("Ты итератор?")
• Возможность принятия нескольких параметров
• Выполнение на этапе компиляции с высокой эффективностью

3. Абстракция с нулевыми накладными расходами

Через проверку на этапе компиляции и условную компиляцию достигается нулевые накладные расходы на время выполнения:

template<Num U, Num T>
constexpr bool will_narrow(U u) {
    if constexpr (!Can_narrow_to<T, U>)
        return false;  // определено на этапе компиляции, без затрат на время выполнения
    // проверка во время выполнения только при необходимости
}

Экспериментальная установка

Проверка примерами кода

Статья проверяет эффективность методов через множество практических примеров кода:

1. Примеры арифметических преобразований: Демонстрируется, как тип Number предотвращает сужающие преобразования
2. Примеры доступа к диапазонам: Демонстрируется, как тип Span обеспечивает безопасный доступ к массивам
3. Примеры алгоритма сортировки: Демонстрируется, как концепции улучшают ясность и безопасность интерфейса алгоритма

Рассмотрение производительности

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

Экспериментальные результаты

Основные достижения

1. Повышение типобезопасности:

   Number<int> test() {
       Number<unsigned int> ii = 0;
       ii = 2;   // OK
       ii = -2;  // выбрасывает исключение - перехватывает ошибку знака
   }
   

2. Безопасность диапазонов:

   Span<int> sa{array};
   int x = sa[10];   // OK, если в диапазоне
   int y = sa[-1];   // выбрасывает исключение - перехватывает ошибку отрицательного индекса
   

3. Улучшение интерфейса алгоритма:

   sort(vec);  // лаконичный интерфейс
   sort(lst);  // ошибка компиляции: list не поддерживает случайный доступ
   

Характеристики производительности

• Проверка на этапе компиляции: нулевые накладные расходы на время выполнения
• Проверка во время выполнения: выполняется только при необходимости с минимальными накладными расходами
• Оптимизация: поддержка встраивания и других оптимизаций компилятора

Связанные работы

История обобщённого программирования

• Концепции STL: итераторы, последовательности, контейнеры (начало 1990-х годов)
• Математические концепции: моноиды, группы, кольца, поля (история в несколько сотен лет)
• Концепции теории графов: рёбра, вершины, графы, DAG (с 1736 года)

Развитие концепций C++

• 2003 год: первое предложение концепций
• 2009 год: концепции C++0x были удалены
• 2017 год: концепции переинтродуцированы
• 2020 год: концепции официально включены в C++20

Сравнение с другими системами ограничений

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

Заключение и обсуждение

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

1. Концепции являются функциями времени компиляции: Такое проектирование обеспечивает оптимальный баланс между гибкостью и эффективностью.
2. Обобщённое программирование и ООП дополняют друг друга:
   • ОП сосредоточено на функциях (алгоритмах) и требованиях к параметрам
   • ООП сосредоточено на объектах и реализации интерфейсов
   • Оба могут эффективно использоваться совместно
3. Единая модель программирования: Обобщённое программирование не является изолированным подъязыком, а составной частью C++.

Философия проектирования

Концепции против иерархии классов

• Концепции: Указывают операции, которые шаблон должен выполнять над своими параметрами
• Иерархия классов: Предопределённые интерфейсы, требующие предусмотрительности
• Концепции более гибкие: Могут использовать любые типы, удовлетворяющие требованиям

Выбор символического представления

// Идеальный функциональный синтаксис (не принят)
void sort(Sortable_range& r);

// Фактически принятый компромиссный синтаксис
void sort(Sortable_range auto& r);

Направления будущего развития

1. Аксиомы (Axioms): Указание семантических свойств конструкций для анализаторов и генераторов кода
2. Диапазоны вывода: Повышение безопасности диапазонов с проверкой диапазонов для операций вывода
3. Улучшение символического представления: Исключение избыточности auto после концепций
4. Перегрузка классов: Перегрузка классов на основе концепций
5. Сопоставление паттернов: Сопоставление паттернов в функциональном стиле программирования
6. Унифицированный вызов функций: Унификация функционального и ООП-стиля вызова функций

Глубокая оценка

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

1. Высокая практичность: Предоставляет методы программирования, которые можно непосредственно применять для решения реальных проблем типобезопасности.
2. Сочетание теории и практики: Имеет глубокую теоретическую основу (математические концепции) и конкретные примеры реализации.
3. Проектирование с нулевыми накладными расходами: Благодаря тщательному проектированию проверок на этапе компиляции достигается типобезопасность без потери производительности.
4. Всестороннее рассмотрение проектирования: Охватывает полное пространство проектирования от базового синтаксиса до продвинутых функций (таких как статическая рефлексия).
5. Авторитетность: Автор Bjarne Stroustrup является создателем языка C++ и обладает неоспоримым авторитетом.

Недостатки

1. Крутая кривая обучения: Синтаксис концепций и паттерны использования могут быть сложными для начинающих.
2. Влияние на время компиляции: Большое количество проверок на этапе компиляции может увеличить время компиляции, что недостаточно обсуждается в статье.
3. Вызовы обратной совместимости: Хотя совместимость сохранена, смешанное использование нового и старого кода может вызвать путаницу.
4. Качество сообщений об ошибках: Хотя концепции улучшают сообщения об ошибках, сообщения об ошибках для сложных концепций всё ещё могут быть трудны для понимания.

Влияние

1. Влияние на сообщество C++: Предоставляет авторитетное руководство по практическому применению концепций C++20.
2. Вдохновение для других языков: Философия проектирования концепций может повлиять на проектирование систем ограничений в других языках.
3. Образовательная ценность: Предоставляет отличный учебный материал для преподавания обобщённого программирования.
4. Практическая ценность: Предоставленные методы можно непосредственно использовать для повышения типобезопасности кода.

Применимые сценарии

1. Системное программирование: Низкоуровневый код, требующий высокой производительности и типобезопасности.
2. Проектирование библиотек: Предоставление чётких спецификаций интерфейсов для обобщённых библиотек.
3. Обучение и подготовка: Использование в качестве учебного материала для концепций и методов обобщённого программирования.
4. Рефакторинг кода: Преобразование существующего небезопасного кода в типобезопасную версию.

Библиография

Статья содержит богатую библиографию, охватывающую различные аспекты от проектирования языка C++ до теории обобщённого программирования, включая в основном:

• Пионерские работы Алекса Степанова по STL и обобщённому программированию
• Технические отчёты и предложения комитета по стандартизации C++
• Исторические документы автора о проектировании и эволюции C++
• Соответствующие исследования в области теории языков программирования

Резюме: Это статья с важной теоретической и практической ценностью, написанная самим создателем языка C++, всесторонне демонстрирующая применение концепций в обобщённом программировании на C++. Статья не только предоставляет практические методы программирования, но и глубоко раскрывает философию проектирования, имея важное справочное значение как для программистов на C++, так и для исследователей в области языков программирования.