Машина Тьюринга на шаблонах

Каждый интересующийся шаблонами в С++ скорее всего слышал об их Тьюринг-полноте и связанных с этим шутках про «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<Blank>;
using machine = Machine<A, 0, tape>;
using result = Run<machine>::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>
class Operation; 

// специализация операции для конкретного типа
template<class Input> 
class Operation {
public:
    // тип, содержащий результат операции
    using type = typename Output; 
}

Использование имени «type» для хранения результатов сделает возможным некоторые полезные трюки с std::conditional и std::integral_constant, которые мы увидим в далнейшем.

1. Так как МТ использует конечный алфавит, мы можем без потери общности считать, что символы на ленте представлены целыми числами. Договоримся, что по умолчанию лента содержит символ, заданный константой Blank, равной -1. При желании это значение можно легко изменить.

constexpr int Blank = -1;

template<int... xs>
class Tape {
public:
    using type = Tape<xs...>;
    constexpr static int length = sizeof...(xs);
};

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

template<class T>
void print(T);

template<>
void print(Tape<>) {
    std::cout << std::endl;
}

template<int x, int... xs>
void print(Tape<x, xs...>) {
    if (x == Blank) {
        std::cout << "_ ";
    } else {
        std::cout << x << " ";
    }
    print(Tape<xs...>());
}

Здесь используется стандартный трюк с рекурсивным шаблоном. По ссылке можно посмотреть на получившийся код: https://ideone.com/DBHSC6

2. Прежде чем перейти к чтению и записи, необходимо сделать некоторые вспомогательные операции:

template<class, class>
class Concatenate;

template<int... xs, int... ys>
class Concatenate<Tape<xs...>, Tape<ys...>> {
public:
    using type = Tape<xs..., ys...>;
};

С конкатенацией все просто.

template<class>
class Invert;

template<>
class Invert<Tape<>> {
public:
    using type = Tape<>;
};

template<int x, int... xs>
class Invert<Tape<x, xs...>> {
public:
    using type = typename Concatenate<
        typename Invert<Tape<xs...>>::type,
        Tape<x>
    >::type;
};

Инверсия чуть-чуть посложнее: берем первый символ, переносим его в конец и конкатенируем с перевернутым хвостом. Внутри разворачивается рекурсия в результате которой получается то, что нам нужно. Вот пример запуска: https://ideone.com/47GKNp

Чтение символов — место, где начинается магия со стандартной библиотекой.

template<int, class>
class Read;

template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
    using type = typename std::conditional<
        (n == 0),
        std::integral_constant<int, x>,
        Read<n - 1, Tape<xs...>>
    >::type::type;
};

Логика на самом деле относительно проста: если n == 0, мы возвращаем первый символ ленты, обернутый в std::integral_constant, в противном случае мы уменьшаем n на единицу и отбрасываем первый символ. Для чего нужна конструкция ::type::type? Первый type относится к std::conditional. std::conditional<T, A, B>::type равняется A, если T == true, и равняется B в остальных случаях. Таким образом, в зависимости от значения n, вся конструкция развернется в одно из следующих выражений:

using type = std::integral_constant<int, x>::type;
using type = Read<n - 1, Tape<xs...>>::type;

Первая строчка эквивалентна type = std::integral_constant<int, x>, вторая вызовет рекурсию. Но почему нельзя было написать этот код вот так:

template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
    using type = typename std::conditional<
        (n == 0),
        std::integral_constant<int, x>,
        typename Read<n - 1, Tape<xs...>>::type
    >::type;
};

Разгадка: в первом случае шаблон Read<n — 1, Tape<xs...>> будет инстанциирован в зависимости от значения n, во втором он будет инстанциирован всегда, так как мы явно используем внутренний alias (::type). Если мы всего лишь упомянем имя шаблона, он не будет инстанциирован, если мы попытаемся использовать что-то из его внутренностей, шаблон будет инстанциирован. Таким образом, выражение из второго примера приведет к бесконечной рекурсии, которая все же остановится, но с ошибкой. Этот примем с ::type::type будет активно использоваться в дальнейшем.
Тут можно посмотреть на пример чтения с ленты: https://ideone.com/vEyASt

