Vera B Karpova

Leonid E Karpov

History of the Creation of BESM: The First Computer of S.A. Lebedev Institute of Precise Mechanics and Computer Engineering

Keywords: digital computer history, Darmstadt conference, Chinese computer

Some aspects of the history of the first Soviet computer development are described. The idea of this work was offered by Sergey Lebedev who formulated the principles, wrote a plan and suggested the structure of the computer which was named BESM -Fast Electronic Calculating Machine. Some new documents are presented -a working notebook with Lebedev's handwritten notes and a plan of a preliminary project draft development. BESM computer became the first in the long series of Soviet computers built under the leadership of Lebedev. It also was used as a prototype of the first Chinese computer built with the help of Soviet engineers.

Introduction

Institute of Precise Mechanics and Computer Engineering of the USSR Academy of Sciences (AS USSR) was established in 1948. At that time, two types of calculating devices (forerunners of modern digital electronic computers) were under development. They were the analog computers (mechanical or electronic but not digital) and the relay computers (digital but electromechanical, not electronic). Both the principles of computer design and computers themselves were introduced in the USSR by Sergey Lebedev (1902-74), shown in Figure 1. One could say that it was predetermined in the very beginning of his scientific activity. In 1933, Lebedev and Prof. Petr Zhdanov published their joint monograph "Stability of parallel functioning of electrical systems" [START_REF] Zhdanov | Stability of parallel functioning of electrical systems[END_REF]. His thesis for a doctoral degree was also devoted to this topic. Almost every project of Lebedev was built on enormous amount of mathematical calculations. Quite logically, that brought up the idea of some facility that could automate those routine operations. That idea was in his mind permanently.

To calculate parameters of the power transmission line from the river Volga to Moscow (several thousand miles) he managed to install highly automated device constructed of powerful coils and capacitors. That device mathematically modeled the real transmission line. Implementation of that model (in fact -a special calculating device) helped to perform all the calculations and produced a complete set of project documents for that unique line. This work was partly repeated by Lebedev during the World War II when he was engaged in design of stabilizing system for tank gun and an automatic targeting device for aircraft torpedo. Those devices could perform both basic arithmetic operations, and differentiation and integration; yet they were still analog devices. Nevertheless, there are evidences that Lebedev was interested in digital computing devices long before the war.

During 1948 and 1949 Lebedev formulated basic principles of electronic calculating machine architecture that were very similar to Janosh (John) von Neumann's principles (see Figure 2 In 1945, Lebedev was elected a member of the Ukraine Academy of Sciences (AS). There he started his work on the electronic calculating machine MESM (Russian abbreviation of "Model Electronnoy Stchetnoy Mashiny" -Model of Electronic Calculating Machine), in 1947 [5]. His actual intention was to begin researches with creating just an operating model but, considering the (post war) financial difficulties of the Academy, such "luxury" was impossible. However, MESM was quite operable computer. Design of storage device and other basic units (including general computer structure) was finished by the end of 1949. The first half of the 1950s was dedicated to manufacturing and adjusting of the machine components.

BESM and Lebedev's Technical Notes

On 16 March of 1950, Lebedev was appointed a director of the Laboratory No. 1 at the Moscow Institute of Precise Mechanics and Computer Engineering (now -IPMCE AS Russia). He continued his work with the Kiev MESM team in parallel. He was invited to the IPMCE by M.A. Lavrentev, than its director, who offered Lebedev the position of chief designer of a new computer called the BESM ("Bystrodeystvuyushchaya Electronnaya Stchetnaya Mashina" -Fast Electronic Calculating Machine). Soon after that MESM got the name of the Small Electronic Calculating Machine (in Russian -Malaya Electronnaya Stchetnaya Mashina): Again MESM, but no longer the "Model".

Lebedev brought his own project draft from Kiev, where he represented his view on the BESM architecture. One of the IPMCE best designers, Petr Golovistikov (shown in Figure 3), in [START_REF] Ryabov | From BESM to supercomputer. Notes on history of Lebedev's IPMCE by his colleagues[END_REF] wrote the following: "There exists a legend that Lebedev drew the whole BESM scheme on his "Kazbek" cigarette boxes or on separate paper sheets. That's wrong. His project description consisted of several thick notebooks. One could see there the detailed schemes and timing diagrams, including many different versions of different operations production." V.B. Karpova, collaborator of the IPMCE museum, identified among other IPMCE documents one of those notebooks (see Figure 4), which had been purchased in Kiev. The notebook consists of 100 grid sheets and is filled out in Lebedev's own hand. Among the titles that are in the notebook, we can see the following.

07.07.50:

External memory management (magnetic recording). 09.07.50:

Sending data from magnetic tape to the drum.

12.07.50:

To consider the model version, which includes common elements for instructions and numbers with one control switch that works on 4 clock pulses (not 3). Reading of this notebook helps us to follow the entire process of gradual (though very fast) understanding of the future computer structure. The first date marked in the notebook is 7 July 1950, when Lebedev was already working on both projectsbringing the MESM model to operational mode and developing the first "real" computer BESM. The last date (12 August 1950) is denoted on page 46 (see Figure 5). The subsequent notes are not dated. This means that it took only one month to fill the half of the notebook. Obviously the second half was filled out by the end of the summer of 1950. During this period, Lebedev developed basic units of the future computer and the algorithms of performing (producing as it is written in the notebook) of basic operations: addition, multiplication, division. It was necessary to calculate everything, even the length of magnetic tapes, intended to be external memory. The calculations like this may be seen on pages 6 and 7 (see Figure 6). As a result, the total tape length was estimated (approximately 200 meters) and the total time of data transfer from tape to drum (about 20 minutes). Moreover, here the remark is, "The time is acceptable ". Lebedev described all operations in details, at the same time he tried to estimate the time needed to perform those operations, trying to find answers to the basic questions of the starting period of every new computer design -is it worth implementing this or that operation, what would be the overall performance of the computer? For example, on page 47 (see Figure 5) after calculating the time of performing the operation of getting the value of 1/x (with precision not less than 2 -30 ) there is the result written: 1,5 milliseconds and the resolution reads: "Acceptable". Pages 84 and 85 are of special interest (see Figure 7). These two pages contain notes which are not about technical details (see Figures 8 and9): they are focused on organizational principles of the big computer project. The notes were definitely made during the preparation for a meeting with government authorities, who were the key persons for the new computer development. In the notes, we can see the concerns with which both development teams (Kiev team and Moscow team) encountered. The number of problems is not small but the conclusion is quiet simple -with a real help for the project, it is possible to build the computer by the second half of 1952. It is surprising but the terms were met. The list of note titles itself shows that Lebedev was doing his design work very carefully, trying to understand all the minutest details, many of which were discovered by the scientist for the first time. He also tried not to forget the importance of perfect project organization and planning. Lebedev himself wrote the BESM project plan, which was identified by V.B. Karpova. This plan was found among the documents in the IPMCE archive storage. Lebedev permanently controlled the progress (Figure 10). According to this plan, the preliminary project draft should have been finished by the end of the first quarter of 1951 (approximately the same time with the completion of MESM model). The plan designated three main work directions:

1. Cells principle schemes design.

2. Mathematical and experimental testing.

3. Preliminary project draft development. For each plan direction twenty basic items were defined, for which the dates and resources were fixed. Those basic works were the following:

From MESM to BESM

The plan was written not for Lebedev alone. By the spring of 1951, nearly fifty engineers have been working in the IPMCE Laboratory No 1. There were experienced employees such as L.A. Lubovitch and K.S. Nesloukhovsky on his team, as well as very young people and future academicians such as V.S. Bourtsev and V.A. Melnikov. The future IPMCE chief designers V.N. Laut and P.P. Golovistikov (who at 27 years of age was four years older than others were) and some other very successful IPMCE collaborators were also among them. Young colleagues of Lebedev who simultaneously monitored two fundamental projects of MESM and BESM, were very helpful for him and his work.

The changes can be seen on the plan. Sometimes the initial dates were shifted, but some of them were later restored. Still the preliminary project draft was completed just during the first quarter of 1951. It was very important for Lebedev to run his both projects without hindering each other. In the very beginning of 1951, the MESM presentation to the state commission took place. On the 21 st of April of 1951 the state commission on BESM project draft started its work. By the end of December 1951 MESM operated in its new design and in summer of 1952, the BESM manufacturing was completed. It was in operation by the autumn of 1952.

The work on BESM was not an easy one. The Special Design Bureau 245 was working on its own computer called the "Strela" (meaning "Arrow") in parallel and in certain circumstances only one computer (BESM or "Strela") could be chosen for serial production. The traces of scientific and technical competition can be seen in Lebedev's notebook (see page 84 of Figure 8). As a result, in April 1953 the State Commission with its chairman M.V. Keldysh approved the successful completion of BESM development. Since June 1953 Lebedev had started his work as the IPMCE director. Now this institute is named after him.

