Turing machine on patterns
Everyone interested in templates in C ++ most likely heard about their Turing completeness and related jokes about “we put a language in your language, so you can program while you program”. In this post I will tell you how to use the templates and constant expressions to build a real Turing machine that calculates the result of its work during compilation, on which it will be possible to run existing programs. For example, a zealous beaver with 4 states and 2 characters looks something like this:
At the output, as expected, we get
Here you can see the code: https://ideone.com/MvBU3Z . If you want to know how everything is arranged inside, welcome to cat.
For the full-fledged operation of the Turing machine (MT further), the following is needed:
1. A tape with symbols
2. A way to read and write symbols on a tape
3. A way to move around the tape and expand it as needed
4. A system of states and transition rules
5. A way to calculate the following entire system state (machine + tape)
6. A way to stop execution when the machine reaches the final state
All operations should 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:
Using the name “type” to store the results will make possible some useful tricks with std :: conditional and std :: integral_constant, which we will see later on.
1. Since MT uses a finite alphabet, we can assume without loss of generality that the symbols on the tape are represented by integers. We agree that, by default, the tape contains the character specified by the constant Blank, equal to -1. If desired, this value can be easily changed.
What can be done with the tape? You can, for example, display it on the screen. The print function will be the only function in the usual sense that will be used in the programs for our machine.
It uses a standard trick with a recursive pattern. The link allows you to look at the resulting code: https://ideone.com/DBHSC6
2. Before proceeding to reading and writing, you need to do some auxiliary operations:
Concatenation is simple.
Inversion is a little more complicated: we take the first character, transfer it to the end and concatenate with the tail turned upside down. Inside, a recursion unfolds as a result of which we get what we need. Here's an example run: https://ideone.com/47GKNp
Reading characters is where magic begins with the standard library.
The logic is actually relatively simple: if n == 0, we return the first character of the tape wrapped in std :: integral_constant, otherwise we decrease n by one and discard the first character. What is the construction of :: type :: type for? The first type refers to std :: conditional. std :: conditional:: type equals A if T == true, and equals B otherwise. Thus, depending on the value of n, the entire construction will unfold into one of the following expressions:
The first line is equivalent to type = std :: integral_constant, the second will cause recursion. But why it was impossible to write this code like this:
The answer: in the first case, the Read pattern> will be instantiated depending on the value of n, in the second it will always be instantiated, since we explicitly use internal alias (:: type). If we just mention the name of the template, it will not be instantiated, if we try to use one 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 accept with :: type :: type will be actively used in the future.
Here you can see an example of reading from the tape: https://ideone.com/vEyASt
Record. Suppose we want to write y instead of x. The write operation can be represented as dividing the entire tape into a part before x, the symbol x itself and the part after x, replacing x with y and concatenating all parts back to the whole. We define the operations for calculating the n first and last characters:
To get the last n characters, we will do approximately the same as 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 ribbon, take the last n characters and flip the result. Examples of use: https://ideone.com/igYF3W .
Finally, the entry itself:
This code is not difficult to understand, knowing what is really happening here. Examples of entries: https://ideone.com/w2mUdh
At the moment, we have a class to represent the tape, and also we can 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 is looking at the symbol at position 0 and we want to move it to the left, the tape needs to be expanded. Similarly, in the case when the machine looks at the final character and moves to the right.
Examples: https://ideone.com/m5OTaT
4. Now you can go to the states. If the machine is in some state and reads a symbol from the tape, we need to know three things: what to write, where to move and what state to go to. 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:
The great feature of modern C ++ is used here: 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 rather tedious, so we’ll wrap up the task of moving to the macro. The state after which the machine should stop will be called Stop.
5. To maintain 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 this class should be able to do is do one step of simulation, calculate its next state.
First we read the symbol from the tape and save it as “symbol”. Next, we instantiate the State class with a specific character value and get a transition rule. The following machine condition is defined as follows:
Why do I need the keyword "template" before "next"? According to the standard, it is necessary to write “template” before the name of the embedded template, if this name is used after the scope operator ("::"). When calculating the move operation, the same effect can be observed.
To calculate the next state of the tape, write a new symbol into it and expand it if necessary, sequentially calling the write and move operations. The calculation of the new position is obvious.
Finally, everything is ready, and we can calculate the next state of the system, take steps. You can write a temporary auxiliary function to display the state of the machine, come up with some simple program and step by step follow its implementation: https://ideone.com/XuBDry. In this example, you can observe how the machine moves right and replaces everything in its path.
6. Everything looks as if it works, but we need to go deeper: the input for the process is the initial state of the machine, its position and condition of the tape, in the end we want to know what happened to the tape when the machine reached the Stop state. Ok, let's write a class
To check the stop condition, we instantiate the current state of the machine and the Stop state with the value 0, after which we compare them with each other using std :: is_same. If they are equal, we return the tape, otherwise the next step is deeds and again we check the stopping condition.
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.
https://ideone.com/AgK4nx . What to do if you want to run the increment several times? Of course, write a separate operation class and call it several times, everything is simple:
https://ideone.com/zPyu6B
On this happy note, let me curl up. Here is a link to github: https://github.com/fnz/CTTM , pull requests with new programs are strictly welcome.
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;
}
At the output, as expected, we get
1 _ 1 1 1 1 1 1 1 1 1 1 1 1
Here you can see the code: https://ideone.com/MvBU3Z . If you want to know how everything is arranged inside, welcome to cat.
For the full-fledged operation of the Turing machine (MT further), the following is needed:
1. A tape with symbols
2. A way to read and write symbols on a tape
3. A way to move around the tape and expand it as needed
4. A system of states and transition rules
5. A way to calculate the following entire system state (machine + tape)
6. A way to stop execution when the machine reaches the final state
All operations should 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 Operation;
// специализация операции для конкретного типа
template
class Operation {
public:
// тип, содержащий результат операции
using type = typename Output;
}
Using the name “type” to store the results will make possible some useful tricks with std :: conditional and std :: integral_constant, which we will see later on.
1. Since MT uses a finite alphabet, we can assume without loss of generality that the symbols on the tape are represented by integers. We agree that, by default, the tape contains the character specified by the constant Blank, equal to -1. If desired, this value can be easily changed.
constexpr int Blank = -1;
template
class Tape {
public:
using type = Tape;
constexpr static int length = sizeof...(xs);
};
What can be done with the tape? You can, for example, display it on the screen. The print function will be the only function in the usual sense that will be used in the programs for our machine.
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());
}
It uses a standard trick with a recursive pattern. The link allows you to look at the resulting code: https://ideone.com/DBHSC6
2. Before proceeding to reading and writing, you need to do some auxiliary operations:
template
class Concatenate;
template
class Concatenate, Tape> {
public:
using type = Tape;
};
Concatenation is simple.
template
class Invert;
template<>
class Invert> {
public:
using type = Tape<>;
};
template
class Invert> {
public:
using type = typename Concatenate<
typename Invert>::type,
Tape
>::type;
};
Inversion is a little more complicated: we take the first character, transfer it to the end and concatenate with the tail turned upside down. Inside, a recursion unfolds as a result of which we get what we need. Here's an example run: https://ideone.com/47GKNp
Reading characters is where magic begins with the standard library.
template
class Read;
template
class Read> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant,
Read>
>::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 decrease n by one and discard the first character. What is the construction of :: type :: type for? The first type refers to std :: conditional. std :: conditional
using type = std::integral_constant::type;
using type = Read>::type;
The first line is equivalent to type = std :: integral_constant
template
class Read> {
public:
using type = typename std::conditional<
(n == 0),
std::integral_constant,
typename Read>::type
>::type;
};
The answer: in the first case, the Read pattern
Here you can see an example of reading from the tape: https://ideone.com/vEyASt
Record. Suppose we want to write y instead of x. The write operation can be represented as dividing the entire tape into a part before x, the symbol x itself and the part after x, replacing x with y and concatenating all parts back to the whole. We define the operations for calculating the n first and last characters:
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;
};
To get the last n characters, we will do approximately the same as 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 ribbon, take the last n characters and flip the result. Examples of use: https://ideone.com/igYF3W .
Finally, the entry itself:
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;
};
This code is not difficult to understand, knowing what is really happening here. Examples of entries: https://ideone.com/w2mUdh
At the moment, we have a class to represent the tape, and also we can 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 is looking at the symbol at position 0 and we want to move it to the left, the tape needs to be expanded. Similarly, in the case when the machine looks at the final character and moves to the right.
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;
};
Examples: https://ideone.com/m5OTaT
4. Now you can go to the states. If the machine is in some state and reads a symbol from the tape, we need to know three things: what to write, where to move and what state to go to. 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
using move = Right;
template
using next = B;
};
The great feature of modern C ++ is used here: 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 rather tedious, so we’ll wrap up the task of moving to the macro. The state after which the machine should stop will be called Stop.
5. To maintain 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 this class should be able to do is do one step of simulation, calculate its next state.
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;
};
First we read the symbol from the tape and save it as “symbol”. Next, we instantiate the State class with a specific character value and get a transition rule. The following machine condition is defined as follows:
template
using nextState = typename State::template next;
Why do I need the keyword "template" before "next"? According to the standard, it is necessary to write “template” before the name of the embedded template, if this name is used after the scope operator ("::"). When calculating the move operation, the same effect can be observed.
To calculate the next state of the tape, write a new symbol into it and expand it if necessary, sequentially calling the write and move operations. The calculation of the new position is obvious.
Finally, everything is ready, and we can calculate the next state of the system, take steps. You can write a temporary auxiliary function to display the state of the machine, come up with some simple program and step by step follow its implementation: https://ideone.com/XuBDry. In this example, you can observe how the machine moves right and replaces everything in its path.
6. Everything looks as if it works, but we need to go deeper: the input for the process is the initial state of the machine, its position and condition of the tape, in the end we want to know what happened to the tape when the machine reached the Stop state. Ok, let's write a class
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;
};
To check the stop condition, we instantiate the current state of the machine and the Stop state with the value 0, after which we compare them with each other using std :: is_same. If they are equal, we return the tape, otherwise the next step is deeds and again we check the stopping condition.
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;
using result = Run>::type;
int main() {
print(tape());
print(result());
return 0;
}
https://ideone.com/AgK4nx . What to do if you want to run the increment several times? Of course, write a separate operation class and call it several times, everything is simple:
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
On this happy note, let me curl up. Here is a link to github: https://github.com/fnz/CTTM , pull requests with new programs are strictly welcome.