You get a bonus - 1 coin for daily activity. Now you have 1 coin

17: General concept of programming styles

Lecture



Why there are no universal methods?

Unfortunately, from the courses of our universities (as was usually the case during the times of the Russian crisis), the extremely important for the world outlook and simply the general culture of science: logic has practically disappeared. This fact is especially regrettable because in the 20th century, logic forced the scientific world view to a qualitatively new level 1 . She first made science think about the limits of its own capabilities.

Here it is worth referring at least to Godel's incompleteness theorem (see, for example, [20]), which states that there is not a single complete theory that describes at least natural numbers. Further, the incompleteness theorem is closely interconnected with the universal algorithm theorem, and it is impossible to bypass it (any attempt to circumvent it refutes itself). The theorem on the universal algorithm entails, as a consequence, the fundamental incompleteness of the universal algorithm (this is a purely functional fact, it does not depend on the concrete construction of the universal algorithm and even on the specific concept of computability underlying the basis). The whole architecture and ideology of modern computing systems is built on the basis of the concept of a universal algorithm (for example, the very existence of a translator from a "universal" language like C ++ is its practical implementation). Thus, the concept of an error in a program is not removable, even in principle .

It means that there is no universal method that allows solving any programmable problem with a guarantee and in a limited time.

You say that people solve problems. But look: each specialist has his favorite tasks, which he solves well. And for your professional growth and sober self-esteem it is very useful to be in a situation where your favorite methods fail. If you have managed to analyze your failure, you are worthy of the title of specialist, but if not, you are on the path to dogmatism or charlatanism 2 .

Often, theoretical considerations of the first level lead to scientific conclusions that are scattered during an in-depth study. But in this case, increasing the depth only enhances the effects of non-universality.

Consider an example of a typical error that is repeatedly made in theoretical justification with the help of the simplest computability models.

Anything that can be calculated can be calculated by a Turing machine. Turing machine can be modeled in C ++. Therefore, nothing but C ++ is needed.

But then it would not be necessary to invent the C ++ language itself, since the machines are designed in such a way that any Turing machine can be simulated in the system of machine commands.

In the history of Russian (or rather, still Soviet) informatics there was a curious case when a minus – minus gave a plus. The ignorance of arrogant virtuoso specialists has stumbled upon the ignorance of a young and ambitious functionary from the Central Committee.

When the question was being considered whether translators should be done, the best Moscow programmers argued that this was not worth doing. They developed an exceptionally perfect system of division of labor when coding at the level of machine commands, when the programmer wrote everything in “meaningful notation”, and the technicians (most often girls) compiled purely mechanical tables and rewritten the meaningful notation into binary codes. The system is described in the book [7]. Therefore, they said that the translators are not needed, the girls' machine programs will be written.

But he rose up young and considered himself a very knowledgeable functionary from the scientific department of the Central Committee and said something like the following:

“I'll reveal the secret information.” We are now creating a machine (this was BESM-6) that will execute a million commands per second. This is what, you girls write a million teams?

Since even in the theory of complexity there are rather independent hierarchies of complexity (for example, winning in time, we often lose memory and vice versa), it is clear that different means are needed for different purposes.

If we go up one more level and consider programs not just as functions on their own, but as a means of solving external problems, then we come across the presence of different versions of mathematics itself (classical and various types of constructive).

Thus, neither absolute truth, nor absolute perfection, nor universal methods are given to man. This is a philosophical conclusion, but philosophy is also a practical science, if you know how to apply it. So let's apply not only the scientific results that flatter us.

Styles, their incarnations, methodologies, techniques, technologies

Since there is nothing universal, you can go to the other extreme, rolling down a set of recipes and losing the very essence of the method: flexibility and wide applicability in various fields. If we focus on such creeping empiricism, then further development quickly comes up against the effect of the garbage heap: unsystematic recipes do not become knowledge. For each class of tasks you need to look for specialized methods and approaches.

