Automated programming - a new milestone or myth? Part 1. Introduction

Table of contents.
1. Introduction
2. State and transition diagram.
3. State and transition diagram. Continuation
4. Efficiency of auto-designed programs
Automated workshop - 1. Example “Display”, development of OA and UA
Avtomatny workshop - 2. Example "Crossing", the mathematical transformations of TK in OA

Probably, there are not so many programmers who have not heard of digital machines, but in order not to cut off the audience, I will briefly describe the essence. An automatic machine is a digital device built on the principle:
')

• combinational circuit (CS) - a digital logic circuit that does not contain inside the memory elements. Those. her condition is determined only by what she has at the entrance.
  
• The inputs of the CS are conventionally divided into two groups: I (n) —external signals (inputs of the automaton), S (n) —the internal state of the automaton at the current step. The internal state is, figuratively speaking, a kind of “mode”, which determines how the automaton will convert external signals I (n) into signals O (n). In the classical combinational circuit (there is no group of inputs S (n)), this “mode” is only one.
  
• The outputs of the CS are also divided into two groups O (n) - signals that go outside, which actually perform the “useful work”, S (n + 1) internal state for the next step. That is, at each step, the automaton, depending on the input signal I (n), not only calculates the desired output signal O (n), but also turns on the signal processing mode for the next step (i.e., signals I (n + 1)) and, if necessary, this mode can be the same or different. In other words, you can set the required modes for any possible cases of sequences of input signals , which makes the automata so “all-powerful”.
  
• For the purpose of synchronization, a memory device (memory, parallel register) is inserted which separates the word relating to the previous step from the word related to the next in the feedback circuit. The symbols n and n + 1 denote the current step, and the next step, i.e. n does not correspond to the time axis, but a sequence of steps. The steps are set by the clock signal, and the clock signal is linked to the time axis through the clock signal. The steps may not be associated with a periodic clock signal, but with the event “arrival of signal I”.
  
• A similar storage device for the same purpose is inserted into the channel of the input signals I
  

If you were not familiar with automata, for all the clarity of the explanation, the benefits of such devices are not obvious, but there is a mathematical abstraction that illustrates the essence well. The operation of the machine can be visually described using the state diagram and transitions . Below is a diagram describing the operation of the device that controls the elevator. This is a very simplified diagram that does not take into account the processes of opening / closing doors, accelerating / stopping, but it gives a visual representation of how the work of real-world objects is modeled using automata. Above the arrows is written the condition under which the transition will occur, in the oval is written
state_name / what_will_to_out_exit_ bye_automatic_in_this_state.

All more or less complex digital circuits are designed exactly as digital machines. Why? The indispensability of the automaton approach in the design of digital circuits is facilitated by three main advantages of the automaton approach:

• Decomposition.
  
• A look at the processes not as a sequence of steps , but as a collection of all possible steps .
  
• Maths.
  

Part 1. Constructive decomposition.

In the mathematical theory of automata, decomposition is the creation from an automaton, working according to a complex state and transition diagram, of several simple and clear automata that have a parallel and / or sequential connection and add up to the original automaton. This is a mathematical and, therefore, an exact procedure.

We consider practical machine building, therefore, in the first part, by decomposition we mean not a mathematical decomposition, but a splitting of an automaton in accordance with common sense. In the second part, examples of mathematical decomposition will be given.

Machines are usually divided into operating and control . The meaning is obvious from the name - the operating machine is the "hands", the manager is the "head". Moreover, the partitioning can be multi-level: the operating automaton, in turn, can be divided into executive and management parts. Those. a manipulator arm can have its own “minimal brain”, translating common commands (“take an object”) into a set of detailed commands that control each “finger”. An even more illustrative example is a processor with pipelines, registers, ALUs and FPU — operating machines, and a microprogram — a control machine.

The principle of splitting a large task into small subtasks is actually already widely used in programming practice; it is the division of a task into subprograms. However, automaton interpretation of programs, i.e. the representation of any software object in the form of an automaton, which has an operating part and a control part, allows you to get away from the mechanistic and naive (in a good sense) fragmentation of the source code and gives a set of practical considerations how to do it, which significantly improves the quality of the program at the stage design . Consider an example that will allow to talk about programmata more substantive. This example will be cross-cutting over several articles.

Formulation of the problem

Suppose we have a b / w graphic display. Its video memory has a standard byte organization, in which each bit represents a certain point. Suppose we need to output text in different, non-monospaced fonts.

