Proceedings of the NATO Advanced Research Workshop on Program Transformation and Programming Environments

The Marktoberdorf Summer Schools on Informatics were started in 1970, with the intention to convene every second or third year a group of top researchers in computing, devoted to preach their most recent results to an elite of advanced students - young and most promising people - and prepared to stand their questions, criticism and suggestions. The themes of these Advanced Study In stitutes under the sponsorship of the NATO Scientific Affairs Division varied slightly over the years, oscillating more or less around Programming Methodo logy, as the following list shows: 1970 Data Structures and Computer Systems 1971 Program Structures and Fundamental Concepts of Programming 1973 Structured Programming and Programmed Structures 1975 Language Hierarchies and Interfaces 1978 Program Construction 1981 Theoretical Foundations of Programming Methodology 1984 Control Flow and Data Flow: Concepts of Distributed Programming 1986 Logic of Programming and Calculi of Discrete Design 1988 Constructive Methods in Computing Science 1989 Logic, Algebra, and Computation Logic, Algebra, and Computation is the theme of the summer school to which this volume is devoted. It is the tenth in succession, but it is also the first in a new series (the "blue" series) that is intended to alternate in future with the traditional (the "red" series) arrangement; in fact the tenth summer school in the "red" series with the title "Programming and Mathematical Method" , held in 1990, was the subject of celebrating both its serial number and the twenty years of Marktoberdorf Summer Schools altogether.

Mathematics has a certain mystique, for it is pure and ex- act, yet demands remarkable creativity. This reputation is reinforced by its characteristic abstraction and its own in- dividual language, which often disguise its origins in and connections with the physical world. Publishing mathematics, therefore, requires special effort and talent. Heinz G-tze, who has dedicated his life to scientific pu- blishing, took up this challenge with his typical enthusi- asm. This Festschrift celebrates his invaluable contribu- tions to the mathematical community, many of whose leading members he counts among his personal friends. The articles, written by mathematicians from around the world and coming from diverse fields, portray the important role of mathematics in our culture. Here, the reflections of important mathematicians, often focused on the history of mathematics, are collected, in recognition of Heinz G-tze's life-longsupport of mathematics.

The Summer School in Marktoberdorf 1990 had as its overall theme the development of programs as an activity that can be carried out based on and supported by a mathematical method. In particular mathematical methods for the development of programs as parts of distributed systems were included. Mathematical programming methods are a very important topic for which a lot of research in recent years has been carried out. In the Marktoberdorf Summer School outstanding scientists lectured on mathematical programming methods. The lectures centred around logical and functional calculi for the * specification, * refinement, * verification of programs and program systems. Some extremely remarkable examples were given. Looking at these examples it becomes clear that proper research and teaching in the area of program methodology should always show its value by being applied at least to small examples or case studies. It is one of the problems of computing science that examples and case studies have to be short and small to be lJresentable in lectures and papers of moderate size. However, even small examples can tell a lot about the tractability and adequacy of methods and being able to treat small examples does at least prove that the method can be applied in modest ways. Furthermore it demonstrates to some extent the notational and calculational overhead of applying formal methods.

Computing Science is a science of constructive methods. The solution of a problem has to be described formally by constructive techniques, if it is to be evaluated on a computer. The Marktoberdorf Advanced Study Institute 1988 presented a comprehensive survey of the recent research in constructive methods in Computing Science. Some approaches to a methodological framework and to supporting tools for specification, development and verification of software systems were discussed in detail. Other lectures dealt with the relevance of the foundations of logic for questions of program construction and with new programming paradigms and formalisms which have proven to be useful for a constructive approach to software development. The construction, specification, design and verification especially of distributed and communicating systems was discussed in a number of complementary lectures. Examples for those approaches were given on several levels such as semaphores, nondeterministic state transition systems with fairness assumptions, decomposition of specifications for concurrent systems in liveness and safety properties and functional specifications of distributed systems. Construction methods in programming that were presented range from type theory, the theory of evidence, theorem provers for proving properties of functional programs to category theory as an abstract and general concept for the description of programming paradigms.

