Template Turing Machine

Anyone interested in C ++ templates most likely heard about their Turing completeness and related jokes about "you can program while you program". In this post I will explain how using templates and constant expressions to build a real Turing machine that calculates the result of my work at compile time, where you can run existing programs. For example, a diligent beaver with 4 states and 2 characters looks something like this:

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; } 

At the exit, as expected, we get

 1 _ 1 1 1 1 1 1 1 1 1 1 1 1 

Here you can look at the code: https://ideone.com/MvBU3Z . Those who want to know how everything works inside, welcome under the cat.

For the full operation of the Turing machine (MT further) you need the following:
1. Ribbon with characters
2. The way to read and write characters on the tape
3. A way to navigate the tape and expand it as needed.
4. The system of states and transition rules
5. A way to calculate the next state of the whole system (machine + tape)
6. The way to stop execution when the machine reaches the final state

All operations must be performed on types and constant expressions, and not on variables as in ordinary life. For consistency with the standard C ++ library, we will use the following calculation method:

 //   template<class> class Operation; //      template<class Input> class Operation { public: // ,    using type = typename Output; } 

Using the name “type” to store the results will make possible some useful stunts with std :: conditional and std :: integral_constant, which we will see later.

1. Since MT uses a finite alphabet, we can assume without loss of generality that the characters on the tape are represented by integers. We agree that by default the tape contains the character specified by the Blank constant, equal to -1. If desired, this value can be easily changed.

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

What can be done with the tape? You can, for example, display it. The print function will be the only function in the usual sense that will be used in the programs for our machine.

 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...>()); } 

It uses a standard recursive pattern trick. Under the link you can look at the resulting code: https://ideone.com/DBHSC6
')
2. Before going on to read and write, you need to do some auxiliary operations:

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

Concatenation is simple.

 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; }; 

Inversion is a bit more complicated: take the first character, move it to the end and concatenate with an inverted tail. Inside recursion takes place as a result of which we get what we need. Here is an example of a launch: https://ideone.com/47GKNp

Reading characters is where the magic begins with the standard library.

 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; }; 

The logic is actually relatively simple: if n == 0, we return the first character of the tape wrapped in std :: integral_constant, otherwise we reduce n by one and discard the first character. What is the construction :: type :: type? The first type refers to std :: conditional. std :: conditional <T, A, B> :: type equals A, if T == true, and equals B in all other cases. Thus, depending on the value of n, the whole structure will unfold in one of the following expressions:

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

The first line is equivalent to type = std :: integral_constant <int, x>, the second will cause recursion. But why it was impossible to write this code like this:

 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; }; 

Solution: in the first case, the Read <n - 1 template, Tape <xs ... >> will be instantiated depending on the value of n, in the second case it will always be instantiated, since we explicitly use the internal alias (:: type). If we just mention the name of the template, it will not be instantiated, if we try to use some of its insides, the template will be instantiated. Thus, the expression from the second example will lead to infinite recursion, which will still stop, but with an error. This will take with :: type :: type will be actively used in the future.
Here you can look at an example of reading from the tape: https://ideone.com/vEyASt

Record. Suppose we want to write on the tape instead of the character x the character y. The write operation can be represented as dividing the entire tape into a part up to x, the x character itself and the part after x, replacing x with y and concatenating all the parts back into an integer. Define operations to calculate the first n and last characters:

 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; }; 

To get the last n characters, we'll do about the same thing we did for reading: shorten the tape one character at a time until the length of the remaining piece is equal to n. To get the first n characters, flip the tape, take the last n characters, and flip the result. Examples of use: https://ideone.com/igYF3W .

Finally, the direct entry:

 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; }; 

This code is not difficult to understand, knowing what is really happening here. Record examples: https://ideone.com/w2mUdh

At the moment, we have a class to represent the tape, and we can also read and write characters. Now you need to learn how to move the tape.

3. Our MT will support the following movement operations: Hold, Left and Right. Each of them should be able to calculate the next position and the next state of the tape, knowing its current state and position. If the car looks at the character at position 0 and we want to move it to the left, the tape needs to be expanded. Similarly, in the case when the car looks at the final symbol and moves to the right.

 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; }; 

Examples: https://ideone.com/m5OTaT

4. Now you can go to the states. If the machine is in some state and reads the symbol from the tape, we need to know three things: what to write, where to go and what state to go. It was decided to program the states as a group of template specializations, where each specialization corresponds to a pair (state, symbol), that is, a transition rule. Suppose we want to set the following rule: being in state A and reading symbol 0, we need to write 1 instead, move to the right and go to state B. This rule will look like this:

 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>; }; 

Here is an excellent opportunity of modern C ++: alias template. The “move” and “next” fields are not just types, but type templates; in the future they will be used by MT to calculate their next state. Writing such a construction for each rule is quite tedious, so let's wrap up the task of switching rules to a macro. The state, after passing into which the car should stop, is called Stop.

5. To keep the state of the entire system (the state of the machine, its current position and the state of the tape), we define the class Machine. The only thing that this class should be able to do is take one step of the simulation, calculate its next state.

 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>; }; 

First we read the symbol from the tape and save it as a “symbol”. Next, we instantiate the State class with a specific character value and get the transition rule. The following machine condition is defined as follows:

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

Why do you need the keyword "template" before "next"? According to the standard, it is necessary to write “template” before the nested template name, if this name is used after the scope resolution operator ("::"). When calculating the move operation, you can observe the same effect.

To calculate the next state of the tape, we write the new symbol into it and, if necessary, expand it by sequentially triggering the write and move operations. The calculation of the new position is obvious.

Finally, everything is ready, and we are able to calculate the next state of the system, take steps. You can write a temporary helper function to display the state of the machine, come up with some simple program and follow its execution step by step: https://ideone.com/XuBDry . In this example, you can observe how the car is moving right and replacing everything in its path.

6. Everything looks as if it works, but we have to go deeper: the input data for the process are the initial state of the machine, its position and the state of the tape, at the end we want to know just what happened to the tape when the machine has reached the Stop state. Okay, let's write a class

 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; }; 

To check the condition of a stop, we instantiate the current state of the machine and the state of Stop with a value of 0, after which we compare them with each other by means of std :: is_same. If they are equal, return the tape, otherwise take the next step and check the condition of the stop again.

Now let's try to write something. For example, increasing numbers in binary format. Suppose that the number is written from left to right, as on a piece of paper.

 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 . What to do if you want to run an incerement several times? Of course, to write a separate operation class and call it several times, it's simple:

 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

On this joyous note I will allow myself to round out. Here is the link to github: https://github.com/fnz/CTTM , pull-requests with new programs are especially welcome.