14: Structural Programming

“Teacher,” said Sun Wu-kun. “I am a simple person and I don’t understand your city language.” What do the props to the wall mean?

“When people start building a house and want to make it strong and strong, they put supports between the walls.” But time passes, and the building collapses, which means that the props have rotted.

Wu Cheng-en. "Journey to the West," Chapter 2

General characteristics of structured programming

In fact, the presentation of the structural style can not fit into the framework of one lecture. But this programming style (or rather, its version, based on cycles and arrays, slightly enriched with recursive procedures) is described and imposed as the only possible one in all currently offered textbooks on programming in traditional languages. In this regard, we have the right to assume that the student is familiar with him (moreover, he is familiar only with him, and we hope that he has not yet lost the ability to perceive other styles). And although you think that you have already become familiar with this version of the structural style, the features omitted in traditional expositions can completely change your view of this style.

We consider structured programming as an equal member of the community of alternative rival friends ¹ .

* * *

Let's start with the fact that we turn to history.

In the theory of program schemes, it was noted that some cases of flowcharts are easier to analyze [16]. Therefore, it was natural to single out such a class of flowcharts, which the Italian scientists S. Bem and C. Djakopini did in 1966. They proved that any flowchart can be reduced to a structured form by using several additional Boolean variables. E. Dijkstra emphasized that programs in this form, as a rule, are easier to understand and modify, since each block has one input and one output.

As a method of structured programming, E. Dijkstra proposed using only the constructions of a cycle and a conditional operator, driving go to as conceptually contrary to this style.

Perhaps this is the first conceptual contradiction, clearly noted and taken into account in the theory and practice of programming (and even in the whole of modern science). But since there was not even a rough idea of ​​the theory of non-formalizable concepts, and the experience of working with small formalizations was transferred to work with them, the structural contradiction was perceived as follows.

Unfortunately, the go to operator is formally compatible with other constructions of traditional (then they said, universal) algorithmic languages. But he really badly interacts with them. So he is bad in itself.

Structural programming is based mainly on the theoretical apparatus of the theory of recursive functions. The program is considered as a partially recursive operator [21] on library subroutines and source operations. Structural programming is also based on the theory of evidence, primarily on natural inference. The structure of the program corresponds to the structure of the simplest mathematical reasoning, which does not use complex lemmas and abstract concepts ² .

Structured programming tools are primarily included in all traditional programming languages ​​and in many non-traditional languages. They occupy the main place in educational programming courses and in theoretical works (for example, [1], [4], [9]).

With structured programming, assignments and local actions become an integral part of the program. It is enough to carefully monitor that each variable in the module is used for one specific purpose, and not to allow "economy", in which the unnecessary variable in this place is temporarily used for a completely different value. Such "savings" confuses the structure of information dependencies, which, with this style, should be well coordinated with the structure of the program.

Structural programming naturally arises in many classes of tasks, primarily in those where the task is naturally split into subtasks, and information into fairly independent data structures . Its main invariant is:

actions and conditions are local .

A necessary feature of a good implementation of a structured programming style is compliance with the consistency, and ideally and unity, of the following program components:

1. The structure of the information space . In essence, any task can be described as the processing of objects, the complete set of which is called the information space of the task.

   The structured programming style requires the following. The task is divided into subtasks, and thus the tree of subtasks is built. The information space is structured in exact accordance with the nesting tree: for each subtask it consists of its local objects defined together with the subtask and for it, and so-called global objects defined as the information space of the directly embracing subtask. Thus, the information space of the entire task (subtasks of the highest level) expands as we move to subtasks at the expense of their local objects. For different child subtasks of one subtask, it has a common part - the information space of the parent subtask ³ .
2. Management structures . The structured programming style in its generally accepted version involves the use of a strictly limited set of control structures: a sequence of statements, conditional and select statements, all computational branches of which converge at one point of the program, as well as procedures whose calculations always end up returning control to the call point.

3. Either loops or recursions are added to the structure statements.

   Attention !

   You will not find this alternative in the traditional presentations of structured programming. The conceptual contradiction between cycles and recursions is much softer than between structural programming operators and structural transitions, and it is noted only in the form of occasionally encountered pragmatic instructions (good wishes) not to mix them arbitrarily.
4. Data streams . By breaking the task down into subtasks, the programmer envisions their interaction by data: some subtasks transfer data to others for processing.
5. Data structures The data are combined into logically related fragments corresponding to the structures of the task or auxiliary constructions entered to solve it.

