The mixed calculations

The mixed calculation represents some universal process defined over pairs (the program, data) and leading generally to obtaining the residual program and partial results. A mathematical analog of the mixed calculation is the functionality which for a certain class of functions with several arguments builds (at a task of some arguments) functions with smaller number of arguments. Process of the mixed calculation can be set, in turn, in the form of the program (the mixed calculator) that allows to ask about self-applicability of the mixed calculations, and the mixed calculator to assimilate s-n-m - Kleene's functions.

The concept of the mixed calculation (and the mixed calculator) in application to processors of processing of programs for which programs and their attributes are data allows to investigate and define different types of processing of programs from the general point of view: from broadcasting and interpretation to the analysis of programs, their conversion and generation of language processors. In a number of works on the mixed calculations and transformational approach Yershov methodologically investigates this conceptual party of the mixed calculations.

Determination of the principle of the mixed calculations as general basis of a large number of processes of work on programs distinguishes Yershov's work from a number of the previous works and Lombardi, Futamura, Turchin's guesses, etc. It also became the reason that Yershov's works formed the basis of the new and actively developing direction in programming connected with theoretical researches and practical applications of the mixed calculations. Use of the mixed calculations was very useful methodologically for understanding and interpretation of different concepts and entities of programming.

The concept of the mixed calculations entered by Yershov as the general model for different types of processing of programs with need demanded a wide range of researches both on properties of the model, and on her treatment in the different fields of possible application. Such width is inherent to the works performed as Yershov and together with pupils - V.E. Itkin, B.N. Ostrovsky, V.K. Sabelfeld, M.A. Bulyonkov. The concept of correctness of the mixed calculations was entered and models of the mixed calculations and obtaining the residual program for which it was possible to prove correctness are defined. The transformational model for which the mixed calculation was set by a set of basic transformations became one of such models on which the attention was focused. The model of the mixed calculations and their correctness were considered both for imperative languages, and for recursive programs. A number of important results on determination of the mechanism of a delay (freezing) of calculations and data, by description process of the mixed calculations for different languages of submission of programs, on formulation of set of basic transformations, on reliability (not cycling) of process of the mixed calculations and so forth was received.

For real applications of the mixed calculations in addition to, certainly, necessary properties of correctness and reliability important are their flexibility and depth. And here Yershov and his pupils managed to promote significantly in researches. The flexibility of the mixed calculations can be considerably increased if the mixed calculator is when obtaining the residual program to consider not only properties of data to have specific value, but also thinner properties determined by the known ratios between data (predicates over data). In this case the mixed calculator operates with some situation defined on data. Depth of the mixed calculations is defined by the scheme of the mixed calculations. Along with the strict scheme of the mixed calculations entered in the beginning the polyvariant scheme connected with promotion of the mixed calculations in alternatives was defined even if the choice of alternatives cannot be defined at such calculation.

Together with Ostrovsky Yershov investigated use of the mixed calculations in such traditionally important area as broadcasting, namely creation of translators for the set description of an input language. It is essential to note that here not only the results showing practical applicability of the principle of the mixed calculations were received (it was possible to build translators significantly more effective, than it is reached at normal automatic creation), but also a number of the facts and observations important for comparison of methods of broadcasting and understanding of an entity of broadcasting and the mixed calculations showing methodological importance of the principle.

Thus, in the field of the mixed calculations Yershov possesses not only determination of fundamental concepts and models, but also the defining contribution to the theory and methodology of this area. He by right is considered the founder and the leader of this direction which is actively developed now in different collectives and the countries.

For a substantial contribution to the theory of the mixed calculations A.P. Yershov was conferred an award of a name of the academician A.N. Krylov.