Ненормальное марковское программирование: неприятности

(Продолжение. См. первую часть, где мы научились кодить на марковских алгорифмах "на бумажке").

Сокращения:

• НАМ - нормальные алгорифмы Маркова

• КТ - компайл-тайм

• РТ - рантайм

Какие неприятности нас ждут?

Я уже сказал, что реализация НАМ в КТ - это задача со звёздочкой.

Что нам придётся героически преодолеть, и о чём понятно прямо на старте?

Первое и самое главное: строки

Хотя std::string можно использовать в КТ, но с оговорками. Выделение памяти не может пересекать границу КТ-РТ.

constexpr std::string make(bool small) {
  if (small)
    return "short"; // small object optimization
  else
    return "long enough string that needs allocation"; // new char[]
}

constexpr auto s = make(true);
constexpr auto l = make(false); // ошибка компиляции

static_assert(make(true) != "");
static_assert(make(false) != ""); // ок. внутри контекста КТ есть свой менеджер кучи

Можно попробовать запихнуть всю НАМ-машину, вместе с программой и данными, внутрь constexpr-функции, как-то

constexpr auto run(std::string data) {
  // внутренние объекты, хоть с аллокацией, хоть без...
  const auto program = RULES(RULE("a", "b"), FINAL_RULE("c", "D"), RULE("e", "f"));
  const auto machine = MACHINE(program);
  // результат - наверняка с аллокацией
  std::string result = machine(data);
  return result;
}

Ну и что мы с этим поделаем? Только в static_assert проверим? А если попытаемся записать в константу, то из-за аллокации она будет не constexpr, и мы просто получим обычный РТ-вызов, пусть и до main().

Так что нам нужны такие строки, которые были бы честными КТ.

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

Отсюда вытекает следующая неприятность.

Второе: циклы над разнотипными переменными

Опять же, в constexpr-функциях есть и for, и while. Но, как и в РТ, они работают с переменными фиксированного типа и с однородными контейнерами.

constexpr int table[] = {1, 2, 3, 4, 5};
constexpr int sum() {
    int s = 0;
    for (auto t : table) s += t;
    return s;
}
constexpr int countdown(int n) {
    int s = 0;
    while (n--) s += n;
    return s;
}

// результаты вычислений - честный КТ, и мы можем применять их, например, в типах
// (здесь - в длинах массивов)
int a[sum()];
int b[countdown(10)];

А программа НАМ, составленная из правил с неоднородными строками, - очевидно, неоднородная.

Поэтому вместо циклов придётся использовать рекурсивные функции. И не только!

Из этого следует

Третье: глубина рекурсии

Рекурсия в КТ - это ценный ресурс компилятора. Будь то непосредственная работа по выведению типа шаблона, или рекурсивная constexpr-функция

template<int N> struct deep_type : deep_type<N-1> {};
template<> struct deep_type<0> {};

constexpr int deep_call(int n) {
    if (n == 0) return 0;
    else return deep_call(n-1);
}

// доиграемся до ошибки компилятора (и спасибо, что не до ICE)
using D = deep_type<1000>;
constexpr int d = deep_call(1000);

Да, у компиляторов есть разные флаги, регулирующие эту глубину, - например, у gcc это -fconstexpr-depth=N и -ftemplate-depth=N . Если задать значения побольше, то вместо диагностики рискуем переполнить стек.

Так что сразу озаботимся техниками развёртывания циклов.

Последнее: смешивание КТ и РТ

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

А отобразить КТ-строки в РТ - это вообще просто. Но об этом ниже.

Неочевидное: система типов

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

Да и всякие служебные типы тоже, конечно же, шаблонные.

Конечно, язык шаблонов C++ необычайно слабо типизирован, почти как лямбда-исчисление, но это, с одной стороны, даёт гибкость, а с другой - нечитаемость ("что значит T? а что значит auto?") и ошибкоопасность (а ошибки в коде времени компиляции обычно приводят к гигантским портянкам диагностики).

Тут у нас есть три пути:

1. писать везде auto / class и длинные_мнемонические_идентификаторы, и блюсти чистоту рук

2. разворачивать формальные параметры шаблонов

3. концепты

// пусть шаблон класса и шаблон функции имеют дело с типами, инстанцированными из шаблона
template<size_t N> struct str { ..... };