6. Ghosts . Often, even the program itself can not be explained through the concepts that are used inside it. More often this happens for her connections with the outside world. Understanding of the program is possible only after comparing real in-program objects with ideal extra-program objects. These ideal non-program objects (ghosts) are often not just unnecessary, but even harmful for the execution of the program ⁴ .

   The first drew attention to the need to introduce ghosts for the logical and conceptual analysis of the programs of G. S. Zeitin in 1971. In America, this "independently" was rediscovered in 1979, although the mentioned article of Zeitin was published in English in a publicly available edition. Even the name of the entities was given the same ... A separate lecture in the course “Foundations of programming” [21] is devoted to this most important and traditionally ignored concept.
7. Supports in the program - values, constructions and entities that are not necessary for understanding the task and program, are not determined by the essence of the task and algorithm, but are forced to be inserted to implement this algorithm on a particular system.

   The props are the opposite of ghosts. In fact, they are the form in which matter penetrates the program, and in this capacity they oppose the totality of ideal entities that generate the structure of the program: both real and illusory - and sometimes they distort it grossly. But without backups, the program simply will not work or will work inefficiently.

For structured programming, the requirement is very important:

All structures are subject to the structure of the information space .

This general requirement is specified in the following.

1. It is necessary that the management structure of the program is consistent with the structure of its information space. Each management structure corresponds to data structures that are consistent with it, and part of the information space. This condition allows a person to easily track the order of execution of structures in the program.
2. Subtasks can exchange data only by referring to objects from the common part of their information spaces (in modern languages ​​it is often global).
3. Information flows must flow according to the hierarchy of management structures; we must clearly see for each program block what it has at the input and what it gives at the output. Thus, the properties of each logically completed program fragment should be clearly understood and ideally clearly described in the program text itself and in its accompanying documentation ⁵ .
4. The description of the variables representing the processed objects, as well as other auxiliary variables during structured programming strictly obeys the division of the task into subtasks.
5. All ghosts act in their structural place and correspond to ideal entities, which, according to the inventor's paradox, must be introduced to effectively solve the problem.
6. All props are strictly localized in the place where they are forced to enter. It is even desirable to designate them differently than ideal entities, for example, leaving mnemonic names only for ideal entities, and call props like jokers like x or i. Care must be taken to ensure that the props do not distort the ideal structure of the program.

Structural programming is best described theoretically, but private descriptions are not consolidated into a single system. Some books interpret it from the point of view of a programmer, others from the point of view of a theorist. So even here, there is still no unified system of views, although, apparently, there are already all grounds for its formation.

Data networks

Consider the basic data structure that appears during structured programming. Accounting for this structure allows you to convert good wishes about the consistency of information flows and the course of management transfers in a fairly rigorous method.

A data network can be formally described as an acyclic directed graph in which all co-paths (that is, paths taken the other way around) are finite and the vertices of which are assigned values .

Consider an example. A well-known standard method of programming in languages ​​without multiple assignments - the exchange of two values ​​through an intermediate

  z: = second;
 second: = first;
 first: = z; 

Corresponds to the following data network:

Fig. 14.1.1. Value exchange

Here, first, second, z can be considered comments, and the data itself is omitted, since their specific values ​​are not important.

This example shows that sometimes for better network structuring, it is advisable to introduce additional vertices corresponding to the conserved values. The edge leading from one such vertex to another is denoted by an arrow that looks like equality. It can be seen in the same way that matter acts on an idea, forcing to introduce additional operators and additional values. In this case, the variable z and the operators that include it are stubs, and, if excluded, the data network becomes simpler. But in common programming languages ​​there are no multiple assignments like

  first, second: = second, first; 

Even if they were, imagine how uncomfortable it would be to read a long multiple assignment and understand what expression is assigned to a variable!

In the case of the program for calculating factorial ^{6, the} network is potentially infinite downward, since any number can be an argument, but the structure is even simpler:

Fig. 14.1.2.

There are no cross dependencies between the parameters, therefore, two known factorial implementations are possible: cyclic and recursive. We will show them in different languages, for all the same in what traditional language to write them.

  function fact (n: integer): integer; 
 var j, res: integer; 
 begin 
 res: = 1; 
 for j: = 1 to n do res: = res * j;
 result: = res; 
 end; 

 int fact (int n) 
 {if (n == 0) return (1); 
   else return (n * fact (n-1));} 

The circuit for building a cyclic program is called stream processing . The values ​​on the next iteration of the loop depend on the values ​​on the previous one.

For the Fibonacci numbers (the same scheme (14.1.2)), the structure is somewhat more complicated than the previous ones, since each subsequent Fibonacci number depends on the two previous ones, but the stream processing method is applicable here.

  int fib (int n)
 {int fib1, fib2;
 fib1 = 1;  fib2 = 1;
   if (n> 2) {
     for (int i = 2; i <n; i ++) {
       int j;  j = fib1 + fib2;  fib1 = fib2;  fib2 = j;
     }
   };
   return (fib2);
 } 

