The report gives account of the IFIP Working Conference in program specification and

 transformation (Bad Tolz, FRG, April 15-17, 1986) attended by 65 specialists from different
countries including the report’s authors, as well as information on the Munich CIP project for
program transformation obtained during the authors’ visit to the Informatics Institute of Technical
University of Munich on the 14^th of April of 1986.

SUBJECT MATTER

The Conference

The conference was being held in April 15-17, 1986, in the town of Bad Tolz, FRG, 85 km from
Munich, and was devoted to an urgent and actively developing direction of present-day
programming – program specification and transformation. The main goal of works in this direction
is to increase the automation level when constructing reliable and efficient programs, to learn to
construct programs and proofs of their correctness with substantial aid of a computer. Here an
important role belongs to formalization of the notions of “program” and “problem formulation”
leading to algorithmic languages and specification languages. Programs and specifications
transformations are the tools that, once having been materialized in software, are being used for

automation of the process of transition from pre-algorithmic problems formulation to reliable and

effective programs for their solution.

The conference was attended by 65 well-known scientists from 16 countries – FRG, USA, France,
England, Italy, Norway, Holland, Sweden, Finland, Spain, Austria, Belgium, Canada, Japan, and
USSR. Among them were developers of experimental program transformation systems, leaders of

programming projects, specialists in programming methodology.

A series of talks by members of the Informatics Institute of Technical University of Munich were
devoted to CIP project carried out in this institute. This project is aimed at the development of
transformational programming methodology where program development is viewed as a process of
sequential transformation of specifications and programs. A prototype system CIP-S was created
allowing carrying out such transformation process staying within the limits of a “wide-spectrum”
CIP-L language and in many respects relying on the aid of computer. At that, transformations
application is done automatically whereas selection of necessary transformations from the vast
system catalogue as well as proving their applicability conditions remains mainly the human
programmer’s part of the job. The paper by Bernhard Muller and Helmut Partsch presented the
objectives of CIP-S system, its main design decisions taken at the formal system specification stage,
as well as the experience obtained by application of algebraic approach to the system’s specification
and transformational approach to the system’s software development. The paper by Rudolph
Berghammer formulated the main theorems and transformation rules constituting mathematical
basis for the notions related to the notion of functions’ composition in applicative language. The
paper by Bernhard Muller and Otto Paukner formulated algebraic laws for operations over sets. The
use of these laws as transformation rules allows to get rid of some specificational constructs and
convert them into algorithmic ones. The paper by Bernhard Muller described a language for writing
algebraic specifications using higher-order operations and formulated a formal theory of algebraic
types.

Some papers presented at the conference were concerned with considering the experience in
implementation of concrete experimental systems for program transformation, generalization and
classification of the methods used. First of all it is necessary to mention the paper by Martin Fizzer
(USA, Institute of Information Sciences) presenting a survey and classification of up-to-date
approaches and techniques of program transformation. The paper by James Boil (USA, Department
of Mathematics and Informatics of Argonne National Laboratory) described an experience in
program development with the help of TAMPR transformation system. Input specifications for this
system are written in LISP and efficient resulting programs are generated in FORTRAN for
sequential and parallel computers. The paper by Hiroshi Nakagawa (Japan, Yokogama National
University) described a program system for Prolog programs transformations directed at
improvement of their efficiency and based on generalized fold and unfold operations.

A great interest of participants was evoked by the talk by Professor C. Hoare (England, Oxford
University) formulating the means for algebraic specification of communicating sequential
processes and analyzing algebraic properties of such specifications. Some more presentations were
also devoted to specification means, in particular the papers by Eugidio Astesiano (Italy, University
of Genoa), David Vail (USA, Institute of Information Sciences), P. Pepper (West Berlin). It was
noted that algebraic specifications allow writing problem formulations in compact form, and their
algebraic properties make it easier to prove correctness of generated programs and correctness of
transformations.

The authors of the report also delivered talks presenting their results on the subjects within the
conference scope. A.P. Ershov presented the paper “Controlled Mixed Computation and its
Application to Systematic Construction of Language-Oriented Analyzers”, and V.K. Sabelfeld
presented the paper “How to Consider Properties of Operations in Global Program Analysis”. The
presentations raised questions and interest of the conference participants.

In addition to participation in the conference the authors seized the opportunity to visit the
Informatics Institute of Technical University of Munich. During the short visit discussions with the
following members of the Institute took place: Walter Dosch, Rudolph Berghammer, Bernhart
Moeller, and Mrs. K. Samelson. In these conversations the authors were introduced to the current
state of CIP project and perspectives of its future development and also watched the demonstrations
of CIP-LS compiler operation and a dialog library card-processing machine running on Siemens
computer.

Discussion of scientific and technical cooperation issues

Besides scientific discussions on the conference topics the work aimed at establishing scientific
contacts and identifying possible forms of cooperation in the fields interesting to Soviet specialists
was carried out. Positive results of these talks may be summarized as follows.

• Prof. F.L. Bauer (Technical University of Munich). A basic agreement was reached on
  handing over the CIP project software for carrying on coordinated experiments.

• Prof. D. Bjorner (Danish Informatics Center, Lyngby, Denmark). A basic agreement was
  reached on holding an international seminar in Denmark and inviting five Soviet specialists
  at the expense of the receiving party.

• Prof. K. Koster (University if Neimen, Netherlands). Proposals were put forward on
  delegating a Soviet specialist for scientific work at the University of Neimen on contract
  basis.

• Prof. A. Haraldson (Linkoping University, Sweden). Confirmed his interest in inviting a
  Soviet specialist to the university on contract basis.

• Prof R.Dewar (New York University, USA). A prominent scientist in the field of
  supercomputer software. Showed interest and desire to make a scientific trip to the USSR.

Propaganda and counter-propaganda

The basis of propagandistic work consisted in scientific advances of Soviet scientists in topical
fields of informatics. In particular, the talks by Soviet participants brought appreciation and
interest that showed in proposals for scientific and technical cooperation. Foreign scientist
showed a great deal of interest in the USSR state program of school computerization and
scientific foundations of the basic course in informatics worked drawn up by Soviet scientists.

Informal discussion of Soviet-American relations and Strategic Defense Initiative allowed to
concentrate attention of foreign scientists at negative aspects of the USA administration’s policy
consisting in infringement of free creative work, politization of science, restricting scientific and
technical cooperation along with strengthening American hegemony in informatics and
computer engineering.

CONCLUSIONS AND RECOMMENDATIONS

1. Transformational methods in programming remain the central and rapidly developing issue
   of theoretical informatics.

2. Although in some directions Soviet works are up to the world level or even set the latter
   (program schemata theory, logical programming and program synthesis, mixed
   computation), an overall scale of these works in the USSR and especially their rate of grows
   is still inadequate.

3. There comes a time for creation of transformational programming and program synthesis
   demonstration systems allowing to get down to the matters of practical efficiency and
   technological implementation.

4. It is necessary to undertake efforts for more profound analysis of CIP project and familiarize
   oneself with its software as far as possible in the scope of the outlined scientific and
   technical cooperation.

5. It is very important to use the given opportunities for long-term scientific visits of Soviet
   specialists to the “small” European countries’ universities with a high scientific image.
   Active work in these scientific groups will be a positive contribution to scientific and
   technical cooperation and will allow to make up for subsiding of Soviet-American scientific
   exchange.

The head of the delegation,

Academician                                    A.P. Ershov

Back