Spiiin's blog

C++ computational quadrants

2024/05/19
Tags: cpp

Увидел в доках boost.hana разделение типов вычислений в C++ на 4 типа (я не понимаю, как Louis Dionne сложил их в квадранты). Ну и, соответственно, внутри C++ существует 4 языка для того, чтобы описывать эти типы вычислений.

1. Runtime computations — “usual computations”. Примитивы для таких вычислений — рантайм контейнеры, функции и алгоритмы (std как пример базового фреймворка)

auto f = [](int i) -> std::string {
  return std::to_string(i * i);
};
 
std::vector<int> ints{1, 2, 3, 4};
std::transform(ints.begin(), ints.end(), std::back_inserter(strings), f);

2. Constexpr computations — constexpr вычисления компилятором. Синтаксис для таких вычислений поддерживается максимально похожим на C++. Можно воспринимать их, как код для отдельной ограниченной платформы (компилятора), которая не поддерживает выделение памяти или исключения. (Sprout — пример библиотеки контейнеров, функций и алгоритмов для таких вычислений)

constexpr int factorial(int n) {
  return n == 0 ? 1 : n * factorial(n - 1);
}
 
template <typename T, std::size_t N, typename F>
  constexpr std::array<std::invoke_result_t<F, T>, N>
transform(std::array<T, N> array, F f) {
  // ...
}
 
constexpr std::array<int, 4> ints{{1, 2, 3, 4}};
constexpr std::array<int, 4> facts = transform(ints, factorial);

3. Heterogeneous computations — гетерогенные вычисления. Работа с суммами (std::variant) и произведениями (std::tuple) типов. Boost.Fusion как пример библиотеки.

auto to_string = [](auto t) {
  std::stringstream ss;
  ss << t;
  return ss.str();
};
 
fusion::vector<int, std::string, float> seq{1, "abc", 3.4f};
fusion::vector<std::string, std::string, std::string>
  strings = fusion::transform(seq, to_string);

4. Type-level computations — вычисления над типами. Boost.MPL как пример библиотеки

template <typename T>
struct add_const_pointer {
  using type = T const*;
};
 
using types = mpl::vector<int, char, float, void>;
using pointers = mpl::transform<types, add_const_pointer<mpl::_1>>::type;

Оптимизации

C++Now 2017: Odin Holmes “Type Based Template Metaprogramming is Not Dead” — доклад про оптимизацию вычислений над типами (Rule of Chiel). Для compile-time вычислений таким заморачиваются редко, нужно хорошо представлять себе, что приблизительно должен сделать под капотом компилятор, раскрывая тот или иной шаблонный код. Без такого представления время компиляции и размер выходного кода становятся непредсказумыми (точнее, предсказумо большими).

Explicit template instantiation - when is it used? — явная специализация шаблонов как приём оптимизации.

Общее

Don’t constexpr All the Things - David Sankel CppNow 2021 — обзор ограничений constexpr computations. И идеи по замене ограниченного языка constexpr на полноценный язык времени компиляции равный языку времени выполнения (не C++).

Matt Calabrese, Zachary Laine: Instantiations Must Go! — слайды про то, как трансформировать синтаксис type-level computations в Heterogeneous computations (на 1 внутренний язык в c++ меньше), основная идея Boost.Hana.

Exploring the design space of metaprogramming and reflection — варианты дизайна рефлексии в C++ через Type syntax/Heterogeneous value/Homogeneous value syntax (2,3 и 4 “квадранты”)
Reflection in C++ Next - Anton Bikineev - Meeting C++ 2017 — тайминг доклада с примерами реализаций этими способами

The next big Thing - Andrei Alexandrescu - Meeting C++ 2018 Opening Keynote — (тайминг) Александреску рассказывает про интроспецию с видом человека, который её придумал. В его терминологии это генерация произвольного кода во время компиляции. Input - чтение любого кода (в proposals), processing - выполнение любого кода в compile-time (wip), output - генерация любого кода (отсутствует совсем).

За пределами C++

Clang/LibTooling AST Notes — интерфейсы к Clang для работы с AST. Метапрограммирование не “на C++”, а “с использованием C++”, без ожидания принятия стандартов, их имплементации, и миграции библиотек.