// первый путь
template<class S> struct foo { ..... };
auto bar(auto s) { ..... }

// второй путь
template<class> struct foo;
template<size_t N> struct foo<str<N>> { using S=str<N>; ..... };
template<size_t N> auto bar(str<N> s) { ..... }

// третий путь
template<class T> concept Str = .....; // true только для str<N>
template<Str S> struct foo { ..... };
Str auto bar(Str s) { ..... } // заодно и тип результата можем уточнить до str<N1>

Поскольку циклы зависят от строк, строки - от типов, а типы - от концептов, - котёнок по имени Гав начнёт спуск на первую ступеньку именно с них.

Концепты

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

Концепт задаёт семейство типов. Обычно это

• "тип T принадлежит семейству F"

• "тип T является обёрткой W над типом U"

  • причём тип U сам по себе может не быть конкретным, а относиться к некоему семейству.

Так как у меня пользовательские типы - это разнообразные структуры, то удобно описывать семейство типов в связке: объявление концепта + пометка структуры, как принадлежащей семейству этого концепта.

CONCEPT(FooBar);
// обявляет концепт FooBar и необходимую обвязку для него,
// в частности, метафункцию is_FooBar, которая понадобится ниже

struct foo {
    REPRESENTS(FooBar)
};
struct bar {
    REPRESENTS(FooBar)
};

Если структура шаблонная, то она сама уже задаёт семейство типов - воплощений шаблона. Но в C++ нет красивого синтаксиса "из коробки" проверить этот факт. Есть некрасивый синтаксис со специализациями.

template<class U> struct buz {.....}; // семейство buz

template<class U> void f(buz<U> arg);

template<class T> struct xyz;
template<class U> struct xyz<buz<U>> {.....};

Естественно, можем руками написать концепт

// специализация спрятана под капот
template<class T> constexpr bool is_Buz_v = false;
template<class U> constexpr bool is_Buz_v<buz<U>> = true;

template<class T> concept Buz = is_Buz_v<T>;

или что-то в таком роде.

Но потом захотим прикрутить туда проверку BuzOfType<bar> и даже BuzOfFamily<FooBar>...

Чтобы избавиться от такой однотипной работы, - есть, опять же, набор макросов и конвенций.

CONCEPT_WITH_TYPE(Buz)
// объявил сразу три концепта
// Buz<T>
// BuzOfType<T, U>   где U - конкретный тип
// BuzOfTraits<T, C> где C - метафункция проверки свойств типа

template<class T> struct buz {
    REPRESENTS(Buz);
    using type = T; // CONCEPT_WITH_TYPE требует, чтобы параметр T был записан в имя type
};

using buz_of_foo = buz<foo>;

static_assert(Buz<buz_of_foo>);
static_assert(BuzOfType<buz_of_foo, foo>);         // проверка U == foo
static_assert(BuzOfTraits<buz_of_foo, is_FooBar>); // проверка is_FooBar<foo>

Тут стоит сказать,

Как можно параметризовать концепты

Концепт сам по себе является неполноценной сущностью. Мы можем применять концепт к типу плюс дополнительным параметрам, - то есть, это такой вид булевой константы, но не можем использовать в качестве параметра шаблона (в том числе параметра концепта).

И вообще, в качестве параметра шаблона можно использовать

• типы (в том числе алиасы)

• константы

• шаблоны типов (в том числе шаблоны алиасов)

Шаблоны констант (is_FooBar_v) - нельзя. А тем более, концепт (FooBar).

Но в метапрограммировании давно уже известны несколько приёмов:

• завернуть метафункцию внутрь конкретного типа-обёртки

• завернуть её в шаблон алиаса, который подставит аргумент куда хочет как хочет

• результатом будет не константа, а тип-обёртка константы, - тогда алиас резолвится в этот тип.

Что, собственно, и сделано

template<class T> concept FooBar = ......;

// DEFINE_TYPECHECKER(FooBar)
template<class T> constexpr bool is_FooBar_v = FooBar<T>;
template<class T> using is_FooBar = std::bool_constant<FooBar<T>>;

// соответственно, определения концептов BuzOf...
template<class T, class U>
concept BuzOfType = Buz<T> && HasTypeOfType<T, U>;

template<class T, template<class>class C>
concept BuzOfTraits = Buz<T> && HasTypeOfTraits<T, C>;

