This report describes the scientific activities developping at the Laboratory for Program Construction and Optimization of the ac. A.P.Ershov Institute of Informatics Systems (IIS) of the Siberian Division (SD) of the Russian Academy of Sciences (RAS) and education program of this laboratory members.
As an independent and autonomous institute of the Siberian Division, IIS has been existing since 1990. However, as a scientific school concerned with fundamental and applied aspects of system informatics it had been existing for two decades hitherto as department of the Computing Centre of the Siberian Division of the Russian Academy of Sciences.
The academician Andrey P. Ershov (1931-1988) was the organizer and the leader of this school, and therefore Institute of Informatics Systems was named after Andrey P. Ershov. A.P.Ershov was a founder of Siberian school of theoretical and system programming. He has made a valuable contribution to forming informatics as a new scientific school and social phenomenon in our country. From the very first days of his scientific activity A.P. Ershov worked out ideas and methods of compiling which are foundation of modern system programming.
The activity of A.P. Ershov has initiated a new scientific school — researching and working out optimizing compilations for high level programming languages. He has formulated a precise definition of mixed computation. These works have been a methodological basis of perspective transformational approach to programming. It is characteristic of A.P. Ershov’s scientific activity the combination of theoretical investigations and practical works. A.P. Ershov being a broad-minded person understood the strategical role of informatization in scientific and technical progress, education and social development of society.
The foundation of new scientific directions : automation of scientific investigations, parallel programming and artificial intelligence has been laid by his works and organizer talent.
In 1979 a scientific reseach group “Theory and compiling methods” headed by V.N. Kasyanov has been organized as a laboratory on Ershov’s initiative. The group was engaged in creation of theoretical bases and experimental systems for constructing qualitative programs by semantic transformation methods.
The large-block scheme theory based on an unified model for imperative programs with complex variables and statements has been developed and used as a general basis for an investigation of a wide spectrum of equivalent and optimizing transformations. A node numbering technique and fast algorithms for control flow analysis and structuring of programs has been developed. Effective algorithms of an analysis of schemes and semantic characteristics of programs needed for its transformations have been constructed. A number of important results in a standard and recursive schemes theory has been obtained. A method of efficient and reliabile programs construction by concretizing transformations of annotated programs has been carried out.
In parallel, some experimental or applied projects for a validation and an implementation of the theoretical concepts and methods were conducted by the staff members of this group: the universal optimizer of the multi-language system BETA, concretizer TRAP and concretization system SKAT for annotated Fortran programs, transformational machine TM for Pascal programs and systems for static semantics analysis of annotated Modula and Fortran programs.
When IIS has been founded this group has been reorganized as Laboratory for Program Construction and Optimization (LPCO) with including a group of school informatics and extending researches in computer education problems.
The group of the school informatics was founded by A.P. Ershov at the Laboratory of Experimental Informatics of Computing Centre in 1975 when the school course “Foundations of informatics and computing technique” was intended. Pupils gratuated Summer School for Young Programmers organized in 1976 by A.P. Ershov were taking a part in the activity of this group.
When G.A. Zvenigorodsky (one of the leader of this group) has died suddenly (1984) the group was headed by L.V. Gorodniaia. Novosibirsk scientific subdivision “School-1” was founded on the base of this group. From 1988 pupils gratuated Summer School for Young Programmers and students interesting in school informatics problems after gratuating Novosibirsk State University became the staff members of this group.
Now the school informatics group and the Laboratory for Program Construction and Optimization as a whole one continue researching and working out experimental educational programming systems for different goals and also uses knowledge in informatics and programming training accumulated under the direct leadership of A.P.Ershov. A nonprofit Siberian Inter- regional Foundation on Informatics and Education was organized in 1991 by staff members of the Laboratory in a cooperation with V.E.Kotov and other Ershov’s disciples for supporting Summer School for Young Programmers and other computer education activities initiated by A.P.Ershov.
The Laboratory’s current researches are aimed at providing higher efficiency and reliability of software. They are split into two complementary parts: theoretical works and development of program systems based on these works. Researches are being conducted along five directions:
- theory and methods of transformational and functional programming,
- basic algorithms and notions of informatics,
- tools for program construction, analysis and transformation,
- user-friendly interface of program systems,
- knowledge representation and teaching programs.