7: General questions of programming

Introduction

Let us begin with a brief comparison of the development paths of the two branches of Sentential programming.

Prolog language development

The British-Canadian group that created Prolog initially focused on problems of mathematical linguistics, where complex data transformations involve hypothesis testing.

This naturally led them to the Refalou orthogonal approach ¹ , formally motivated by mathematical logic. The presence of precisely formal motivation did a disservice to the Prolog language and the whole direction. Its essence was disguised by a primitive methodological and theoretical analysis and an inadequate name: logical programming.

Prolog was inspired by the restriction of the classical predicate calculus proposed by Horn. As is well known (see, for example, the book [20]), in the classical logic in any sufficiently rich theory, pure existence theorems emerge when it is impossible to isolate the construction of the required object from the proof. If we confine ourselves to the conjunctions of the implications of the form

,

where each component is an elementary formula and the proved statement itself has the same form, then it is possible to obtain a construction from the proof, since we do not have even indirect ways to formulate and nontrivially use something similar to . Such formulas are called horn .

One can get rid of extra quantifiers by using scolemization , when existential quantifiers are replaced by a function whose arguments are all variables connected by previously standing quantifiers of universality ² . Thus, we arrive at the simplest form of Horn formulas ( Horn implications ):

.

Applying to the last formula a transformation performed only in classical logic, we arrive at Horn clauses:

.

It is from the last form of representation of horn statements that the main data structure of the Prolog language is named. But the fact that the implication is transformed into a disjunction is not actually used anywhere in this language, it served only to establish interconnections with the algorithm of the resolution method [30], which at that moment was the last cry of fashion in the automatic proof of the theorem (and really huge conceptual promotion). The resolution method still remains one of several most frequently used methods of automatic proof, and the only one known to the general public. This method has put three ideas (unification, standardization of goals, standardization of the order of withdrawal), which Prolog was a beautiful programmer implementation. But the findings of the Prolog language are not exhausted by the realization of ideas taken from the theory. They made a significant contribution to the theory and methodology of programming ³ .

It is by the example of the Prolog language that the Western programmer community has clearly realized that there may be completely different models of program execution, which are neither traditional nor their extensions. He was rehabilitated and sometimes successfully used the method of dynamic generation of the program. The idea of ​​indirect computation management has become topical. These advantages are more than enough so that Prolog can be considered an important fundamental achievement.

The development of the Prolog language is hampered, first of all, by too much binding to a specific model of calculations, which was fixed too early in the pursuit of imaginary efficiency. The perception of his place and role is completely distorted. In fact, Prolog is an excellent piece for the modeling language of ideas, and not logical programming.

Consider what exactly this procurement prevents in reality to become such a language. As we have repeatedly seen, the main obstacle is the loss of integrity caused by superfluous possibilities. First of all, these are eclectic additions of operational tools, which provoke the programmer to operational thinking and hacker style. Thus, in the labyrinth problem it would be natural not to loop execution, when there are no restrictive conditions forcing the program to move forward, but an indication that the process does not have enough conditions that certain restriction options are possible that make the program correct. As a result, language developers had to look for additional means of expressing the required, rather than proposed, actions. They did not find anything better in comparison with the known operational methods and included the corresponding means in the language, completely losing the original concept.

One of the classic examples of using high-level models and flat, inadequate practice, but attractively sounding and simply explained, conclusions drawn from them is the statement: "Horn's logic is sufficient for specification of calculations, because, as was proved, it is equivalent to the Turing machine ⁴ ". It would be possible to agree with this statement if the solutions of real problems that appeal to fact databases and should be solved using knowledge bases of statements that are consequences of the available facts could always be formulated in such a divided manner: then the correlation clauses and then the information is manipulated. In fact, thus formulated solutions are suitable only for a narrow class of problems that are characterized by the stability of facts, and only in the case when efficiency is not taken into account.

Development of the Refal language and its dialects

The Refal language was created by VF Turchin for analytical calculations in physics. Initially, Turchin thought out the very idea of ​​concretization and presented it in the form of a language, pointedly written down in a not too directly representable form. For example, there was no concept of determinative, the proposals had the form similar to

§1.1.2 E1 + (E2 * E3) = (K E1 + E2.) * (K E1 + E3.)

The specific syntactic form of the language given in the theoretical work of Turchin (see, for example, [27]) was immediately changed for convenience of presentation and work ⁵ . Already at the first implementation, the identification algorithm given above was thought out, the hierarchical comments were thrown at the beginning of the sentences, and instead the concepts of determinative and function appeared.

Further refinement required I / O procedures and a mechanism for storing global data, which was implemented through stacks of buried data. The resulting language Refal-2 for a long time was the practical standard Refal-systems.

