Biography

A.P.Ershov, an outstanding Soviet programmer and mathematician, was born on April 19, 1931, in Moscow. He died on December 8, 1988, in Moscow after the fatal decease.

A.P.Ershov came from the intellectual family. His father was a chemical engineer, his mother was a librarian. The family was a typical representative of Russian democratic intelligentsia: medical officer, professor-chemist, academician specializing in the history of Byzantine Empire. Revolutionary and Communist Party workers of the early days of the Soviet power were among the members of the family.

Since 1943 the Ershovs lived in Siberia, in Kemerovo, where in 1949 A.P.Ershov finished the secondary school and in the same year he joined the Physics and Engineering Faculty of Moscow State University. But because of numerous absurd vetos, so typical for the Stalin's ages, he was prohibited to study physics. Fortunately, Ershov managed to enter the Mechanics and Mathematics Faculty of the University. He began his studies at the Department of Computational Mathematics headed by academician S.L.Sobolev and then, under the strong influence of A.A.Lyapunov, he took a great interest in programming.

In 1953, being a student, he went to work for the Institute of Precise Mechanics and Computing Machinery (ITMiVT); one of the first Soviet programming teams had been established in this organization.

This way that, in fact, was not quite voluntary, led him to programming. But the choice of a field of activity made by A.P.Ershov seemed to be lucky both for himself and for programming. In fact, Ershov had versatile gifts and, without any doubts, he could reach great results in any other area, in particular, in primarily chosen physics. But such aspects of his talent as a power of uncommon apprehension, an ability to find the real basis of intuitively forming knowledge and to see perspective points of growth seemed to be extremely appropriate in the emerging discipline of computer science. Turning to another, more established scientific domain, Ershov should probably have lesser possibilities for realizing his intellectual potential, so, it was a happy choice for him. On the other side, at the time a computer science, as no scientific discipline whatever, required scientists with the character of forerunner (like Ershov) to form the initial scientific amd methodological basis. Ershov's activities that should be considered below seemed to be completely in keeping with the needs of computer science, so, it was Ershov's happy choice for programming.

Ershov received his diploma in 1954; it was the first time in the USSR when the graduates had the speciality "programming". In 1954-1957 he was a post-graduate student with professor A.A.Lyapunov as a supervisor. Ershov's Ph.D.thesis devoted to the notion of operator algorithm was written as early as 1958, but because of "guarded" looks of mathematicians towards the new science he obtained his doctoral degree not till 1962 and quantified in 1968 with the thesis on compiler construction techniques. In 1970 A.P.Ershov became a corresponding member and in 1984 a full member of the Academy of Sciences of the USSR.

This quick promotion is related with the fact that in late 1950s Ershov became one of the leading Soviet programmers not only due to his own brilliant researches, but as a leader of productively working software teams. In 1957 the Computing Center of the USSR Academy of Sciences was set up and Ershov was appointed Head of the Department of Automatic Programming. In connection with organization of the Siberian Branch of the USSR Academy of Sciences and at the request of Academician S.L.Sobolev, the first director of the Institute of Mathematics of the Siberian Branch of the USSR Ac.Sci., A.P.Ershov became an organizer and, in fact, head of the Programming Department of the Institute.

In 1960 he formally accepted the post of head of the Department and left Moscow for Novosibirsk. Siberian Branch of the USSR Ac.Sci. offered good opportunities for wide-scale researches, which was very attractive to young and active scientists, and in late 1950s and early 1960s Ershov was among those who, together with academicians-founders, established Institutes of new scientific center in Academgorodok near Novosibirsk. Later on the Department headed by A.P.Ershov became an essential part of the Computing Center of the Siberian Branch of the USSR Academy of Sciences that was organized by academician G.I.Marchuk in 1964. Due to Ershov's efforts Akademgorodok became one of the leading centers in computer science. He should be recognized as a founder of later well-known Siberian School of System and Theoretical Programming, whose activity was combined from the work of a large number of Ershov's students and successors in different Institutes of the Siberian Branch of the USSR Academy of Sciences. He himself, formally being only Head of Department of the Computing Center, was a leader and informal head of large and actively working community of Novosibirsk programmers.

A.P.Ershov greatly influenced on development of the theory and practice of programming in all the country. This influence is far from being restricted either by the fact that he was head of one of the leading scientific schools, or by his own scientific contribution considered below. In essence, since late 1960s Ershov played key role in the programming community in the USSR. He was one of the main organizers of two first All-Union Conferences on Programming (in Kiev and Novosibirsk), he initiated a great number of conferences, symposiums and workshops on various problems of system and theoretical programming, he served as a member of editorial boards of all leading programming journals in the USSR and was Editor-in-Chief of Mikroprotsessornye Sredstva i Sistemy since foundation of this journal. Ershov chaired several All-Union Commissions and Working Groups. In 1987 he was appointed Head of Scientific Council on Cybernetics that coordinated researches in computer science in the Soviet Union.

As a matter of fact, Ershov recognized the importance of ogranizational activity in forming new research directions and gave much attention to it both in the country and abroad. Ershov actively participated in IFIP: he was a member of IFIP Committees and Working Groups, vice-president of IFIP-68 Programming Committee, invited lecturer at IFIP-71 Congress, organizer of several IFIP Working Conferences. In 1980 Ershov received the Silver Core Award for services rendered to IFIP. He was one of the Editors of Acta Informatica and Information Processing Letters and the member of Editorial Board of Theoretical Computer Science and some other journals.

Ershov established contacts with colleagues and friends abroad; he lectured in Universities of Europe, USA and Japan. Since 1965 Ershov was the member of ACM, in 1975 he was appointed Distinguished Fellow of the British Computer Society. In the late years he significantly contributed into international activities on teaching programming.