So, in a stream, the structure of two elements changes. It could be directly described as a data structure, and this should have been done if the program were a little more complicated. Then, instead of the j-prop, we would have to introduce a new structure value as a backup.

There is another backup in the program - the cycle parameter i, which is needed only for the formal organization of the cycle.

Recursive implementation of Fibonacci numbers is written even easier and serves as a great example of how contemptible matter kills a beautiful, but shallow idea.

  int fib (int n)
 {if (n <3) return (1);
     else return (fib (n-1) + fib (n-2));
 } 

If n is large enough, each of the previous values ​​of the Fibonacci function will be calculated many times, and without any use: the result will always be the same! But all the props removed ...

In the following example, the inefficiency of recursion compared to a well-organized cycle is even more obvious. Suppose you need to find a path where you can collect the maximum amount of gold, through a network of values ​​similar to that shown in Fig. 14.1.

Fig. 14.1. Golden mountain

With the cyclical organization of calculations, we will have to calculate the value at each point of the mountain only once (to find the prey on the optimal path to this point). Here, the property of optimal paths is used, which makes possible the so-called wave or dynamic programming methods: each initial segment of a locally optimal path is locally optimal. This property is a ghost behind the efficient cyclic implementation of the algorithm, and numerous paths, respectively, are ghostly values ​​that do not need to be calculated. In the recursive implementation, we do not take into account this ghost, and he ruthlessly takes revenge for the blatant ignorance of the theory.

Now consider the case when the recursive implementation is much more elegant cyclic, it is easier to generalize and not worse in efficiency ⁷

Fig. 14.1.3. Euclidean algorithm

In this case, the path to obtain the result does not branch out, and we can only move along it in the right direction (from the target to the source data) and in fairly large steps.

  function Euklides (n, m: integer) integer;  {
   assume m <= n}
 begin
    if n = m then resut: = n
       else result: = Euklides (n mod m, m);
 end; 

If we try to calculate the greatest common factor by moving from data to a target, then we will have to build a huge array of GCD values, only an insignificant part of the values ​​in which will be needed to construct the result. The cost of calculating each individual element in this case is small, and in the opposite direction of the movement a second count does not arise.

In the simplest case, the Euclidean algorithm models the situation that appears in the tasks of processing recursive structures, such as lists. The fact that in some cases there is a repeated counting is a small evil, when these cases are rare and irregular. Repeated counting also occurs in cyclic programs, since it is sometimes harder to find matching elements in a large array than to re-calculate the values ​​we need. That is why recursion turned out to be such an effective method of working with lists and allowed to build an adequate first-order foundation for modern functional programming.

Consider the two extreme cases of movement over the network. When a network is represented as a data structure, a method of lazy movement over the network naturally arises, when, after calculating the values ​​at the next point, one of the points is selected, for which all previous values ​​have already been calculated, and the values ​​at this point are calculated. As can be seen, in particular, using the example of the golden mountain, this method is non-deterministic and can be largely parallelized. But in a particular algorithm, we will have to choose a specific way of lazy movement, and it can be extremely unsuccessful: for example, it will provoke a long movement into a dead end when we have a short path to the goal. Even in theoretical studies, it is necessary to impose conditions on the method of lazy movement in order to guarantee the achievement of a result (see, for example, the theorem on the completeness of semantic tables in the book [20]).

Another extreme case of movement on the network when the network is divided into identical layers. For example, in the network (14.1.4)

Fig. 14.1.4. Fully replaceable array

You can imagine a layer as a static array and seemingly completely forget about the network itself. Забытый призрак мстит за себя, в частности, при необходимости распараллеливания вычислений, и предыдущий случай отнюдь не эквивалентен следующему.

Fig. 14.1.5. Постепенно заменяемый массив

Конечно же большая сеть данных становится необозримой. Справиться с нею можно, лишь разбив сеть на подсети. Таким образом, блоки программы соответствуют относительно автономным подсетям.

Еще Э. Дейкстра в книге [ 11 ] предложил в каждом блоке описывать импортированные и экспортируемые им глобальные значения. Но такая "писанина" раздражала хакеров и в итоге так и не вошла в общепризнанные системы программирования. Сейчас индустриальные технологии требуют таких описаний, но из-за отсутствия поддержки на уровне синтаксического анализа все это остается благими пожеланиями, так что, если хотите, чтобы Ваша программа была понятна хотя бы Вам, описывайте все перекрестные информационные связи!

Резюмируя вышеизложенное, можно сделать следующие выводы.