All characters in the same font height, but the font can be changed on the fly, in the process of outputting the same line. Similarly, attributes can be changed - bold, italic, underline. To control the parameters, esc-sequences are used , which include the control character '\ n', a line break, i.e. the text of one line can be displayed on several lines on the display. For example, the text:

"Text 1 \033[7m Text 2 \033[27m \033[1m Text 3 \033[21m \n Text 42" 

The text is displayed in the area bounded by a rectangle (Fig. 4, c) and may have an offset. The coordinates of the output area are not specified in familiarity, but in pixels, the coordinates can be negative, which means going beyond the output area. Text outside the output area is clipped.

We need to create a function that implements all this, with a prototype

 void Out_text(int x0, int y0, int x1, int y1, int x_shift, int y_shift, char * Text); 

The compilation of an automaton (that is, a model of the process being implemented) is carried out from the general to the particular, from top to bottom, but the detailed elaboration of the model and its software implementation, on the contrary, occur from the bottom up. This is dictated by the fact that usually the lowest level is directly tied to the actuators, which puts us in a certain framework and limits the possibility of "maneuver", while the higher levels are more flexible in this regard, and the framework for them follows from the implementation of the underlying automatons.

The process of creating the software implementation is iterative, first the lowest level of the model (developed from top to bottom ) is implemented, then the next level is developed, the underlying level is being corrected in parallel, after which the development proceeds to a higher level, with the underlying being adjusted as necessary. Competent design requires minimal processing of the underlying levels, limited to their addition . The final realization of automata in the form of program code is carried out after the compilation of all automata, but nevertheless, the sketches of algorithms are performed in parallel with the design of automata. All the underlying calculations were performed by me, not after drawing up the program, as an illustration, but before creating the program code, as an important design stage. So, let's start developing.

As follows from the condition of the problem, the initial sequence of characters in the general case looks like: Text1 control1 Text2 control2 Text3 control3 Text4 control4 Text5 \ 0
where upN control esc-sequences, characters of translation and end of line that separate text blocks from each other. The breakdown of text into blocks is convenient in that it allows you to use the maximum number of identical settings within one block (for example, text height and the coordinates of the beginning of a line).

The development of a pair of OA-UA always begins with the development of OA. OA is built on the basis of our attempts to model all aspects of the process that our machine gun will control. In the case of the display, we have a couple of distinct aspects: splitting the text into blocks separated by control sequences and assembling graphic data in a buffer that will be reset to video memory. Consequently, the automaton will consist of two sub-devices shown in fig. five.

• first send the Write_byte command (byte coordinates on the display)
• after which it is possible to get confirmation
• and only after that you can transfer bytes.

The operating part of the blocking machine consists of an input stream of bytes, which is divided into blocks. To avoid unnecessary copying, text blocks are parts of the source line that are passed to the Text Block Output Machine in the form of two Text_begin and Text_end pointers.

The breakdown machine controls the settings of the Text Block Output Machine through direct access to the corresponding variables of the machine.

The automatic breakdown of text into blocks is a very simple OA, it can be said that there is no automaton, just a couple of pointers plus a set of replaceable variables, but we consider the general principle, the principle that will be useful when developing the second automaton - Automatic output of a text block

Once an OA has been developed, it is easy to make up the control automaton required for it.

In this case, the controlling automaton is well described both in terms of the algorithmic graph-scheme and in terms of the state diagram, but since this is an automaton, we use the state diagram. The state diagram not only emphasizes the “automatism” of the task, it is useful in that it is an alternative, more convenient way of writing conventional software algorithms. If you look at the essence of the question, a state diagram is a natural form of recording a software process in a broad sense, while an algorithmic graph-diagram is an artificial construction that already contains implementation features that are most often obvious and do not require their separate recorded. Moreover, it is these very features of the implementation (when they are minor details) that sometimes disguise the main idea, pushing itself to the forefront along with the really important details. In the next part, a fine example will be given showing the difference between the algorithm given by the graph scheme and the algorithm given by the state diagram. The state diagram is elementarily converted into program code.

Text block output machine

As was shown above, control sequences can, among other things, set the output coordinates of the next text block. The coordinates of the current text block are set by variables x, y.

The example uses a 5x7 font, but the described module supports work with characters of any size. As a result, a large string build buffer may be required, which is often an important factor for embedders. To minimize the buffer, instead of a set of parallel registers, one can be used that performs “vertical scanning”, we are talking about vertical scanning of the entire text block, i.e. displays a line one pixel high and wide across the entire text block.

When correctly implemented, the speed of this variant of the algorithm is almost as good as the case with parallel registers, although it still requires overhead: 3 bytes per character, but it allows you to completely refuse the line buffer, which for the 256 pixels wide display and 24 pixels high gives savings