// где вспомогательные концепты, проверяющие вложенный тип T::type
template<class T, class U>
concept HasTypeOfType = std::same_as<typename std::remove_cvref_t<T>::type, U>;

template<class T, template<class>class C>
concept HasTypeOfTraits = C<typename std::remove_cvref_t<T>::type>::value;

Как населять концепт представителями

Сразу же поясню, почему выбрал дизайн с объявлением REPRESENTS внутри структуры.

По большому счёту, у нас есть два варианта - объявлять внутри и снаружи.

Снаружи кажется более универсальным (можно подселить к концепту произвольный тип, например, int). Но если структура шаблонная, то придётся делать детектор типа весьма многословным:

template<class T> constexpr bool is_FooBar_v = false;  // по дефолту
template<class T> concept FooBar = is_FooBar_v<T>;

template<class X, int N, auto Something>
struct ohoho { ..... };
// частичная специализация детектора
template<class X, int N, auto Something>
constexpr bool is_FooBar_v<ohoho<X, N, Something>> = true;

И там ещё кое-какие тонкости вылезают, даже связанные с возможностью нарушения ODR.

В частности, мы не можем использвать этот концепт внутри структуры, без ещё большей писанины.

А REPRESENTS устроен следующим образом (упрощённо)

// объявляем тэг
struct FooBar_concept_probe{};

// объявляем концепт
template<class T> concept FooBar =
    requires { std::remove_cvref_t<T>::represents_concept(FooBar_concept_probe{}); };

// вносим метку в структуру
template<class X, int N, auto Something>
struct ohoho {
    static void represents_concept(FooBar_concept_probe) {};
};

Таким образом, можно объявлять одну и ту же структуру представителем нескольких семейств. Просто напишем внутри несколько REPRESENTS.

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

namespace ns1 { CONCEPT(FooBar) }
namespace ns2 {
  struct foo {
    REPRESENTS(ns1::FooBar)
  };
}

Впрочем, если всё-таки нужен концепт, населённый произвольными типами, то сделать это руками не составит сложности.

template<class T> concept ArbitraryFamily = /* делаем, что хотим */;

DEFINE_TYPECHECKER(ArbitraryFamily)
// определяет is_ArbitraryFamily для дальнейшей интеграции с моими концептами

Но и это ещё не всё, что связано с концептами.

Как поступать со ссылками?

Концепты встречаются в синтаксисе 4 способами:

• в выражениях, как шаблон булевой константы

• в requires, как уточнение типа результата

• уточнение параметра-типа в шаблоне

• уточнение auto-значения в шаблоне

static_assert(FooBar<foo> && !FooBar<int>);

foo f();
static_assert(requires{ {f()} -> FooBar; });
// нельзя потребовать, что f возвращает именно foo, но можно - "тип, такой же, как foo"
// вот зачем нужен same_as наряду с is_same_v
static_assert(requires{ {f()} -> std::same_as<foo>; });

template<FooBar T> struct foobarwrapper {};
// эквивалентно
template<class T> requires FooBar<T> struct foobarwrapper {};

void g(FooBar auto x, FooBar auto const& y, FooBar auto&& z);
// эквивалентно
template<class X, class Y, class Z>
auto g(X x, Y const& y, Z&& z)
requires FooBar<X> && FooBar<Y> && FooBar<Z>;

Видите, где подвох? Если X и Y - это типы значения, то Z - универсальная ссылка.

И, чтобы наш шаблон FooBar работал, он должен принимать универсальную ссылку.

Правда, в таком случае ограничение на параметр foobarwrapper окажется слишком широким: помимо структур foo или bar туда можно будет подсунуть foo& или bar&&.

Ну, тут уж выходов два:

• или заводить связанную пару концептов, скажем,

  • FooBarGeneric (всеядный, можно использовать с auto / decltype(auto))

  • FooBarValue (строго для типов foo, bar),

• или оставить один и надеяться на чистоту рук и на дополнительные проверки

  • requires (!std::is_reference_v<T>)

  • static_assert(!std::is_reference_v<T>)

Я пошёл вторым, простым путём. Из-за этого во вспомогательных концептах делается std::remove_cvref_t<T>.

На следующих ступеньках нас ждут строки... И новые неприятности со строками!