The narrower the class of tasks, the more common features these tasks have. This is most clearly seen if the class of tasks is distinguished not by a nomenclatural feature (for example, accounting tasks, tasks for automating workflow), but by criteria reflecting the essence of the structures involved in the tasks. To some extent, the more abstract the description of the task, the better for developing a programming method.

Consider an example . Suppose there is an enterprise with a number of different machines, producing parts. It receives a variety of orders, and in accordance with the priorities of orders and parts processing technology, it is necessary to dynamically build the schedule of operation of the machines. Having solved this problem and faced some time later with the task of document management in a company producing specifications for a large number of various drugs for consumers and for specialists, one can see the similarity of two tasks. In a well-organized bureaucratic machine, each performer works like a machine, performing his operation, just as there is a network of dependencies (some performers can work only after they have prepared the material for others), and the same methods (and often even almost the same programs). ) transferred to the planning of paper flow.

Thus, in order to systematize information and turn it into knowledge, it is necessary to single out the general characteristics of the particular solutions found. These general characteristics are transformed into techniques, and then, with their awareness and generalization, into methods .

The method is a powerful weapon, and therefore, along with great advantages, it necessarily has big drawbacks. In particular, the application of the method requires a sufficiently high intellectual level and possession of a number of skills taught by the exact sciences, in particular, the ability to move from the concrete to the abstract and back. Since the vast majority of specialists do not own the thinking at such a level that they can apply the method in its pure form, the method is specified in the methodology.

A technique is a set of patterns, procedures, and recipes that specify method 3 . For example, the method of multidimensional modeling, which forms the basis of the UML (Unified Modeling Language), is specified in the methodology.

An example of a technique is the generic part of RUP (Rational Unified Process). The UML itself only supplies material for a specific methodology: forms in which it is possible to build a system of interrelated models describing different sides of the program being created, and procedures for debugging such descriptions. The methodology can already be used by a significant minority of 4 specialists, since its use requires elementary operations of concretization and composition and is accessible to people with a combination of thinking. But for successful application in a team, the methodology must be specified further.

The same RUP, besides a technique of application of multidimensional models, contains a part concerning the work schedule of the programmer team according to this technique. This is technology. The technology signs actions, provides document templates, defines the roles and functions of the persons involved in the project. Since the laborer in programmer teams is qualified with the technique of ordinary "iron" production, programmer technologies, unlike industrial ones, leave some room for specification and modification, making it possible to substitute whole series of dynamically defined specific actions into templates. On the "iron" production technology - a strictly defined sequence of operations, roughly corresponding to the debugged program in the programmer world.

RUP allowed dozens of times to increase the productivity of programmers in solving problems, with poor content and a heaped user interface. Familiarity with a specific method of industrial programming should be the subject of a separate course; it is also useful for those who will never use such a technique in their life, since they can go directly to the method level. For them, this technique will be an example of specifying the method that such a person must do if he does not wish to remain misunderstood.

But, besides the methods, there are two more floors. The first of the higher floors began to be considered in the 70s. XX century. This is a programming methodology 5 . Methodology is actually orthogonal to methods: it is a superstructure on the other wing of the programmer building. In this case, it suffices to refer to structured programming. The method is implemented using the methodology and within it.

The second of the higher floors was first systematically investigated in the book [22]. It is connected with the fact that in programming we deal with much more abstract and ideal concepts than in material production. Therefore, the length of logical constructions increases, the complexity of the formalization of the methods used decreases, and we are much more dependent on the logic of our reasoning than on the "matter".

The logic of construction differs from the logic of the design of the finished reasoning, which is taught on standard courses and on which the classical version of mathematics is based. From the beginning of the twentieth century, a constructive direction appeared in mathematics (variants of which are, in particular, intuitionism and Soviet constructivism), for which the main thing is not proof, but the ideal construction it contains. The founder of the constructive direction, L.E. Ya. Brauer (Holland), established that the reasons why a mathematical proof does not always give a construction lie in logic. Thus, the concept of constructive logic appeared, in which we are interested not in the truth of formulas, but in their realizability (the possibility of constructing the solution of a problem by specified means).