The title of this book contains the words ALGORITHMIC LANGUAGE, in the singular. This is meant to convey the idea that it deals not so much with the diversity of program ming languages, but rather with their commonalities. The task of formal program develop It allows classifying ment proved to be the ideal frame for demonstrating this unity. concepts and distinguishing fundamental notions from notational features; and it leads immediately to a systematic disposition. This approach is supported by didactic, practical, and theoretical considerations. The clarity of the structure of a programming language de signed according to the principles of program transformation is remarkable. Of course there are various notations for such a language. The notation used in this book is mainly oriented towards ALGOL 68, but is also strongly influenced by PASCAL - it could equally well have been the other way round. In the appendices there are occa sional references to the styles used in ALGOL, PASCAL, LISP, and elsewhere."

Konrad Zuse is one of the great pioneers of the computer age. He created thefirst fully automated, program controlled, freely programmable computer using binary floating-point calculation. It was operational in 1941. He built his first machines in Berlin during the Second World War, with bombs falling all around, and after the war he built up a company that was taken over by Siemens in 1967. Zuse was an inventor in the traditional style, full of phantastic ideas, but also gifted with a powerful analytical mind. Single-handedly, he developed one of the first programming languages, the Plan Calculus, including features copied only decades later in other languages. He wrote numerousbooks and articles and won many honors and awards. This is his autobiography, written in an engagingly lively and pleasant style, full of anecdotes, reminiscences, and philosophical asides. It traces his life from his childhood in East Prussia, through tense wartime experiences and hard times building up his business after the war, to a ripe old age andwell-earned celebrity.

This book is the second of two volumes that present the main results which emerged from the project CIP - "C"omputer-Aided, "I"ntuition-Guided "P"rogramming - at the Technical University of Munich. Its central theme is program development by transformation, a methodology which is becoming more and more important. Whereas Volume I contains the description and formal specification of a wide spectrum language CIP-L particularly tailored to the needs of transformational programming, Volume II serves a double purpose: First, it describes a system, called CIP-S, that is to assist a programmer in the method of transformational programming. Second, it gives a non-toy example for this very method, since it contains a formal specification of the system core and transformational developments for the more interesting system routines. Based on a formal calculus of program transformations, the informal requirements for the system are stated. Then the system core is formally specified using the algebraic data types and the pre-algorithmic logical constructs of the wide spectrum language CIP-L. It is demonstrated how executable, procedural level programs can be developed from this specification according to formal rules. The extensive collection of these rules is also contained in the book; it can be used as the basis for further developments using this method. Since the system has been designed in such a way that it is parameterized with the concrete programming language to be transformed, the book also contains a guide how to actualize this parameter; the proceeding is exemplified with a small subset of CIP-L.

In a time of multiprocessor machines, message switching networks and process control programming tasks, the foundations of programming distributed systems are among the central challenges for computing sci enti sts. The foundati ons of di stributed programming compri se all the fasci nating questions of computing science: the development of adequate com putational , conceptual and semantic model s for distributed systems, specification methods, verification techniques, transformation rules, the development of suitable representations by programming languages, evaluation and execution of programs describing distributed systems. Being the 7th in a series of ASI Summer Schools at Marktoberdorf, these lectures concentrated on distributed systems. Already during the previous Summer School s at Marktoberdorf aspects of di stributed systems were important periodical topics. The rising interest in distributed systems, their design and implementation led to a considerable amount of research in this area. This is impressively demonstrated by the broad spectrum of the topics of the papers in this vol ume, although they are far from being comprehensive for the work done in the area of distributed systems. Distributed systems are extraordinarily complex and allow many distinct viewpoints. Therefore the literature on distributed systems sometimes may look rather confusing to people not working in the field. Nevertheless there is no reason for resignation: the Summer School was able to show considerable convergence in ideas, approaches and concepts for distributed systems.

