"The Cure for the Disease": automatic programming
News about various software vulnerabilities appear regularly, everyone is used to it. However, one thing is errors in the mobile application, and another is the possible shutdown of a nuclear reactor. Today we will talk about the origins of software problems and a possible way to remedy the situation, in particular, automatic programming.
Robson # / Flickr / CC
At the beginning of the year, the State Atomic Energy Corporation ROSATOM had questions regarding the legitimacy of the software used in nuclear power plants. The company's specialists did not find the documentation for the software platform "PORTAL". This system is used at several power plants in different regions and is a software for collecting, processing and displaying information on the status of power units and equipment control.
')
As it turned out, there is no design, technological and operational documentation in the archive of system developers, and some employees work with unidentified versions of software components. Access to the source code of such an important system from private parties makes us think about security, since a failure at a nuclear power plant can lead to serious consequences.
Situations like the one described above are far from uncommon in the whole world. In many ways, the cause of this situation is the desire of companies to solve the problem as quickly as possible and be the first to enter the market. As a result, developers are forced not to “design programs”, but to write them immediately. In this case, the software documentation is often omitted.
If there is a need to change something, then programmers simply correct the code, not taking into account that each such intervention creates a springboard for problems in the future. Probably, this will have to have other developers. That's just to understand someone else's code without enough detailed documentation and maintenance is not easy.
Automaton programming is a programming paradigm in which a program or its fragment is interpreted as a model of a formal automaton. This term was proposed in 1991 by the head of the ITMO University Programming Technology Department, Anatoly Shalyto.
To understand the principle of the program could anyone who interacts with it, the behavior of the software is described using transition graphs . Symbols allow you to present even the most complex algorithms in a compact and understandable form, since the transition graph often fits on one monitor screen. This makes it possible to cover the whole picture with a glance.
In the framework of automaton programming, it is assumed that a program is written only after it has been designed. In this case, each project necessarily ends with the release of documentation. Designing automata that describe the logic of the solutions, leads to the fact that programs require minimal debugging and almost immediately ready to run. If the need for debugging does arise, it is possible to generate debugging protocols that reflect the behavior of automata in terms of states, transitions and influences.
As an example of using the automaton approach in constructing an algorithm, we present the solution of the direct bypass problem (0–9) of a binary tree.
Binary tree example
We assume that each vertex contains its own number and pointers to child vertices. In C ++, this structure can be represented as follows:
We also introduce into the system the function put (int x) , which outputs the number of the vertex in the output sequence, and the class that implements the stack with the following interface:
The idea of ​​the proposed algorithm is that when going around a binary tree, three directions of movement can be distinguished: left, right, and up. Depending on the current direction of motion, the properties of the current vertex and the extreme symbol in the stack, you can determine where to go next. Therefore, it is convenient to compare each direction of motion with the control state of the automaton. The connection diagram of the tree walker and its transition diagram are shown in the images below.
Connection scheme of the machine that traverses the tree
Transition diagram of the automaton that traverses the tree
Note that the theory of finite automata was successfully applied by Corezoid to build the cloud platform of the same name for IT solutions. Anatoly Shalyto speaks about the need to introduce this method into modern development: “Programmers are very smart, and they use automata, like other mathematical abstractions, when they consider it necessary. And I say: it is always necessary to use it [automaton programming] to describe programs with complex behavior, in which their behavior depends on history. ”
According to Anatoly Shalyto, the quality of the programs is ensured not only through testing and verification, but also by building relationships between the customer and the developer from the very beginning of work on the project. The formalized technical task on the basis of the automaton programming methodology helps to achieve this.
PS From the above text one can get the impression that with the help of automaton programming only “toy” tasks can be solved. However, it is not.
The given example is not typical for this programming paradigm - it is intended not for the implementation of computational algorithms of the type considered, but for control algorithms with complex behavior depending on the prehistory, which the pattern creators dislike so much.
True, when learning computational algorithms, automaton programming came in handy: Georgy Korneev and Matvey Kazakov showed that based on it, visualizers can be designed and automated to build them even for very complex discrete mathematics algorithms, and not to write them manually every time, like “God for put the soul. " An example of project documentation is given here , and here is an example of such documentation for a complex project.
The documentation for an even more complex project can be found here . The site is.ifmo.ru there are many more projects, both student and others, the study of which will be able to answer many of your questions. With the book Polikarpova N.I. and Shalyto A.A. Automata programming. SPb .: Peter, 2010 can be found here .
And do not fantasize - write: shalyto@mail.ifmo.ru.
Robson # / Flickr / CCAt the beginning of the year, the State Atomic Energy Corporation ROSATOM had questions regarding the legitimacy of the software used in nuclear power plants. The company's specialists did not find the documentation for the software platform "PORTAL". This system is used at several power plants in different regions and is a software for collecting, processing and displaying information on the status of power units and equipment control.
')
As it turned out, there is no design, technological and operational documentation in the archive of system developers, and some employees work with unidentified versions of software components. Access to the source code of such an important system from private parties makes us think about security, since a failure at a nuclear power plant can lead to serious consequences.
Where do legs grow
Situations like the one described above are far from uncommon in the whole world. In many ways, the cause of this situation is the desire of companies to solve the problem as quickly as possible and be the first to enter the market. As a result, developers are forced not to “design programs”, but to write them immediately. In this case, the software documentation is often omitted.
If there is a need to change something, then programmers simply correct the code, not taking into account that each such intervention creates a springboard for problems in the future. Probably, this will have to have other developers. That's just to understand someone else's code without enough detailed documentation and maintenance is not easy.
Automata programming comes into play
Automaton programming is a programming paradigm in which a program or its fragment is interpreted as a model of a formal automaton. This term was proposed in 1991 by the head of the ITMO University Programming Technology Department, Anatoly Shalyto.
To understand the principle of the program could anyone who interacts with it, the behavior of the software is described using transition graphs . Symbols allow you to present even the most complex algorithms in a compact and understandable form, since the transition graph often fits on one monitor screen. This makes it possible to cover the whole picture with a glance.
In the framework of automaton programming, it is assumed that a program is written only after it has been designed. In this case, each project necessarily ends with the release of documentation. Designing automata that describe the logic of the solutions, leads to the fact that programs require minimal debugging and almost immediately ready to run. If the need for debugging does arise, it is possible to generate debugging protocols that reflect the behavior of automata in terms of states, transitions and influences.
As an example of using the automaton approach in constructing an algorithm, we present the solution of the direct bypass problem (0–9) of a binary tree.
Binary tree example
We assume that each vertex contains its own number and pointers to child vertices. In C ++, this structure can be represented as follows:
struct Node { int id; // Node* left; // Node* right; // }; We also introduce into the system the function put (int x) , which outputs the number of the vertex in the output sequence, and the class that implements the stack with the following interface:
template class Stack { void push(const T& x); // x void pop(); // const T& top() const; // }; The idea of ​​the proposed algorithm is that when going around a binary tree, three directions of movement can be distinguished: left, right, and up. Depending on the current direction of motion, the properties of the current vertex and the extreme symbol in the stack, you can determine where to go next. Therefore, it is convenient to compare each direction of motion with the control state of the automaton. The connection diagram of the tree walker and its transition diagram are shown in the images below.
Connection scheme of the machine that traverses the tree
Transition diagram of the automaton that traverses the tree
Note that the theory of finite automata was successfully applied by Corezoid to build the cloud platform of the same name for IT solutions. Anatoly Shalyto speaks about the need to introduce this method into modern development: “Programmers are very smart, and they use automata, like other mathematical abstractions, when they consider it necessary. And I say: it is always necessary to use it [automaton programming] to describe programs with complex behavior, in which their behavior depends on history. ”
According to Anatoly Shalyto, the quality of the programs is ensured not only through testing and verification, but also by building relationships between the customer and the developer from the very beginning of work on the project. The formalized technical task on the basis of the automaton programming methodology helps to achieve this.
PS From the above text one can get the impression that with the help of automaton programming only “toy” tasks can be solved. However, it is not.
The given example is not typical for this programming paradigm - it is intended not for the implementation of computational algorithms of the type considered, but for control algorithms with complex behavior depending on the prehistory, which the pattern creators dislike so much.
True, when learning computational algorithms, automaton programming came in handy: Georgy Korneev and Matvey Kazakov showed that based on it, visualizers can be designed and automated to build them even for very complex discrete mathematics algorithms, and not to write them manually every time, like “God for put the soul. " An example of project documentation is given here , and here is an example of such documentation for a complex project.
The documentation for an even more complex project can be found here . The site is.ifmo.ru there are many more projects, both student and others, the study of which will be able to answer many of your questions. With the book Polikarpova N.I. and Shalyto A.A. Automata programming. SPb .: Peter, 2010 can be found here .
And do not fantasize - write: shalyto@mail.ifmo.ru.
Source: https://habr.com/ru/post/323122/
All Articles