Later it turned out that different logics correspond to different classes of means and resource constraints. These logicians do not just diverge, but contradict each other. In order to maintain at least minimal internal consistency of our reasoning during the construction of a complex artificial object (in our case, a program), it is necessary to determine from the very beginning a class of means and resource constraints that must be taken into account.

Thus, there are classes of methods for constructing programs that logically contradict each other and are applicable each in their own field. These classes provide the most general picture of programs based on selected models of computing environment.

Structural programming corresponds to the view of the computing environment as a repository of individual values ​​related by relationships, and the view of the nineteenth century mathematics to the world as something that can be described by numerical characteristics; the role of the program in this case is the calculation of new values ​​by the old.

Automata programming corresponds to the consideration of actions as changing the computing environment significantly and globally, with the result that what was, may be wrong.

Sentential programming considers the computational environment as a global regular structure of values ​​that can be checked for compliance with regularly defined patterns and changed by the same regular substitution of other substructures into it and re-switching of links.

Event programming considers the computing world as something changing in time, and the program as a set of active agents sending messages to each other through the external world and producing actions in it, as a result of which the external world can activate other agents.

All these four styles use only limited (from the point of view of logical formulas) fragments of the corresponding constructive logics. For example, in a structural style, we can assume that there is only one implication in a formula, since all actions transform values, not functions.

Functional programming in its current form corresponds to the view of mathematics of the end of the twentieth century on the world as a set of higher order structures and functionals that produce others on the basis of some structures. It only uses the full language of constructive logic, in which the implementations of complex formulas are functionals.

Thus, the concept of programming style emerged as a set of paradigms and methodologies corresponding to the same class of logical methods used in the construction of programs.

At the first level, all styles fit into the next morphological box according to the coordinates of the action-condition, locality-globality, revealing the purpose of each style.

Actions Conditions Style
Local Local Structural
Global Local Automatic
Local Global Event
Global Global Sentential

In each style there are hypostases. Hypostases are forms in which the high-level and abstract concept of style is manifested in our concrete constructions. Hypostasis logically do not contradict each other 6 , but they are in fact irreconcilably hostile (sometimes even more than different styles), if one tries to use them interchangeably. This is due to the fact that the incarnations are tuned to different disciplines of resource use.

In the structural style there are two incarnations: cyclic and recursive. Cyclic hypostasis is good when the data structures are static and not too deep, and the next layer of information is almost completely used by the next layer. A recursive form is good when the data structures are dynamic and deep, and on the next layer only a small part of the previous layer is needed, or the layers themselves have a small width.

In the automaton style there are two incarnations: serial and parallel. Serial hypostasis is good when the system is presented as a single block of information, and parallel - when the system is divided into relatively autonomous interacting subsystems.

Note that on the automaton style it is possible to trace how the same programs can be implemented by different programming methods that lie inside the same style. Methods of implementation are close to technological discipline, they interfere with each other with arbitrary mixing more technologically than logically or resourcefully. If a program is built with an eclectic mix of several methods, it is harder to debug and especially modify.

In the event-style, there are two incarnations: from events and from priorities. Here you can see that the style appears and exists independently of language support and sometimes even in spite of it.

The functional style of the hypostasis has not yet appeared, since it itself was not conscious and is constantly mixed with the recursive apostasy of structured programming. Here you can see how lack of attention to the interfaces between different styles leads to the integration of one style into another. Even when (as in this case) they interact well, they would even better exist separately.

When do you need to use different styles and how do they interact?

The experience of the author has shown that in very many cases, students who have all the initial data in order to solve a problem by substituting specific values ​​into a general statement, however, are lost without seeing the general in common.

An example . After the problem was solved, whether the polynomial x 2 + (p - 1) over the residue field is modulated by factors, the students deeply thought about the question of whether the polynomial x 2 + 2 could be expanded into a field modulo 3.

In this regard, we will give some tips on the practical application of general principles.

Attention !