In Refal-4, two attempts were made to expand the language. Firstly, as in many other systems, the emerging trendy object-oriented tools were quite mechanically added to the Refal. This attempt quickly reached an impasse and was abandoned. Secondly, metaoperations were identified. This innovation has proven its viability and survived. In Refal-5 [37], which is now the de facto standard ⁶ , objects were discarded, but the idea of ​​meta-coding was consistently carried out as a standard superstructure over the language. It received its final design nested procedures and additional conditions.

Of the other existing versions of the language, Refal-6 and Refal + [10], which develop the same line, are worth noting. In the implementation Refal + moved away from the representation adopted in [25] in order to take advantage of modern garbage collection algorithms. Instead of stacks of buried values, these languages ​​offer objects that have only one meaning. In particular, such objects are used to describe graphical input and output, which is completely ignored in the standard Refal. In these versions, it is allowed to declare the function retractable and try to handle failure if it is impossible for the identification. But the author of these versions ignored the conceptual incompatibility of failures with the general management structure in Refal. From Refal +, in addition to the new data structure, it is worth noting the concept of streamlining possible identifications and the ability to control this ordering to some extent (although the language provides only a transition from direct order to its conversion, but this already gives in some cases a big gain in expressiveness ).

The most noticeable disadvantage of the new versions of Refal ⁷ was the lack of distinction between abstract and concrete syntax. It would be possible to simply abandon the fixation of the design in the language definition and give the opportunity to determine the syntactic extensions and representations by the developers themselves.

It is worth noting that the current Refal language is in a soft conceptual contradiction with the idea of ​​dynamically calculating programs that is so brilliantly implemented in it. The decision to execute that functional bracket, inside which there are no other such brackets, was justified and logical when creating Refal, and now it prevents the effective use of the meta-transformation apparatus. It should be noted that Refal is ripe for a true representation of a multi-hierarchical structure, which will allow the language to enter new classes of applications. Thus, in the near future we can expect the emergence of a new sentence language, realizing the idea of ​​concretization. It will be just trouble if, under a beautiful wrapper, someone slips a conceptually ill-conceived 'pragmatic' solution into this area. The gain from pragmatism will be minimal, temporary and local, and the losses will be long, an order of magnitude better than those of traditional languages, and also global.

It was in Refal that it was clearly shown how to choose the data structures and algorithm of the abstract machine for non-traditional calculations and how important it is. In it for the first time got rid of a rigid binding to specific syntax. He demonstrated to the Soviet programmer community the possibility of alternative computing models by fulfilling the same role in the east as Prolog in the west. It was first implemented the concept of embedded partial computing programs. He did not succumb to the pressure of fashion, and this contributed to the realization of the availability of alternatives, even when approaches are close in principle . All this is enough to recognize the pioneering role of this language.

Comparison of versions of sentence programming

First of all, the management methods of the Prolog language and the Refal language are fundamentally different. In Prolog, failure is global, but correctable, and in Refal it is local, but fatal .

Unification in Prolog and specification in Refal are operations of about the same level of generality. But the directions of unification and specification are orthogonal.

• Concretization deals with expressions in which subexpressions can be distinguished in various ways, and the tree-like hierarchical structure is combined with a linear structure within one hierarchy level, and when unified in Prolog and in logic, all expressions are strictly limited to brackets or commas, that is, only a hierarchical structure is present.
• The concretization does not look deeper into the hierarchy than is clearly indicated in the relevant rule, and unification can move along the levels of the hierarchy as deep as necessary.
• When instantiating, the variables are local, and their values ​​do not affect the interpretation of the rest of the memory area, and when unified, the variables are global, the resulting unification takes place immediately in the entire field of view, and not only in its active part.
• When specifying variables in the course of establishing the values, failures and returns are possible, and when standardizing, the values ​​of the variables are recursively typed in accordance with the algorithm for finding a unifying substitution, and the failure of this single option means the failure of the entire unification attempt.

Attention !

The models of unification and concrete definition are formally incompatible, because by connecting them we get an algorithmically insoluble concept of identification (N. K. Kossovsky et al., 1990) .

This is the deepest theoretical result and one of the rare direct warnings made by the theory of practice ⁸ . Therefore, with the similarity of many of the ideas on which they are based, these models develop and must continue to develop independently (which does not preclude the creative borrowing of ideas from one incarnation approach to another). Please note that we are faced with the same situation that exists for cyclical and recursive forms of structured programming.

In the same way as the cyclic form of structured programming, Refal is adapted to work with data that is expanded mainly in breadth and for widening the process. In the same way as a recursive hypostasis, Prolog is adapted for deploying the process in depth and for working with data that has a limited width, but a greater depth.