On 23 rd of October 1953 Lebedev was elected a member of the AS USSR within the Division of Physics and mathematics. He was the first academician with specialization "calculating devices". In 1954 he was rewarded by the USSR government highest award for creating the BESM computer and in 1956 he was given the USSR highest honorable title "Hero of Socialist Labour". Many problems earlier seemed to be unsolvable, because of the large amount of calculations, were easily solved using BESM. Lebedev himself liked the example of calculating the artillery shell flight trajectory. With BESM, this calculation was faster than the shell itself. The first BESM (Figure 11) was installed on the ground floor of the IPMCE building in Moscow. For the long time it was solving both scientific/theoretical and application problems (some of them were described in Lebedev's article in [3]). In particular, this computer was used for calculating the trajectory of the rocket that brought the USSR emblem to the Moon. After establishing of the Computing Centre at the AS USSR in 1955, the new task had to be performed by IPMCE: to prepare BESM computer for mass production. That was done by the end of 1957, when a factory in Ulyanovsk (a city on river Volga) started to manufacture the computer named BESM-2 (Figure 12). These computers were installed in almost all computing centers of the country. BESM-2 was used for calculating the data for the Earth satellites launching and for the first manned space ships.

BESM-2 was reproduced in China with the help of IPMCE team of engineers headed by Oleg Shcherbakov [2]. V.A. Melnikov also visited China. Five IPMCE collaborators were given state awards of the Chinese People's Republic. There are several pictures with IPMCE engineers and their Chinese colleagues in the IPMCE museum (Figures 13 and14).

In October 1955, Lebedev made his report at the International Conference for electronic calculating machines in Darmstadt (West Germany). That was a real sensation: BESM appeared to be the fastest computer in Europe. The future would have shown that all the computers of the BESM series (from the first BESM to BESM-6) were the best universal computers in Europe for the moment of their first appearance.

Getting such powerful instrument as BESM for complicated mathematical calculations did not stop development of new computers. By that time, Lebedev could clearly see the important role of computers in the state scientific and economic progress. By the moment of BESM's completion Lebedev had already thought over the principles and architecture of a new computer -M-20 that should have become the fastest computer in the world (its performance was about 20000 instructions per second). Many new logical operations were implemented in M-20 such as address modifications, operation combinations, and hardware loop support.

Besides general applications Lebedev made a great contribution in another computer implementation field -controlling objects in a real time mode. For his colleagues and the future IPMCE director V.S. Bourtsev (Figure 15) among them, Lebedev formulated the task of building small computers "Diana-1" and "Diana-2", that were intended for using in the systems of directing a fighter to its targets [1]. Yesterday's students soon became famous scientists who carried on the development of new computers. Academician V.S. Bourtsev started his carrier in IPMCE with designing the BESM instruction management unit. He continued with taking part in the design of a series of "Diana" computers, which were followed by the M-40, M-50, 5E92b, 5E51, 5E26 and the "Elbrus" series. The first work of (future) academician V.A. Melnikov started with BESM operation management unit, later he continued it with BESM-2, BESM-6, and the AS-6.

In the IPMCE museum, there is a model of one of the BESM-1 sections (Figure 16), which is a real monument to science and engineering. This model represents original units, cells and separate fragments of BESM-1 and BESM-2 that remained intact since the beginning of 1950s.

The value of BESM computer for Russian and world computer engineering can hardly be overestimated. Many of that, what was first tested in process of this computer design, is an ordinary ("classical") thing now [START_REF]Development of the methods and auxiliary devices for converting numbers from decimal to binary system and backward[END_REF]6,[START_REF]Development of the auxiliary units for solving the system of linear equations. 8. Development of the fast internal memory unit[END_REF].

  ), who described his conception in a secret report in 1945. This work became known in the Soviet Union much later; all of Lebedev's work (both theoretical and practical) was carried on independently. Lebedev emphasised the following requirements: o A computers must have arithmetic device, memory, control and input/output units; o Both the program written in machine codes and the numbers should be stored in the same memory; o Binary notation should be used for representation numbers and instructions; o All calculations should be performed automatically according to the -stored in memory-program; o Logical operations should be performed in addition to arithmetic operations; o Computer memory should have a hierarchic structure.

Fig. 1 .Fig. 2 .

 12 Fig. 1. S.А. Lebedev (1950s) Fig. 2. Janosh (John) von Neumann

Fig. 3 .Fig. 4 .

 34 Fig. 3. Petr P. Golovistikov (the 1950s). Fig. 4. Cover of Lebedev's working notebook.

Fig. 5 .

 5 Fig. 5. Pages 46 and 47 of Lebedev's working notebook.

Fig. 6 .

 6 Fig. 6. Pages 6 and 7 of Lebedev's working notebook.

Fig. 7 .

 7 Fig. 7. Pages 84 and 85 of Lebedev's working notebook.

Fig. 8 .

 8 Fig. 8. Lebedev's working notebook fragment devoted to the organizational problems of two development teams.

Fig. 9 .

 9 Fig. 9. Lebedev's working notebook fragment devoted to the BESM project expectations.

Fig. 10 .

 10 Fig. 10. BESM preliminary project draft plan handwritten by Lebedev in 1950.

Fig. 11 .

 11 Fig. 11. BESM-1 computer on the ground floor of IPMCE building in Moscow.

Fig. 12 .

 12 Fig. 12. Serial version of the BESM computer that was named BESM-2.

Fig. 13 .

 13 Fig. 13. O.K. Shcherbakov (to the right) and A.A. Pavlikov together with the member of Chinese group in IPMCE.

Fig. 14 .

 14 Fig. 14. V.A. Melnikov (to the right) during his business trip to China.

Fig. 15 .

 15 Fig. 15. V.S. Bourtsev.

Fig. 16 .

 16 Fig. 16. Model of BESM-1 computer in the IPMCE history museum.


B M Malashevich

D B Malashevich

Keywords: Centre of microelectronics, Zelenograd, (miniature) radioset "Micro", IC, "Tropa"

This article deals with appearance of microelectronics in the USSR and establishing of its innovation centre in Zelenograd, Moscow. Prerequisites for creation of the microelectronics, measures on the development of the scientific-research centre are considered and the acting persons presented. Structure of the centre is described as a complex research and development corporation with complete set of functions. Its enterprises are displayed as well as their specialization and their first achievements. The technical level of the microelectronics centre production released in the first years of work is evaluated as corresponding to the world's manufacturing level; however, some reasons for lagging behind world leaders, beginning in the following period, are also mentioned.

Introduction

During the last half of the last century, the technology of assembly of the radioelectronic equipment (REE) from discrete elements has settled the possibility. The world had come to the sharpest REE crisis and radical measures were required. In the USSR the electronic industry was an independent branch of the State Committee on electronic techniques (abbreviated GKET in Russian), then transformed the Ministry of electronic industry (MEP), under the ministry of A.I. Shokin.

Preconditions

By this time and in the USSR and abroad, preconditions were already ripened for the creation of semiconductors and hybrid integrated circuits (IC). Integrated technology had been industrially mastered for semiconductor transistors, thick-film, and thin-film ceramic printed circuit-boards. The question was only: which one would be the first will be lit up with a pleasant IC idea. The first that appeared were Jack Kilby from Texas Instruments (TI) and Robert Noyce from Fairchild Semiconductor in the USA. In 1958, they had made the first IC: J. Kilby on germanium and R. Noyce on silicon. Juri Osokin of the Riga Plant of Semiconductor Instrumentation was the third one to begin production and supplies of the semiconductors ICs "R12-2" in 1962 (Figure 1).

Simultaneously with them appeared a hybrid IC. Both American and our experts predicted the most intensive development of the hybrid ICs, however, claiming that semiconductor ICs would dominate the market only by 1980.

Figure 1. The three first ICs: of Jack Kilby, of Robert Neuse, and of Juri Osokin (an IC crystal with a germanium plate fragment in the background)

Using germanium for ICs was not promising. It has quickly understood both at TI and at Pulsar that the direction was toward silicon. Between 1959 and1960, they began to work at Pulsar on creation of planar technology of silicon devices. By the end of 1961 at Pulsar, they generated a department of microelectronics whose chief was B.V. Malin.

Trailblazers

In the USSR, they formed two groups of trailblazers in the Soviet microelectronics: at GKET and at NPO "Almaz" (then "KB-1"). Since first half of the 1950s the Almaz chief engineer F.V. Lukin had organized active works on microminiaturization REE on the then available element base. However, by the end of 1950s, it became clear, that more radical methods were needed. Here then F.V. Lukin also had charged A.A. Kolosov to one of the most active, competent and interested in the decision of this problem of specialists in the Almaz. They freely knew three foreign languages thoroughly to study approaches to microminiaturization on foreign and domestic sources.

The results of this work were generalized in 1960 in A.A. Kolosov's small monographic called Questions of Microelectronics, which became the textbook for many specialists. In this work, the author has perfectly proved the necessity and timeliness of the beginning of large-scale works on research of the problems connected with the creation of integrated circuits; he stated new principles of REE creation. In 1960, F.V. Lukin had charged А.А. Kolosov to create the very first laboratory in the USSR on microelectronics. The laboratory started active work involving numerous scientific research institutes and universities as counterparts. Ideas of microelectronics had started to expand in the country. So, the non-suspecting F.V. Lukin, had started to prepare for a theoretical reserve and a staff for the Center of microelectronics in Zelenograd, which would be established in three years. See Figure 2 for a partial view of the center.

During the same period, A.I. Shokin's assembled a group of specialists at Pulsar and GKET to seek ways of generating output from the REE crisis. He had already concluded about the necessity of the creation and development of a new branch sectormicroelectronics. The branch sector, (i.e. systems of scientific research institutes (abbreviated NII in Russian), would design offices (KB), and develop skilled and serial factories distributed all over the country; they would solve all special problems on the creation and duplication of products of microelectronics. In 1959 he directed specialists to the USA to train and study planar silicon technology. When A.A. Kolosov had addressed K.I. Martjushchov's deputy, A.I. Shokin, with the results of the works and the offer on microelectronics, he received full understanding. At once, he had estimated the initiative and had suggested to organize a conference to gather the necessary heads. Such conference took place in the end 1961 in Leningrad under K.I. Martjushov's presidency. With the basic report A.A. Kolosov, with the supporting report on systems of memory, F.G. Staros, director SKB-2 in Leningrad, acted. Then A.A. Kolosov and K.I. Martjushov invited A.I. Shokin to discuss the problem, they came to the conclusion about the necessity of the creation of the uniform Center of microelectronics (CM).