This book is the second of two volumes that present the main results which emerged from the project CIP - Computer-Aided, Intuition-Guided Programming - at the Technical University of Munich. Its central theme is program development by transformation, a methodology which is becoming more and more important. Whereas Volume I contains the description and formal specification of a wide spectrum language CIP-L particularly tailored to the needs of transformational programming, Volume II serves a double purpose: First, it describes a system, called CIP-S, that is to assist a programmer in the method of transformational programming. Second, it gives a non-toy example for this very method, since it contains a formal specification of the system core and transformational developments for the more interesting system routines. Based on a formal calculus of program transformations, the informal requirements for the system are stated. Then the system core is formally specified using the algebraic data types and the pre-algorithmic logical constructs of the wide spectrum language CIP-L. It is demonstrated how executable, procedural level programs can be developed from this specification according to formal rules. The extensive collection of these rules is also contained in the book; it can be used as the basis for further developments using this method. Since the system has been designed in such a way that it is parameterized with the concrete programming language to be transformed, the book also contains a guide how to actualize this parameter; the proceeding is exemplified with a small subset of CIP-L.

The title of this book contains the words ALGORITHMIC LANGUAGE, in the singular. This is meant to convey the idea that it deals not so much with the diversity of program ming languages, but rather with their commonalities. The task of formal program develop It allows classifying ment proved to be the ideal frame for demonstrating this unity. concepts and distinguishing fundamental notions from notational features; and it leads immediately to a systematic disposition. This approach is supported by didactic, practical, and theoretical considerations. The clarity of the structure of a programming language de signed according to the principles of program transformation is remarkable. Of course there are various notations for such a language. The notation used in this book is mainly oriented towards ALGOL 68, but is also strongly influenced by PASCAL - it could equally well have been the other way round. In the appendices there are occa sional references to the styles used in ALGOL, PASCAL, LISP, and elsewhere."

Konrad Zuse is one of the great pioneers of the computer age. He created thefirst fully automated, program controlled, freely programmable computer using binary floating-point calculation. It was operational in 1941. He built his first machines in Berlin during the Second World War, with bombs falling all around, and after the war he built up a company that was taken over by Siemens in 1967. Zuse was an inventor in the traditional style, full of phantastic ideas, but also gifted with a powerful analytical mind. Single-handedly, he developed one of the first programming languages, the Plan Calculus, including features copied only decades later in other languages. He wrote numerousbooks and articles and won many honors and awards. This is his autobiography, written in an engagingly lively and pleasant style, full of anecdotes, reminiscences, and philosophical asides. It traces his life from his childhood in East Prussia, through tense wartime experiences and hard times building up his business after the war, to a ripe old age andwell-earned celebrity.

herrschen. Bedeutsam ist auch die Abgrenzung der dritten Ebene, der Ebene der verselb- standigten Variablen und Zeiger. Der vergleichsweise geringe Umfang von Kap. 7 bedeutet einerseits, dass die Beschreibung sich auf Grundsatzliches beschrankt, dem sich viele aus der Literatur der Systemprogrammierung bekannte Einzelheiten unterordnen, beispiels- weise aus D. E. Knuth's, The Art of Computer Programming' oder G. Seegmullers, Ein- fuhrung in die Systemprogrammierung', andererseits aber auch, dass die Vervollstandi- gung der theoretischen Grundlagen noch aussteht. Zu den einzelnen Abschnitten dieses Buches gibt es einen Hintergrund unterschiedlich weit entwickelter mathematischer Theorien. Wichtige Grundbegriffe sind verbandstheore- tischer Natur. Die fundamentalen Arbeiten von D. Scott haben das eindrucksvoll bewie- sen. Bei den Rechenstrukturen des 3. Kapitels steht die moderne Theorie der universellen Algebra im Hintergrund, insbesondere Arbeiten von Birkhoff und Tarski sind hier von Be- deutung. Da wir kein mathematisches Lehrbuch vorlegen, mussen wir uns meistens mit Andeutungen und Hinweisen begnugen. Das Buch hat sich aus Vorlesungen und begleitenden UEbungen entwickelt, die in den letz- ten Jahren an der Technischen Universitat Munchen gehalten wurden. Es entstand in enger Wechselwirkung mit dem Projekt CIP ("Computer-aided Intuition-guided Programming") und dem Teilprojekt "Breitbandsprache und Programmtransformation" im Sonderfor- schungsbereich 49, Programmiertechnik, an der Technischen Universitat Munchen. Bei dem Versuch, fur ein einigermassen abgerundetes, geschlossenes Lehrgebaude der Programmie- rung die Fundamente zu legen, musste vieles fragmentarisch bleiben. In manchen Punkten war es notwendig, Positionen zu beziehen, die auf den ersten Blick unkonventionell erschei- nen moegen, um Erstarrungen zu loesen und einseitige Doktrinen zu korrigieren.