A.P.Ershov was an undisputable authority and astonished expert in a large amount of soviet software projects designed and developed under his influence. Being a careful and kind teacher, Ershov paid much attention to training of programmers. Since 1958 he was a teacher, firstly, of Moscow State University and then a professor of Novosibirsk State University, where he taught cources on various fields of computer science.

Ershov's accomplishments in scientific and educational activities were widely recognized in the country. He has been honored with several Orders of the USSR. In 1983 for his contributions to the theoretical study of mixed computation he was awarded the Academician Krylov Prize, the main award presented by the USSR Academy of Sciences for fundamental studies in applied mathematics. Ershov was the first programmer who received this very prestigious prize. In 1985 for the works on methodology of large software system construction he was honored the Prize of the USSR Council of Ministers. This nominated Prize is awarded for outstanding applied researches.

The scientific biography of A.P.Ershov is strongly determined by the fact that he is one of the leading world-known scientists whose activity allowed such research directions as theoretical and system programming to be established. He left the legacy of more than 200 books, papers, reprints, to say nothing of a large number of prefaces, editorial papers, reviews and comments as well as newspaper publications, verses (which were really perfect) and so on. The size of this book does not permit a complete review of all Ershov's papers to be done, so we shall limit ourselves to the consideration of the main ideas and fundamental publications.

A.P.Ershov was one of the first Soviet programmers to make a key contribution to the computer science in our country, that is why the formation and evolution of his scientific interests to a large extent correspond to the formation and evolution of programming in our country and abroad.

As most of the programmers of the fifties, A.P.Ershov was beginning with construction of numerical algorithms and subroutines. In the first paper [1]* the method of matrix inversion has been suggested which is referred to the class of completion methods. Due to compactness and convenient recurrent correlations, this method has become a basis for constructing subroutines for a number of early Soviet computers (thus, the program for the BESM computer has been written by Ershov).

The middle fifties were a period of formation of theoretical and system programming. System programming was originated from research direction called at the time an automatic programming and devoted to design of programming languages and their compilers. The works of Rutishauser and Lyapunov essentially stimulated these researshes. The first Soviet programming languages were based on ideas of operator schemes suggested by A.A.Lyapunov. These schemes defined a program structure in terms of operators belonging to some fixed classes with further representation of the operators. A.P.Ershov headed the project aimed at designing one of the first Soviet programming programmes for the BESM and Strela computers (integrated design of programming language and system was then referred to as a programming programme). The results of this work had been summarized in [5] which was the first monograph on automatic programming in the world and it was immediately translated into English and published abroad and also presented in the papers [2], [3], [9] appeared in 1956-1958. In these works A.P.Ershov for the first time suggested a number of notions, approaches, and techniques that formed a classical basis for programming languages and systems. They include the notion of a loop as a fundamental language construction, a triad internal representation of expressions, the usage of hash function for searching coincident fragments (names), an algorithm of optimal register allocation, the initial ideas of data flow analysis, etc.

Ershov's further works on programming languages and compiling techniques laid the foundation for this research direction. Such well-known optimizing programming systems as ALPHA, ALPHA -6 and BETA were constructed on the base of his ideas, and in many respects they defined modern methodology of optimizing compilation.

The design of the ALPHA system was begun with constructing a language, which was inherent in traditions of programming programme construction. This language was alienated from the initial version of Algol, the so called Algol-58. The team headed by A.P.Ershov carried out a project simultaneously with the international group working on Algol-60. In many aspects the results of these two groups turned out to be similar, so, when the description of Algol-60 has appeared, a new language designed by Ershov's team was referred to as an extension of Algol-60 [7], [14]. This language preliminary called "Input" or "Siberian" language, has become finally known under the name of the ALPHA language.

In the ALPHA language a notion of multidimensional values has been introduced and operations over the values, including construction operations, have been defined for the first time. All these notions are now standard and widely used in such conventional programming languages as PL/1, Algol 68 and Ada.

The concepts which are now natural to any language, namely, a variety of loops and definition of initial values by expressions, were originally proposed in ALPHA. Enumerations and upper (temporary) superscripts were interesting features of the language, but further they, in essence, remained unrepeated. Metafacilities of the ALPHA language description are out of the limits of context-free grammar.

The ALPHA system was the fisrt in the world optimizing programming system for the languages more complex than Fortran. The Algol-60 system simultaneously developed by Hawkins and Huxtable* in the UK, with functional capabilities similar to those of the ALPHA system, has been never implemented. It is worth noting, because at that time the very possibility of constructing compilers for the languages more complex than Fortran was contested by many specialists. The ALPHA system turned out to be a constructive proof of this possibility, which essentially removed barriers on the way of designing new languages with more rich semantics.

The draft proposals of the ALPHA system have been published in [8]. The general description of the system may be found in [17], [21] (the reprint edition of [17] appeared earlier, in 1964). The ALPHA system design and development greatly contributed to the methodology of optimizing compilation. A multipass optimization-oriented compilation scheme was proposed and implemented, at the first time optimizing transformations of intermediate program representation were used in practical program optimization, and intermediate program representations oriented to optimization algorithms were defined and constructed.

Memory economy techniques proposed by Ershov and implemented in the ALPHA system have formed a theoretical and practical basis for the forthcoming researches. In [17] A.P. Ershov introduced a concept of information flow graph for defining such program transformation as global memory economy (complete model is presented in [19]), the problem of memory economy was reduced to the well-known problem of graph vertex coloring in the paper [12], and the outlines of the heuristic algorithm of near optimal graph coloring were formulated in a joint (with G.I.Kozhukhin) paper [10].

Basic principles of a complete theory of memory economy have been formulated in [30]. These results greatly influenced not only the implementation of memory economy techniques but other researches too, in particular, they provide a good example for practical construction of program optimization models.