The CM idea consisted in the formation of an innovative center for microelectronics. It would be locally placed functionally with a full complex of scientific research institutes with the experimental plants, solving all specific problems of creation and application of IC. For CM special materials, it should develop the technological, control, and measuring equipment for direct IC, based on REE. All this should be fulfilled on experimental plants and be transferred for mass duplicating to serial factories. In the USSR, they were already able to create the research-and-production centers and A.I. Shokin had the relevant experience.

The Decree

CM allocation had to be small and independent; the location city should be close to Moscow and it should create a scientific research institute and experimental plants. They found the place for such a city. In 1958, the Krjukovo railway station near Moscow was ideal for light industry construction of the "Sputnik" settlement (it has received the name «Zelenograd» in 1963).

By this time, there were obvious disproportions: provision for mass habitation was under construction and practically nothing had been made on the industrial building. However, expansion of works on creation CM needed the decree of the Central Committee of the CPSU and SM of the USSR; its output needed the consent of the first secretary of the Central Committee of the CPSU and chairman of SM of the USSR, N.S. Khrushchev. A.I. Shokin had begun preparations. The main base for preparation for the Decree the CM creation and all accompanying documents, posters, and exhibits became Pulsar. Supervising the preparation was V.N. Malin (chief of the general department of the central committee of the CPSU), I.D. Serbin (chief of the defensive department of the central committee of the CPSU), and L.V. Smirnov (chairman of the military-industrial commission).

In the beginning of 1962, A.I. Shokin had achieved N.S. Krushchev's consent to carry out a small exhibition with a report during a break of session of presidium of the central committee of the CPSU. Hence, N.S. Khrushchev had already apprehended the idea and straight off did not reject it. Action took place, and N.S. Khrushchev had agreed on the further consideration of the offer. It has not simply agreed, but, similarly, had allocated for itself the problem of microelectronics and it was important for the nation.

Soon, in March of 1962, at the annual viewing of the architectural projects in Red hall of Mossoviet, they reported about serious disproportions in building of "Sputnik", N.S. Khrushchev said:

"It is necessary to discuss about microelectronics". Apparently, he had discussed the issue with A.I. Shokin and F.G. Staros soon arrived at "Sputnik" for reconnaissance. In parallel with the preparation of the decree, work on the creation of a technology hybrid (in the SKB-2) and planar (in the Pulsar) integrated circuits were systematically developed.

For the final decision the situation in which would refer N.S. Khrushchev, microelectronics and demonstration of its advantages on clear was necessary to it an example. A.I. Shokin has created such situation. On 4 May of 1962 in Leningrad, the meeting with N.S. Khrushchev's participation on problems of ship construction was planned, and one of the major problems was onboard electronics. A.I. Shokin has applied all organizational experience and manager art, has involved old connection, and overlapping of the necessary events at last took place in time and space. Having arranged Khruschev's visit in SKB-2 by Staros before meeting, Alexander Ivanovich successfully used three trumps which in the given situation were directed at F.G. Staros: it KB was in Leningrad; at it was than to surprise; N.S. Khruschev was a bit attracted to F.G. Staros's since he accepted some participation in arrangement of its Russian destiny.

By the end of the 1990s in the American Russian-speaking magazine called The Problem of Eastern Europe appeared an article by M. Kuchmet titled "Participation of Americans in the Soviet microelectronics". The article affirmed that the Soviet microelectronics industry and its Center in Zelenograd's was created exclusively owing to the initiative, diligence and intelligence of two American engineers Alfred Sarant (in the USSR known as Phillip Georgievich Staros) and Joel Barr (known as Joseph Veniaminovich Berg). By 1950, they had emigrated from the USA to Czechoslovakia, and by 1955, they moved to the USSR where they headed a small KB in Leningrad, where they were subordinated to the GKET. This article contradicted a reality that had started numerous publications and that had distorted the historical representation of CM's creation.

Because of F.G. Starosa's roles (I.V. Berg had no independent value), we shall dwell a bit more on this story. In SKB-2 they prepared F.G. Staros's then model samples of a control computer "UM-NH" and a tiny radio receiver. They were constructed based on tiny and non-packaged elements; the senior chiefs were amazed by the small sizes. The visit was well organized. Almost month of vigorous spadework proceeded. One day prior to A.I. Shokin's visit they led a rehearsal with Staros, which should be explanatory. The visit is well daring: "UM-NH" and a radio receiver had made a necessary impression upon N.S. Khruschev. At the same place, A.I. Shokin has reported the project of the Decree on creation CM in "Sputnik" as one approved in whole by Khruschev. After intensive coordination, on 8 August of 1962, they signed the Decree of the Central Committee of the CPSU and SM of the USSR. See Figure 3.

As it is usual in similar cases, it was the conceptual Decree, the first in a turn that would follow behind. In it, they legalized that CM was to be in "Sputnik" and that henceforth, the problem of the creation and development of a homemade microelectronics plant has found the character of a national problem.

The general provisions of the concept of construction CM have been certain:  Complex character CM with the organization of all cores of necessary scientific research institutes and experimental plants for designing and manufacturing IC is certain,  CM the status of parent organization in the country on microelectronics with problems is given:  Maintenance of designing and pilot production IC on a world technological level in interests of defense of the country and a national economy;  Maintenance of a perspective scientific reserve;  Development of principles of designing of the radio-electronic equipment and the computer on the basis of microelectronics, the organization of their manufacture, transfer of this experience to the corresponding organizations of the country;  Unification IC, conditions of their application in the equipment at the enterprises of the country;  A professional training, including specialists of the top skills. The Decree made certain that an initial variant of structure of the CM enterprises. It had five new scientific research institutes with three experimental plants. They included the scientific research institute of theoretical bases of microelectronics, the scientific research institute of microcircuitry, the scientific research institute of technology of microelectronics, the scientific research institute of mechanical engineering, and the scientific research institute of special materials. Additionally, they were given corresponding tasks on their creation.

It is important to note once again that the creation of CM was not an isolated action; it was a part of larger program of creation new branch sectormicroelectronics and A.I. Shokin was its initiator and its organizer of realization. In various regions of the country (Moscow, Leningrad, Kiev, Minsk, Voronezh, Riga, Vilnius, Novosibirsk, Baku and other places) saw the beginning of alterations of available GKET enterprise or the creation of new scientific research institutes with experimental plants. In addition, serial factories with KB emerged for design and mass production the ICs, special materials, and technological and control-measuring equipment. Thus, CM was only a part of a huge iceberga main peak, but only a part of it.

It is necessary to consider as special conditions of creation and development of domestic microelectronics. The electronic industry of the countries of the Europe, the USA, Japan what remained rigid was a competition between firms as were the participants of a wide international cooperation. Our microelectronics had been completely excluded from it. The USA had created the special international seventeen-country "Coordinating Committee of East-West Trade Policy" (COCOM) that supervised all scientific, technical, trade, and economic mutual relations from the USSR. The COCOM had developed a position paper of 250 pages across Soviet progress. It was impossible to sell not only high technologies and the products belonged to area of any high technology, microelectronics, and computers, but also other technological devices such as measuring equipment, materials, and precision machines. Consequently, in the Soviet electronic industry, it was necessary to do make everything ourselves. Certainly, special services partially managed to punch a wall on COCOM surrounding us and in a roundabout way to extract some products, documentation, materials, and equipment. However, all that was extracted was in scanty quantities and only to look and feel. It was necessary to design all this and to duplicate it in sufficient volume. Sometimes, the received samples were copied, but an exact copy to make it was impossible because of differences in materials, technologies, and equipment. Sometimes they did functional analogues; sometimes they completely did their own development. Nevertheless, they always developed and duplicated everything themselves. Besides in 1963 it had transferred us four designed it KB vacuum disposition system for mark thin-film (the first in the country). We at once began to master technology, and owing to it to 1964, there were the first microelectronic products. And if waited, while will construct our institute of mechanical engineering, we would lose two to three years".

The Center of Microelectronics

F.G. Staros with CM shared both the ideas and a reserve. In NII MP, the idea of the micro-receiver was already based on microelectronic technology and it had been realized anew. Angstrem issued products designed in Leningrad such as the block of memory on ferrite plates with many openings of a "Cub-2", shown in Figure 4. In NII TT, the idea was more technological; a reliable variant of "Cub-3" was creatively advanced and designed. Probably, there were also other examples. F.G. Staros had really brought a certain contribution to the preparation of the creation of NC. He was one of the active members of the large command and this command stood at the forefront, though not the first.

On 29 January of 1963, the vice-president of the GKET approached F.V. Lukin and on 8 February of 1963, he became director of CM. Its deputy for science had appointed F.G. Staros, still remaining the chief at the Leningrad KB. However, F.G. Staros had ambitions and plans for the post of director of CM. Not having received his expected appointment, he had taken offence and had actually withdrawn from performance of functions of the deputy director. This caused harm to that business on which the organization had placed many forces. I.N. Bukreev tells about it in the following:

