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

(Сокращения: НАМ - нормальные алгорифмы Маркова, КТ - компайл-тайм, РТ - рантайм).

Следующая неприятность, которая нас ждёт, - это циклы, которые в КТ вовсе не циклы. Нам надо как-то научиться бегать по правилам, из которых состоит НАМ-программа.

Продолжение. Первая часть - программирование на НАМ. Вторая - обзор неприятностей, концепты.

Пришло время запутаться и распутаться со строками в компайл-тайме... и с зависимыми типами.

Основные требования к КТ-строкам - чтобы можно было использовать их в качестве параметров шаблона, и чтобы можно было писать constexpr-функции, логика и типы которых зависят от значений аргументов. Это не очень сложно, но может быть неочевидно.

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

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

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

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

Какие программы могут быть по-настоящему достойны хаба "ненормальное программирование"?

Конечно же, программы для нормальных марковских алгорифмов! (Далее - НАМ).

Но, будем честны перед собой: абстрактные машины - очень просты в реализации. Зачастую вызов состоит в том, чтобы сделать какую-нибудь эзотерическую версию, язык для машины на минималках, и затем ещё и минимизировать транслятор для него.

Поэтому поставим задачу со звёздочкой: научимся писать для НАМ в компайл-тайме С++!

Для начала, посмотрим: что такое НАМ и что на них вообще можно делать.

Я хочу сыграть с вами в одну игру...
— Дж. Конвей, про игру "Жизнь" (и про фрактран тоже)

Эту статью я хотел написать ещё полтора года назад, но почему-то замешкался и стёр черновик. Но вот наконец дошли руки.

Суть игры

Вы задаёте список неотрицательных рациональных дробей (программу) и некоторое натуральное число (состояние).
Ищете в программе первую дробь, такую, что произведение её на состояние остаётся натуральным. Это значение становится новым состоянием.
Повторяете процедуру.
Если ни одна из дробей не подошла, программа останавливается.

Этот список дробей является программой на эзотерическом языке Фрактран, о котором на хабре была статья.

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

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

Итак. Пусть у нас есть полиморфная (шаблонная, перегруженная, - неважно) функция f(x).
И мы написали концепт, который говорит, что тип может быть аргументом этой функции.
Назовём его fable, то есть, "f-абельный", или, по-русски, "сказка". (Эта сказка будет страшной).

На C++20 это выглядит очень просто и элегантно. (Без requires в виде шаблонной метафункции это тоже делается, но заметно громоздче).

Представьте себе, что вы студент, изучающий современные фичи C++. И вам дали задачу по теме concepts/constraints. У преподавателя, конечно, есть референсное решение "как правильно", но для вас оно неочевидно, и вы навертели гору довольно запутанного кода, который всё равно не работает. (И вы дописываете и дописываете всё новые перегрузки и специализации шаблонов, покрывая всё новые и новые претензии компилятора).

А теперь представьте себе, что вы — преподаватель, который увидел эту гору, и захотел помочь студенту. Вы стали упрощать и упрощать его код, и даже тупо комментировать куски юнит-тестов, чтобы оно хоть как-то заработало... А оно всё равно не работает. Причём, в зависимости от порядка юнит-тестов, выдаёт разные результаты или вообще не собирается. Где-то спряталось неопределённое поведение. Но какое?

Сперва преподаватель (то есть, я) минимизировал код вот до такого: https://gcc.godbolt.org/z/TaMTWqc1T

Программистам на C++ хорошо (надеюсь!) известно, что во время компиляции можно производить разнообразные вычисления. Лишь бы эти вычисления были "чистыми", без побочных эффектов. Это делается на шаблонах и на constexpr функциях.

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

Для стресс-тестирования возьмём наивную формулу чисел Фибоначчи:

f(n) = (n < 2) ? 1 : f(n-1) + f(n-2)

class Base { virtual int foo() const = 0; };
class A : public Base { int foo() const { return 1; } };
class B : public Base { int foo() const { return 2; } };
class C : public Base { int foo() const { return 3; } };
class D : public Base { int foo() const { return 4; } };

Base* getconfig(char cfg) // не будем пока отвлекаться на уборку мусора
{
  switch(cfg)
  {
  case 'a': return new A();
  case 'b': return new B();
  case 'c': return new C();
  case 'd': return new D();
  default: throw std::invalid_argument("bad type");
  }
}

int entry(Base* x, Base* y) { return x->foo()*10 + y->foo(); }

void run(char cx, char cy) { std::cout << cx << cy << " : " << entry(getconfig(cx), getconfig(cy)) << std::endl; }