The further Ershov's works on optimizing compilation have resulted in development of the well-known ALPHA-6 system [35] which is used till now. Repeating many features of the ALPHA system, ALPHA-6 has a more compressed scheme of compilation (10 passes instead of 24). The concept of internal language of program representation as a basis for optimizing transformation algorithms is more precisely defined in the compilation scheme. ALPHA-6 optimizing compilation scheme allows one-language compilers with advanced program optimization, including a global one, to be constructed.

In 1968 A.P.Ershov proposed an idea of extensible machine-oriented programming language adaptable to different object codes. This language, SIGMA, [23] was designed by A.P.Ershov in common with A.F.Rar and others and implemented on several Soviet computers by G.G.Stepanov [78]. The SIGMA language provided facilities for formal description of object language and computer architecture and included free-structured macros. A compact set of basic macros defined lists and words (machine words) consisting of syllables, which allowed efficient data structures to be constructed. The extension mechanism was also implemented by means of the macros. The practical usage revealed that the language was easily adopted to computers with different architecture, including very specific ones. The fruitfulness of the idea of a language with a dense and extensible kernel is proved by the present-day popularity of Forth.

In 1971 A.P.Ershov published the papers [27], [28] which initiated the BETA project. In the framework of the long-term BETA project (summing-up publication [79] appeared in 1982) methodological and experimental researches on fundamental principles of programming languages and compiler construction have been carried out. The very attempt of joint implementation of a variety of programming languages required the essense of the fundamentals to be revealed.

In the 70s the BETA project had mainly research and experimental character, and in the first part of the 80s a multi-language compiling system BETA was implemented.

The 70s were a period when modern methodology of compiler construction arase, when a new generation of high level languages, from PL/1 to Pascal, appeared and was introduced into programming practice. C, Ada and Modula-2 were proposed later, but in many aspects, concerning both language features and implementation facilities, they followed the line of the above-mentioned languages.

The BETA project was in the main stream of general researches and had essential influence on the progress in this area. At that time the problem of designing a standard compilation scheme relevant to a wide spectrum of programming languages was very urgent, and just that scheme was suggested and implemented in the BETA system [38]. It is worth noting that the compilation scheme which was developed on the base of experience gained in 1970s turned out to be practically useful in 1980s: in the BETA system Simula-67 and Pascal as well as Ada and Modula-2 were implemented according to the common compilation scheme.

In the framework of the BETA project a concept of metaprocessors [39] to automatic production of corresponding fragments of the compilation scheme, which forms a basis of modern compiler construction systems, was suggested and worked upon. But in the final version of the system the metaprocessors were reduced to the common library of compiling procedures, which proved to be practically advantageous and theoretically promising approach to automatic compiler construction. In a joint, with V.V.Grushetskij, paper [52] an idea of abstract syntax proposed by J.McCarthy was essentially extended, which allowed this approach to be widely used in design and automatic construction of various language processors.

An internal language plays the central role in the general conception of the compilation scheme in the BETA system [36, 50]. The study of the BETA internal language formed a marked part of the world-wide researches that introduced a concept of internal language and internal representation of the program as fundamental notions in the methodology of constructing a wide variety of programming language processors: compilers, analyzers, program transformation systems, etc. In the BETA system the internal language plays three roles: it constitutes a semantic basis for input languages, it supports optimizing tranaformations at the internal language level and it provides source representation to generate the object code for different computers. The functional overloading of the internal language resulted in the difficulties of its design and implementation.

The original concept of the internal language as a minimal set of orthogonal notions was interesting from theoretical and methodological viewpoints, but in practice this approach turned out to be improper. The final version of the internal language as a union of abstractions of input language notions and constructions including incompletely interpreted constructs depended on a particular input language was designed according to Ershov's ideas proposed in [26]. The analysis of a large number of input languages, their generalization and abstraction were essential procedures which significantly contributed to the comprehension of intensional semantics of existing programming languages.

Based on ideas and concepts suggested by A.P.Ershov, the BETA internal language proved to be appropriate for practical implementation of data flow analysis algorithms and optimizing transformations [38], [79]. Machine-orientation of the language provided practical efficiency of code generation from this language to such considerably different computers as BESM-6 and SM family.

Analyzing general notions of programming languages and realizing some limitations of the concepts, A.P.Ershov came to fundamental and promising idea of a programming lexicon as a common environment to program design and validation [97]. The lexicon is defined as "a phase-structured linguistic system comprising a formal notation to represent all generally meaningful constructs used both in problem formulation and program synthesis and transformation."

According to Ershov, lexicon "expresses program properties and assertions rather than the programs themselves." A programming language codes the objects belonging to the subject domain of the problem, whereas our knowledge about the objects remains outside the program text. But the lexicon is a means to describe the objects belonging to subject domains and it includes a notation to construct knowledge bases for these domains. A program expressed by means of the lexicon comprises, in a sense, the description of its semantics as the set of non-trivial facts about the function being computed unlike a "pure" program that does not provide any information about its functional properties. The lexicon, in contrast to a particular programming language, is an open system. On the whole, the goal of translating each text presented in the lexicon into a machine program is not set, but, if necessary, any machine program may be expressed in the lexicon. By analogy with a natural language, the lexicon has a possibility to describe its one part in terms of its other part.

It is not worth considering the lexicon as something given once and forever. This is just carefully chosen and evolving system of good designations. The more meaningful and comprehensive notation the lexicon has, the more successful it is. The successful application of the lexicon strictly depends on meaningfulness and comprehension of its notation."

We suppose the programming lexicon to be one of the main ideas proposed by A.P.Ershov and a potential source to provide scientific and methodological basis for the future programming.

A.P.Ershov's works on automatic programming are conceptually related to his researches on the theory of programming. The paper [4] on operator algorithms, where he proposed a model of program later known as a standard program schemata, was the first one in this field. A concept of operator algorithm was based on the concept of logical program schemata suggested by A.A.Lyapunov and aimed at constructing an exact model to describe properties of real-world programs.

