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

    Каждый интересующийся шаблонами в С++ скорее всего слышал об их Тьюринг-полноте и связанных с этим шутках про «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, пулл-реквесты с новыми программами сугубо приветствуются.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 3

      0
      print какой-то не совсем времени компиляции. С каким-то рекурсивным дерганием cout и прочей лабудой. При том, что сравнительно несложно сделать constexpr строки, накидать опять же constexpr конкатенацию и сделать static_assert(false, constexpr_str) например. При большом желании можно обойтись в значительной мере магией variadic templates и иметь только constexpr-конверсию в char[] (а может и попросту const, не уверен)
        0
        Да, возможно. Главное вычислить конечное состояние ленты во время компиляции, распечатать ее — дело второе.
          0
          Нет, вру, static_assert понимает только литералы вторым аргументом. Все равно этот рекурсивный cout режет глаз. В общем сделал PR https://github.com/fnz/CTTM/pull/1

        Only users with full accounts can post comments. Log in, please.