Do not take what is given below as templates! For templates, go to other addresses .

  1. If you have a lot of structural or (God forbid) non-structural transitions, or all the time you have to assign values ​​to the features, and then check them, see if you can select a module in the automaton style.
  2. If you start to think of a task as a calculation (not necessarily over numbers), use structured programming.
  3. If you intend to transfer the unnumbered (for example, algebraic, topological or logical) theorem you like to the algorithm for solving your problem, think about the functional style.
  4. If you have every following value requires few data, but different values ​​refer to the same, do not even try to program recursively, you can save the recursive description as program documentation, and write the program itself in terms of loops and arrays.
  5. If the data is strictly subdivided into branches used by different subsequent values, it is often better to write recursively.
  6. If you start looking at data as active units that interact with each other, use object-oriented programming.
  7. If in the previous case objects as they are provided by modern programming systems did not fit, use any package 7 to organize quasi-parallel work in conditional time and program from events.
  8. If you need to convert complex structured texts into other texts, do not be lazy to use Refal (or a new language of advanced concrete programming, if it already appears by the time you read it).
  9. В частности, если исходные данные или конечный результат имеет формат символьного файла, совершенно неудобоваримого для стандартных процедур ввода/вывода используемой Вами основной системы программирования, пишите препроцессоры или постпроцессоры на Рефале (либо, в крайнем случае, на Perl).
  10. Если Вы путаетесь в многочисленных условиях, когда удача либо неудача порою проявляется после нескольких попыток и неясно, куда нужно вернуться, посмотрите, нельзя ли проверку условий запрограммировать на языке Prolog 8 (или на новом языке сентенциального унификационного программирования, если он уже появится к тому времени, когда Вы будете это читать).

О сочетании стилей

Если программа хотя бы средней величины (перерастает 500 строк на стандартном языке), то наверняка в ней найдутся модули, требующие разных стилей.

Дадим некоторые практические рекомендации по сочетанию стилей.

  1. Структурное и автоматное программирование нужно как можно жестче разделять на уровне модулей. Вопрос о языковой совместимости и интерфейсах здесь не возникает, поскольку оба они реализуются стандартными средствами традиционных языков.
  2. Две ипостаси структурного программирования также нужно как можно жестче разделять средствами модульности.
  3. Параллельная ипостась автоматного программирования в настоящий момент может быть реализована практически только последовательными средствами, воспользуйтесь системой моделирования в условном времени.
  4. Событийное программирование стоит выделять в самостоятельные модули либо целиком выносить в Perl-программы.
  5. В настоящий момент имеется целый ряд языков, основанных на идеях функционального программирования и продолжающих тенденции языка LISP на более современном уровне. Они имеют интерфейсы с С++ и Java, так что для написания модуля в функциональном стилевнутри большой, в основном традиционной, программы лучше воспользоваться Ocaml или Haskell.
  6. Common Lisp обладает достаточно удовлетворительно проработанными интерфейсами с C++. Эти интерфейсы могут эффективно использоваться профессионалами. В отношении же концептуальной целостности Lisp остается несравненным, и, если значительная часть Вашей программы функциональная, стоит пользоваться им.
  7. Common Lisp обладает удовлетворительно проработанными интерфейсами с Prolog. Но автор не считает разумным писать программу, соединяя функциональный стиль и унификационную ипостась сентенциального, и будет благодарен за примеры противного, если такие найдутся.
  8. Тем не менее указанный в предыдущем пункте интерфейс полезен, если Вы решили использовать задел, накопленный на одном из двух упомянутых языков, в новой программе, написанной на другом. Но будьте готовы к тому, что концептуальные несовместимости могут в некоторый момент оказаться хуже необходимости переписать используемые программы по-своему.
  9. Хороших интерфейсов с Рефалом нигде нет. Но, несмотря на это, есть один практический совет. Системы ввода/вывода Common Lisp и Prolog настолько неудобны и морально устарели, что написание пре- и постпроцессоров обработки входных и выходных данных на Рефале (либо Perl) окупается, а в Lisp или Prolog есть смысл пользоваться лишь простейшими возможностями ввода и вывода, принимающими предварительно обработанные и полностью укладывающиеся в структуру языка данные и выдающими их также без учета пользовательского формата.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Programming Styles and Techniques

Terms: Programming Styles and Techniques