English Version Русская версия

Бульонков Михаил Алексеевич
Институт систем информатики имени А.П. Ершова СО РАН, , mike@iis.nsk.su

Mixed Computation in Novosibirsk

The works of Andrei Ershov had a stimulating impact on the development of theoretical computer science. The idea of mixed computation came to Ershov on the ground of his research in compiler development, program optimization and transformation. He formulated the notion of mixed computation as a basic principle of system programming. In his earlier works on the subject Ershov defined partial evaluator as a software processor with some program representation and part of its input data as input, and the transformed program, partial result, and the data requiring additional processing as output.

Next he noticed that the behavior of partial evaluator where the operations of available data evaluation alternate with generation of residual program, are similar to the behavior of a compiler where program analysis steps alternate with object code generation. This reasoning culminated in discovery of correlations between program interpretation and its translation into object code.

An example of professional ethics is the fact that Ershov called those independently discovered correlations Futamura projections after a Japanese researcher who had come upon them six years before. Despite the very similar ideas and conclusions appearing in a number of works of Lombardi, Futamura, Turchin, and others, it was thanks to Andrei Ershov’s persistence and energy that the idea of mixed computation gained extreme popularity. The notion of mixed computation introduced by Ershov as the common model for various typed of program processing and the basis for defining a broad class of program processors demanded extensive research of both the properties of the model itself and its interpretation in different possible application areas. Various aspects of mixed computation – from theoretical and even philosophical to purely practical – were further developed in the works of his colleagues and followers: V. Itkin, B. Ostrovskiy, V. Sabelfeld, M. Bulyonkov, G. Barzdin et al.

For his works in the field of mixed computation Andrei Ershov was awarded the honorary Krylov Award of the USSR Academy of Sciences (1984).

In 1992 in the Institute of Informatics Systems was formed a mixed computation research group, which in 1997 was transformed into the Mixed Computation Laboratory. The emphasis of the laboratory work was set on practical applications of mixed computation. Among other things, the laboratory developed a partial evaluator for the Modula-2 language. The acquired experience in program specialization is used, in particular, in a current joint project of the Mixed Computation Laboratory, TERKOM Enterprize (St. Petersburg, Russia) and Relativity Technologies Inc.(USA). The aim of the project is the development of tools for reengineering and modernization of outdated software. One of the key tasks in the process is the so called business logic extraction. Many of the mechanisms used in this process are, in essence, adapted methods of program specialization.