Bøger i Monographs in Computer Science serien

This text is an introduction to programming in general, and a manual for programming with the language Modula-2 in particular. It is oriented primarily towards people who have already acquired some basic knowledge of programming and would like to deepen their understanding in a more structured way. Neveltheless, an introductory chapter is included for the benefit of the beginner, displaying in a concise form some of the fundamental concepts of computers and their programming. The text is therefore also suitable as a self-contained tutorial. The notation used is Modula-2, which lends itself well for a structured approach and leads the student to a working style that has generally become known under the title of structured programming. As a manual for programming in Modula-2, the text covers practically all facilities of that language. Part 1 covers the basic notions of the variable, expression, assignment, conditional and repetitive statement, and array data structure. Together with Palt 2 which introduces the important concept of the procedure or subroutine, it contains essentially the material commonly discussed in introductory programming courses. Part 3 concerns data types and structures and constitutes the essence of an advanced course on programming. Palt 4 introduces the notion of the module, a concept that is fundamental to the design of larger programmed systems and to programming as team work. The most commonly used utility programs for input and output are presented as examples of modules.

The second half of the twentieth century saw an astonishing increase in computing power; today computers are unbelievably faster than they used to be, they have more memory, they can communicate routinely with remote machines all over the world - and they can fit on a desktop. But, despite this remarkable progress, the voracity of modem applications and user expectations still pushes technology right to the limit. As hardware engineers build ever-more-powerful machines, so too must software become more sophisticated to keep up. Medium- to large-scale programming projects need teams of people to pull everything together in an acceptable timescale. The question of how pro gram- mers understand their own tasks, and how they fit together with those of their colleagues to achieve the overall goal, is a major concern. Without that under- standing it would be practically impossible to realise the commercial potential of our present-day computing hardware. That programming has been able to keep pace with the formidable advances in hardware is due to the similarly formidable advances in the principles for design, construction and organisation of programs. The efficacy of these methods and principles speaks for itself - computer technology is all-pervasive - but even more telling is that they are beginning to feed back and inftuence hardware design as weIl. The study of such methods is called programming methodology, whose topics range over system-and domain-modelling, concurrency, object orientation, program specification and validation. That is the theme of this collection.

This text attempts to change the way we teach logic to beginning students. Instead of teaching logic as a subject in isolation, we regard it as a basic tool and show how to use it. We strive to give students a skill in the propo­ sitional and predicate calculi and then to exercise that skill thoroughly in applications that arise in computer science and discrete mathematics. We are not logicians, but programming methodologists, and this text reflects that perspective. We are among the first generation of scientists who are more interested in using logic than in studying it. With this text, we hope to empower further generations of computer scientists and math­ ematicians to become serious users of logic. Logic is the glue Logic is the glue that binds together methods of reasoning, in all domains. The traditional proof methods -for example, proof by assumption, con­ tradiction, mutual implication, and induction- have their basis in formal logic. Thus, whether proofs are to be presented formally or informally, a study of logic can provide understanding.

A research project to investigate the design and construction of reliable computing systems was initiated by B. Randell at the University of Newcastle upon Tyne in 1972. In over ten years of research on system reliability, a substantial number of papers have been produced by the members of this project. These papers have appeared in a variety of journals and conference proceedings and it is hoped that this book will prove to be a convenient reference volume for research workers active in this important area. In selecting papers published by past and present members of this project, I have used the following criteria: a paper is selected if it is concerned with fault tolerance and is not a review paper and was published before 1983. I have used these criteria (with only one or two exceptions!) in order to present a collection of papers with a common theme and, at the same time, to limit the size of the book to a reasonable length. The papers have been grouped into seven chapters. The first chapter introduces fundamental concepts of fault tolerance and ends with the earliest Newcastle paper on reliability. The project perhaps became well known after the invention of recovery blocks - a simple yet effective means of incorporating fault tolerance in software. The second chapter contains papers on recovery blocks, starting with the paper which first introduced the concept.

