Nenormal

Nenormal - проект для хаба "ненормальное программирование" на habr.ru

Это реализация нормальных алгорифмов Маркова (НАМ) на языке шаблонов C++, выполняемая во время компиляции.

Не пытайтесь использовать этот код в продакшене! Он вынесет мозг компилятору!!!

Черновик статьи

Список документации

• TODO
• Примеры
• Концепты
• Композиция функций
• Троичная монада
• Аугментация
• Передача значений
• Плохие правила

Машина Нормального Алгорифма Маркова (НАМ-машина)

Машина устроена следующим образом.

• Программа - это последовательность правил подстановки - троек
  • строка поиска search
  • строка замены replace
  • признак "финальное/обычное" (по умолчанию, для краткости, - "обычное")
• Данные - это строка text, над которой выполняется программа

Один такт машины состоит в том, что мы находим первую подходяющую search-строку - самую левую подстроку в text, и выполняем одиночную замену её на replace-строку.

Например, программа [("world", "mir"), ("hello", "privet")] над текстом "hello world" за первый такт заменит world на mir, несмотря на то, что hello там тоже есть.

Машина останавливается,

• когда было применено правило с признаком "финиш"
• когда ничего не удалось найти (и заменить).

Детали реализации

О том, как устроены циклы над функциями - в тексте details/functional_composition.md

Но проще всего сразу смотреть на примеры и юниттесты.

Концепты

Нужны в основном для повышения читаемости и уменьшения ошибкоопасности кода.

Каждому шаблону структуры (или семейству таких структур) с именем, например, foo<...> назначается концепт Foo<T>.

Это позволяет вместо громоздких объявлений функций

template<XXXXX> auto bar(foo<XXXXX> f)

писать лаконично

auto bar(Foo auto f)

Подробнее о концептах - в тексте Концепты

Зависимые типы

Зависимый тип ct<auto V> (ct - compile time) переводит произвольное constexpr-значение V в тип. Это нужно в первую очередь для строк произвольной длины.

Значение можно извлечь из типа через статический член value.

Строки

Обычный строковый литерал "something" не является полноценной сущностью языка, и в одних случаях выступает, как массив, в других - как указатель, что не позволяет напрямую работать с ним, как с constexpr-значением.

Для представления строки используется структура - обёрткаstr<size_t N> над массивом char[N+1], где N - размер массива без учёта концевого нуля.

Методы size(), begin(), end() не включают этот концевой ноль.

Строке соответствует зависимый тип ct<Str auto s> - для этого вводится концепт CtStr

Именованные строковые литералы

Для уменьшения громоздкости

• вместо str{"hello"} используется именованный литерал "hello"_ss. (ss - static string)
• вместо ct<str{"hello"}>{} - именованный литерал "hello"_cts. (cts - compile time string)

Элементы НАМ-машины

Призак продолжения/финиша - чтобы не запутаться в булевых флажках сделан как

enum rule_kind { rule_kind::regular, rule_kind::final };

Каждая инструкция машины - это функция

• параметризованная
  • парой строк search и replace
  • и признаком продолжения/финиша,
• принимающая "ещё не найденную" строку not_matched_yet,
• возвращающая успешный результат
  • matched_regular если правило обычное
  • matched_final если правило финальное
  • либо признак неудачи - not_matched_yet.

Поскольку тип результата (выбор между строкой и неудачей, а также длина строки) зависит от входного значения, то аргументом является не Str, а CtStr.

В коде, чтобы отличать эти строки, введён концепт MachineData, - либо CtStr, либо аугментированная строка (см. Аугментация).

Для однородности, возвращаемая строка тоже CtStr. На самом деле, можно было бы возвращать constexpr Str auto - но мы немедленно переводили бы её в CtStr для передачи в другие правила.

Возвращаемый результат RuleOutput - это обёртка над MachineData, - одна из структур, образующих семейство. Подробнее см. Tristate

Аргументом является не непосредственно MachineData, а частный случай RuleOutput - RuleInput - то есть, not_matched_yet<T>, где T - MachineData.

Подробнее, зачем сделано именно так, - см. передача аргументов

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

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

template<Str auto search, Str auto replace, rule_kind kind> struct rule {
    constexpr
    RuleOutput decltype(auto)
    operator()(RuleInput auto&& text) const
    { ..... }
};

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

Подпрограммы НАМ-машины

Последовательность инструкций p1 = rule<s1,r1,f>{}, p2 = rule<s2,r2,f>{}, ... можно представить как одну макро-инструкцию, или подпрограмму.

Логика её работы такая:

• если подстановка dst1 = p1(src) успешна, возвращаем dst1
• если подстановка dst2 = p2(src) успешна, возвращаем dst2
• и так далее
• если все подстановки неудачны, возвращаем not_matched_yet

То есть, вид функции такой же, как у одиночной инструкции.

(Если в подпрограмме нет инструкций, то она сразу возвращает not_matched_yet).

Поэтому структура rules<Rule auto ps...> также является представителем концепта Rule.

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

Цикл исполнения

Цикл является функцией rule_loop, принимающей на вход MachineData и возвращающей RuleOutput.

Из тех же соображений, типы аргумента и результата содержат полиморфные строки, а сама функция - это шаблон структуры

template<Rule auto program> struct rule_loop {
    constexpr
    RuleFinalOutput decltype(auto)
    operator()(RuleInput auto&& src) const {.....}
};

Машина реализует цикл вида

while (true) {
    auto dst = program(src);
    if (dst is final) return dst;
    src = dst.value;
}

но, поскольку в этом цикле типы меняются, то используется рекурсия.

Формально, rule_loop также попадает под концепт Rule, но с важным отличием!

Инструкции и подпрограммы выполняются строго за один такт, а цикл работает до упора.

НАМ-машина целиком

Машина принимает строку на вход - и возвращает окончательную строку.

Поэтому machine_fun является простейшей надстройкой над rule_loop.

Способ написания кода

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

Подробнее о примерах - в examples/

Расширения

Хотя изначально НАМ-машина преобразует строки в строки, мы можем дополнить данные в духе монады State.

Это позволяет совершать вычисления как во время компиляции, так и во время исполнения, что может пригодиться для отладки.

Подробнее - см. аугментация