"The joke is recollected: «Have decided to collect those who on the first Saturday carrying a log from V.I. Lenin. Five thousand persons had responded nearby. Actually, there were only five. The same occurs now: many, "close known" Staros's, tell pull the long bow about its invaluable contribution to becoming Zelenograd microelectronics, initiating unhealthy interest to the person of this man. … Itself Staros in Zelenograd never worked. I to it equipped a cabinet in "boarding school" (in 1-st microdistrict). But there was it here only 3-4 times at some o'clock. … Actually, there was Staros in Zelenograd only till the summer a 1963. During this period from the first directors to it I contacted only. … Lukin becomes director of a under construction Center of microelectronics and Staros's appoint it deputy on a science. … Certainly, it wished to supervise over the Center. Well, does not happen. After purpose Lukin it more here did not appear."

Director of NII TT of V.S. Sergeev is even more categorical:

"About Staros and Berg. I revolted when they named "father" of microelectronics and Zelenograd. From the point of view of techniques, their influence was zero. By the way, in America Staros in microelectronics was not engaged."

These are direct certificates of two direct participants of theevents, the first directors of the first undertakings. One should not forget that Alfred Sarrant (in the USSR -F.G. Staros) stopped working as an electrical engineer in 1946, i.e. a year beforecreation of the first transistor in 1947 (the first informationabout it appeared in 1948), and in 1950 (before creation of the firstintegrated circuit in 1958) left the USA emigrating to Europe.

The heads created CM present on work just not twenty-four hours straight. Their drivers, who are not maintaining such mode of work that varied with frightening frequency. In reality, F.G. Staros's busy season happened in Zelenograd where he ignored weekly conferences. That is, in the fray of heavy daily work to creation the electronic industry, which demanded not only knowledge but also selflessness, he practically never participated. As a result, in 1964 there is an order on removing F.G. Staros's from the deputy director position at CM. Figure 5 shows the founders of the center.

The First Results

Soon, CM had started the creation of essential new production. In May of 1963 at NII TM they designed the first samples of vacuum deposition equipment. In the second half of 1963 at NII MP, the first results on thin-film technology were already developed and they designed the radio receiver «Micro». Its first model was the direct strengthening receiver and the second was the superhetrodyne. In 1964 when I.N. Bukreev brought this receiver to the USA at the congress of radio engineers, it made a world sensation! Photos and statements appeared in newspapers: How could the USSR overtake us? The «Micro» was sold for currency in France and England. Khruschev took them with himself abroad as souvenirs and gave them to G. Nasser and Queen Elizabeth.

The radio receiver «Micro» (Figure 6) used thin-film technology; it was first time in the country that they used batch production of microelectronics. In the second half of 1963 in NII MP the receiver was designed and its batch production began in 1964 at Angstrem's, where eighty thousand pieces were transferred to the MRP serial factory in Minsk. Up to the middle of the 1970s, one could buy this microreceiver in shops of the USSR and France. By 1964, NII TT started developing a series of thick-film HIC "Tropa"; its designer was A.K. Katman. Technical materials and literature in this area did not exist; there were only photos of the microcircuits that were issued by the firm IBM. All work began with nothing. They designed everything: the circuitry, the constructions, materials, technologies, and equipment.

By 1965 in Zelenograd, the Micron had begun to release the first semiconductor IC "Irtysh", designed by A.P. Golubev in NII ME based on the planar technology created in the Pulsar and put on the Micron. See Figures 7 and8 The results of many years of NC work did not look bad at a level of world microelectronics. Its first productradio receiver «Micro», already had no equal the world. The first hybrid IC corresponded to a world level. By the way, the first-ever IC, flown the Moon (in 1969) and returned to the Earth, were Angstrem's "Tropas". In semiconductor IC, the USSR noticeably lagged behind, but would soon catch up with world leaders. In the 1970s, the most successful semiconductor company in the world was Intel. Intel issued the dynamic RAM in a capacity of 4К bits in 1974 and Angstrem issued the same in 1975. Accordingly, it issued 16К bits in 1977 and in the beginning of 1978; in 1979 both firms have issued on the market 64К-bit modules practically simultaneously. The similar situation existed at NII ME. In the beginning of the 1970s, the director of NII ME, K.A.Valiev, went to the USA to Motorola to show them the IC series 500 (analogous to the МС10000). Having investigated samples, experts of firm ascertained, that at identity of topology, IC series 500 had a higher speed than their designs and they were compelled to ascertain that the USSR technology was better. There are a number of other similar examples. See Figure 9.

The culmination of this competition began in 1979 when at NII TT they designed a single-crystal 16-digit computer, K1801VE1, with an "Electronics NC" architecture (in present terminologythe microcontroller). According to conclusion of the State Commission inspecting the project at that time, a computer of such level (with a 16-bit arithmetic-logical unit) did not have foreign analogues. As a whole during the period from 1964 to 1980, the backlog of development at NC on various types of IC comparisons with the maximum world achievements changed between zero and three years. Sometimes they pulled forward. Nevertheless, approximately the same dynamics existed and at leading foreign firms, they lagged behind their competitors and then advanced them a little. That is, it is possible to confirm that development of microelectronics at the NC in Zelenograd as a whole corresponded to a world level during those years.

However, regarding the volume of production of integrated circuits, the branch as a whole lagged considerably behind the foreign level; the means did not suffice for the development of capacities of serial factories (and they in microelectronics were very dear) in the country. As a result, the loading on the experimental NC plants had sharply increased, specifically by a batch production of integrated circuits. This was the beginning of a fatal decline; it affected the further prospects of developing microelectronics. Opportunities to improve experimental plants for new materials, processes, technological routes, equipment, and products became sharply limited. Because of this and a number of other reasons, by approximately 1980 the progressing backlog of the Soviet microelectronics compared to a foreign level had begun. The rest is history.

Figure 2 .

 2 Figure 2. Two of three buildings, from its beginning; Soviet Center of Microelectronics in Zelenograd

Figure 3 .

 3 Figure 3. Initiators creation Soviets microelectronics: Alexander Ivanovich Shokin, Feodor Viktorovich Lukin, Andrey Alexandrovich Kolosov, Boris Vladimirovich Malin, Fillip Georgievich Staros

  Soon after the release of the Decree, A.I. Shokin's command had started the creation of the CM (later the Centre of science -NC). The CM Decree had been given the right to employ specialists from any part of the USSR. Professionals and a scientific reserve in microelectronics, owing to the preliminary actions of A.I. Shokin, F.V. Lukin, and A.A. Kolosov who were already available in the country at the moment of signing of the Decree.The formation of scientific research institute with experimental plants had begun. In 1962 began the scientific research institute of microdevices (NII MP) with a factory "Component" and Scientific research institute of precise machine building (NII TM) with "Elion". In 1963 began the scientific research institute of precise technologies (NII TT) with "Angstrem" and the scientific research institute of materiology (NII MV) with "Elma". In 1964 began the scientific research institute of molecular electronics (NII ME) with "Micron" and the scientific research institute of physical problems (NII FP). In 1965 began the Moscow institute of electronic technics (MIET) with "Proton" (in 1972). In 1968 began the central bureau on application of integrated microcircuits (CBPIMS). In 1969 began the specialized computer center (SVC) with "Logic" (in 1975). By the beginning of 1971 at NC in Zelenograd 12.8 thousand people were working. In 1976 based on the NC the country created the "Centre of science" with thirty-nine enterprises in different cities of the country that employed almost eighty thousand people. The uniform organization at CM was not repeated; its enterprises submitted to the fourth central board of the GKET. The first had been organized by NII MP and NII TM. The appointed directors were I.N. Bukreev and E.H. Ivanov typed experts and organized work of scientific research institute while on the time premises. Workers of the Central board and GKET helped them. F.G. Staros also helped in part. Here is the recollection of I.N. Bukreev: "Staros actively helped me. Specialists of NII MT trained at it in Leningrad.

Figure 4 .

 4 Figure 4. "Cub-2" -The module RON in capacity of 16 19-digit words, "Cub-2" in capacity of 128 19-digit words, Between them a coin 1 copeck 2003) The size of the module 32х34х4,125 mm. The size of the block: 128х19 bats -32х34х42 mm 256х19 bats -32х34х42 mm Such a Cub flied around of the Moon.

Figure 5 .

 5 Figure 5. Founders of the Center of microelectronics in Zelenograd at an input in NII TT and a factory «Angstrem». From left to right: L.S. Garba (director of «Elma» at NII MV), B.V. Tarabrin (director of CB PIMS), K.A. Valiev (director of NII ME), A.J. Malinin (director of NII MV), V.F. Lukin (director НЦ), D.I. Juditsky (director SVC), A.K. Katman (chief engineer of NII TT), V.V. Savin (director of NII TM), G.V. Bechin (director of «Angstrem» at NII TT), V.S. Sergeev (director of NII TT).

Figure 6 .

 6 Figure 6. The product of microelectronics first in the USSRradio receiver «Micro»It is produced on the basis of thin-film hybrid technology, a thin-film payment on a photo on the right with double increase. The size of the receiver 43х30х7,5 mm (without acting controls). The broadcast through phone for a hearing aid, inserted in an ear (the third at the left) was listened.

  .

Figure 7 .

 7 Figure 7. First series IC in the USSR, "Tropa", thick-film, a top number, "Posol", thin-film, the bottom number. (At the left and in the centerin the double size, on the rightin full size).