This volume is being published for two reasons. The first is to present a collection of previously published articles on the subject of programming methodology that have helped define the field and give it direction. It is hoped that the scientist in the field will find the volume useful as a reference, while the scientist in neighboring fields will find it useful in seriously acquainting himself with important ideas in programming methodology. The advanced student can also study it-either in a course or by himself -in order to learn significant material that may not appear in texts for some time. The second reason for this volume is to make public the nature and work on programming methodology of IFIP Working Group 2.3, hereafter called WG2.3. (IFIP stands for International Federation for Information Processing.) WG2.3 is one of many IFIP Working Groups that have been established to provide international forums for discussion of ideas in various areas. Generally, these groups publish proceedings of some of their meetings and occasionally they sponsor a larger conference that persons outside a group can attend. WG2.3 has been something of a maverick in this respect. From the beginning the group has shunned paperwork, reports, meetings, and the like. This has meant less pUblicity for IFIP and WG2.3, but on the other hand it has meant that meetings could be devoted almost wholly to scientific discussions.

This book develops a theory of formal power series in noncommuting variables, the main emphasis being on results applicable to automata and formal language theory. This theory was initiated around 196O-apart from some scattered work done earlier in connection with free groups-by M. P. Schutzenberger to whom also belong some of the main results. So far there is no book in existence concerning this theory. This lack has had the unfortunate effect that formal power series have not been known and used by theoretical computer scientists to the extent they in our estimation should have been. As with most mathematical formalisms, the formalism of power series is capable of unifying and generalizing known results. However, it is also capable of establishing specific results which are difficult if not impossible to establish by other means. This is a point we hope to be able to make in this book. That formal power series constitute a powerful tool in automata and language theory depends on the fact that they in a sense lead to the arithmetization of automata and language theory. We invite the reader to prove, for instance, Theorem IV. 5. 3 or Corollaries III. 7. 8 and III. 7.- all specific results in language theory-by some other means. Although this book is mostly self-contained, the reader is assumed to have some background in algebra and analysis, as well as in automata and formal language theory.

In writing this book, our goal was to produce a text suitable for a first course in mathematical logic more attuned than the traditional textbooks to the re- cent dramatic growth in the applications oflogic to computer science. Thus, our choice oftopics has been heavily influenced by such applications. Of course, we cover the basic traditional topics: syntax, semantics, soundnes5, completeness and compactness as well as a few more advanced results such as the theorems of Skolem-Lowenheim and Herbrand. Much ofour book, however, deals with other less traditional topics. Resolution theorem proving plays a major role in our treatment of logic especially in its application to Logic Programming and PRO- LOG. We deal extensively with the mathematical foundations ofall three ofthese subjects. In addition, we include two chapters on nonclassical logics - modal and intuitionistic - that are becoming increasingly important in computer sci- ence. We develop the basic material on the syntax and semantics (via Kripke frames) for each of these logics. In both cases, our approach to formal proofs, soundness and completeness uses modifications of the same tableau method in- troduced for classical logic. We indicate how it can easily be adapted to various other special types of modal logics. A number of more advanced topics (includ- ing nonmonotonic logic) are also briefly introduced both in the nonclassical logic chapters and in the material on Logic Programming and PROLOG.

In this book, a programming model is developed that addresses the fundamental issues of "large-scale programming," unifying several concepts from database theory, object-oriented programming and designs of reactive systems. The model and the associated theory have been christened "Seuss." The major goal of Seuss is to simplify multiprogramming. To this end, we separate the concern of concurrent implementation from the core program design problem. A program execution is understood as a single thread of control - sequential executions of actions that are chosen according to some scheduling policy - yet program implementation permits concurrent executions of multiple threads. As a consequence, it is possible to reason about the properties of a program from its single execution thread, whereas an implementation may exploit the inherent concurrency for efficient execution.

Algorithmic Algebra studies some of the main algorithmic tools of computer algebra, covering such topics as Grobner bases, characteristic sets, resultants and semialgebraic sets. The main purpose of the book is to acquaint advanced undergraduate and graduate students in computer science, engineering and mathematics with the algorithmic ideas in computer algebra so that they could do research in computational algebra or understand the algorithms underlying many popular symbolic computational systems: Mathematica, Maple or Axiom, for instance. Also, researchers in robotics, solid modeling, computational geometry and automated theorem proving community may find it useful as symbolic algebraic techniques have begun to play an important role in these areas. The book, while being self-contained, is written at an advanced level and deals with the subject at an appropriate depth. The book is accessible to computer science students with no previous algebraic training. Some mathematical readers, on the other hand, may find it interesting to see how algorithmic constructions have been used to provide fresh proofs for some classical theorems. The book also contains a large number of exercises with solutions to selected exercises, thus making it ideal as a textbook or for self-study.