Even the machine implementation of these languages ​​is akin to two aspects of structured programming. In Refal, calls that look like recursive, in fact, are not recursive ⁹ , because we end up giving rise to the call, and only after that proceed to working out the generated ones. Prolog is more like recursion, because after calling an internal predicate, we can return to the external one and continue trying to unify it. In Refal, the common memory field is sufficient, and in Prolog, the control data (return points ¹⁰ ) are also forced to memorize.

It is worth noting that the potential programming, and especially its variety based on the identification-replacement model, perfectly combines with the idea of ​​associative memory (see p. 31), and a breakthrough is possible at the same time at the hardware and software levels.

The alternative programming concept, based on returns and unification, is perfectly combined with the idea of ​​a data stream machine. The Japanese tried to use it in their fifth generation computer project. The failure of this project has for a long time discredited the direction of connecting potential programming with data streams, but it will have to return to another technical and, apparently, on a much more conceptually verified programmer basis.

The concept of unification and returns after failure is extremely well suited to express -parallelism (see § 15.2). Moreover, there are already systems (in particular, Muse) that implement this version of parallelism in the Prolog language.

Refal, in turn, is great for & paralleling. Substitution of variable values ​​into the resulting expression can be done independently of each other. Moreover, in principle it would be possible even in the current version of Refal to calculate various functional brackets in parallel, only values ​​transmitted through the instillation-digging apparatus can prevent this. But this is a standard synchronization problem for parallel computing, which can be handled by well-developed means, especially since the apparatus for appropriate program markup has been conceptually prepared in the language during its compilation.

Thus, the two branches of the potential programming are oriented even to different classes of parallel computing. It is by the example of sentence programming that we concluded that there should be alternative implementations for other styles . Their identification was prevented primarily by the law of the ecological niche.

When creating and developing the languages ​​PROLOG and Refal, the strengths and weaknesses of the Russian and Anglo-American schools of science were clearly manifested.

VF Turchin did an adequate analysis, which was not obsolete for 40 years, but he did not strive for general comprehension and too much popularization (perhaps because he did not need to beat out grants). His followers clearly perceived the idea and developed it, almost completely avoiding the conceptually contradictory possibilities. But the popularization of the language and the external side of working with it (convenient systems, interfaces, etc.) turned out to be almost completely ignored, and therefore the language remains the property of a narrow group of adherents.

Representatives of the Refal community explained their position on the interfaces in the following way.

- Teapots and lamers do not use Refal anyway, and a qualified person will easily write an adapter, especially since the system code is open.

The author at one time was forced to write an adapter between the Refal-2 and Algol 68, but, of course, such a solution and the above arguments are not satisfactory.

From the very beginning, the creators of Prolog have largely used theory and methodology as spells or prayers that are not related to the essence of the matter and are pronounced for its consecration. Thus, the theoretical basis was immediately inadequate, which led to the rapid spread of the system and the loss of conceptual unity. The language, to a much greater degree than Refal, was polluted by alien elements. ¹¹

Неадекватность теории практике помешала осознанию реальных достижений подхода, основанного на унификации, поскольку они часто противоречили мифам и саморекламе. Зато развитие внешнего оформления и удобных (с точки зрения дизайна) средств работы с языком шло адекватными темпами, а реклама его действительных и мнимых достижений далеко опережающими. Язык вошел в практику обучения многих университетов мира и попал даже в стандарты программ обучения специалистов IFAC.

Если говорить о практических задачах, то Prolog значительно лучше подходит для поиска, а Рефал — для синтаксических преобразований. Стоит также помнить, что в нынешнем состоянии Prolog не может служить даже для прототипирования, это язык лишь для моделирования решений и логики поведения программы.Но это — особенность нынешних конкретных реализаций идеи унификации и возвратов, она связана с тем, что примитивный концептуальный механизм пришел в противоречие с выявившимися богатейшими потенциальными возможностями подхода.

Рефал делает символьные преобразования столь же эффективно, как и программа на традиционном языке, и поэтому может быть использован на всех уровнях: и для создания прототипа программы, и для написания надпрограммы, и для написания подпрограммы.

Таким образом, Рефал по эффективности и ясности представления уже сейчас может служить языком прототипирования, и, если бы его снабдить удовлетворительными интерфейсами, вполне мог бы служить и для окончательных решений, работающих в многоязыковой среде. В момент написания книги существует единственный имеющийся надежно работающий интерфейс Рефала: с языком PHP преобразования HTML-текстов.

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

Prolog currently has interfaces, but, as a rule, they are focused only on C ++ and LISP ¹² and are not standardized at all. Each implementation has its own interface.

We have addressed the general lack of current programming systems. This is a poor study of connections with other languages. When creating higher-level tools, it is necessary from the very beginning to consider the issues of communication with other languages ​​and the use of language in a multilingual and multi-style programming methodology.