In the following papers [6,11] A.P.Ershov has more exactly defined the notion of operator algorithm and its relation to actual programs described by the logical schematas, and investigated the correlations between the operator algorithm and such well-known concepts as partially recursive functions and Markov normal algorithms. In these papers the problems of defining optimizing transformations on a program model, and constructing the model of the actual program were posed. The modern theory of program schemata is to a large extent based on early Ershov's works.

The first program model in the framework of modern theory of program schemata, the so called Yanov schemes, was proposed by Yu.I.Yanov in 1958*. In [20] A.P.Ershov reformulated Yanov's results in the form that was currently used in the theory of programming. Graph-theoretical representation earlier proposed in Ershov's papers on operator algorithms allowed more strict formalization to be introduced and axiomatic of Yanov schemes to be refined. It is the axiomatic on which further researches on Yanov schemes are based, in so far as this simplification allows more profound properties of Yanov schemes transformations to be investigated.

In the paper [21] A.P.Ershov introduced a concept of information graph and a concept of schemes over distributed memory (the former in the same form is used in the theory of program schemata and in program optimization).

These notions turned out to be very important both for the theory and such applications as memory economy and program parallelization. The problems of mutual transformations of the schemes over general and distributed memory were also considered in [21]. The general theory of memory allocation was brought to perfection in [30].

The monograph [51] seemed to be extremely interesting and valuable from the methodological point of view. It summarized the theoretical and applied results obtained by A.P.Ershov and his disciples in the theory of Yanov schemes and memory economization problem. The overall significance of the work is hardly possible to overestimate: in this book a correlation between the theory and practice of programming is established, it is clearly shown how theoretical models arise in response to practical needs and how, in turn, the study of these models provides results necessary in practice. As a matter of fact, there are very few such monographs in the world programming literature, and Ershov's book, stimulating a cooperation between theoreticians and practising programmers, is especially useful for both. The character of A.P.Ershov as a scientist in whose activity a theory, methodology and practice of programming were always combined, is evidently revealed in the book.

The joint paper [17] by A.P.Ershov and A.A.Lyapunov devoted to the formalization of the concept of a program had a significant influence on development of the theory of program schemata. All the results obtained till that time were brought together and compared. It is essential that the works on parallel program schemata carried out in Novosibirsk under the leadership of A.P.Ershov were also considered in the paper. Theoretical results were considered with respect to such practical applications as automation of programming and program optimisation. The formulation of a number of new problems related with a development of both the theory of programming and the applications played an important role in further researches.

In the beginning of the 70's Ershov's paper on the theory of program schemata [29] was of no less importance. In comparison with [17], this overview considered new papers and tried to understand new problems arisen at the last time. Besides, it is worth noting two aspects. The first aspect consists in meaningful representation of requirements to the algebra of programming as a universal notation allowing manipulation with processes and algorithms. The second one shows the interrelations between internal language and theoretical models of programs. The paper [28] was the invited paper presented to the IFIP Congress in Lyublyana and then it was republished in the collection of the best papers of 1971.

All the papers of 1967-73 had essential stimulating influence on the development of theoretical programming. The main problems of the theory of program schemata have been outlined, different trends and models have been compared, a common set of notions and terms has been formulated, and various theories and results of their applications have been collected together; in other words, the foundation of the theory of program schemata as an integral research direction in theoretical computer science has been laid in these works.

While the theory of program schemata dealt with a program, i.e. an object to be investigated and modelled, in further researches on the theory of programming A.P.Ershov made the next step, initiating an investigation of the process of work on a program. A concept of mixed computation as a basic principle of systems programming that defined, in either aspect, an operation of processors to handle programs was formulated in the paper [53] and then in [54], [56], [69], and [70].

Mixed computation is a universal process defined over pairs (program, data) and leading in general to obtaining a residual program and partial result. Mathematical image of mixed computation is a functional that given the values of some arguments builds for a certain class of functions with several arguments functions with lesser number of arguments. A process of mixed computation may in turn be given in the form of a program (partial evaluator). This fact allows a question concerning self-applicability of mixed computation to be raised and the partial evaluator itself to be likened to Kleene's s-m-n function.

The notion of mixed computation (and partial evaluation) in connection with program processors, whose data are programs and their attributes, makes it possible to investigate and uniformly define different kinds of program processing - from compilation and interpretation to program analysis, program transformation and generation of language processors themselves. In the series of the works A.P.Ershov methodologically studied this conceptual aspect of mixed computation.

It was the definition of mixed computation principle as a general basis for many different program processors that distinguished Ershov's work from the previous works and insights of Lombardi, Futamura, Turchin and others, and it was the reason why Ershov's works became the basis for a new and rapidly developing branch of programming connected with theoretical investigation and practical applications of this principle. From the methodological point of view mixed computation by itself proved to be extremely helpful in understanding and treating various notions and entities of programming.

The notion of mixed computation introduced by Ershov as a general model for different kinds of program processing required both the properties of the model itself and its interpretation in various application domains to be widely investigated. Just this width is inherent in the papers [65], [68], [90], [99], [102], [104] which are written by either Ershov himself or together with his disciples - Itkin, Ostrovsky, Sabelfeld, Bulyonkov.

The concept of correctness of mixed computation was also introduced and there were defined the models of mixed computation and of residual program generation whose correctness could be proved. The main attention was focused on transformational model, for which mixed computation was defined by a set of basic transformations. The model of mixed computation and its correctness were considered both for imperative languages and recursive programs. A number of important results were obtained in describing the mechanism of computation and data suspension, in defining the mixed computation process for different program representation languages, in formulating the set of basic transformations, in providing mixed computation safety (termination), etc.

