Продолжение. Начало здесь. Предыдущая часть. Репозиторий с кодом - на гитхабе.
(Сокращения: НАМ - нормальные алгорифмы Маркова, КТ - компайл-тайм, РТ - рантайм).
Следующая неприятность, которая нас ждёт, - это циклы, которые в КТ вовсе не циклы. Нам надо как-то научиться бегать по правилам, из которых состоит НАМ-программа.
Как устроена НАМ-программа на C++
В предыдущей главе я уже сказал, что каждое элементарное правило - это синглетон, параметризованный двумя строками (поиска и замены) и флажком (обычное/финальное). А подпрограмма - это синглетон, параметризованный набором правил.
Интерфейс подпрограммы должен быть таким же, как у элементарного правила, чтобы можно было делать подпрограммы с подпрограммами. Не то, что это жизненная необходимость, но для структурирования НАМ-кода очень полезно. (Минималистичный движок мог бы состоять ровно из трёх уровней: машина, список правил, элементарные правила).
Более того, цикл исполнения НАМ-машины тоже можно сделать с таким же интерфейсом. У него на входе строка в какой-то декорации, и на выходе строка в какой-то декорации.
template<class T> concept RuleInput = .....; // обёртка над CtStr
template<class T> concept RuleOutput = .....; // обёртка над CtStr
enum class rule_kind { regular, final };
template<Str auto search, Str auto replace, rule_kind kind>
struct rule {
REPRESENT(Rule)
constexpr RuleOutput decltype(auto) operator()(RuleInput auto&& in) const {
// пытаемся выполнить подстановку,
// возвращаем
// - признак успеха-неуспеха,
// - результат подстановки,
// - достигли или нет финального состояния
}
};
template<Rule auto... ps>
struct rules {
REPRESENT(Rule)
constexpr RuleOutput decltype(auto) operator(RuleInput auto&& in) const {
// ПСЕВДОКОД!!!
for (p in ps...) {
auto out = p(in);
if constexpr (matched(out)) return out;
}
return in;
}
};
template<Rule auto p>
struct rule_loop {
REPRESENT(Rule)
constexpr RuleOutput decltype(auto) operator(RuleInput auto&& in) const {
// ПСЕВДОКОД!!!
auto current = in;
while (true) {
auto out = p(current);
if constexpr (final_state(out)) return out;
if constexpr (!matched(out)) return out; // иначе зациклимся
current = out;
}
}
};Что это за декорации, я и расскажу ниже. Но начну с того, как вообще делать такие циклы.
Disclaimer
В этой статье я не просто покажу итоговое решение, а устрою именно забег по граблям. Покажу, как вообще можно писать КТ-циклы, какие идеи за этим стоят, и что из этого оказалось неприятностями, которые меня ждали.
Это не значит, что промежуточные решения плохие, - в других условиях их очень даже можно использовать.
Тут есть важные неочевидные моменты, которые могут пессимизировать код, а то и приводить к неопределённому поведению, если оптимизировать бездумно.
Цикл for
Напомню, что у нас две беды: разнотипные элементы последовательности (в данном случае - правила) и разнотипные результаты, получаемые на каждой итерации. Зато хорошо, что количество элементов заранее известно (вариадик).
Используем fold-expressions...
Если бы результаты были однородными (и assignable), - как внутри функции concat_str из предыдущей главы, - то можно было бы сделать с помощью fold-expressions на операторе "," или конъюнкции (либо дизъюнкции).
void do_for_all(auto arg, auto... funs) {
(funs(arg) , ...);
}
auto chain_for_all(auto seed, auto... funs) {
((seed = funs(seed)), ...);
// разворачивается в
seed = f1(seed),
seed = f2(seed),
.....;
return seed;
}
auto chain_for_all_while(auto seed, auto cond, auto... funs) {
((cond(seed) && (seed = funs(seed), true)) && ... && true);
// разворачивается в
cond(seed) && (seed = f1(seed), true) &&
cond(seed) && (seed = f2(seed), true) &&
.....
true; // последнее нужно на случай, если sizeof...(funs) == 0
return seed;
}Делаем конвеер...
Но что, если нам нужно сделать что-то вида fn(...(f2(f1(seed)))...).
Так это же конвеер! (seed >> f1 >> f2 >> ... >> fn). Всё, что необходимо, - это наколдовать двуместный оператор. Тут - либо сам seed такое умеет, либо сделаем обёртку.
template<class T> struct arg_wrapper {
T value;
auto operator >> (auto fun) const {
using U = decltype(fun(value));
return arg_wrapper<U>{fun(value)};
// CTAD тут не работает.
// внутри класса имя класса означает не шаблон, а конкретное воплощение.
// поэтому тип придётся вывести вручную.
}
};
auto chain_for_all(auto seed, auto... funs) {
return (arg_wrapper{seed} >> ... >> funs).value;
}Делаем монаду Either...
Чтобы прервать цикл, - нужно сделать КТ-развилку: до точки прерывания оператор применяет функцию к аргументу, а после - игнорирует входящую функцию. Например, так:
template<class T, class C> struct either {
T value;
C cond;
constexpr bool is_right() const { return cond(value); }
decltype(auto) operator >> (auto fun) const {
if constexpr (cond(value)) {
return either<decltype(fun(value)), C>{fun(value), cond}; // rvalue
} else {
return *this; // const&
}
}
};
auto chain_for_all(auto seed, auto cond, auto... fs) {
return (either{seed, cond} >> ... >> fs).value;
}Я не просто так назвал обёртку either, - это действительно монада Either. Стартовое и промежуточные значения аргумента - либо Right что-то (продолжаем забег), либо Left что-то (игнорируем хвост).
<disclaimer>
Я не ставил перед собой задачу сделать полноценный интерфейс "тайпкласс монада", потому что моя задача - не хаскелл или скалу воспроизвести, а решить прикладную задачу.
</disclaimer>
Если мы договоримся, что функции сами отображают результат в Either, то можно не тащить проверочный предикат:
// здесь все f - это функции EitherOfSmth auto (Smth auto)
// где Smth - предметная область
template<Smth T> struct left {
REPRESENTS(EitherOfSmth)
REPRESENTS(LeftOfSmth)
T value;
// не будем заниматься копированием себя, а отдадим ссылку
EitherOfSmth auto&& operator >> (auto f) && { return std::move(*this); }
};
template<Smth T> struct right {
REPRESENTS(EitherOfSmth)
REPRESENTS(RightOfSmth)
T value;
EitherOfSmth auto operator >> (auto f) && { return f(std::move(value)); }
};
EitherOfSmth auto chain_for_either_monad(Smth auto seed, auto... fs) {
return (right{std::move(seed)} >> ... >> fs);
}(Здесь и далее я не буду поддерживать одновременно const& и &&, чтобы не загромождать рассуждения. Иначе там появятся страшненькие конструкции вида std::forward<decltype(v)>(v) и дублирование функций либо deducing this).
Делаем switch...
Но посмотрим, в каких случаях функция, выполняющая НАМ-правило (или НАМ-подпрограмму) возвращает Right? Когда аргумент не подошёл. Получается, что для сигнатуры EitherOfSmth(Smth) мы постоянно занимаемся распаковкой-переупаковкой. То, что хорошо для хаскелла, - плохо для C++. Поэтому первая идея - заменить сигнатуру на EitherOfSmth(RightOfSmth). Вместо тотальных функций из Smth в Either мы сделали частичные внутри Either. Но благодаря ветвлению в операторе >>, они, на самом деле, тотальные из Right в Either.
template<Smth T> struct left {
REPRESENTS(EitherOfSmth)
REPRESENTS(LeftOfSmth)
T value;
// не будем заниматься копированием себя, а отдадим ссылку
EitherOfSmth auto&& operator >> (auto f) && { return std::move(*this); }
};
template<Smth T> struct right {
REPRESENTS(EitherOfSmth)
REPRESENTS(RightOfSmth)
T value;
// функция может вернуть ссылку на this, если аргумент ей не подошёл
EitherOfSmth decltype(auto) operator >> (auto f) && { return f(std::move(value)); }
};
EitherOfSmth auto chain_for_either_monad(EitherOfSmth auto seed, auto... fs) {
return (std::move(seed) >> ... >> fs);
}
EitherOfSmth decltype(auto) some_fun(EitherOfSmth auto&& arg) {
if constexpr (.....)
return std::move(arg);
else
return left{.....};
}Тут, кстати, возникает интересная проблема - время жизни объектов. К концу выражения может приехать
исходный right-аргумент (не подошло ни к одной функции) по rvalue-ссылке
промежуточный left-результат (функция из середины вернула) по rvalue-ссылке
окончательный left-результат (последняя функция вернула) по rvalue
В первом случае было бы оптимально - передать внутрь забега по rvalue-ссылке и вернуть из забега тоже по rvalue-ссылке (не подошло для всей НАМ-подпрограмме). А во втором мы просто обязаны сделать из rvalue-ссылки честное rvalue, и вернуть копию.
Поэтому немного доработаем
template<Smth T> struct left {
.....
left commit() && { return std::move(*this); }
};
template<Smth T> struct right {
.....
right&& commit() && { return std::move(*this); }
};
EitherOfSmth decltype(auto) switch_for_either_monad(EitherOfSmth auto&& seed, auto... fs) {
return (std::move(seed) >> ... >> fs).commit();
}Для наглядности, переименую функцию цикла: switch_for_either_monad. Потому что это не просто цепочка, где из произвольных Right получаются другие произвольные Right или Left, а именно поиск первого подошедшего правила. Тут прямо оговорено, что если результат Right, то это та же самая ссылка, что и на входе.
Делаем switch ещё лучше!..
Но раз так, то оказывается, мы можем сократить работу! Заставим компилятор выполнить КТ-вычисление внутри КТ-вычисления. Смотрите, в чём трюк. Мы договорились, что функция возвращает Right, когда аргумент не подошёл. Значит, если мы найдём такую функцию, которая вернёт Left, то применим лишь её.
template<class F> struct matched_fun;
template<EitherOfSmth T> struct will_match_to {
auto operator | (auto f) const {
using R = decltype(f(std::declval<T>()));
if constexpr (RightOfSmth<R>)
return *this;
else
return matched_fun{f};
};
auto&& doit(T&& arg) const { return arg; } // если ничего не подошло
};
template<class F> struct matched_fun {
F f;
const auto& operator | (auto g) const { return *this; }
decltype(auto) doit(auto&& arg) const { return f(std::move(arg)); }
};
EitherOfSmth decltype(auto) switch_for_either_monad(EitherOfSmth auto&& seed, auto... fs) {
using T = decltype(seed);
return (will_match_to<T>{} | ... | fs).doit(std::move(seed));
}Казалось бы, мы заставили компилятор выполнить одно дело дважды. Сначала он всё равно вычислял результаты всех функций из головы, а затем ещё раз вычислил успешный результат.
Но.
Во-первых, когда таких запусков свитча много (на каждой итерации НАМ-машины), компилятор обязан будет инстанцировать все служебные функции под каждый набор типов аргументов.
В самом общем случае chain... это operator >> для (T0,F1), (T1,F2), ..., (Tn_1,Fn).
Если chain работает как switch, - то operator >> (T0,F1), ..., (T0,Fk), (Lk,Fk1), ..., (Lk,Fn) - где правило номер k вернуло Left.
И, поскольку для каждой итерации эти типы T0 и Lk уникальны, то компилятор инстанцирует тривиальные хвостовые operator >> (Lk,Fm) ... (Lk,Fn) - фактически, одинаковые, но формально, уникальные. Потом он их проинлайнит, но пространство символов себе и линкеру замусорит.
А для хитрого свитча - забег по голове никуда не делся, но весь хвост - это operator| (Fk1,Fk2), (Fk2,Fk3), ..., (Fn_1,Fn). Одни и те же для всех итераций.
Во-вторых, объём работы для вывода типа не превосходит объём работы для вычисления значения. А в некоторых случаях оказывается заметно меньше. Это будет важно, когда я начну передавать в НАМ-машину не голые строки-синглетоны, а аугментированные - с разной отладочной информацией.
В-третьих, когда я наконец вытащу КТ-вычисления в РТ, - поиск подходящего правила по-прежнему останется в КТ, вместо того, чтобы в РТ бегать по всей неподходящей голове и по всему отвергнутому хвосту, пусть даже занимаясь передачей ссылок, и надеясь, что компилятор сможет оптимизировать это всё.
Цикл while
В отличие от for (или switch), здесь ситуация другая: элемент всего один, но количество итераций непредсказуемо (и может измеряться сотнями и даже тысячами).
Рекурсия неизбежна, и, к сожалению, C++ не обещает поддержку концевой рекурсии. Поэтому выход один: разворачивать цикл по кусочкам.
Пусть у нас уже есть монада Either, - не хочу протаскивать какие-то сторонние предикаты.
Для функции тела цикла она значит нечто иное: Left - закончили вычисления (достигли финального состояния), Right - продолжили (сделали подстановку в обычном правиле).
Наивный цикл ("пока не получим Left") выглядит так
EitherOfSmth auto run_naive_loop(EitherOfSmth auto seed, const auto& f) {
if constexpr(Left<decltype(seed)>)
return seed;
else
return run_naive_loop(f(std::move(seed)), f);
}Помня о том, что мы в Either, можем развернуть кусок цикла прямо на месте
EitherOfSmth auto run_unrolled_loop(EitherOfSmth auto seed, const auto& f) {
if constexpr(Left<decltype(seed)>)
return seed;
else
return run_unrolled_loop(std::move(seed) >> f >> f >> f >> f >> f, f);
}
// или даже так (старый добрый карринг)
template<class F> struct unrolled_loop {
F f;
auto operator()(EitherOfSmth auto seed) const {
return std::move(seed) >> f >> f >> f >> f >> f >> *this;
}
};
auto run_unrolled_loop(auto seed, auto f) { return unrolled_loop{f}(std::move(seed)); }Но этот код несёт две проблемы. Первая - мы захардкодили величину развёртки цикла (сколько раз скопипастили >>f), а вторая - холостой забег по хвосту цепочке, когда получили Left.
Штош, решим это не самым красивым способом, без операторов, зато надёжным.
Развёртка цикла без лишнего хвоста
// Да-да, тот самый цикл for. Но с учётом того, что функций будет 1 или мало.
auto chain(RightOfSmth auto seed, auto f, auto... fs) {
if constexpr (sizeof...(fs) == 0 || Left<decltype(f(std::move(seed)))>)
return f(std::move(seed));
else
return chain(f(std::move(seed)), fs...);
}
// развёртка цикла на небольшую глубину n - по аналогии.
auto repeat(RightOfSmth auto seed, auto f, CtSize ctn) {
constexpr size_t n = ctn.value;
static_assert(n > 0);
else if constexpr (n == 1 || Left<decltype(f(std::move(seed)))>)
return f(std::move(seed));
else
return repeat(f(std::move(seed)), f, ctv<n - 1>);
}
// а теперь займёмся развёрткой развёрток
// U - unroll
template<size_t U, class F> struct multiply_f {
static_assert(U > 0);
F f;
auto operator()(RightOfSmth auto seed) const {
if constexpr (U <= 10)
return repeat(std::move(seed), f, ctv<U>);
else
return chain(
std::move(seed),
multiply_f<10>{f},
multiply_f<U-10>{f}
);
}
};
template<size_t U, class F> struct unrolled_loop {
static_assert(U > 0);
F f;
auto operator()(RightOfSmth auto seed) const {
return chain(std::move(seed), multiply_f<U>{f}, *this);
}
};Мы уменьшили глубину рекурсии в U раз, но она всё ещё линейно зависит от числа итераций.
Логарифмическая глубина (если она нам нужна)
Можем пойти ещё дальше, сделать глубину логарифмической. Для этого каждый новый цикл будем запускать не над тем же телом f, а над его повторением:
template<size_t U, size_t M, class F> struct unrolled_loop {
static_assert(U > 0);
static_assert(M > 0); // 1 означает линейную глубину
F f;
auto operator()(RightOfSmth auto seed) const {
return chain(
std::move(seed),
multiply_f<U>{f},
unrolled_loop<U, M>{ multiply_f<M>{f} }
);
}
};На самом деле, логарифмическая глубина не всегда нужна. Даже если мы ограничим глубину рекурсии в constexpr-функциях, например, -fconstexpr-depth=100 (по умолчанию у gcc там 512, кажется), то при U=50 мы получаем порядка 2500 итераций. А при глубине 500 - уже 22550. Для работы с синглетонами строк это очень много.
Ограничение длительности (если оно нам нужно)
Любая программа может зависнуть. Не хотелось бы, чтобы компилятор просто вывалился в ICE или выдавил всю систему в своп.
Чтобы это не случилось, добавим к циклу ещё один параметр - лимит итераций. Это несложно, но громоздко (особенно, если глубина логарифмическая).
constexpr size_t UNLIMITED = std::numeric_limits<size_t>::max();
template<size_t U, size_t M, class L, class F> struct unrolled_loop {
static_assert(U > 0);
static_assert(M > 0); // 1 означает линейную глубину
F f;
auto operator()(RightOfSmth auto seed) const {
decltype(auto) s = std::move(seed);
if constexpr (L == 0)
return seed;
else if constexpr (L < U)
return multiply_f<L>{f}(s);
else {
auto uf = multiply_f<U>{f};
if constexpr (M == 1)
if constexpr (L == UNLIMITED)
return chain(s, uf, *this);
else
return chain(s, uf, unrolled_loop<U, 1, L - U>{f});
else {
auto mf = multiply_f<M>{f};
if constexpr (L == UNLIMITED)
return chain(s, uf, unrolled_loop<U, M, UNLIMITED>{mf});
else {
// самый страшный случай
constexpr size_t Lnext = (L - U) / M;
constexpr size_t Uhere = L - Lnext * M; // U <= Uhere < U+M
return chain(s, uf, unrolled_loop<Uhere, M, Lnext>{mf});
}
}
}
};Pen-pineapple-apple-pen!
Пришло время взглянуть на то, как работают оба цикла вместе.
НАМ-правило берёт строку (выковыривая её из right-обёртки) и в случае неуспеха возвращает эту же right-строку, а в случае успеха - left-нечто. Тем самым мы обеспечили прерывание НАМ-подпрограммы до самого верхнего уровня (если у нас там вложенные подпрограммы были).
Цикл НАМ-машины берёт это нечто (выковыривает из left) и смотрит - это результат успеха обычного или финального правила. Если обычного, то идёт на следующий круг. Если финального - завершается.
Следовательно, нечто для обычного правила - это right-строка, а для финального - left-строка.
То есть, НАМ-машина и все её детальки живут в категории Either (Either CtStr CtStr) CtStr.
Аргументы функций - всегда Right CtStr.
Результаты
неудача подстановки - Right CtStr
обычная подстановка - Left (Right CtStr)
финальная - Left (Left CtStr)
А чтобы цикл никогда не столкнулся с right (ничего не подошло) и не знал, как из него что-то выковыривать, - просто добавим в конец программы пустое финальное правило. Тогда программа всегда будет возвращать какой-то left.
Красота? Страшная сила!
Только эта красота, к сожалению, имеет свою цену. В ходе экспериментов выяснилось, что компилятор тратит на какие-то мелочные работы слишком много сил и памяти. Я полагаю, он валит все специализации left<left>, left<right>, left<str> в одну большую кучу. Мой ноутбук перегревался, а на больших программах (на арифметике) вываливал систему в своп.
Я же говорил, что нас ждут неприятности!
Поэтому пришлось изобрести ad-hoc монаду из трёх, а не дважды-двух видов.
Неприятность эту мы переживём.
Tristate
Это в точности отвечает внутреннему состоянию НАМ-машины:
not_matched_yet<CtStr> - строка ещё не сопоставлена с правилами
matched_regular<CtStr> - выполнена обычная подстановка
matched_final<CtStr> - выполнена финальная подстановка
Только тело цикла теперь должно не выковырять новое значение из left-обёртки, а поменять вид:
программа вернула not_matched_yet - ни одно правило не подошло - превращаем в matched_final, аварийное завершение (иначе мы просто зациклимся, снова ничего не подойдёт)
matched_regular - перекладываем в not_matched_yet и отправляем на следующий виток
matched_final - оставляем как есть.
Чтобы не плодить типы с разными именами, я предпочёл завести структуру с параметром-флажком
CONCEPT_WITH_TYPE(Tristate)
CONCEPT_WITH_TYPE(NotMatchedYet)
CONCEPT_WITH_TYPE(Matched)
enum class tristate_kind {
not_matched_yet,
matched_regular,
matched_final,
};
template<tristate_kind kind, class T> struct tristate {
using type = T;
T value;
REPRESENTS(Tristate)
REPRESENTS_COND(NotMatchedYet, kind == tristate_kind::not_matched_yet)
REPRESENTS_COND(Matched, kind != tristate_kind::not_matched_yet)
decltype(auto) operator >> (auto f) && {
if constexpr (kind == tristate_kind::not_matched_yet)
return f(std::move(*this));
else
return std::move(*this);
}
// забег по цепочке (seed >> f1 >> ... >> fn).commit()
// чтобы не было висячей ссылки
decltype(auto) commit() && {
if constexpr (kind == tristate_kind::not_matched_yet)
return std::move(this);
else
return tristate{std::move(this)}; // не tristate<tristate<...>>, а копия
}
// в конце итерации
decltype(auto) commit_loop() && {
if constexpr (kind == tristate_kind::matched_regular)
return tristate<T, tristate_kind::not_matched_yet>{std::move(value)};
else
return tristate<T, tristate_kind::matched_final>{std::move(value)};
}
};
template<class T> using not_matched_yet = tristate<T, tristate_kind::not_matched_yet>;
template<class T> using matched_regular = tristate<T, tristate_kind::matched_regular>;
template<class T> using matched_final = tristate<T, tristate_kind::matched_final>;Подпрограмма всё так же выполняет switch-забег, - естественно, глядя не на Right-Left, а на NotMatchedYet / Matched.
Цикл машины теперь нуждается в промежуточной функции "тело цикла", которая делает этот самый commit_loop.
template<Rule auto p> struct loop_body {
auto operator()(NotMatchedYet auto seed) const {
return seed.commit_loop();
}
};
template<Rule auto p> struct rule_loop {
constexpr size_t U = 50;
constexpr size_t M = 1;
constexpr size_t L = 5000;
static constexpr auto body = loop_body<p>{};
// естественно, что unrolled_loop переписан с Either на Tristate
static constexpr auto loop = unrolled_loop<U,M,L>{body};
auto operator()(NotMatchedYet auto seed) const {
return loop(std::move(seed));
}
};Получилась вот такая диаграмма состояний
Или, укрупнённо (и с пределом по количеству)
НАМ-машина целиком
Посмотрим, что в итоге у нас получилось на данный момент. (Скоро мы этот момент исправим и дополним...)
CONCEPT(Rule)
CONCEPT(Machine)
template<class T> concept MachineData = CtStr<T>;
template<class T> concept RuleInput = NotMatchedYetOfTraits<is_MachineData>;
template<class T> concept RuleOutput = TristateOfTraits<is_MachineData>;
enum class rule_kind {
regular,
final,
};
template<Str auto s, Str auto r, rule_kind k> struct rule {
REPRESENTS(Rule)
RuleOutput decltype(auto) operator()(RuleInput auto&& input) const {
MaybeOfTraits<is_CtStr> auto res = try_substitute(input.value, ctv<s>, ctv<r>);
if constexpr (!res)
return std::move(input);
else if constexpr (k == rule_kind::matched_regular)
return matched_regular{res.value};
else
return matched_final{res.value};
}
};
// тут вся обвязка для switch...
template<Rule auto... ps> struct rules {
REPRESENT(Rule)
RuleOutput decltype(auto) operator()(RuleInput auto&& input) const {
return switch_for_tristate_monad(std::move(input), ps...);
}
};
template<Rule auto program> struct loop_body {
REPRESENT(Rule)
RuleOutput decltype(auto) operator()(RuleInput auto&& input) const {
return input.commit_loop();
}
};
template<Rule auto program> struct rule_loop {
REPRESENT(Rule)
RuleOutput decltype(auto) operator()(RuleInput auto&& input) const {
return unrolled_loop{loop_body<program>{}}(std::move(input));
}
};
// машину, в принципе, можно параметризовать и программой без цикла,
// такая машина выполнит ровно одну итерацию и остановится.
template<Rule auto loop> struct machine {
MachineData auto operator()(MachineData auto input) const {
return loop(not_matched_yet{std::move(input)}).value;
}
};Ну вот, мы проделали основную часть спуска по лестнице с неприятностями!
В следующей части пойдём превозмогать рантайм.