Сообщение ненормальные нормальные алгорифмы от 01.05.2026 20:23
Изменено 01.05.2026 20:26 Кодт
ненормальные нормальные алгорифмы
Вот давеча LaptevVV спрашивал про constexpr, так у меня есть кое-чего.
Хочу показать свою заготовку.
Пилю библиотеку Нормальных Алгорифмов Маркова во время компиляции.
https://github.com/nickolaym/nenormal
Понятное дело, что это извращения с кодом, и вообще, когда допилю, (надеюсь, к Дню Программиста), сделаю статью на хабре.
Но сейчас мне просто нужна обратная связь по коду.
Из TODO
— обмазать всё пространствами имён
— унифицировать имена и даже их стиль (там у меня и кемелКейс местами есть)
— переписать доки, нормально осмыслить базис теории категорий, который там просвечивает, но вполсилы
— сделать так, чтобы код одинаково хорошо работал и во время компиляции на уникальных типах, и во время исполнения на однородных
— сделать аугментацию более универсальной (сейчас сигнатура колбеков зафиксирована, и вызываются они строго в определённых местах)
— выкинуть неудачные подходы к снаряду, добавить удачные
— сделать инструменты статического и динамического анализа машины (возможное зацикливание, ошибки, отчёты...)
Пока всего этого нет, — статьи тоже нет )))
Но я обещаю, будет!
Что это и зачем
1) НАМ — абстрактная машина, представляющая последовательность правил поиска-и-замены подстрок. Состояние машины — это строка.
Машина ищет первое подходящее правило и меняет первое вхождение искомой строки на заменную. Если правило не помечено, как финальное, то машина повторяет эту процедуру.
Если ничего не подошло, то состояние не изменилось и, очевидно, не изменится. Такое диагностируемое зацикливание также является финальным состоянием.
Можно сказать, что в конце НАМ-программы неявно стоит правило (""/"",стоп).
2) Во время компиляции использовать динамические контейнеры можно ОЧЕНЬ ограниченно, поэтому сделал всё на чистых константах времени компиляции, для этого нужны зависимые типы.
3) Циклы на полиморфных типах невозможны, поэтому сделано всё на рекурсии. Но рекурсия — ограниченный ресурс компилятора (да и рантайма), поэтому применил лайфхаки по развёртыванию циклов.
Сейчас машина допускает программы неограниченной длины (300 правил как нефиг делать), работающие не более 9000 итераций (глубина 900 помножить на развёртывание цикла на 10 шагов).
Увеличить время работы можно экспоненциально!!! (сделать цикл саморасширяемым), но это в конечном счёте убьёт компилятор.
Пример программы
В порядке безумия я там даже умножение и деление на марковских алгорифмах забабахал. Последовательность Коллаца.
Работает! Только компилируется около полутора минут.
Хочу показать свою заготовку.
Пилю библиотеку Нормальных Алгорифмов Маркова во время компиляции.
https://github.com/nickolaym/nenormal
Понятное дело, что это извращения с кодом, и вообще, когда допилю, (надеюсь, к Дню Программиста), сделаю статью на хабре.
Но сейчас мне просто нужна обратная связь по коду.
Из TODO
— обмазать всё пространствами имён
— унифицировать имена и даже их стиль (там у меня и кемелКейс местами есть)
— переписать доки, нормально осмыслить базис теории категорий, который там просвечивает, но вполсилы
— сделать так, чтобы код одинаково хорошо работал и во время компиляции на уникальных типах, и во время исполнения на однородных
— сделать аугментацию более универсальной (сейчас сигнатура колбеков зафиксирована, и вызываются они строго в определённых местах)
— выкинуть неудачные подходы к снаряду, добавить удачные
— сделать инструменты статического и динамического анализа машины (возможное зацикливание, ошибки, отчёты...)
Пока всего этого нет, — статьи тоже нет )))
Но я обещаю, будет!
Что это и зачем
1) НАМ — абстрактная машина, представляющая последовательность правил поиска-и-замены подстрок. Состояние машины — это строка.
Машина ищет первое подходящее правило и меняет первое вхождение искомой строки на заменную. Если правило не помечено, как финальное, то машина повторяет эту процедуру.
Если ничего не подошло, то состояние не изменилось и, очевидно, не изменится. Такое диагностируемое зацикливание также является финальным состоянием.
Можно сказать, что в конце НАМ-программы неявно стоит правило (""/"",стоп).
2) Во время компиляции использовать динамические контейнеры можно ОЧЕНЬ ограниченно, поэтому сделал всё на чистых константах времени компиляции, для этого нужны зависимые типы.
3) Циклы на полиморфных типах невозможны, поэтому сделано всё на рекурсии. Но рекурсия — ограниченный ресурс компилятора (да и рантайма), поэтому применил лайфхаки по развёртыванию циклов.
Сейчас машина допускает программы неограниченной длины (300 правил как нефиг делать), работающие не более 9000 итераций (глубина 900 помножить на развёртывание цикла на 10 шагов).
Увеличить время работы можно экспоненциально!!! (сделать цикл саморасширяемым), но это в конечном счёте убьёт компилятор.
Пример программы
constexpr auto executor = machine_fun<
rule_loop<
rules<
rule<str{"hello"}, str{"privet"}, regular_state>{},
rule<str{"world"}, str{"mir"}, regular_state>{}
>{}
>{}
>{};
// правила внесены как аргументы шаблона, а не как члены кортежа. всё равно типы зависимые, поэтому члены-данные - избыточны
constexpr auto input_value = str{"hello world!"}; // строка времени компиляции - здесь это константный массив (длина выведена из литерала)
constexpr auto input = ct<input_value>{}; // константа времени компиляции с уникальным типом
constexpr auto result = executor(input); // в constexpr-функцию (operator()) передали истинную константу и получили на выходе истинную константу
constexpr auto result_value = result.value; // сама строка лежит в статической константе
static_assert(result_value == str("privet mir!"});В порядке безумия я там даже умножение и деление на марковских алгорифмах забабахал. Последовательность Коллаца.
Работает! Только компилируется около полутора минут.
ненормальные нормальные алгорифмы
Вот давеча LaptevVV спрашивал про constexpr, так у меня есть кое-чего.
Хочу показать свою заготовку.
Пилю библиотеку Нормальных Алгорифмов Маркова во время компиляции.
https://github.com/nickolaym/nenormal
Понятное дело, что это извращения с кодом, и вообще, когда допилю, (надеюсь, к Дню Программиста), сделаю статью на хабре.
Но сейчас мне просто нужна обратная связь по коду.
Из TODO
— обмазать всё пространствами имён
— унифицировать имена и даже их стиль (там у меня и кемелКейс местами есть)
— переписать доки, нормально осмыслить базис теории категорий, который там просвечивает, но вполсилы
— сделать так, чтобы код одинаково хорошо работал и во время компиляции на уникальных типах, и во время исполнения на однородных
— сделать аугментацию более универсальной (сейчас сигнатура колбеков зафиксирована, и вызываются они строго в определённых местах)
— выкинуть неудачные подходы к снаряду, добавить удачные
— сделать инструменты статического и динамического анализа машины (возможное зацикливание, ошибки, отчёты...)
Пока всего этого нет, — статьи тоже нет )))
Но я обещаю, будет!
Что это и зачем
1) НАМ — абстрактная машина, представляющая последовательность правил поиска-и-замены подстрок. Состояние машины — это строка.
Машина ищет первое подходящее правило и меняет первое вхождение искомой строки на заменную. Если правило не помечено, как финальное, то машина повторяет эту процедуру.
Если ничего не подошло, то состояние не изменилось и, очевидно, не изменится. Такое диагностируемое зацикливание также является финальным состоянием.
Можно сказать, что в конце НАМ-программы неявно стоит правило (""/"",стоп).
2) Во время компиляции использовать динамические контейнеры можно ОЧЕНЬ ограниченно, поэтому сделал всё на чистых константах времени компиляции, для этого нужны зависимые типы.
3) Циклы на полиморфных типах невозможны, поэтому сделано всё на рекурсии. Но рекурсия — ограниченный ресурс компилятора (да и рантайма), поэтому применил лайфхаки по развёртыванию циклов.
Сейчас машина допускает программы неограниченной длины (300 правил как нефиг делать), работающие не более 9000 итераций (глубина 900 помножить на развёртывание цикла на 10 шагов).
Увеличить время работы можно экспоненциально!!! (сделать цикл саморасширяемым), но это в конечном счёте убьёт компилятор.
Пример программы
В порядке безумия я там даже умножение и деление на марковских алгорифмах забабахал. Последовательность Коллаца.
Работает! Только компилируется около полутора минут.
Хочу показать свою заготовку.
Пилю библиотеку Нормальных Алгорифмов Маркова во время компиляции.
https://github.com/nickolaym/nenormal
Понятное дело, что это извращения с кодом, и вообще, когда допилю, (надеюсь, к Дню Программиста), сделаю статью на хабре.
Но сейчас мне просто нужна обратная связь по коду.
Из TODO
— обмазать всё пространствами имён
— унифицировать имена и даже их стиль (там у меня и кемелКейс местами есть)
— переписать доки, нормально осмыслить базис теории категорий, который там просвечивает, но вполсилы
— сделать так, чтобы код одинаково хорошо работал и во время компиляции на уникальных типах, и во время исполнения на однородных
— сделать аугментацию более универсальной (сейчас сигнатура колбеков зафиксирована, и вызываются они строго в определённых местах)
— выкинуть неудачные подходы к снаряду, добавить удачные
— сделать инструменты статического и динамического анализа машины (возможное зацикливание, ошибки, отчёты...)
Пока всего этого нет, — статьи тоже нет )))
Но я обещаю, будет!
Что это и зачем
1) НАМ — абстрактная машина, представляющая последовательность правил поиска-и-замены подстрок. Состояние машины — это строка.
Машина ищет первое подходящее правило и меняет первое вхождение искомой строки на заменную. Если правило не помечено, как финальное, то машина повторяет эту процедуру.
Если ничего не подошло, то состояние не изменилось и, очевидно, не изменится. Такое диагностируемое зацикливание также является финальным состоянием.
Можно сказать, что в конце НАМ-программы неявно стоит правило (""/"",стоп).
2) Во время компиляции использовать динамические контейнеры можно ОЧЕНЬ ограниченно, поэтому сделал всё на чистых константах времени компиляции, для этого нужны зависимые типы.
3) Циклы на полиморфных типах невозможны, поэтому сделано всё на рекурсии. Но рекурсия — ограниченный ресурс компилятора (да и рантайма), поэтому применил лайфхаки по развёртыванию циклов.
Сейчас машина допускает программы неограниченной длины (300 правил как нефиг делать), работающие не более 9000 итераций (глубина 900 помножить на развёртывание цикла на 10 шагов).
Увеличить время работы можно экспоненциально!!! (сделать цикл саморасширяемым), но это в конечном счёте убьёт компилятор.
Пример программы
constexpr auto executor = machine_fun<
rule_loop<
rules<
rule<str{"hello"}, str{"privet"}, regular_state>{},
rule<str{"world"}, str{"mir"}, regular_state>{}
>{}
>{}
>{};
// правила внесены как аргументы шаблона, а не как члены кортежа. всё равно типы зависимые, поэтому члены-данные - избыточны
constexpr auto input_value = str{"hello world!"}; // строка времени компиляции - здесь это константный массив (длина выведена из литерала)
constexpr auto input = ct<input_value>{}; // константа времени компиляции с уникальным типом
constexpr auto result = executor(input); // в constexpr-функцию (operator()) передали истинную константу и получили на выходе истинную константу
constexpr auto result_value = result.value; // сама строка лежит в статической константе
static_assert(result_value == str{"privet mir!"});В порядке безумия я там даже умножение и деление на марковских алгорифмах забабахал. Последовательность Коллаца.
Работает! Только компилируется около полутора минут.