In practical usage mixed computation should satisfy not only the necessary requirements of correctness and safety, but also those of flexibility and profundity. And here too Ershov and his disciples succeeded well in their studies. Flexibility of mixed computation can be noticeably increased if in the process of obtaining the residual program partial evaluator takes into account not only the property of data to have specific values but more subtle properties determined by the known relations between data (predicates over data). In this case partial evaluator operates with some environment defined over data. Profundity of mixed computation is determined by the scheme of the latter. Along with the strict scheme of mixed computation introduced at first, there was defined a polyvariant scheme where mixed computation is propagated into alternatives even if the choice between them cannot be defined.

Together with B.Ostrovsky A.P.Ershov investigated the apllication of mixed computation to such an important area as compilation, namely, parser generation for a given definition of a source language. The obtained results demonstrated practical applicability of mixed computation principle (the authors succeeded in constructing parsers nearly as efficient as ad-hoc ones). These and subsequent investigations revealed some facts and observations important to juxtaposition of methods of compilation and showing methodological significance of mixed computation principle.

Thus, in the field of mixed computation Ershov not only postulated the basic concepts and models but also made a decisive contribution to the theory and methodology of mixed computation. He is by right reputed the founder and the leader in the field actively developing now in numerous scientific groups in many countries.

On the base of transformational model of mixed computation and his works on the theory of compilation and program optimization, A.P.Ershov introduces the concept of a transformational machine in [74]. The transformational machine is an abstract computer executing programs in some "superlanguage", its commands being transformations of pairs (program, data). These commands preserve some invariant which guarantees correctness of transformations. The concept of transformational machine seems to be very promising both as a theoretical model for program processors definition and validation and as a methodological basis for constructing various program tools.

The concept of transformational machine is a substantial contribution to the transformational approach to program construction which was popularized by Ershov with great enthusiasm, and whose different aspects he investigated in a series of his works in the 80's. The transformational approach is now developed by a number of research groups in the USSR and abroad and it seems to be highly promising, since it allows very secure and efficient programs to be obtained and an extent of reusability of software to be raised. Ershov's works on transformational approach [66], [74] give a natural growing point for further investigation.

It should be noted that along with the works on languages and methods of compilation, the works on mixed computation and transformational approach were the source of the above-mentioned Ershov's idea of the lexicon of programming.

The papers [73] and [76] devoted to the computability problems seem to be the last Ershov's contribution into the theory of programming. Ershov himself considered these works as an attempt to bring together different approaches to computability which were formed in mathematical logic and in the theory of programming. Since the concept of computability plays an important role in both fields of research and has a large significance in the set of programming concepts, its definition abstracted from inessential syntactical or model notions and, at the same time, absorbing entities necessary both for the theory and numerous applications is evidently one of the main problems affecting further interdependency betweem mathematics and computer science. A large number of definitions of computability has been deeply analyzed and compared, and the contributions to the general theory has been estimated in the fundamental paper [76]. On the basis of this analysis Ershov found an idea for the definition of computability: to reduce the definition of a computable function to the notion of determinant being invariant with respect to different ways of computation specification. These results will apperently have the same stimulating influence on this research area as in the early 70's Ershov's works had in the theory of program schemata.

Ershov's ability to estimate currrent state of both the science and practice and to find real growing points and research prospects that will define further evolution of programming should be considered as great services to national and international computer science. Thus, in the middle 60's he pioneered in recognizing new possibilities of human-computer interaction provided by time-sharing systems. In 1966 Ershov initiated design and development of automated inrormation stations (the AIST project). In the framework of this project a wide variety of researches on computer system architecture, software and simulation has been carried out and the first Soviet time-sharing system AIST-0 has been developed.

In the paper [19] given at AFIPS 1967 FJCC a plan of this system was outlined, and at the 2nd All-Union Programming Conference in 1970 a summary of the project was presented. AIST-0 was implemented on home-made multiple computer system, and, having essentially pioneer character, it greatly contributed to the development of such research directions in the USSR, as computer architecture and operating systems. Unfortunately, an orientation to copying foreign computers later on resulted in slowing-down of these researches.

Separate implementation of control and processing facilities within the single processor, hierarchical structure of software, isolation of the kernel of the operating system, natural combination of different interaction and processing modes provided high efficiency and flexibility of the AIST-0 system.

Summarizing the lessons of AIST and several similar projects both in our country and abroad in the paper presented at the IFIP 68 Congress [24], Ershov formulated several vital theses: on specialization of processors in multiprocessor time-sharing system, on general- and special-purpose time-sharing systems and their applicability, on difference between time-sharing system interaction requirements set by professional and non-professional programmers and on the aspect of these systems later known as "user-friendliness".

The experience gained when supervising such large projects as ALPHA and AIST allowed A.P.Ershov to recognize clearly the general problems of software development. In 1973 the paper [26] that essentially influenced further evolution of this research direction appeared in the Soviet journal Kibernetika. The paper presented a deep and thorough analysis of the external properties of the forth generation computers and the variety of programming systems, namely, operating systems, compilers and their input languages, special-purpose information processing systems, including application packages, whose classification, proposed in the paper, remained valid till now. A number of specific information processing systems was pointed out and their internal and external properties were defined. A general model of operating system, the so called basic operating system with layered structure, was proposed.

The general character of the problems in programming language implementation and construction of interactive language processors and visualization systems was stressed in the paper, and although this generality did not result, in contrast with the author's supposition, in creating universal systems, it stimulated works on searching for a general methodology of constructing such the systems. Nevertheless, a one universality-bounded multilanguage compiling system was created on the base of this generality: it was the BETA system described above.

The consideration of technological aspects of software development was another essential feature of the paper. A.P.Ershov was one of the first Soviet computer scientists who gave rise to the problem of developing a discipline of software engineering. It should be noted that in the end of the sixties Ershov's attempts to draw an analogy between software development and industrial production, to put a discipline, an order and instrumentation into programming that was considered by many old-days programmers as essentially unregulated and creative process were met with active resistance and even sharp protest. In heated discussions he had to advocate assertions seemed to be trivial now.