Since the development of a pair of OA-UA always starts with the development of OA, and the development of OA starts from the lowest level, we will compose OA for an automatic text output.

Operational automatic output of characters on the screen consists of a buffer in which a text string is collected. Since the width of the character does not equal the width of the byte, each new character will have some shift. For the implementation of the shift is used shift register. If the string buffer is a set of parallel registers corresponding to individual rows, then one shift register is required. As can be seen from the illustration, we have two end-to-end counters Current_byte and Current_shift, which, increasing from symbol to symbol, determine the amount of shift and the place where to put the shifted symbol.

  //         int Current_shift, Current_byte; //        u1x * Text; u1x * Text_end; tFont * Current_font; //     Width  -     u1x * Symbol_array; int Width; //        int Line_width; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// inline void Out_text_block () { Clear_line_buffer(); //     while(Text < Text_end) { Width = Current_font->Width_for(*Text); Symbol_array = Current_font->Image_for(*Text); Line_width -= Width; //      ,    if(Line_width <= 0) break; //       10 Out_symbol(); // Current_byte, Current_shift     . Current_shift += Width; Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; Text ++; }// while(Text < Text_end) Finalize: Out_line_buffer_in_videomemory(); return; }// inline void Out_text_block () 

When composing an operational automaton, it is imperative to take into account all the described points, so we turn to the following abstraction. This (compilation of abstraction) is also part of the automaton approach — one should not neglect the clear visual representation of the problem, although this does not follow directly from the automaton theory. This abstraction was born after I portrayed different versions of the layout of the text.
All characters of the string are divided into categories:

• Characters that do not fall into the output window (1) are simply ignored.
  
• The first character, partially or completely trapped in the output window (2), may require an additional shift to the left compared to the type 3 in order to cut off the pixels protruding beyond the output area. The dropped bytes and bits are simply lost.

• Characters that fall completely into the output area (3), as well as characters of type (2), require shifting to the right, the value of which depends on the coordinate of the character.

As was shown above, the polishing of the software implementation occurs at the last stage, however, for clarity, I will give the source code in its final form, despite the fact that the idea of ​​eliminating double shift appeared already in the process of optimization, after the entire module was debugged, and for this we only had to slightly change the function Out_symbol. The same applies to the use of the Start_line and End_line variables, which will appear only when developing the outgoing Out_text function, but adding them only slightly affected the appearance of the Out_symbol function.

The full version of the source is located by reference in the Display.h / Display.cpp file. There is also a compiled example (Project1.exe). The project itself under Builder 6

 class tShift_register Symbol_buffer; vector< tShift_register > Line_buffer; //         int Start_line, End_line; int Left_shift, Current_shift, Current_byte; //     Width  -     u1x * Symbol_array; int Width; int bytes_Width; //    bytes_Width,      int bytes_Width_after_shift; inline void Out_symbol () { for(int Current_line = Start_line; Current_line <= End_line; Current_line++) { Symbol_buffer.Clear(); //////////////////////// //   2  3    Out_symbol,      if(Left_shift)//  2 { //     8          int Start_symbol_byte = Left_shift >> 3; // void tShift_register::Load(int Start_index_in_destination, u1x * Source, int Width); Symbol_buffer.Load(0,Symbol_array + bytes_Width * Current_line + Start_symbol_byte,\ bytes_Width - Start_symbol_byte); // .15 // void tShift_register::Shift(int Start, int End, int Amount); Symbol_buffer.Shift (0, bytes_Width_after_shift, Current_shift - (Left_shift & 7) ); Symbol_buffer[0] &= Masks_array__left_for_line_buffer[ Current_shift ]; // .16 Line_buffer[Current_line].Or(Current_byte, &Symbol_buffer[0], bytes_Width_after_shift ); } else //  3 { Symbol_buffer.Load(0,Symbol_array + bytes_Width * Current_line, bytes_Width); // .14 Symbol_buffer.Shift(0, bytes_Width_after_shift, Current_shift); // .16 Line_buffer[Current_line].Or(Current_byte, &Symbol_buffer[0], bytes_Width_after_shift ); } }// for(int Current_line = Start_line, Current_line <= End_line, Current_line++) }// inline void Out_symbol () 

 class tShift_register Symbol_buffer; vector< tShift_register > Line_buffer; tVideomemory Videomemory; //        int Start_line, End_line; //         int Left_shift, Current_shift, Current_byte; //        u1x * Text; u1x * Text_end; tFont * Current_font; //      Out_text_block //     Width  -     u1x * Symbol_array; int Width; int bytes_Width; //    bytes_Width,      int bytes_Width_after_shift; //        //      int Line_width; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// inline void Out_text_block () { Clear_line_buffer(); //////////////////////////////////////// //        Type_1: //     while(Text < Text_end) { Width = Current_font->Width_for(*Text); //         if(Left_shift >= Width) { Left_shift -= Width; Text++; } else goto Type_2; }// while(Text < Text_end) //   return; //////////////////////////////////////// Type_2: //  Current_byte = Current_shift >> 3; Current_shift = Current_shift & 7; Symbol_array = Current_font->Image_for(*Text); bytes_Width = (Width + 7) >> 3; bytes_Width_after_shift = (Width + Current_shift + 7) >> 3; Line_width -= (Width - Left_shift); //  ? if(Line_width <= 0) { Width -= Left_shift; goto Type_4; } Out_symbol(); //  Left_shift Width -= Left_shift; Left_shift = 0; //    Text++; //////////////////////////////////////// Type_3: //  ? while(Text < Text_end) { // Current_byte, Current_shift     . Current_shift += Width; Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; //     Width = Current_font->Width_for(*Text); Symbol_array = Current_font->Image_for(*Text); bytes_Width = (Width + 7) >> 3; bytes_Width_after_shift = (Width + Current_shift + 7) >> 3; Line_width -= Width; //  ? if(Line_width <= 0) goto Type_4; Out_symbol(); Text++; }// while(*Text < Text_end) Current_shift += Width; Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; //   goto Finalize; //////////////////////////////////////// //   4     2'  3' Type_4: Out_symbol(); Current_shift += (Width + Line_width); Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; for(int Current_line = Start_line; Current_line <= End_line; Current_line++) { Line_buffer[Current_line][Current_byte] &= Masks_array__right_for_line_buffer[Current_shift]; } Finalize: Out_line_buffer_in_videomemory(); return; }// inline void Out_text_block () 