1. Сеть данных сама по себе в программу не переходит, в программу переходят лишь некоторые свойства сети в качестве призраков и некоторые куски сети в качестве реальных значений.
2. Программа определяется не только сетью данных, но и конкретной дисциплиной движения по этой сети.
3. В случае, если очередные слои сети, появляющиеся при движении согласно заданной дисциплине, примерно одинаковы и состоят из многих взаимосвязанных значений, у нас возникает циклическая программа.
4. В случае, если вычисление можно свести к вычислениям для независимых элементов сети, чаще всего удобней рекурсия.
5. Самый общий способ движения по сети - ленивое движение, когда мы имеем право вычислить следующий объект сети, если вычислены все его предшественники.
6. Структурное программирование нейтрально по отношению к тому, каким именно способом будет исполняться полученная программа: последовательно, детерминированно, недетерминированно, совместно, параллельно либо даже на распределенной системе, - поскольку сеть лишь частично предписывает порядок действий.
7. Конкретный выбор порядка действий в последовательной детерминированной программе является подпоркой, о которой постоянно забывают. Поэтому он чаще всего вредит при перестройке программы.

Attention !

Поскольку структурное программирование отработано и преподается лучше всего, здесь появилась возможность остановиться на гораздо более глубоких и принципиальных вопросах, чем в других стилях. В частности, призраки и подпорки возникают везде, они не являются спецификой структурного программирования, это важнейшие понятия для спецификации, документации и перестройки любой нетривиальной программы

Selection

Рассмотренные до сих пор сети данных представляли в первую очередь тот случай, когда в программе нет значительных альтернативных блоков. Условие было лишь средством проверки перехода от одного этапа вычислений к другому. Однако на самом деле, как правило,программа содержит выбор. Для представления выбора в языках программирования имеются условные операторы и операторы выбора. Рассмотрим, что же стоит за выбором.

Пример 14.3.1 . Пусть в некоторый момент исполнения программы Вам необходимо временно выбросить больший из двух хранимых в основной памяти обрабатываемых блоков на диск. Поскольку разница в длине менее 2 ¹⁶ =65536) несущественна, мы можем записать выбор примерно в следующей форме.

  if
  length(A)-lengtn(B)>65536 -> {
    Save(A); Dispose(A); A_present:=false;},
  length (A) -lengtn (B) <65536 -> {
    Save (B); Dispose (B); B_present: = false;}
 fi 

We used this form to more clearly emphasize the conditions under which actions are performed.

The proposed form of recording is based on the concept of protected teams proposed by E. Deikstroy. The protected command is executed only under the condition that the guard is executed. But if this text is read by a programmer, he must understand that 'only' does not always mean that when the condition is met, the command will be executed. Dickstra's choice operator consists of many guarded commands. In a specific syntax, we use the form for them.

 Guard -> Command 

The relative location of the protected commands in the selection operator is indifferent ⁸ . One of the protected commands is executed , the security of which is true. The specific forms of conditional sentences and choice clauses available in languages ​​are props for implementing protected commands.

It follows from the above that in its essence the choice is as non-deterministic as the execution of the structural program. If several guards are executed, from the point of view of the task, it doesn’t matter which of the actions to choose. However, the available programming tools ⁹ make us definitely make a choice, and of course, almost always we forget to write in the comments that the choice is in fact indifferent, and then with program modifications there are patches on supports, etc.

When there is a choice, we are forced to move from a data network to a more complex structure: & - -graphs. Some vertices can be labeled as - vertices, which means that it is enough to get one of the results corresponding to the incoming arcs, and initiate only one of the performances corresponding to the outgoing arc. For the structured & - graph, it is necessary that it be a network that satisfies the following condition: there is an injection matching each -top from which there are several arcs, -the vertex ψ (ν), from which only one arc goes, such that any path passing through the first vertex, passes through the second. This indigestible theoretical condition is merely stated in exact language, that-vertices should be grouped into structures of the following type, shown in Fig. 14.2 (the number of options can be any).

Fig. 14.2. Network of protected teams

  int search (ELEMENT x)
 ELEMENT y;  int result;
 if (good (x)) {
    return id (x)}
    else for (int i = 0; i <100; i ++)
       {y = get_successor (x, i); 
        result = search (y);
        if (result> 0) return result;
       }
    return 0;
 } 

  / * Examples of structural goto. * /
 .  .  .
 do {y = f (x, y)};
    if (y> 0) break;
    x = g (x, y);
 } while (x> 0);
 .  .  .
 {.  .  .
    {
     if (All_Done) goto Success;
    }
 .  .  .
 Success: Hurra;} 

  if x = 0 then sin (y) else tan (y) 

  if x> 0 then a1 else a2 fi [if y> 0 then j else i fi]: = 
 if z> 0 then sin (u) else tan (u) fi 

  (x: = 3, y: = x + y, z: = x + y)