Машина Тьюринга на шаблонах
Каждый интересующийся шаблонами в С++ скорее всего слышал об их Тьюринг-полноте и связанных с этим шутках про «we put a language in your language, so you can program while you program». В этом посте я расскажу как с помощью шаблонов и константных выражений построить настоящую машину Тьюринга, вычисляющую результат своей работы во время компиляции, на которой можно будет запускать уже существующие программы. Например усердный бобер с 4 состояниями и 2 символами выглядит как-то так:
ADD_STATE(A);
ADD_STATE(B);
ADD_STATE(C);
ADD_STATE(D);
ADD_RULE(A, Blank, 1, Right, B);
ADD_RULE(A, 1, 1, Left, B);
ADD_RULE(B, Blank, 1, Left, A);
ADD_RULE(B, 1, Blank, Left, C);
ADD_RULE(C, Blank, 1, Right, Stop);
ADD_RULE(C, 1, 1, Left, D);
ADD_RULE(D, Blank, 1, Right, D);
ADD_RULE(D, 1, Blank, Right, A);
using tape = Tape;
using machine = Machine;
using result = Run::type;
int main() {
print(result());
return 0;
}
На выходе, как и положено, получаем
1 _ 1 1 1 1 1 1 1 1 1 1 1 1
Тут можно посмотреть на код: https://ideone.com/MvBU3Z. Желающие узнать как все устроено внутри, добро пожаловать под кат.
Для полноценной работы машины Тьюринга (МТ далее) нужно следующее:
1. Лента с символами
2. Способ считывать и записывать символы на ленту
3. Способ перемещаться по ленте и расширять ее по мере надобности
4. Система состояний и правил перехода
5. Способ вычислять следующее состояние системы целиком (машина + лента)
6. Способ останавливать выполнение, когда машина достигает финального состояния
Все операции должны выполняться над типами и константными выражениями, а не над переменными как в обычной жизни. Для согласованности со стандартной библиотекой С++, мы будем использовать следующий способ вычислений:
// объявление операции
template
class Operation;
// специализация операции для конкретного типа
template
class Operation {
public:
// тип, содержащий результат операции
using type = typename Output;
}
Использование имени «type» для хранения результатов сделает возможным некоторые полезные трюки с std: conditional и std: integral_constant, которые мы увидим в далнейшем.
1. Так как МТ использует конечный алфавит, мы можем без потери общности считать, что символы на ленте представлены целыми числами. Договоримся, что по умолчанию лента содержит символ, заданный константой Blank, равной -1. При желании это значение можно легко изменить.
constexpr int Blank = -1;
template
class Tape {
public:
using type = Tape;
constexpr static int length = sizeof...(xs);
};
Что можно сделать с лентой? Можно ее, например, вывести на экран. Функция print будет единственной функцией в обычном понимании, которая будет использоваться в программах для нашей машины.
template
void print(T);
template<>
void print(Tape<>) {
std::cout << std::endl;
}
template
void print(Tape) {
if (x == Blank) {
std::cout << "_ ";
} else {
std::cout << x << " ";
}
print(Tape());
}
Здесь используется стандартный трюк с рекурсивным шаблоном. По ссылке можно посмотреть на получившийся код: https://ideone.com/DBHSC6
2. Прежде чем перейти к чтению и записи, необходимо сделать некоторые вспомогательные операции:
template
class Concatenate;
template
class Concatenate, Tape> {
public:
using type = Tape;
};
С конкатенацией все просто.
template
class Invert;
template<>
class Invert> {
public:
using type = Tape<>;
};
template
class Invert> {
public:
using type = typename Concatenate<
typename Invert>::type,
Tape
>::type;
};
Инверсия чуть-чуть посложнее: берем первый символ, переносим его в конец и конкатенируем с перевернутым хвостом. Внутри разворачивается рекурсия в результате которой получается то, что нам нужно. Вот пример запуска: https://ideone.com/47GKNp
Чтение символов — место, где начинается магия со стандартной библиотекой.
template
class Read;
template
class Read> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant,
Read>
>::type::type;
};
Логика на самом деле относительно проста: если n == 0, мы возвращаем первый символ ленты, обернутый в std: integral_constant, в противном случае мы уменьшаем n на единицу и отбрасываем первый символ. Для чего нужна конструкция :: type: type? Первый type относится к std: conditional. std: conditional: type равняется A, если T == true, и равняется B в остальных случаях. Таким образом, в зависимости от значения n, вся конструкция развернется в одно из следующих выражений:
using type = std::integral_constant::type;
using type = Read>::type;
Первая строчка эквивалентна type = std: integral_constant, вторая вызовет рекурсию. Но почему нельзя было написать этот код вот так:
template
class Read> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant,
typename Read>::type
>::type;
};
Разгадка: в первом случае шаблон Read> будет инстанциирован в зависимости от значения n, во втором он будет инстанциирован всегда, так как мы явно используем внутренний alias (:: type). Если мы всего лишь упомянем имя шаблона, он не будет инстанциирован, если мы попытаемся использовать что-то из его внутренностей, шаблон будет инстанциирован. Таким образом, выражение из второго примера приведет к бесконечной рекурсии, которая все же остановится, но с ошибкой. Этот примем с :: type: type будет активно использоваться в дальнейшем.
Тут можно посмотреть на пример чтения с ленты: https://ideone.com/vEyASt
Запись. Допустим мы хотим записать на ленту вместо символа х символ y. Операцию записи можно представить как деление всей ленты на часть до х, сам символ х и часть после х, замену x на y и конкатенирование всех частей обратно в целое. Определим операции для вычисления n первых и последних символов:
template
class NLast;
template
class NLast> {
public:
using type = typename std::conditional<
(n == sizeof...(xs)),
Tape,
NLast>
>::type::type;
};
template
class NFirst;
template
class NFirst> {
public:
using type = typename Invert<
typename NLast<
n, typename Invert>::type
>::type
>::type;
};
Чтобы получить n последних символов, будем делать примерно то же, что делали для чтения: укорачивать ленту по одному символу, пока длина оставшегося куска не станет равна n. Чтобы получить первые n символов, перевернем ленту, возьмем последние n символов и перевернем результат. Примеры использования: https://ideone.com/igYF3W.
Наконец, непосредственно запись:
template
class Write;
template
class Write> {
public:
using type = typename Concatenate<
typename Concatenate<
typename NFirst>::type,
Tape
>::type,
typename NLast<(sizeof...(xs) - pos - 1), Tape>::type
>::type;
};
Этот код не сложно понять, зная, что тут на самом деле происходит. Примеры записи: https://ideone.com/w2mUdh
В данный момент мы имеем класс для представления ленты, а также умеем читать и писать символы. Теперь нужно научиться двигать ленту.
3. Наша МТ будет поддерживать следующие операции передвижения: Hold, Left and Right. Каждая из них должна уметь вычислять следующую позицию и следующее состояние ленты, зная текущее ее состояние и позицию. Если машина смотрит на символ в позиции 0 и мы хотим сдвинуть ее влево, ленту необходимо расширить. Аналогично в случае, когда машина смотрит на конечный символ и двигается вправо.
template
class Hold;
template
class Hold> {
public:
constexpr static int position = pos;
using tape = Tape;
};
template
class Left;
template
class Left> {
public:
constexpr static int position = typename std::conditional<
(pos > 0),
std::integral_constant,
std::integral_constant
>::type();
using tape = typename std::conditional<
(pos > 0),
Tape,
Tape
>::type;
};
template
class Right;
template
class Right> {
public:
constexpr static int position = pos + 1;
using tape = typename std::conditional<
(pos < sizeof...(xs) - 1),
Tape,
Tape
>::type;
};
Примеры: https://ideone.com/m5OTaT
4. Теперь можно переходить к состояниям. Если машина находится в каком-то состоянии и читает символ с ленты, нам нужно знать три вещи: что писать, куда двигаться и в какое состояние перейти. Состояния решено было запрограммировать как группу специализаций шаблонов, где каждая специализация соответствует паре (состояние, символ), то есть правилу перехода. Предположим, мы хотим задать следующее правило: находясь в состоянии A и прочитав символ 0, нужно записать вместо него 1, сдвинуться вправо и перейти в состояние B. Выглядеть это правило будет вот так:
template<>
class A<0> {
public:
constexpr static int write = 1;
template
using move = Right;
template
using next = B;
};
Здесь использована отличная возможность современного С++: alias template. Поля «move» и «next» не просто типы, а шаблоны типов, в дальнейшем они будут использованы МТ для вычисления своего следующего состояния. Писать такую конструкцию для каждого правила довольно утомительно, поэтому обернем задание правил перехода в макрос. Состояние, перейдя в которое машина должна остановиться, назовем Stop.
5. Чтобы удерживать состояние всей системы (состояние машины, ее текущая позиция и состояние ленты), определим класс Machine. Единственное, что должен уметь этот класс — делать один шаг симуляции, вычислять свое следующее состояние.
template class State, int pos, int... xs>
class Machine> {
constexpr static int symbol = typename Read>::type();
using state = State;
template
using nextState = typename State::template next;
using move = typename state::template move;
constexpr static int nextPos = move::position;
using modifiedTape = typename Write>::type;
using nextTape = typename move::tape;
public:
using step = Machine;
};
Сперва мы считываем символ с ленты и сохраняем его как «symbol». Далее мы инстанциируем класс State с конкретным значением символа и получаем правило перехода. Следующее состояние машины определяется следующим образом:
template
using nextState = typename State::template next;
Зачем нужно ключевое слово «template» перед «next»? Согласно стандарту, перед именем вложенного шаблона необходимо писать «template», если это имя используется после оператора разрешения области видимости (»::»). При вычислении операции перемещения можно наблюдать тот же эффект.
Чтобы вычислить следующее состояние ленты, запишем в нее новый символ и по необходимости расширим, последовательно вызвав операции записи и перемещения. Вычисление новой позиции очевидно.
Наконец, все готово, и мы умеем вычислять следующее состояние системы, делать шаги. Можно написать временную вспомогательную функцию для вывода состояния машины, придумать какую-нибудь простую программу и пошагово следить за ее выполнением: https://ideone.com/XuBDry. В этом примере можно наблюдать, как машина движется право и заменяет все на своем пути.
6. Все выглядит так, как будто работает, но мы должны идти глубже: входными данными для процесса являются начальное состояние машины, ее позиция и состояние ленты, в конце мы хотим знать только что случилось с лентой, когда машина достигла состояния Stop. Окей, напишем класс
template
class Run;
template class State, int pos, int... xs>
class Run>> {
using step = typename Machine>::step;
public:
using type = typename std::conditional<
std::is_same, Stop<0>>::value,
Tape,
Run
>::type::type;
};
Чтобы проверить условие остановки, мы инстанциируем текущее состояние машины и состояние Stop со значением 0, после чего сравниваем их между собой посредством std: is_same. Если они равны, возвращаем ленту, в противном случае делам следующий шаг и снова проверяем условие остановки.
Попробуем теперь написать что-нибудь. Например увеличение чисел в бинарном формате. Предположим, что число записано слева направо, как на бумажке.
ADD_STATE(S0);
ADD_STATE(S1);
ADD_STATE(S2);
ADD_RULE(S0, Blank, Blank, Left, S1);
ADD_RULE(S0, 0, 0, Right, S0);
ADD_RULE(S0, 1, 1, Right, S0);
ADD_RULE(S1, Blank, 1, Right, S2);
ADD_RULE(S1, 0, 1, Left, S2);
ADD_RULE(S1, 1, 0, Left, S1);
ADD_RULE(S2, Blank, Blank, Hold, Stop);
ADD_RULE(S2, 0, 0, Right, S2);
ADD_RULE(S2, 1, 1, Right, S2);
using tape = Tape;
using result = Run>::type;
int main() {
print(tape());
print(result());
return 0;
}
https://ideone.com/AgK4nx. Что делать, если хочется запустить инкеремент несколько раз? Конечно же написать отдельный класс операции и несколько раз его вызвать, все просто:
template
class Increment { };
template
class Increment> {
public:
using type = typename Run::length - 1, Tape>>::type;
};
using tape = Tape;
int main() {
print(tape());
print(Increment::type());
print(Increment::type>::type());
print(Increment::type>::type>::type());
print(Increment::type>::type>::type>::type());
print(Increment::type>::type>::type>::type>::type());
return 0;
}
https://ideone.com/zPyu6B
На этой радостной ноте позволю себе закруглиться. Вот ссылка на github: https://github.com/fnz/CTTM, пулл-реквесты с новыми программами сугубо приветствуются.