The output process is obvious, but the explanations are not redundant:

• If the left byte intersects, then the corresponding byte of the video memory is read, masked and superimposed on the leftmost byte of the line buffer (which is already masked during the output to the line buffer).
• If the rightmost byte is intersecting, the corresponding byte of video memory is read, masked, and then superimposed on the rightmost byte of the line buffer (which is masked by the padding mask).
• After that, the entire line buffer is copied to video memory, the line Start_line of the line buffer goes to line y of the buffer, and so on up to End_line and y + End_line - Start_line, respectively, as shown in Figure 20.

 //   //     //////////////////////////////////////////////////////////////////////////////////// if(x1 < x0) { int temp = x0; x0 = x1; x1 = temp; } if(y1 < y0) { int temp = y0; y0 = y1; y1 = temp; } if(x0 < 0) { x_shift += x0; x0 = 0; } if(y0 < 0) { y_shift += y0; y0 = 0; } if(x1 > x_max) { x1 = x_max; } if(y1 > y_max) { y1 = y_max; } //    inline bool Init_text_block() { //   //////////////////////////////////////////////////////////////////////////////////// x += ( x0 + x_shift); y += ( y0 + y_shift); //   //////////////////////////////////////////////////////////////////////////////////// if (x < x0) { Left_shift = x - x0; x = x0; } else { Left_shift = 0; } if(x >= x1) return false; x_byte = x >> 3; Start_shift = Current_shift = x & 7; Current_byte = 0; Line_width = x1-x; //   //////////////////////////////////////////////////////////////////////////////////// if (y < y0) { Start_line = y0 - y; y = y0; } else Start_line = 0; if(Start_line >= Current_font->Height()) return false; if( (Current_font->Height() - Start_line) < ( y1 - y) ) End_line = Current_font->Height() - 1; else End_line = Start_line + (y1 - y) - 1; return true; } 

 /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// //   void Out_text_block (); inline void Control_processing (); void Out_text (int arg_x0, int arg_y0, int arg_x1, int arg_y1, int arg_x_shift, int arg_y_shift, unsigned char * argText) { //  // ... while(*Text_end) { ////////////////////////////////////// state__Inside_text_block: while(1) { switch(*Text_end) { //            case '\0': case '\n': goto state__Out_text_block; } Text_end++; } ////////////////////////////////////// state__Out_text_block: if( (Text_begin != Text_end) && Init_text_block()) Out_text_block(); Text_begin = Text_end; ////////////////////////////////////// state__Control_processing: if(*Text_end == 0) return; //      Control_processing(); }//while(*Text_end) }//void Out_text (int arg_x0, int arg_y0,