This book is written as an introduction to the theory of error-free computation. In addition, we include several chapters that illustrate how error-free com- putation can be applied in practice. The book is intended for seniors and first- year graduate students in fields of study involving scientific computation using digital computers, and for researchers (in those same fields) who wish to obtain an introduction to the subject. We are motivated by the fact that there are large classes of ill-conditioned problems, and there are numerically unstable algorithms, and in either or both of these situations we cannot tolerate rounding errors during the numerical computations involved in obtaining solutions to the problems. Thus, it is important to study finite number systems for digital computers which have the property that computation can be performed free of rounding errors. In Chapter I we discuss single-modulus and multiple-modulus residue number systems and arithmetic in these systems, where the operands may be either integers or rational numbers. In Chapter II we discuss finite-segment p-adic number systems and their relationship to the p-adic numbers of Hensel [1908]. Each rational number in a certain finite set is assigned a unique Hensel code and arithmetic operations using Hensel codes as operands is mathe- matically equivalent to those same arithmetic operations using the cor- responding rational numbers as operands. Finite-segment p-adic arithmetic shares with residue arithmetic the property that it is free of rounding errors.

In this book, a programming model is developed that addresses the fundamental issues of 'large-scale programming'. The approach unifies several concepts from database theory, object-oriented programming and designs of reactive systems. The model and the associated theory has been christened "Seuss." The major goal of Seuss is to simplify multiprogramming. To this end, the concern of concurrent implementation is separated from the core program design problem. A program execution is understood as a single thread of control - sequential executions of actions that are chosen according to some scheduling policy. As a consequence, it is possible to reason about the properties of a program from its single execution thread.

A mathematical and logical foundation for the specification and development of interactive systems based on a model that describes systems in terms of their input/output behavior. Based on this model, the authors build a basic method, called FOCUS, that enables interactive systems to be described by characterizing their histories of message interaction. The book progresses from an introduction and guided tour of FOCUS through streams, specifications and their properties, and behavioral, interface, and conditional refinements.

Here, the authors strive to change the way logic and discrete math are taught in computer science and mathematics: while many books treat logic simply as another topic of study, this one is unique in its willingness to go one step further. The book traets logic as a basic tool which may be applied in essentially every other area.

Programming is a fascinating and challenging subject. Unfortunately, it is rarely presented as such. Most often it is taught by "e;induction"e;: features of some famous programming languages are given operational meaning (e.g. a loop "e;goes round and round"e;), a number of examples are shown, and by induction, we are asked to develop other programs, often radically different from the ones we've seen. Basically we are taught to guess our programs, and then to patch up our guesses. Our errors are given the cute name of "e;bugs"e;. Fixing them becomes puzzle-solving, as does finding tricks that exploit or avoid poorly designed features of the programming language. The entire process is time-consuming and expensive. And even so, we are never quite sure if our programs really work in all cases. When approached in this way, programming is indeed a dull activity. There is, however, another approach to programming, an approach in which programs can be developed reliably, with attention to the real issues. It is a practical approach based on methodically developing programs from their specifications. Besides being practical, it is exciting. Many programs can be developed with relative ease. Problems which once were difficult can now be solved by beginners. Elegant solutions bring great satisfaction. This is our subject. We are interested in making programming an exciting topic!

An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language, thus introducing readers to new classes of algorithms which may be analysed more precisely than was the case until now.

The programming language SETL is a relatively new member of the so-called "very-high-level" class of languages, some of whose other well-known mem bers are LISP, APL, SNOBOL, and PROLOG.

One of the reasons that influenced my decision to write this book is my dissatisfaction with the fact that the existing books on programming methodology and the associated concepts, techniques, and programming language notation are largely based on mathematical problems and math ematically oriented algorithms.