Das Buch wurdigt den grossen Pionier der Informatik, dessen Erfindungen das Computerzeitalter mitbegrundet haben. Erstmals wird die Architektur der Rechenmaschinen detailliert beschrieben. Ein Stuck Lebens-, Computer- und Zeitgeschichte reflektieren Zuses gescheiterte Versuche der Patentanmeldung. Highlight fur Leser: Eine Java-Simulation der Z3, im Buch vorgestellt und uber Internet zuganglich!

Die Kryptologie, eine jahrtausendealte "Geheimwissenschaft," gewinnt fur den Informatiker zusehends praktische Bedeutung in Verbindung mit Datenbanken und Telekommunikation. Neben ihre Nutzung in rechnergestutzten offentlichen Nachrichtensystemen ("offentliche Schlussel") treten interne Anwendungen, die sich auch auf Zugriffsberechtigungen und den Quellenschutz von Software erstrecken.
Der erste Teil des Buches handelt in elf Kapiteln von den Geheimschriften und ihrem Gebrauch - von der Kryptographie. Im zweiten Teil wird in elf weiteren Kapiteln das Vorgehen zum unbefugten Entziffern einer Geheimschrift - die Kryptanalyse - besprochen, wobei sich insbesondere Hinweise fur die Verfahrensbeurteilung ergeben.
Das Buch setzt nur elementare mathematische Kenntnisse voraus. Mit einer Fulle spannender, lustiger und bisweilen anzuglicher Geschichten aus der historischen Kryptologie gewurzt, ist es selbst fur den Laien reizvoll zu lesen.
"

Neben das theoretische Studium der Informatik muB praktische Obung treten, fUr den Anfanger eine Praxis des Programmierens, die an den Besuch der EinfUhrungs vorlesung anschlieBt. Auch hierfiir solI eine Grundlage gelegt werden. Durch die Ver wendung von ALGOL 68, einer begriftlich ebenso reichhaltigen wie differenzierten Sprache mit iibersichtlichem Aufbau, ist der Obergang zu anderen Programrnierspra chen sehr leicht gemacht. Bei der im Text gewlihlten Anordnung ist nachteilig, daB man zu Beginn wenig Material fUr die Ubungen hat. Dem kann abgeholfen werden, indem man die Ab schnitte 1. 1, 1. 4,4. 1 und 4. 2 vorwegnimmt und damit rasch zu Ubungen iiber Codes und Schaltungen kommt. AnschlieBend konnen die Abschnitte 1. 2, 1. 3, 1. 5, 1. 6 zu sammengefaBt werden; auch kann 4. 3 an das dritte Kapitel angehlingt werden. Beim Aufbau dieser Vorlesung konnten wir uns auf konstruktive Beitrlige unserer Herren Kollegen K. SAMELSON, M. PAUL, F. PEISCHL stiitzen. Eine erste Ausarbeitung fertigte im Studienjahr 1967/68 Frau D. MAISON an. Bei den Ubungen zur Vorlesung, insbesondere der Zusammenstellung von Aufgaben, hatten wir die Hilfe von Herrn R. GNATZ und Herrn H. J. WALTHER, welch letzterer auch eine zweite Ausarbeitung im Studienjahr 1968/69 redigierte. Herr Kollege SAMELSON, der die EinfUhrungsvor lesung im Studienjahr 1969/70 las, hat uns wertvolle Kritik geliefert, daneben hatten wir zu einzelnen Kapiteln niitzliche Hinweise von den Herren Kollegen J. EICKEL, P. DEUSSEN, W. HAHN und Frl. U. HILL."