As early as in the sixties Ershov persisted in the opinion that, in spite of intellectual and creative character of programming, this process required organization and reglamentation, it needed a set or a system of agreements and rules to be set up and, moreover, instrumental support to be provided. Heading and actively participating in large programming projects, Ershov, with his inquisitive mind, could not help posing the question "How is it being done?" In the papers on the ALPHA and AIST systems A.P.Ershov has already proposed a number of organizational principles and agreements. The paper [33] was the first Ershov's work completely devoted to software engineering. This was the first Soviet paper on a new research direction and the Russian translation of the English term "software engineering" was also suggested by Ershov himself.

The main part of the paper [33] was concentrated on the technology of compilation proper. The general aspects of compiler construction: a structure of compilers, supporting facilities, a choice of implementation techniques, organization of debugging and documentation - all these questions were studied in the paper. Problems of automatic compiler construction and computer-aided documemtation were also discussed. The consideration of the problems of compiler technology within the general framework of the technology of large software system construction was an important feature of the paper. Practically complete survey of the works on software engineering and related problems together with their deep analysis was suggested. All this made the paper fundamental for the forthcoming Soviet researches in this direction.

In a number of other papers A.P.Ershov investigated and developed software engineering problems. He proposed a matrix- like organization of a team of programmers [34] and new specification of the stages of software development with special attention on compiler construction and succeeded in analyzing technological aspects of the ALPHA-6 project [38]. In the paper [61] written together with G.D.Chinin, the structure of programmers'team involved in production compiler construction was defined, the solution of the important problem of continuity and reusability of software was suggested, and the structure and informational support of the design process were considered. Being oriented to the technology of compilation, the paper provides also a number of interesting ideas concerning industrial development of other kinds of software.

From the methodological point of view, the report [86] presented at the meeting of Presidium of the USSR Academy of Sciences significantly contributed to the development of sofware engineering and formation of its conceptual basis. This report seemed to be not less important for the programming community than to the members of Presidium whom it was delivered to.

In computer science the attempts to turn a programming process into a provable one with program correctness being guaranteed or controlled at each step of program construction, have been undertaken for a long time. Being rather successful, these attempts could be invaluable in real-life programming technologies that necessarily required a reliability (a high level of correctness) of the program. Thus, for instance, Dijkstra's approach based on an ideal tendency to construct a program as an explicit inference from a mathematical statement of a problem is widely known. In spite of the ideal character and hard discipline being imposed on, this approach forms an ideological basis for a number of modern technologies which, in fact, is not always completely reached. But Ershov's approach is strictly connected with practical experience of programming and consists in extraction of the discipline from the practice rather than in its dictation. This approach seems to be more efficient as well as more broad.