Figure 8 .

 8 Figure 8. The first in CM semiconductor IC "Irtysh". Photo of topology of a crystal.

Figure 9 .

 9 Figure 9. IC "Tropa" first-ever send in 1969 in a free space, have flown about the Moon and have returned to the Earth.Fragment of a board of computer "Argon". Part IC is dismantled for research of results of long influence on them of a free space.


Mikhail Bulyonkov
email: mike@iis.nsk.su

Mixed Computation in Novosibirsk 

Keywords: Mixed computation, partial evaluation, program specialization

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Futamura Projections -Andrei Ershov

Andrei Petrovich Ershov came to the idea of mixed computation from his work in compiler construction, program optimization, and transformation. In his first works on the subject, mixed computation processor, or partial evaluator was defined as program processor that has as its input some program representation and part of its input data, and produces as its output transformed program, partial result, and the data demanding further processing.

Next thing Ershov noticed was the fact that compiler's behavior is very similar to that of mixed computation: operations of the compiled program analysis alternate with object code generation. These considerations culminated in discovery of relationships between program interpretation and its translation into object code. For this purpose, they interpreted a partial evaluator in a more restricted sensewithout intermediate data and partial result: mix(p, x) = p x such that p(x, y) = p x (y)

Let us call the last equality a mixed computation equation. Let int be interpreter of some language L, written in the language whose programs can be processed by mix. Then int(p, d) = p(d) for each program p in L and its data d. Then, substituting int in the mixed computation equation, we get int(p, d) = int p (d) whence int p (d) = p(d) Thus, programs int p and p are equivalent, but note that we write them in different languages: p in L, and int p in the interpreter language. In other words, mixed computation applied to interpreter implements compilation, and int p is an object code for p.

We can obtain very interesting relations under the assumption that partial evaluator possesses the property of self-applicability. For this to occur, we must write it in the same language as the one for which it is intended. We leave to the reader the proof of the following relations: mix int (p) = int p and mix mix (int) = mix int Thus, mix int transforms a program into object code and hence implements the function of compiler, while mix mix transforms the language semantics, defined in the form of interpreter, into compiler and therefore appears to be compilers generator.

Anybody who had a faintest notion of compilers and interpreters and who became familiar with these relations, at first could not believe in them and looked for some hanky-panky trick. They then became delighted with the beauty, clarity, and depth of their meaning 1 . Today I can clearly imagine Ershov's disappointment at having discovered a paper by Japanese researcher Yoshihiko Futamura, who had published these relations back in 1971. Andrei Petrovich called the independently found relations Futamura projections, although the last of the three was not present in Futamura's paper; it serves as an excellent example of professional ethics.

The main approaches to implementing mixed computations appeared as early as the first works on the subject. They include:

1. Partial evaluation refers to the immediate execution of all instructions from the source program that depend only on available data. We reduced the remaining instructions and placed them into a residual program.

2. Generating extension splits the process of residual program construction into two stages. First, we classify all actions of a program as -available‖ or -delayed‖. Then we generate a program that, given as input the available data of the source program, becomes the residual program. People recognized the importance of the static classification of a program's actions as available and delayed much later; they called it binding-time analysis, or BTA.

3. Transformational approach refers to obtaining the residual program from the source by application of a sequence of so-called reducing transformations such as constant propagation, reduction of expressions and conditionals with constant conditions, loop unfolding, and the elimination of unused computations.

We recognized rather quickly the main problems of mixed computationa problem of delayed control and related problem of mixed computation termination. In his first works on mixed computation, Ershov neatly disguised these problems, which he acknowledged in a reply to my pointed questions. It had taken years of research and experiments to arrive to a practical implementation from a sketchy idea. However, back then the main goal was to introduce the computer science community to the idea of mixed computation potential and Ershov dealt with it brilliantly. Dozens of times, at various conferences and seminars, in papers and informal talks he spoke about Futamura projections and mixed computation, forming a new school in system programming. His large comprehensive article with many color illustrations that appeared in the popularscientific journal -V mire nauki‖2 [Ersh84] serves as spectacular example of this activity. The works in the mixed computation field brought Andrei Ershov the prestigious Krylov Prize of the USSR Academy of Sciences.

Algebra of Mixed Computation -Vladimir Itkin

A rather different background and approach to the study of mixed computation appears in the works of Vladimir Itkin. He gave an impression of a withdrawn, cloistered scientist who valued strictness of proof and theoretical power of result much more that its practical applicability -a typical example of a -theorist‖3 . He wrote several of his first papers in co-authorship with Ershov, but subsequently their co-operation became less close. The motive was Ershov's words that in their joint papers, the general idea was his, while Itkin worked over the technical details. Even subsequent clarificationsonly the general idea and all technical detailsapparently were not enough for Vladimir. Although he worked independently, he obtained results and gave a solid theoretical and conceptual basis to other researchers.

The starting point of Itkin's research was a theory of program schemata, oriented in the first place to imperative operator programs over common memory. The most actively used notion was that of explicatoran operator ensuring the required state of some part of program memory. In the simplest case, an explicator is expressed by assignment of given values to variables.

The role of explicators was twofold: on the one hand, being ordinary operators, they were part of the program, so at any moment, the mixed computation process could terminate and the current program declared the residual one. On the other hand, explicators were like current computation points. Vladimir Itkin analyzed and substantiated different patterns of mixed computation process (e.g. end-to-end, dotted, polyvariant). A substantial part of the process was the manipulation with explicators such as the -application‖ of program statements and merging. Itkin managed to abstract these operations by introducing the set of axioms they have to satisfy. It has lead to the so-called algebra of mixed computations [START_REF] Itkin | An Algebra and Axiomatization System of Mixed Computation, Partial Evaluation and Mixed Computation[END_REF]. Vladimir Itkin's last works were of a philosophical nature. Partial evaluation interested him as a fundamental process of a transition from the general to the special. He died tragically in 1991 when he froze to death on his way to church.

Parser Specialization -Boris Ostrovsky

To make the idea of mixed computation more viable, it was essential to find some practical application for it. Ershov proposed this issue to his post-graduate student Boris Ostrovsky as a subject of his Ph.D. thesis. His task was to transform automatically a universal parser for some class of grammars into specialized grammar-oriented parser [START_REF] Ostrovsky | Controlled mixed computation and its application to systematic generation of language-oriented parsers[END_REF]. It was clear that parser specialization, although being of independent value, was only the first step on the way to Futamura projections implementation, since we can consider a universal parser as an interpreter, a grammar as an interpreted program, and the input string as its data. From this point of view, only the first projection was at issue and the task of achieving partial evaluator's self-applicability was out of question.

Ostrovsky based his partial evaluator on the transformation approach. To be more exact, it was not a proper partial evaluator, but rather a transformation machine with an ad hoc set of transformations. The process of transformations application was similar to the process of Markov's normal algorithms execution. Transformation markers labeled the text of a universal parser. Usually the process started with a single marker of initial transformation placed before the first program instruction. A non-deterministic iteration of marker selection and application of its transformation followed to the construct labeled by it. The transformation resulted in a program modification and a placement of new markers. The process repeated until no marker remained.

For each universal parser one had to develop the set of transformations individually. In fact, there was a separate partial evaluator for each class of grammars. However, even this approach was technologically justified. First, the basic transformation set was reusable, which guaranteed the ad hoc parser correctness. Second, they could use a single partial evaluator, after being -tuned‖ once, for a number of grammars. Third, the system supported sophisticated tools for grammar transformation such as regular part extraction and postprocessing tools applied to residual programs.

The mixed computation system developed by Ostrovsky was one of the most -if not the most -advanced for those days. Unfortunately, the routine of teaching at the remote university kept Boris from active continuation of the work in this field.

The Limanchik Summer School on Mixed Computation

In my opinion, research on mixed computation reached true national level after the conference on mixed computation held at the -Limanchik‖ summer camp of Rostov State University in 1983. The conference was an out-and-out success! It afforded the opportunity to meet and establish good professional contacts to all active researchers in this field. There is no point in discussing the whole conference program; instead, I will note only two memorable scenes.

Viktor Kasyanov gave a talk on the reducing program transformations. The set of transformations was wide enough and constituted a substantial part of the SOCRAT system aimed at processing FORTRAN programs. One of the system's features was the fact that transformations were based not only on a program's text, but also on user annotations. We considered these annotations as -a priori‖ true statements about a program that could both reduce complexity of necessary analysis and increase applicability of transformations. During the ensuing discussion, Nikolay Nepeivoda took floor and declared in his usual offhand manner that not a single program exists to which one could apply such transformations. Later, it turned out he meant to say that no programmer would deliberately write a branch instruction with an always-true condition. However, in the case of automatically generated programs, application of such transformations can be very promising.

In another discussion Sviatoslav Lavrov cast doubt on practicality of Futamura projections for production compilers, since they cover only the most simple and well-studied syntax-directed part of the process. The most interesting problems of compilation such as register allocation or common subexpressions elimination have origins in neither a partial evaluator nor an interpreter; therefore, they cannot appear in automatically obtained compiler4 .

Polyvariant Mixed Computation -Mikhail Bulyonkov

Another Ershov's post-graduate student, Tatiana Shaposhnikova, suggested the idea solving the problem of nontermination of interpreter specialization. When she told me about her idea for the first time, I was unprepared to perceive it, since Tatiana's suggestion led to an introduction of unstructured goto statements. In my opinion, it posed a problem, because she essentially based the existing mixed computation patterns on program structuring as in the propagation of available information through delayed conditionals.