Am 20. Oktober 1980 veranstalteten die Bayerische Akademie der Wis- senschaften und die Technische Vniversitat Miinchen ein Gedachtnis- kolloquium aus AnlaB des 10. Todestages von Robert Sauer. In dieser Festschrift sind die Beitrage abgedruckt, die in der Vormit- tagssitzung unter dem Titel Robert Sauers Leben und Werk - Erinnerungen an Robert Saue- vorgetragen wurden. Die Reihenfolge der Beitrage wurde dem chronolo- gischen Ablauf von Sauers Leben angepaBt. Erganzt wird die Festschrift durch die Bibliographie und biographische Notizen. Organisationskomitee: Prof. Dr. Dr es sc. h. c. Friedrich L. Bauer, TV Miinchen und Bayerische Akademie der Wissenschaften Prof. Dr. Roland Bulirsch, TV Miinchen Prof. Dr. Klaus Samelson t, TV Miinchen Prof. Dr. Gunther Schmidt, TV Miinchen Prof. Dr. Gerhard Seegmiiller, Leibniz-Rechenzentrum der Bayerischen Akademie der Wissenschaften Prof. Dr. Hans J. Stetter, TV Wien Autorenverzeichnis Prof. Dr. Herbert Franke Ordinarius flir Sinologie an der UniversiUit Mtinchen, Prasident der Bayerischen Akade- mie der Wissenschaften Prof. Dr. Wolfgang Wild Ordinarius ftir Theoretische Physik, Prasident der Technischen Universitat Mtinchen Dr. h. c. Johannes von Elmenau Ministerialdirigent i. R. im Bayerischen Staatsministerium ftir Unterricht und Kultus Prof. Dr. Josef Lense emeritierter ordentlicher Professor ftir Hohere Mathematik und Analytische Mechanik an der Technischen Universitat Mtinchen Prof. Dr. Carl Heinz ordentlicher Professor ftir Technische Mechanik an der Rheinisch-Westfiilischen Techni- schen Hochschule Aachen Prof. Dr. Heinz Jordan Vorsitzender des Vorstandes der Deutschen Forschungs- und Versuchs-Anstalt flir Luft- und Raumfahrt Frau Angela Molitoris Kanzlerin i. R. der Technischen Universitat Mtinchen Dr. Dr. h. c. mult.

Fiir den hiennit vorgelegten zweiten Teil und den Anhang "Methodik des Programmie rens" gilt das bereits im Vorwort zum ersten Teil Gesagte. Herrn Dr. H. WOSSNER, der sich weit iiber Beratung hinaus an der Erarbeitung von Aufgaben und Losungen beteiligte, mochten wir besonders danken. Oem Verlag und der Druckerei danken wir fUr die bewiesene groBe Geduld und fUr die ErfUllung unserer Wiinsche beziig lich des manchmal schwierigen Formelsatzes. Miinchen, im Herbst 1975 F. L. BAUER. R. GNATZ . U. HILL Inhaltsverzeichnis* 5. Kapitel Dynamische Speicherverteilung Kellerspeicher 5. 1. 1 Giiltigkeitsbereich und Lebensdauer . . . 3 39 5. 1. 2 Blockstruktur, Organisation des Kellerspeichers 5 40 5. 1. 3 Lebensdauer von Variablen . . 6 41 5. 1. 4 Felddeskriptor. . . . . . . . 6 41 5. 1. 5 Felddeskriptor, Dreiecksmatrix 7 43 5. 1. 6 Speicherverteilung flir Felder 7 45 5. 1. 7 Leitzellentechnik. . . . . . . 8 48 Prozeduren 5. 2. 1 Ackermann-Hermes-Funktion. . . 10 50 5. 2. 2 Struktur rekursiver Prozeduraufrufe 10 52 5. 2. 3 Dynamische Verweisketten . . . . 11 52 5. 2. 4 Dynamische und statische Verweisketten 12 54 5. 2. 5 Prozeduraufrufe. . . . . . . . . . . 13 55 Allgemeine Speicherverteilung 5. 3. 1 Anonyme Objekte . . . . . . . . . . 14 57 5. 3. 2 Speicherverteilung flir anonyme Objekte. 14 58 * Die kursiv gedruckten Seitenzahlen beziehen sich auf die Losung der Aufgabe. VIII Inhaltsverzeichnis 5. 3. 3 Speichern von Verbunden, Organisation der Halde und Speich- bereinigung. . . . . . . 15 59 5. 3. 4 Beispiel aus der Linguistik. 15 61 5. 3. 5 Speicherverteilung fUr Zeichenreihen 16 64 5. 3. 6 Streu-Speicherung. . . . . . . . 17 68 6."