A.P.Ershov defines and analyzes three styles of provable programming: synthesizing, assembling and concretizing ones. Synthesizing programming (including, in particular, the approach based on Dijkstra's ideas) is related to automatic, automatizable or manual manipulation with knowledge about a problem, application domain and mathematical ways of provable reasoning. In assembling programming a program is constructed from already existing and validated fragments. Concretizing programming is based on systematic construction of specialized programs from universal "scaffold" (mixed computation is a kind of such programming). Ershov, on the one hand, considers special features of each style and marks the differences which should be expressed in different supporting methods and tools and, on the other hand, he stresses that in the process of constructing real software these styles may and often must be combined. This provides an advanced methodological basis for future programming technologies.

The work on provable programming, having a large significance for software engineering, at the same time is closely related with such Ershov's works on general aspects of prpgramming as the paper [26] already mentioned above. In the 70's-80's these Ershov's papers clearly analyzed and estimated current situation in our country and abroad, formulated the problems and proposed possible ways of the solution. The names of the papers - "Multi-access computing center" [45], "A programming system for micro- and mini-computers" [59], "Some subjective remarks on actual problems of programming" [64], "Integrated software development: a formulation of the problem" [81], "Personal computer - an ancestor of mammals in the dinosaur world of multi-access computer center" [82], "An experiement of integral approach to the urgent problems of software" [89] - are very meaningful by themselves. Oriented to professional programmers, but easily understood by non-professionals, clearly written, well-structured and founded, these works greatly influenced readers allowing the current situation to be comprehended, reappraisal of values to be made and new ideas and research directions to be formulated.

The experience gained in designing architecture and software for large information processing systems was summarized in [45]; the presentation was based on ideas of the ES computer family prevailed at that time. In [59] a new phenomenon, namely, emergence of mini- and micro-computers was considered from the viewpoint of the prospective usage, the unlimited capabilities of new computing means were forecasted and new features specific for microcomputer software, i.e., integrated approach to joint design of hardware and software, specialization of software, orientation to non-professional users were outlined. An extreme importance of portability and compatibility of micro-computer software was also stressed and possible solutions of the problems were proposed in the paper.

A.P.Ershov was especially right when in [64] he did not agree with the thesis on the stabilization of the situation in programming which had been suggested by somebody else, and defined the points of active growth: new ideas in the programming languages, crystallization and formulation of the fundamental concepts of compilation, transition from data bases to knowledge bases (the latters were called "complex data bases" in the paper), design of supporting tools (later on, in Ada terms, referred to as programming environments). It should be noted that Ershov's prognosis proved to be completely correct. In the same paper a state-of-the-art in the theory of programming has been evaluated and the correlation with a practice has been established, which is essential to define future ways of theoretical computer science development. The problems of teaching programming and training of personnel were also discussed, but we shall turn to these questions below.

The above-mentioned papers had significant influence on evolution of programming, but now they have mainly historical interest, whereas the papers [81], [82], [89], [91], [100] remain actual. Rich contents and lapidary style of the papers make it hardly possible to retell the main ideas and concepts: it would certainly require much more time and space. Integrating kernel of these works is the necessity to develop an advanced infosphere of future informatizated society. A structure and specification of hardware that should be constructed in the USSR are estimated, main characteristics of the software are defined, and a wide spectrum of scientific problems crucial for design of the infosphere is outlined in the papers. The special features of computing means - microprocessors and personal computers (just personal computers rather than multi-access computing centers) - favoured the development of the infosphere are marked. The asserted thesis: "Personal computer is not just a little large computer, but a technical phenomenon requiring a free and uninfluenced and, at the same time, a global approach to development of methods and techniques to work with it" is undoubtly of a great importance.

It should be noted that the progress of programming requires not only new ideas, but also deep comprehension of both accumulated knowledge and process of programming evolution as well as division into periods firstly corresponding to computer generation change. The paper [89] has touched upon these questions, and in addition, the history of formation and evolution of computer science in the USSR has been considered in [44], [47], [48], [71], [75] (some papers have been written together with M.R.Shura-Bura).

The formation of a new branch of science needs its position among the other scientific disciplines to be defined. This is especially true for programming that in relatively short time became one of the most wide-spread intellectual professions. A.P.Ershov has performed great services for the computer science both in our country and in the world because in his papers he has revealed and explained a number of essential features inherent in programming as a science and human activity. Ershov's thoughts on this theme can be found eslewhere, but there exist several well-known papers, over and over translated and published, which are completely devoted to, so to say, "professionological" rather than to scientific or technological aspects of programming: what is a programming as a science and human activity, who is a programmer as a specialist in a particular intellectual work. "Aestetics and the human factors in programming" [31], "Programming, the second literacy" [71], "Two faces of programming" [77] should be referred to such papers also republished in this volume.

In the paper [31] dedicated to early departed talented programmer G.I.Kozhukhin, a constructive analysis of contradictions between the creative nature of programming labour and its industrial organisation being inevitable in any mass profession has been made. The main thesis of the paper is as follows: "Programming embodies rich, deep and novel aestetic principles on which the inner relationship of a programmer to his profession is based, those principles which give him both intellectual and vivid emotional satisfaction. This aestetic has roots in the creative nature of programming, in the difficulties which programming overcomes, and in the social significance of programming." There are many profound ideas and remarks commenting this thesis in the paper. The author considers programmers to be an intellectual elite and, at the same time, stresses the necessity to make the art of programming a public property.

Further development of this idea is presented in [71]. The title of this paper that has become a popular metaphor and used everywhere, including the highest tribunes, without any reference to the author, stresses the historical analogy between the literacy which is a common property in the modern society, and ability of programming (in a wide sense) which any member of computerized society should possess of. Ershov remarks that a programming is necessary for a contemporary man not only because that in the nearest future computers will spread in all directions of our life, but because everyday planning and foreseeing are now necessary. He says: "The second literacy is not only the ability to write computer instructions, but also the way to bring up a man who is resolute and prudent at the same time." In conclusion A.P.Ershov considers programming to be an essential component of modern learning and teaching.

In [77] A.P.Ershov proposed precise formulation of intuitive supposition that programming should not be considered in a uniform way. Two kinds of programming processes were distinguished: a programming for himself and programming for a customer, and in details described essential differences between those two kinds, or faces of programming. He proposed two terms: "a programmer-slave" and "a programmer-boss", respectively, and outlined profound differences in the styles, manners and criterions. Such constructive differentiation of programming is extremely important when designing real-life software technologies as well as when considering more general problems being expressed in ethics and aesthetics of programming. The pure scientific aspects of the paper were devoted to the model of programming environment for the programmer-boss on the base of the transformational machine.

These Ershov's papers, perfectly written and clearly manifested his intellectual power, intrinsic convinction and active attitude to life, were becoming outstanding events for programmers community. It is worth noting the influence exerted by these papers on ethics of programming, since the ethical problems of this kind of human activity, in the light of public and state significance of programming products now and in the future, seem to be very important.

A.P.Ershov has touched upon the problems of teaching programming in several above-mentioned papers, but at the first time he proposed a comprehensive program of computer education in the short paper [46] presented to International Conference on Reliable Software in 1975. In this paper he outlined a curriculum of high-school training of systems programmers that included fundamental grounding, profound study of professional disciplines and participation in real-life programming projects. In above-cited paper [64] a course in foundations of programming is considered as a heart of systems programmer education. This course proposes a successive presentation of conceptual, mathematical, linguistic, technological and organizational foundations of programming, which seems to be the best thought-out structure of such the course. It should be noted that these ideas were immediately related with the practical activities of A.P.Ershov: he was a professor of Novosibirsk State University, an organizer and first lecturer of the general course of programming at the Faculty of Mathematics and Mechanics of the university.

Later on A.P.Ershov turned his attenion to teaching programming and, in more broad terms, informatics in secondary schools. In the last ten years, having realized the principal importance of computer education in our country and worldwide, Ershov devoted much energy and that was called an ardour of a heart to this problem. He was one of the founders of the so called school informatics, an undisputed leader in Soviet school informatics and one of the chief specialists in this domain throughout the world.

In the paper [67] written together with G.A.Zvenigorodskij and Yu.A.Pervin he established the ways of development of the school informatics till the present time. Ershov was one of the authors and editors of the first Soviet school course in informatics aa well as teacher's guide [93], [96], [101], 103]. He also participated in preparing a new school course in informatics [107] appeared not long before his death.

Ershov developed the TV-course in programming for pupils, he led the design and development of educational programming systems as well as school-oriented software as a whole, acted as an organizer and expert and so on. Here his active attitude to life and high sense of civic responsibility were again revealed. Overcoming obstacles and difficulties that often were small-minded and exhausting, acting as a popularizer, educator and organizer, playing unexpected but necessary parts, Ershov devoted a lot of time and efforts to formation of school informatics.

It should be noted that scientific solutions proposed in Ershov's papers on school informatics [83], [95], [98], [106] were rigorously substantiated and related with the deeply comprehended essence of computer science. In [95], [98] Ershov proposed the structure of the course in informatics on the base of the following principles: separation and combination of "theoretical" and "operational" skills; anthropocentric approach (pupil's identification of himself with an executor of algorithms); appeal to day-to-day experience, etc. He stressed the importance of separate comprehension of the notion of algorithm and existence of the notation system to represent algorithms (algorithmic language) and proposed the scheme of algorithmization and solution of problems that seemed to be appropriate to initial training.