I succeeded in finding sufficient conditions of specialization process termination. If the binding-time analysis classifies variables and, therefore, program instructions statically (i.e. if we declare a variable static, it remains so at any moment of specialization), and the range of each available variable is finite, then each branch of polyvariant specialization will inevitably lead to an already passed state. In certain sense, computation turns out to be -shut‖ inside a matrix with rows corresponding to initial program instructions and columns corresponding to available memory states. Each cell of this matrix contains the corresponding reduced instruction.

Andrei Petrovich grasped this idea with enthusiasm5 it has become the key to implementation of selfapplicable partial evaluator Mix suitable for carrying out all three Futamura projections. To reduce -technical‖ problems, we designed a special imperative language IL whose set of basic operations included among others the operation of expression reduction. We presented the methodological comprehension of the obtained results in our joint paper [START_REF] Bulyonkov | How Do Ad-Hoc Compiler Constructs Appear in Universal Mixed Computation Processes?[END_REF].

Unfortunately, we were a little late again. Just a few months earlier, Peter Sestoft, under the supervision of Professor Neil Jones from DIKU, showed the successful implementation of all Futamura projections for a small subset of the functional language LISP. In turn, they were surprised to discover belatedly the paper [Bul84] that described the technique they independently found during their partial evaluator implementation. However, these small disappointments became the starting point of a long-term collaboration, mutual visits, and healthy competition between DIKU and Novosibirsk group.

Partial Evaluation and Compilation Phases -Guntis Barzdin

Guntis Barzdin came to Novosibirsk to negotiate the possibility of his post-graduate study at Latvian University with Ershov as his scientific adviser. After having settled his affairs, Guntis paid me a visit and was very surprised to find me being only a few years older than he was. He had read my papers and pictured me as reputable man of science that was contrary to fact. During our discussions of mixed computation and Futamura projections, Guntis noted that they used only program specialization, while ignoring the possibility of obtaining intermediate data. It would be interesting to look at the projections in more general interpretation of mixed computation.

For the sake of simplicity let mix computation be represented by two processors: specializer spec generating residual program p x , and partial evaluator peval generating intermediate data x p : spec(p, x) = p x peval(p, x) = x p such that p(x, y) = p x (x p , y) for every y. On the one hand, if peval is trivial and x p is always empty, these relations degenerate into ordinary mixed computation equation. On the other hand, if the result of available computation is expressed as intermediate data, we can consider the task of mixed computation to be converting the data x into anotherin some sense, more effectiverepresentation of x p.

Substituting in the above equations p with int, x with program p, and y with the data d of program p, we have

spec(int, p) = int p peval(int, p) = p int such that int(p, d) = int p (p int , d)
Besides converting a program into some intermediate representation, mixed computation also generates an interpreter of this representation. In the case of degeneration, generation of the interpreter int p does not depend on program p at all, but only on the binding-time analysis result. The difference between such an interpreter and the initial one is the following: Whenever the initial interpreter performs computations over the initial data, the residual interpreter extracts the results of these computations from data structure x p . The residual interpreter has some auxiliary variables pointing to the current data element of x p . The algorithm we developed was the mirror image of polyvariant specialization, where the specialization process generated the next residual program fragment; the partial evaluator generated intermediate data element by putting there the values of this fragment's available expressions.

If available, we could split data into two sufficiently independent parts. There appears the possibility of a mixed strategy when we express one part of available computations in residual program and the other in intermediate data. The resulting residual program can be in turn specialized against the intermediate data. This strategy when applied to compilation problems corresponds to sequential compilation phases.

The main advantage of partial evaluation compared to specialization is that a more compact result occurs with the same volume of available computation because we no longer need to -decorate‖ computed values with the initial program fragments. On the other hand, we pay for this with the residual interpretation expenses [START_REF] Barzdin | Mixed Computation as a Tool for Extracting Compilation Phases, Methods of Compilation and Program Construction[END_REF]. We did not bring the idea of polyvariant partial evaluator even to experimental implementation. Later Carolina Malmkjar from Copenhagen University did it.

Guntis Barzdyn wrote his Ph.D. thesis on the problems of inductive program synthesis. He successfully defended it after Ershov's death in 1988.

The M2Mix -Dmitry Kochetov

I became the scientific adviser to Dmitry Kochetov by recommendation from Igor V. Pottosin. The subject of his postgraduate research was a partial evaluator for a real-life programming language. Since Dmitry knew very little about mixed computation, he could not even imagine how difficult the task would be that he was going to attack. We chose Modula-2 as the source language. It was not only very popular at that time in the Institute of Informatics Systems. However, Modula-2 was also the language of the programming system that Igor Pottosin developed in the context of a contract with large industrial organization. That raised the chances of practical use of partial evaluator 6 .

The M2Mix project required solutions of non-trivial theoretical and implementation problems. For example, since the source language had pointers and arrays, we needed a non-trivial binding time analysis and alias analysis in particular.

In order to avoid redundant code duplication, we developed an original configuration analysis. Its goal consisted of detecting for each program point the set of variables whose values influence specialization process. Even if the splitting of all program variables into static and dynamic does not change during specialization, the trivial solution that presumes storing and comparing the completely active and reached memory makes such a partial evaluator practically unusable with respect to both time and memory. We can optimize the specialization process by discarding the following variables from consideration: o variables that do not change in the considered fragment of program. The internal representation of program in the interpreter specialization is an example of such variable; o variables that can be evaluated based on the values of other essential variables; o variables not used in the considered fragment, and dead variables in particular 7 .

Similarly, it would be very unpractical to compare memory states at each source program point. In order to avoid non-termination it would be sufficient to trace only the set of so-called control points that cuts all program loops that modify static memory. This solution is evidently not optional. The problem is that a small number of control points may lead to residual code duplication, while large number of control points would lead to computational overhead.

Unlike most of the previous projects, we implemented M2Mix as generating extension processor. An important motivation for this decision was efficiency. However, the main reason was more fundamental; such implementation provided an easy way to guarantee that specialization performed exactly the same operations as the ordinary execution. Since we had no other way to execute a program but to translate it by the compiler at hand, we did both specialization and residual program execution in the same way 8 .

One of specific features of Modula-2 language is the complete absence of unstructured goto control transfer. Being very positive for formal definition of analysis methods, it became a problem when it came to 6 It should be noted here that partial evaluators were being already used in industrial projects. As an example, one can refer to the works of Samochadin [START_REF] Samochadin | Optimized for Structured Microcomputer Assembler Programs, Microprocessor programming[END_REF] from Leningrad Polytechnical Institute on specialization of low-level control programs, the works of Romanovsky [Rom95] from the Institute of Automation of SB AS on the optimization of computer graphics programs. But in our case the objective was much more ambitiousto make practically useful a general purpose partial evaluator, which, like a compiler, cannot -know‖ about a particular application domain, but about the source language only. 7 The specified conditions are not precise and serve for demonstration of the idea only. For example, a variable may be used in the given fragment, but should be considered essential, since it must be transitively transferred to the fragment where it is used. 8 Once we spent a lot of time trying to understand why some numerical analysis program and its specialized version produce different results. Finally, it turned out that the problem was in the fact that compiler options that were set for compilation of generating extension differ from those that were set for compilation of residual program.

generation of residual program. To overcome that, we used a well-known trick of modeling labels and jumps by a global loop with nested switch. Unexpectedly, it turned out that despite the fact that the residual program had minimum of interpretation left, it still worked several times more slowly than the original one. Again, the problem was in the fact that program efficiency depends not only on the number of executed high-level language operations, but also on the compiler's ability to implement them efficiently. In that respect, we could better optimize the compact and clear program of the original interpreter than the residual program with non-local control transfers and intertwined data dependencies. Post-optimization focused on this problem. It improved the residual program via common optimizations as well as the special transformations, which take into account the fact that the partial evaluator generated the program.

We tested the M2Mix on the standard test bench, including the Fast Fourier Transformation and the universal scanner Lex. These works formed the basis for Dmitry Kochetov's Ph.D. thesis -Efficient specialization of Algol-like programs‖. Currently, he works for Microsoft Corporation.

.

Binding-Time Improvement

In a certain sense, Nikolay Nepeivoda's prophesy came true. We had one of the most powerful partial evaluators, but had no program on which we could apply it successfully because when a programmer develops a general-purpose program he or she rarely cares about whether it is suitable for specialization or not.

The tools that improve source program binding-time properties would be a good supplement for further enhancement of partial evaluator. Boris Ostrovsky introduced a considerable selection of such transformations. Yuri Bannov in his master thesis has significantly extended this list and in addition, he has formulated conditions for appropriateness of their use. Following Boris Ostrovsky, Yuri Bannov worked on application of mixed computation to parsers, but his freedom of maneuver was restricted to partial evaluator M2Mix and universal parser Yacc9 .

The work titled -Polyvariant binding time analysis for higher-order functions‖ by Vladimir Ya. Kurlyandchik also focused on binding-time improvement. In contrast to the traditional orientation for the Novisibirsk community toward imperative languages, here the subject of the research was functional programs. The general idea consisted in the following: in usual monovariant binding-time analysis, we declare a variable as dynamic even if there is only one execution when it becomes dynamic. The developed methods allow for transformation of the original program by copying both program and data, so that more computations become static.

The university declared that the master theses of Vladimir Kurlyandchik and Yuri Bannov were the best graduate student's works in the recent years. Now they both work as managers in software companies.

Postscriptum

