March 3, 2017 at 08:28"Cure for the disease": automatic programming
News about various software vulnerabilities appears regularly, everyone is used to it. However, errors in the mobile application are one thing, and the possible shutdown of a nuclear reactor is another. Today we’ll talk about the origins of software problems and a possible way to fix the situation, in particular, automated programming. Robson # / Flickr / CC
At the beginning of the year, Rosatom State Corporation had
questions to the legitimacy of software used in nuclear power plants. The company's specialists did not find documentation on the PORTAL software platform. This system is used at several power plants in different regions and is a software for collecting, processing and displaying information about the state of power units and equipment management.
As it turned out, in the archives of the system developers there is no design, technological and operational documentation, and some employees work with unidentified versions of software components. Access to the source code of such an important system by private individuals makes us think about security, since a failure at a nuclear power plant can lead to serious consequences.
Situations such as those described above are far from uncommon throughout the world. In many ways, the reason for this 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 right away. In this case, the documentation for the software is often omitted.
If there is a need to change something, then programmers just edit the code, not considering that each such intervention creates a springboard for problems in the future. Probably, other developers will have to do this. It’s just to understand someone else’s code without enough detailed documentation and maintenance is not easy.
Automated programming is a programming paradigm in which the program or its fragment is interpreted as a model of some formal automaton. This term was proposed in 1991 by Anatoly Shalyto, head of the Department of Programming Technology at ITMO University.
To understand the principle of the program could be any person interacting with it, the behavior of software is described using transition graphs . Symbolic notation allows us to represent 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 capture the whole picture with a glance.
As part of automatic programming, it is assumedthat the program is written only after it has been designed. Moreover, each project necessarily ends with the release of documentation. The design of automata that describe the logic of work of solutions leads to the fact that programs require minimal debugging and are almost immediately ready to run. If the need for debugging still arises, then you can generate debugging protocols that reflect the behavior of automata in terms of states, transitions, and actions.
As an example of using the automaton approach in constructing an algorithm, we give a solution to the direct traversal problem (0–9) of a binary tree.
An example of a binary tree.
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 the put (int x) function in the system , which displays the vertex number in the output sequence, and the class that implements the stack with the following interface:
The idea of the proposed algorithm is that when traversing a binary tree, three directions of movement can be distinguished: left, right, and up. Depending on the current direction of movement, the properties of the current vertex and the extreme symbol in the stack, you can determine where to move next. Therefore, it is convenient to compare each direction of movement with the control state of the machine. The circuit diagram of the tree traversal automaton, as well as its transition diagram, are shown in the images below.
The circuit diagram of the machine that implements the tree walk
Transition diagram of an automaton that implements tree bypass
Note that the theory of finite automata was successfully used by Corezoid to build the eponymous cloud platform for IT solutions. Anatoly Shalyto says about the need to implement this method in modern development: “Programmers are very smart, and they use machines, like other mathematical abstractions, when they consider it necessary. And I say: always [automatic programming] should be used to describe programs with complex behavior, in which their behavior depends on the background. ”
According to Anatoly Shalyto, the quality of programs is ensured not only through testing and verification, but also through building relationships between the customer and the developer from the very beginning of work on the project. A formalized technical task based on the automated programming methodology helps to achieve this.
PS From the given text it may seem that with the help of automatic programming it is possible to solve only “toy” problems. However, it is not.
The given example is not typical for this programming paradigm - it is not intended for implementing computational algorithms like the one considered, but for control algorithms with complex behavior that depends on a prehistory that pattern creators dislike.
True, while teaching computational algorithms, automated programming came in handy: Georgy Korneev and Matvey Kazakov showed that it can be used to design visualizers and automate their construction even for very complex discrete mathematics algorithms, rather than writing them manually each time, like “God on put his soul. " An example of project documentation is given here , but an example of such documentation for a complex project.
The documentation for an even more complex project can be found here . On the site is.ifmo.ruThere are many more projects, both student and others, the study of which will be able to answer many of your questions. With a book by Polikarpova N.I. and Shalyto A.A. Automated programming. SPb .: Peter, 2010 can be found here .
And do not dream - write: shalyto@mail.ifmo.ru.
questions to the legitimacy of software used in nuclear power plants. The company's specialists did not find documentation on the PORTAL software platform. This system is used at several power plants in different regions and is a software for collecting, processing and displaying information about the state of power units and equipment management.
As it turned out, in the archives of the system developers there is no design, technological and operational documentation, and some employees work with unidentified versions of software components. Access to the source code of such an important system by private individuals makes us think about security, since a failure at a nuclear power plant can lead to serious consequences.
Where do the legs grow from
Situations such as those described above are far from uncommon throughout the world. In many ways, the reason for this 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 right away. In this case, the documentation for the software is often omitted.
If there is a need to change something, then programmers just edit the code, not considering that each such intervention creates a springboard for problems in the future. Probably, other developers will have to do this. It’s just to understand someone else’s code without enough detailed documentation and maintenance is not easy.
Automated programming comes into play
Automated programming is a programming paradigm in which the program or its fragment is interpreted as a model of some formal automaton. This term was proposed in 1991 by Anatoly Shalyto, head of the Department of Programming Technology at ITMO University.
To understand the principle of the program could be any person interacting with it, the behavior of software is described using transition graphs . Symbolic notation allows us to represent 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 capture the whole picture with a glance.
As part of automatic programming, it is assumedthat the program is written only after it has been designed. Moreover, each project necessarily ends with the release of documentation. The design of automata that describe the logic of work of solutions leads to the fact that programs require minimal debugging and are almost immediately ready to run. If the need for debugging still arises, then you can generate debugging protocols that reflect the behavior of automata in terms of states, transitions, and actions.
As an example of using the automaton approach in constructing an algorithm, we give a solution to the direct traversal problem (0–9) of a binary tree.
An example of a binary tree.
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 the put (int x) function in the system , which displays the vertex number 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 traversing a binary tree, three directions of movement can be distinguished: left, right, and up. Depending on the current direction of movement, the properties of the current vertex and the extreme symbol in the stack, you can determine where to move next. Therefore, it is convenient to compare each direction of movement with the control state of the machine. The circuit diagram of the tree traversal automaton, as well as its transition diagram, are shown in the images below.
The circuit diagram of the machine that implements the tree walk
Transition diagram of an automaton that implements tree bypass
Note that the theory of finite automata was successfully used by Corezoid to build the eponymous cloud platform for IT solutions. Anatoly Shalyto says about the need to implement this method in modern development: “Programmers are very smart, and they use machines, like other mathematical abstractions, when they consider it necessary. And I say: always [automatic programming] should be used to describe programs with complex behavior, in which their behavior depends on the background. ”
According to Anatoly Shalyto, the quality of programs is ensured not only through testing and verification, but also through building relationships between the customer and the developer from the very beginning of work on the project. A formalized technical task based on the automated programming methodology helps to achieve this.
PS From the given text it may seem that with the help of automatic programming it is possible to solve only “toy” problems. However, it is not.
The given example is not typical for this programming paradigm - it is not intended for implementing computational algorithms like the one considered, but for control algorithms with complex behavior that depends on a prehistory that pattern creators dislike.
True, while teaching computational algorithms, automated programming came in handy: Georgy Korneev and Matvey Kazakov showed that it can be used to design visualizers and automate their construction even for very complex discrete mathematics algorithms, rather than writing them manually each time, like “God on put his soul. " An example of project documentation is given here , but an example of such documentation for a complex project.
The documentation for an even more complex project can be found here . On the site is.ifmo.ruThere are many more projects, both student and others, the study of which will be able to answer many of your questions. With a book by Polikarpova N.I. and Shalyto A.A. Automated programming. SPb .: Peter, 2010 can be found here .
And do not dream - write: shalyto@mail.ifmo.ru.