SavePearlHarbor

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

—

от автора

admin

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

Сокращения:

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

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

  • РТ — рантайм

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

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

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

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

Хотя 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 {.....}; // семейство buztemplate<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 == foostatic_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::typetemplate<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_vstatic_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>.

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

ссылка на оригинал статьи https://habr.com/ru/articles/1047886/