In 1992, the Institute of Informatics Systems organized the mixed computation research group. Later, in 1997 they transformed it into the laboratory of mixed computation. The tough 1990s seriously affected the character of research because financial self-provision became the highest priority. Experimental works, whose results could not have immediate use in industrial projects, were either frozen or continued by students. At the same time, computing machinery rapidly changed. New programming paradigms were widely adopted; the computing power increased by several orders of magnitude and they perfected the methods of compilation. Advanced compilers commonly used many features that seemed to be specific to mixed computation such as polyvariancy, loop expansion, and procedure unfolding.

However, it would be wrong to call the experience in the area of specialization without merit. A joint ongoing project between the St. Petersburg company TERCOM and American company Relativity Technologies [START_REF]Automated Program Re-engineering[END_REF] is an example. The project focused at developing a means for re-engineering and modernizing legacy applications. One of the key problems there is the extraction of business logic. One of the approaches, known as domain-based slicing, is essentially a specialization to known values of program variables in known program points. Even if the method is not suitable for obtaining of object code from an interpreter, it gives a satisfactory solution for many non-trivial tasks that emerge from practice and could unlikely appear in the -academic‖ setting. For example, o more than one value or a range of values may be associated with a variable for specialization, o negative specializationspecification of the set of values to which static variable should not be equal, o specification of the values of static variables not in the beginning of specialized program, but at the point where the values enter the program, e.g. where they are read from the database, o specialization of programs consisting of many components.

I heard that Andrei Petrovich made a long-distant call to his son Vasily and for several hours described his new findings. Similar story is told about Valentin Turchin, who also found these relations independently.

The Russian edition of Scientific American journal.

I was always amazed by Itkin's -cut and paste‖ technique of paper writing. If he had to insert or reposition a couple of sentences in his written text, he did it not by editor's markup or by notes on the underside, but literally cut and pasted a piece of sheet with the text to the right place. The result of his effort amounted to a long paper belt picturesquely snaking through his whole office. Upon completion of works, all that remained to be done was cut it into standard-sized pages and give to the secretary for typing.

N. Jones[START_REF] Jones | Challenging Problems in Partial Evaluation and Mixed Computation, Partial Evaluation and Mixed Computation[END_REF] later formulated and researched a similar but more abstractly stated problem: -Can program specialization yield more than linear acceleration?‖ Here we suppose that complexity measurement takes into account only the delayed data size, and the available data size is constant.

It was Ershov who translated into English (or to be honestrewrote in English) my paper[START_REF] Bulyonkov | Polyvariant mixed computation for analyzer programs[END_REF] that was later extensively cited.

In the course of this work an interesting experiment was carried out that evidently proved the concept's efficiency. The task was to obtain two specialized parser: one should be generated automatically from the universal one, while the other should be written manually from the scratch. Even without mentioning that we could not get rid of all errors in manually written parser, it was simply less efficient than the one generated automatically.


Nikolay Petrovich Brusentsov

Julia Sergeevna Vladimirova

Julia S Vladimirova
email: vladimirova@cs.msu.su

Ternary Dialectical Informatics

Keywords: Ternary informatics, opposition coexistence, content consequence, Aristotle's syllogistics, Carroll's -Symbolic Logic‖

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The deficiency of modern binary informatics is specified with inadequacy of its foundation is adequate for its specification since it uses binary logic. This so-called -classical‖ formal logic, based on prior transcendental law of the excluded middle, does not show the perfect reflection of the reality and it is out of keeping with common sense. It is so opposite to practical arithmetic, for example, it is not useful for solving real problems. This binary logic is the logic of an artificial, discrete world of binary computers. There is no modality; possibility cannot differentiate from necessity. Even the most fundamental logical relation of content consequence has expressions by -material implication‖. These paradoxes for which distinguished logicians have tried for many years to overcome in vain.

It is clear why logic cannot become a school subject. The development of logical thinking or the study of logic, first as school task and then as a university one, does not lead to mentality improvement. The situation became worse with computerization of the education. With the general discussions concerning the intellectualization of computer processing of information and information safety, there is a suppression of people's intellect everywhere with stilted binary logic.

Most agree that Aristotle is the founder of logic. He created a system of demonstrative conclusionsthe syllogistics that are still an unsurpassed mentality instrument. Syllogistics is dialectic; there is no paradox in it, but we cannot transform it into a modern logical calculus. This motivated suspicions that there was something wrong in Aristotle's logic such as his denial of empty sets. However, there are not only empty sets in syllogistics but also fuzzy sets that were invented by L. Zadeh in 1965 and these are still not -mastered‖ with modern logic. The principal difference of Aristotle's logic from modern, -classical‖ one is that it is not binary; rather it is ternary. Contrary to the -law of excluded middle‖ with -necessary is‖ and -necessary isn't‖, there is the third one affirming, -possible is and possible isn't‖. We predicate the -threevaluedness‖ to the relation of consequence that depletes the determined by Aristotle in the -Prior Analytics‖ [paragraph 57 line number l]:

-…when two things are so related to one another, that if the one is, the other necessarily is, then if the latter is not, the former will not be either, but if the latter is, it is not necessary that the former should be. But it is impossible that the same thing should be necessitated by the being and by the not-being of the same thing‖

Mathematical Considerations