Die hier vorgelegte Sammlung von Aufgaben und Loesungen erganzt das Lehrbuch, Informatik. Eine einfuhrende UEbersicht' von F. L. BAUER und G. Goos, Heidelberger Taschenbucher Bd. 80, 91. Die Anordnung entspricht kapitelweise der Anordnung im Lehrbuch, die- weitere Unterteilung ist hauptsachlich durch didaktische Gesichts- punkte bestimmt. Die Aufgaben sind grossenteils an der TU Munchen in Tutor- ubungen behandelt worden. Sie dienen in der Regel dazu, die in der Vorlesung ein- gefuhrten Begriffsstrukturen auszufullen und zu festigen; dies gilt insbesondere fur die Programmierungsaufgaben, bei denen der banale Nebenzweck, die Gewoehnung an eine formale Notation, nicht in den Vordergrund treten soll. Haufig bringen die Aufgaben auch Erganzungen und Vertiefungen des Stoffes. Im Charakter der Auf- gaben haben wir uns bemuht, Abwechslung zu zeigen. Wenig Raum haben wir dabei dem Typ von Aufgaben gegeben, der so fatalerweise an, programmiertes Lernen' er- innert: Aufgaben, bei denen man mit Ja oder Nein antworten kann; oder Aufgaben, bei denen etwa von funf vorgelegten Programmfassungen herauszufinden ist, welche Fassungen, wenn uberhaupt, richtig sind. Solche Aufgaben regen den Geist nicht an, von intelligenten Studenten werden sie leicht als Qualerei aufgefasst. Sie moegen ge- eignet sein, um im Selbststudium oder im Tutorunterricht mechanisch zu uberprufen, ob man mitkommt', und deshalb ihren Platz haben in einer modemen Didaktik des Massenstudiums. Sie sind unschwer zu konstruieren, und die wenigen Beispiele, die wir bringen, moegen als Anhaltspunkte dienen. Dies gilt ubrigens fur alle Aufgaben: Sie sollen auch zu abgewandelten und neuen AufgabensteIlungen anregen.

Die "Empfehlungen zur Ausbildung auf dem Gebiet der Daten verarbeitung" des Bundesministers fur wissenschaftliche For schung (1968) und die daraufhin gefaBte "Gemeinsame Stel lungnahme des Fachausschusses Informationsverarbeitung der GAMM (Gesellschaft fur Angewandte Mathematik und Mechanik) und des Fachausschusses 6 der NTG (Nachrichtentechnische Gesellschaft)" von 1969 haben in Deutschland zum Aufbau des Informatik-Studiums gefuhrt, der sich auch in einer "Rahmen ordnung fur die Diplom-Prufung in Informatik" niedergeschla gen hat. Man hat dabei den Diplom-Informatiker deutlich yom Diplom-Ingenieur der Elektrotechnik, der Nachrichtentechnik abgegrenzt. Man hat aber glucklicherweise auch darauf geach tet, daB der Diplom-Informatiker eine Verst ndigungsmoglich keit mit dem Ingenieur beh lt und ist nicht in den Fehler verfallen, einen abgekapselten, nur theoretisch-mathematisch interessierten Informatiker anzustreben. Zwar nimmt die Ma thematik teils ihrer unmittelbaren Anwendung wegen, teils als Element der formalen Bildung, die fur Informatiker so ungeheuer wichtig ist wichtiger manchmal als fur Mat- matik. er einen prominenten Anteil der Randstudien des - formatikers ein. Aber auch die Grundlagen der Physik und Elektrotechnik muB der Informatiker beherrschen, wenn er die Brucke zum Ingenieur betreten will. Das vorliegende Buch, aus Vorlesungen entstanden, versucht, aus der uberw ltigenden Fulle des Stoffes die wichtigsten, fur das Verst ndnis einerseits, fur die unmittelbare Anwen dung andererseits unumg nglichen Grundlagen der Physik und Elektrotechnik herauszulosen und unter einem einheitlichen Gesichtspunkt darzustellen. Es ist ein Buch fur Informatiker VI und macht deshalb oft dort Abstriche, wo der Physiker, wo der Elektroingenieur mehr erwarten wUrde."