In the last paper [108] published in his lifetime Ershov thoroughly analyzed the problems of computer-aided learning and of teaching informatics in secondary schools and, that was very important, he considered the problems of school informatics in the wide context of computerization of the society and related them with the general problems of mathematical education. Shortly before his death Ershov prepared a draft version of the concept of computerization of education in the USSR that could be expected to become available to a reader. In the last years of his life Ershov devoted much efforts to publication of school encyclopeadia of computer science.

Ershov's works on man-machine communication in natural language are remarkable contributions into solution of the problem. In [13] for the first time in the Soviet and, may be, international literature Ershov made attempts to strictly formulate a number of problems of natural language interface with computer. His thoughts on this matter, together with researches carried out by linguist I.A.Mel'chuk and systems programmer A.S.Narin'yani, have led to the initiation of the RITA project [42]. It has been never implemented in full-scale, but a number of essential ideas of the RITA project may be found in linguistic processors and AI systems realized later: separation of intermediate level in semantic representation, lingware and software correlations in interactive systems, existence of components to interface with other (classic) programming systems, plurality of the values of interpretive functions (the latter was generalized by A.S.Narin'yani in the notion of subdefinite sets) and so on.

Later on Ershov tried to give a more constructive character to the problem of natural language communication by differentiating a very important subset of a language of "technical prose" from the natural language. In [63] he generally defined the technical prose as a linguistic carrier of human relations of production and noted that, in fact, it should be separated in a special linguistic category. A number of characteristics of the technical prose, namely, its inherent formalization and clearness of communicative functions, shows not only actual necessity but possibility to learn a computer to completely (Ershov stresses this word) comprehend and perceive the language of the technical prose. Further he considered essential features of the global model of complete language comprehension with respect to the technical prose.

In these studies and thoughts Ershov has gone beyond the limits of the proper computer science and formulated a fundamental problem of constructing a machine fund of Russian language. Noting its correlation with the solution of the problem of man-machine communicaation in a natural language, Ershov stressed very large scientific, cultural and applied significance of the fund. In the papers [94] and [104] he came back to the problem when it had been recognized and comprehended by linguists, and refined its formulation. It is interesting to note that Ershov's pioneering role in the statement of the problem has been superficially stressed by the fact that the citations from the paper [63] are used as elements of the cover design of the collection of papers [104] on the machine fund of Russian language printed in Nauka Publishing House in 1986.

This is one of examples of the key role of Ershov's wokrs in new areas of computer science and applications; some were given above, and the list may be continued.

One of the first approaches to intellectual system construction was proposed in the paper [15] written in joint with Academician G.I.Marchuk and presented to IFIP Congress in 1965. The joint (with V.P.Il'yin) paper [60] has essentially contributed into formation of problems of applied packages of programs in the USSR. Development of office automation as a new research direction was greatly influenced by the papers [85] and [87].

But Ershov's creative legacy is not limited by the books, reprints and papers in professional journals considered in the present volume. His papers in popular magazines and newspapers oriented to a wide audience as well as editor's prefaces to numerous monographs and collections of papers on programming were perfectly written, precisely formulated and excellently styled; they contain a plenty of valuable ideas, assertions and estimations almost equally interesting to professionals, to casual computer users and to people being rather far from computer science.

A.P.Ershov initiated and was at the head of a number of another projects not considered above. The high level language SETL programming system, the professional workstation MRAMOR and school-oriented programming system SHKOL'NITCA should be mentioned among them. Ershov did not take formal part in the projects, and his name was absent in the publication titles, but his ideas and discussions had stimulated influence on these works.

Ershov did independent researches and received important results in many different scientific areas. In principle, such diversity is characteristic of many programmers of the fifties and early sixties: it is possible to mention Soviet and foreign programmers who have interesting results in three-four different research areas. This is natural for the scientists standing at the origins of a new science and, unfortunately, impossible for those who enter the well-established science with a wide spectrum of researches. But even among the first programmers A.P.Ershov is exceptional in truly Lomonosov's breadth of interests and results.

The goal of this paper is not only to provide a survey of Ershov's works but to trace their evolution and to show the interrelations between them. It has been done in the text, but in order to pay a special attention to this aspect, a dependency graph of Ershov's papers is given at Fig.1, where arcs denote influence of the works (the papers devoted to general problems of computer science have certainly arisen under the influence of practically all the papers and, in turn, have influenced all of them).

Academician A.P.Ershov, an outstanding computer scientist, has greatly contributed to formation of informatics throughout the world and in many respects defined the current state of the art. He left the legacy that included approaches and methods to form essential part of the theory, methodology and modern practice of programming together with ideas and concepts to provide a basis for future investigations. And just the latter needs to be continued and evoled. They are: the concept of mixed computation, the notion of abstract computability, transformational approach, the formulation of scientific grounds of provable programming and, at last, an embedding idea of the lexicon of programming as a source of researches on constructing a future image of programming.

Time and space limitations allowed only brief overview of Ershov's ideas and results to be presented; the works theirselves should be read and used.

I.V.Pottosin
Ershov's Institute of Informatics Systems