Запись. Допустим мы хотим записать на ленту вместо символа х символ y. Операцию записи можно представить как деление всей ленты на часть до х, сам символ х и часть после х, замену x на y и конкатенирование всех частей обратно в целое. Определим операции для вычисления n первых и последних символов:

template<int, class>
class NLast;

template<int n, int x, int... xs>
class NLast<n, Tape<x, xs...>> {
public:
    using type = typename std::conditional<
        (n == sizeof...(xs)),
        Tape<xs...>,
        NLast<n, Tape<xs...>>
    >::type::type;
};

template<int, class>
class NFirst;

template<int n, int... xs>
class NFirst<n, Tape<xs...>> {
public:
    using type = typename Invert<
        typename NLast<
            n, typename Invert<Tape<xs...>>::type
        >::type
    >::type;
};

Чтобы получить n последних символов, будем делать примерно то же, что делали для чтения: укорачивать ленту по одному символу, пока длина оставшегося куска не станет равна n. Чтобы получить первые n символов, перевернем ленту, возьмем последние n символов и перевернем результат. Примеры использования: https://ideone.com/igYF3W.

Наконец, непосредственно запись:

template<int, int, class>
class Write;

template<int pos, int x, int... xs>
class Write<pos, x, Tape<xs...>> {
public:
    using type = typename Concatenate<
        typename Concatenate<
            typename NFirst<pos, Tape<xs...>>::type,
            Tape<x>
        >::type,
        typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type
    >::type;
};

Этот код не сложно понять, зная, что тут на самом деле происходит. Примеры записи: https://ideone.com/w2mUdh

В данный момент мы имеем класс для представления ленты, а также умеем читать и писать символы. Теперь нужно научиться двигать ленту.

3. Наша МТ будет поддерживать следующие операции передвижения: Hold, Left and Right. Каждая из них должна уметь вычислять следующую позицию и следующее состояние ленты, зная текущее ее состояние и позицию. Если машина смотрит на символ в позиции 0 и мы хотим сдвинуть ее влево, ленту необходимо расширить. Аналогично в случае, когда машина смотрит на конечный символ и двигается вправо.

template<int, class>
class Hold;

template<int pos, int... xs>
class Hold<pos, Tape<xs...>> {
public:
    constexpr static int position = pos;
    using tape = Tape<xs...>;
};

template<int, class>
class Left;

template<int pos, int... xs>
class Left<pos, Tape<xs...>> {
public:
    constexpr static int position = typename std::conditional<
        (pos > 0),
        std::integral_constant<int, pos - 1>,
        std::integral_constant<int, 0>
    >::type();

    using tape = typename std::conditional<
        (pos > 0),
        Tape<xs...>,
        Tape<Blank, xs...>
    >::type;
};

template<int, class>
class Right;

template<int pos, int... xs>
class Right<pos, Tape<xs...>> {
public:
    constexpr static int position = pos + 1;

    using tape = typename std::conditional<
        (pos < sizeof...(xs) - 1),
        Tape<xs...>,
        Tape<xs..., Blank>
    >::type;
};

Примеры: https://ideone.com/m5OTaT

4. Теперь можно переходить к состояниям. Если машина находится в каком-то состоянии и читает символ с ленты, нам нужно знать три вещи: что писать, куда двигаться и в какое состояние перейти. Состояния решено было запрограммировать как группу специализаций шаблонов, где каждая специализация соответствует паре (состояние, символ), то есть правилу перехода. Предположим, мы хотим задать следующее правило: находясь в состоянии A и прочитав символ 0, нужно записать вместо него 1, сдвинуться вправо и перейти в состояние B. Выглядеть это правило будет вот так:

template<>
class A<0> {
public:
    constexpr static int write = 1;

    template<int pos, class tape>
    using move = Right<pos, tape>;

    template<int x>
    using next = B<x>;
};

