Brainfuck interpreter using normal Markov algorithms
Under the cat, you will find the most abnormal implementation of the Brainfuck interceptor using normal Markov algorithms. In this implementation, all Brainfuck operators and the interpreter itself are normal Markov algorithms. The purpose of this post was to consider Brainfuck from the point of view of the classical theory of algorithms and to bring its implementation with the help of some classical clarification of the concept of the algorithm. Who is not afraid to harm your brain with such abnormal programming, welcome (under the cut there is a lot of text, sometimes difficult to understand if you are not familiar with the theory of algorithms, but at the end of the post there is a link to the implementation of this interpreter that you can try in action). Its speed, for obvious reasons, is not very high, but from the point of view of understanding the algorithms of work, it is very visual.
It all started with the fact that the mass of posts about Brainfuck on Habré knocked me out yet to learn what it is. In addition, my friend, also a programmer, pushed me to this post, saying something like: “Since you are torturing students at the university with this theory of algorithms, describe the Brainfuck interpreter using a primitive recursive function.” This phrase and the bad weather and mood and pushed to what happened. Since Habr IT is not a mathematical resource, instead of implementation using recursive functions, it seemed to me more correct to do the implementation using normal Markov algorithms.
To get acquainted with the basic concepts that will appear you can read:
Brainfuck;
Recursive functions;
Normal Markov algorithm.
As you know, Brainfuck is Turing a complete language, which theoretically allows you to implement with its help any algorithm. Let's see what Brainfuck is from the point of view of the theory of algorithms. Most accurately it can be described as a kind of a hybrid of the Turing machine and a machine with natural-valued registers. Since Brainfuck is Turing complete, it means it can be implemented both on a machine with natural-valued registers and on a Turing machine, recursive functions, Markov algorithms (which I did).
And so, what is implemented:
What is needed to implement the interpreter on the normal Markov algorithms: a string into which we will enter the code on the brainfack (without the "," operator), the string that serves as the memory tape, the buffer string (to output the result), the string to output the result.
')
When the interpreter starts, the string-tape should look like
._ ...
The number of points is the number of available memory cells, the symbol _ is a pointer to the current cell.
We will specify the Markov products as two arrays of rows of the same length: the first is the left parts of the products, the second is the right. If the right part of the product ends with FIN, then this means that this product will be final.
To begin with, what is simpler is the implementation of the brainflyc operations using Markov algorithms.
Well, now actually the normal interpreter algorithm. It is executed on the source line, after each production the subalgorithm from the table of operations is invoked (see above).
You have the opportunity to execute the entire program at once or to execute it step by step. The implementation is in C #, so for its work you need an installed .NET 2.0.
Demonstration of the work of the classic Hello World! on Brainfuck on this interpreter.
PS I hope it was at least someone interesting. I tried to keep within the smallest amount of text.
The implementation of the interpreter. You can try this monster at work.
How was this idea born
It all started with the fact that the mass of posts about Brainfuck on Habré knocked me out yet to learn what it is. In addition, my friend, also a programmer, pushed me to this post, saying something like: “Since you are torturing students at the university with this theory of algorithms, describe the Brainfuck interpreter using a primitive recursive function.” This phrase and the bad weather and mood and pushed to what happened. Since Habr IT is not a mathematical resource, instead of implementation using recursive functions, it seemed to me more correct to do the implementation using normal Markov algorithms.
To get acquainted with the basic concepts that will appear you can read:
Brainfuck;
Recursive functions;
Normal Markov algorithm.
Brainfuck proper
As you know, Brainfuck is Turing a complete language, which theoretically allows you to implement with its help any algorithm. Let's see what Brainfuck is from the point of view of the theory of algorithms. Most accurately it can be described as a kind of a hybrid of the Turing machine and a machine with natural-valued registers. Since Brainfuck is Turing complete, it means it can be implemented both on a machine with natural-valued registers and on a Turing machine, recursive functions, Markov algorithms (which I did).
And so, what is implemented:
| Team brainfuck | Command description | Implemented? |
| > | move to the next cell | Implemented. |
| < | go to previous cell | Implemented. |
| + | increase the value in the current cell by 1 | Implemented. |
| - | decrease the value in the current cell by 1 | Implemented. |
| . | print the value from the current cell | Implemented. |
| , | enter value from outside and save to current cell | Not implemented, so this operation is not of particular interest from the point of view of Markov algorithms. |
| [ | if the value of the current cell is zero, go ahead by the program text on the cell following the corresponding one] (taking into account nesting) | Implemented. |
| ] | if the value of the current cell is not zero, go back to the text of the program on the character [(including nesting) | Implemented. |
What is needed to implement the interpreter on the normal Markov algorithms: a string into which we will enter the code on the brainfack (without the "," operator), the string that serves as the memory tape, the buffer string (to output the result), the string to output the result.
')
When the interpreter starts, the string-tape should look like
._ ...
The number of points is the number of available memory cells, the symbol _ is a pointer to the current cell.
We will specify the Markov products as two arrays of rows of the same length: the first is the left parts of the products, the second is the right. If the right part of the product ends with FIN, then this means that this product will be final.
To begin with, what is simpler is the implementation of the brainflyc operations using Markov algorithms.
| Team brainfuck | Implementation by Markov algorithm |
| > | In the line-tape:string[] left = new string[5] { "|_.", "@_|", "@_.", "_..", "_.|" }; |
| < | In the line-tape:string[] left = new string[2] { "|_", "._" }; |
| + | In the line-tape:string[] left = new string[1] { "_"}; |
| - | In the line-tape:string[] left = new string[1] { "|_" }; |
| . | In the buffer string:| > .a |
| [ | In the source line (takes into account the nesting [])string[] left = new string[10] { "_+", "_-", "_.", "_,", "_<", "_>","_[","_]","**","]*" }; |
| ] | In the source line (takes into account the nesting [])string[] left = new string[11] { "+_", "-_", "._", ",_", "<_", ">_", "]_", "[_", "*_","[**", "[*" }; |
Well, now actually the normal interpreter algorithm. It is executed on the source line, after each production the subalgorithm from the table of operations is invoked (see above).
| What to replace | What to replace | Called subalgorithm |
| _ + | + _ | + |
| _- | -_ | - |
| _ [ | [_ | [ |
| _> | > _ | > |
| _ < | <_ | < |
| _] | If on the line-tape can perform products ._. on ._. FIN, then ] _ otherwise call the subalgorithm] | ] |
| _. | ._ | . |
You have the opportunity to execute the entire program at once or to execute it step by step. The implementation is in C #, so for its work you need an installed .NET 2.0.
Demonstration of the work of the classic Hello World! on Brainfuck on this interpreter.
PS I hope it was at least someone interesting. I tried to keep within the smallest amount of text.
The implementation of the interpreter. You can try this monster at work.
Source: https://habr.com/ru/post/113234/
All Articles