In syllogistics, we present the consequence relation as universal affirmatives with premise -any x is y‖. In this case, we see that any x-thing is necessarily a xy-thing, and any y'-thing (not y-thing) is necessarily an x'y'-thing. Besides, a xy'-thing must be an exclusion as x must necessarily be y (x cannot be y'). At the same time, we cannot exclude x'y-things; they are possible but not necessarily, as there are xy-things and x'y'-things. If we assume both premises,--any x is y‖ and -any y is x‖-then we must exclude xy'-and x'y-things. Hence, there will exist an equivalence relation--x is interchangeable to y‖.

In binary logic, we would have to admit -interchangeable/not interchangeable‖.

For the relation of consequence, we need three values, which are -necessary is‖, -possible but not necessary‖, and -impossible‖. Therefore, there is not enough binary implication for the adequate expression of consequence.

With xy'-things, consequence is impossible; if there are no xy'-things, then we cannot exclude consequence; otherwise, it is possible but not necessary. In case of inexistence of xthings or y'-things, the implication does not express any interconnection between terms and does not form a two-dimensional relation. In these cases, the other term can have any value independently.

To smooth away -paradoxes‖ of implication, it is enough to prevent these cases of the invariability of its terms. Hence, a strict implication of Lewis is an inexistence of xy'-things; that is, V'xy' is paradoxically performed when x-things do not exist and y'-things do not exist-or when V'x and V'y'. There would not be paradoxes if with V'xy' we demand Vx and Vy'-the existence of x-things and y'-things. As the result, the implication of Lewis becomes the necessary consequence VxV'xy'Vy' [START_REF] Brusentsov | Ternary interpretation of Aristotle syllogistics‖[END_REF]. In perfect normal form of this relation, VxyV'xy'Vx'y', is visibly ternary. Members xy and x'y' belong to concerned subset Cartesian product {x, x'}x{y, y'}, member xy' antibelongs to it and member x'y is withheld. Withholding expresses the third variety of belonging that is possible, but not necessary. A subset that admits a possible belonging is fuzzy and a relation presented with it is ternary.

In the mathematical logic, deviation from Aristotle's opinion of the universal affirmative premise that -All A is B‖, takes it from a content consequence to binary implication. Hilbert and Ackerman proved the deviation with mathematical application logic needs -where taking Aristotle's opinion as a foundation was pointless‖ [7, p.79]. They did not take into consideration that the logic lost the richness of content, thinking that their logical calculus -makes possible successful problem comprehension where simple content logical thinking is principally weak‖ [7, p.17].

Indeed, logic became mindless two or three thousand years ago. Ancient stoics sought after incredible abstraction and carried it out with the help of -propositions‖ subordinated to -law of excluded middle‖. That law allowed only two truth-values--true‖ and -false‖. Adequate to reality, Aristotle's syllogistics became a dead scholasticism with binary logic. Mathematical logic presented this -classic‖ thinking with strict algebraic forms evidently showed its inadequateness [START_REF] Losev | Critical notes about bourgeois mathematical logic‖[END_REF].

Stoics -compensated‖ for the lack of the consequence relation in their logic to implement conclusions according to the rules of modus ponens and modus tollens. In mathematical logic, we know that an implication is not a consequence. -The relation ‗if X then Y ' should not be understood as a form for relation of foundation and consequence. On the contrary, the proposition X  Y is always true when X is false or when Y is true‖ [7, p. 20]. At the same time, however, in mathematical logic even its founders identify binary implication with ternary and with Aristotle's consequence as the first and the second one associated with the proposition -All A are B‖. As a result, from mathematical logic point of view, they consider the perfect forms of syllogisms darapti, bamalip, felapton, fesapo to be false [7, p.79]. The syllogism of submission of quotient to common is rejected as according to the deviation from Aristotle's interpretation -Some A is B‖ is not a consequence from -All A are B‖.

Yan Lukasevitch created a ternary modal logic in 1920 in his detailed book titled, -Aristotle's syllogistics from a modern formal logic point of view‖ [START_REF] Lukasevitch | Aristotle's Syllogistics from Modern Formal Logic Point of View[END_REF]. He proved algebraically with the help of the identification of the ternary consequence the material implication of Aristotle's statement--But it is impossible that the same thing should be necessitated by the being and by the not-being of the same thing‖ -is false. It is also false from the logical point of view that they did not obey the basic logical lawthe law of identity. We cannot identify the proposition -All A are B‖ that expresses the consequence relation B from A with -No one A isn't not-B‖, the help of which binary implication relation is presented in natural language.

The problem is that logic cannot be without a consequence relation that is in essence is ternary; furthermore, it does not exist in binary logic. We express the relation called implication like consequence with the same -If… then…‖ relation and the same -→‖ marker. It is not striking that we can interpret implication as consequence. However, if there is no logic without consequence then logic with implication instead of consequence is not logic at all! Then from inexistent things follows -whatever‖, from 2x2=4 is that -snow is white‖.

Defective binary logic ignores common sense. The result of its application does not meet with natural expectations. In the book by T. Oppenheimer [START_REF] Oppenheimer | The Flickering Mind: The False Promise of Technology in the Classroom and How Learning Can Be Saved[END_REF], he proves the indisputable bad influence of computer education in American schools. The author insists on removing computers from schools; but it is hardly possible in current situation. The -root of all evil‖ is not with computers but with the primitive unnatural logic of the discrete binary world that students study. It blocks their ability to master the logic of real world. If there were natural logic in computers, the result of studying computers would be the opposite.

However, there is no adequate (dialectical) logic in all -science of thinking‖, even where it does not follow the -law of excluded middle‖ and focuses on invention of not binary logics. This invention is unsuccessful because it has a formal character. If they researched the essentials of the problem, then they would have found out that Aristotle's logic is ternary and that ternary is a necessary, but not a sufficient, condition for adequate logic. Aristotle's logic is adequate; hence, it makes no sense to invent non-Aristotle logics.

Carroll Logic

A good exception is -Symbolic Logic‖ by Lewis Carroll [START_REF] Carroll | Symbolic logic‖, L. Carroll Story with Bundles[END_REF] that did not receive appropriate (like Aristotle's one) understanding and development. There is neither discontent -true‖ or -false‖ propositions nor -law of excluded middle‖. His logic researches propositions that expressed interconnections of things characterized with combinations of features (peculiarities).

-The Universe contains ‗Things' … Things have ‗Attributes' … Any Attribute, or any Set of Attributes, may be called an ‗Adjunct' ‖ The proposition is considered as a natural language expression of a relation that connects adjuncts of things with terms x, y, z, … . At the same time, the essence of Carroll's relation visually reflects his diagram and algebraic -index method‖ that formally allows obtaining a content conclusion from data opinions, if they exist.

Carroll's diagram is on the surface identified to Pirs' truth table used to identify Boolean functions. However, expressed with the diagram, we interpret it not as extensional (as class of things) but intentional as set of things or subset of Cartesian product of pairs of opposite adjuncts. Besides, the diagram cells obtain not one from two values, but one from three values; it could also obtain cells that have -0‖ or -1‖ and they permit empty cells. They denote nothingness of the belonging of things to the subset presented in the diagram. Nevertheless, Carroll understood value -1‖ as existence, value -0‖ as inexistence of a thing; empty cells belong to neither.

For example, Lewis' strict implication relation V'xy' at Carroll's two-term diagram only one value appears--0‖ in the xy'-cell. Carroll expressed this relation in three ways using a universal negatives proposition: -No one xy' exists‖ or -no one x is y'‖ or -No one y' is x‖. The universal affirmative proposition -All x are y‖ includes a particular affirmative in Carroll's -Some x is essence y‖ that is equal to existence of the proposition -Some xy exist‖. Carroll called -All x are y‖ a double proposition that was equal to two opinions: -No one x is y'‖ and -Some x is y‖; that is, V'xy'Vxy. In the diagram, -0‖ is in the cell xy' and -1‖ is in the cell xy.

Mathematical Details

It is clear that this is not implication (one of its paradoxes is eliminated) but it is not a full Aristotle consequence. He does not take into consideration the contrapositive of a consequencea false step, as it is peculiar to all efforts to make syllogism algebraic. As compensation [START_REF] Brusentsov | Diagrams of L. Carroll and Aristotle syllogistics‖[END_REF], -Symbolic logic‖ of Carroll becomes a well-composed and perfect statement of Aristotle's syllogisticsa foundation of dialectical logic.

The most important component of logic content appeared an identified dialectic principle in the Aristotle's syllogisticsthe principle of opposition coexistence [START_REF] Brusentsov | Wandering around three pines (dialectics adventures in informatics)‖[END_REF]. It expresses the contrapositive of a universal affirmative proposition as the symmetry of a relation expressed with a universal negative proposition; it constitutes the visible demonstrations of this principle. The fact is that the initial adjuncts x, x', y, y', z, z' … expressed with terms x, y, z … made sense as the result of things comparison that have opposite adjuncts, for example, an x-thing and an x'-thing. In other words, the principle of opposition coexistence means that a subset of the Cartesian product {x, x'}x{y, y'} reflects a content relation that has all pairs opposite adjuncts -VxVx'VyVy'. In Carroll's diagram, VxVx'VyVy' reflected with token data of -1‖ existence on every one of four interior walls that denotes non-emptiness of classes x, x', y, y'.

These equivalent realities are part of Aristotle's Universe (AU)the foundation of content logic [START_REF] Brusentsov | Wandering around three pines (dialectics adventures in informatics)‖[END_REF]. In it Lewis' implication V'xy' and The existence of a xy'-thing according to the principle of opposition coexistence entails the existence of its antipodean x'y-thing. Therefore, the particular affirmative and the particular negative premises of the syllogism become double and they are two, not four:

Ixy ≡ Axy  Ayx ≡ VxyVx'y' Oxy ≡ Exy  Ex'y' ≡ Vxy'Vxy' At the same time, common conditions are not two but four that come from one by term inverting:

Exy ≡ Axy', Ex'y' ≡ Ax'y, Ayx ≡ Ax'y'.

Syllogistics algebra that corresponds to Carroll's interpretation of its diagram with token symbolized existence and inexistence of things compared with cells and -walls‖ in similar to -index method‖ but instead of indexes it uses prefix functor of existence V --disjunct‖ (integral disjunction similar to integral sum ) and its inversion V'symbol of inexistence. The illustration presented in the diagram relation reflects a conjunction of disjuncts, not inverted and inverted, and members of conjunction that corresponds to empty cells that are not present (silent). Every trit takes one of three values: -+‖ for existence, --‖ for inexistence, and -0‖ for silence. For example, consequence (x  y) ≡ VxyV'xy'Vx'y' is reflected with the value of a four-trit scale: +-0+, a particular negative premise Oxy coded with the value: 0++0. There are eight double place relations in syllogistics [START_REF] Brusentsov | Reanimation of Aristotle's syllogistics‖[END_REF]:

Axy ≡ Ay'x' ≡ Exy' ≡ Ey'x ≡ + -0 + Ayx ≡ Ax'y' ≡ Eyx' ≡ Ex'y ≡ + 0 -+ Exy ≡ Eyx ≡ Axy' ≡ Ayx' ≡ -+ + 0 Ex'y' ≡ Ey'x' ≡ Ax'y ≡ Ay'x ≡ 0 + + -Ixy ≡ Ix'y' ≡ Iyx ≡ Iy'x' ≡ Oxy' ≡ Oyx' ≡ Ox'y ≡ Oy'x ≡ + 0 0 + Oxy ≡ Oy'x' ≡ Oyx ≡ Ox'y' ≡ Ixy' ≡ Iy'x ≡ Ix'y ≡ Iyx' ≡ 0 + + 0 x  y ≡ AxyAyx ≡ Exy'Eyx' ≡ + --+ x  y' ≡ ExyEx'y' ≡ Axy'Ayx' ≡ -+ + -Computerizing proof of conclusions (true modi of syllogism) is carried out by two terms premise presentation with three term scales from witch crossing searching conclusion is taken by middle term elimination, if it exists. For example, modus Barbara: AyzAxy  Axz in three term x, y, z-scales is realized: Ayz ≡ + -0 + + -0 + Axy ≡ + + --0 0 + + Ayz Axy ≡ + ---0 0 0 + The elimination y gives x, z-scale +-0+, i.e. Axz. Subordination of particular premises is proved with a common crossing of coding these premises scales. So, the subordination Axy  Ixy, is equal to AxyIxy = Axy, proved with crossing + -0 + + 0 0 + = + -0 + .

In syllogistics based on the opposition coexistence of all doubtful modi from the classical logic point of view and a row of modi missed with traditional syllogistics. For example, from premises of doubtful modus bamalip, there is not only particular but also a universal conclusion:

Azy ≡ + 0 -+ + 0 -+ Ayx ≡ + + 0 0 --+ + Azy Ayx ≡ + 0 -0 ---+ Eliminating y we have + 0 -+ ≡ Azx ≡ Ax'z', i.e., AzyAyx  Azx The correction of traditional theory is proof of denying with it modus of the first figure IyzAxy  Ixz:

Iyz ≡ + 0 0 + + 0 0 + Axy ≡ + + --0 0 + + IyzAxy ≡ + 0 --0 0 0 + That with y elimination is +00+, i.e. Ixz. By the same way, the true of the next missed modus is proof of the first figure IyzExy  Oxz and similar modi of other figures.

Fig. 1 .

 1 Fig. 1. Material Implication: Extensional interpretation (Pirs' table, Boolean class algebra)

Fig. 2 .

 2 Fig. 2. Content Consequence: Intentional interpretation (Carroll's diagram in Aristotle's Universe AU)