Здесь использована отличная возможность современного С++: alias template. Поля «move» и «next» не просто типы, а шаблоны типов, в дальнейшем они будут использованы МТ для вычисления своего следующего состояния. Писать такую конструкцию для каждого правила довольно утомительно, поэтому обернем задание правил перехода в макрос. Состояние, перейдя в которое машина должна остановиться, назовем Stop.

5. Чтобы удерживать состояние всей системы (состояние машины, ее текущая позиция и состояние ленты), определим класс Machine. Единственное, что должен уметь этот класс — делать один шаг симуляции, вычислять свое следующее состояние.

template<template<int> class State, int pos, int... xs>
class Machine<State, pos, Tape<xs...>> {
    constexpr static int symbol = typename Read<pos, Tape<xs...>>::type();
    using state = State<symbol>;

    template<int x>
    using nextState = typename State<symbol>::template next<x>;

    using move = typename state::template move<pos, modifiedTape>;
    constexpr static int nextPos = move::position;

    using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type;
    using nextTape = typename move::tape;

public:
    using step = Machine<nextState, nextPos, nextTape>;
};

Сперва мы считываем символ с ленты и сохраняем его как «symbol». Далее мы инстанциируем класс State с конкретным значением символа и получаем правило перехода. Следующее состояние машины определяется следующим образом:

template<int x>
using nextState = typename State<symbol>::template next<x>;

Зачем нужно ключевое слово «template» перед «next»? Согласно стандарту, перед именем вложенного шаблона необходимо писать «template», если это имя используется после оператора разрешения области видимости("::"). При вычислении операции перемещения можно наблюдать тот же эффект.

Чтобы вычислить следующее состояние ленты, запишем в нее новый символ и по необходимости расширим, последовательно вызвав операции записи и перемещения. Вычисление новой позиции очевидно.

Наконец, все готово, и мы умеем вычислять следующее состояние системы, делать шаги. Можно написать временную вспомогательную функцию для вывода состояния машины, придумать какую-нибудь простую программу и пошагово следить за ее выполнением: https://ideone.com/XuBDry. В этом примере можно наблюдать, как машина движется право и заменяет все на своем пути.

6. Все выглядит так, как будто работает, но мы должны идти глубже: входными данными для процесса являются начальное состояние машины, ее позиция и состояние ленты, в конце мы хотим знать только что случилось с лентой, когда машина достигла состояния Stop. Окей, напишем класс

template<class>
class Run;

template<template<int> class State, int pos, int... xs>
class Run<Machine<State, pos, Tape<xs...>>> {
    using step = typename Machine<State, pos, Tape<xs...>>::step;

public:
    using type = typename std::conditional<
        std::is_same<State<0>, Stop<0>>::value,
        Tape<xs...>,
        Run<step>
    >::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<Blank, 1, 1, 0, Blank>;
using result = Run<Machine<S0, tape::length - 1, tape>>::type;

int main() {
    print(tape());
    print(result());
    return 0;
}

https://ideone.com/AgK4nx. Что делать, если хочется запустить инкеремент несколько раз? Конечно же написать отдельный класс операции и несколько раз его вызвать, все просто:

template<class>
class Increment { };

template<int... xs>
class Increment<Tape<xs...>> {
public:
    using type = typename Run<Machine<S0, Tape<xs...>::length - 1, Tape<xs...>>>::type;
};

using tape = Tape<Blank, 1, 1, 0, Blank>;

int main() {
    print(tape());
    print(Increment<tape>::type());
    print(Increment<Increment<tape>::type>::type());
    print(Increment<Increment<Increment<tape>::type>::type>::type());
    print(Increment<Increment<Increment<Increment<tape>::type>::type>::type>::type());
    print(Increment<Increment<Increment<Increment<Increment<tape>::type>::type>::type>::type>::type());
    return 0;
}

https://ideone.com/zPyu6B

На этой радостной ноте позволю себе закруглиться. Вот ссылка на github: https://github.com/fnz/CTTM, пулл-реквесты с новыми программами сугубо приветствуются.