Specification and Transformation of Programs is short for a methodology of software development where, from a formal specification of a problem, programs correctly solving that problem are constructed by stepwise application of formal, semantics-preserving transformation rules. This book is primarily intended as a general introductory textbook. It can also be seen as a comprehensive account of the transformational methodology developed within the Munich CIP project. The contents of the book reflect the essential steps in a sequential process of software development from an informally stated problem, via a formal problem specification, to a final, efficient program. Aspects considered include linguistic means for describing the various intermediate stages in the process, individual techniques for the transition between these stages, and strategies for applying these techniques. All aspects are illustrated by representative examples.
1. Introduction.- 1.1 Software Engineering.- 1.2 The Problematics of Software Development.- 1.3 Formal Specification and Program Transformation.- 1.4 Our Particular View of Transformational Programming.- 1.5 Relation to Other Approaches to Programming Methodology.- 1.6 An Introductory Example.- 2. Requirements Engineering.- 2.1 Introduction.- 2.2 Some Formalisms Used in Requirements Engineering.- 3. Formal Problem Specification.- 3.1 Specification and Formal Specification.- 3.2 The Process of Formalization.- 3.3 Definition of Object Classes and Their Basic Operations.- 3.4 Additional Language Constructs for Formal Specifications.- 3.5 Structuring and Modularization.- 3.6 Examples.- 3.7 Exercises.- 4. Basic Transformation Techniques.- 4.1 Semantic Foundations.- 4.2 Notational Conventions.- 4.3 The Unfold/Fold System.- 4.4 Further Basic Transformation Rules.- 4.5 Sample Developments with Basic Rules.- 4.6 Exercises.- 5. From Descriptive Specifications to Operational Ones.- 5.1 Transforming Specifications.- 5.2 Embedding.- 5.3 Development of Recursive Solutions from Problem Descriptions.- 5.4 Elimination of Descriptive Constructs in Applicative Programs.- 5.5 Examples.- 5.6 Exercises.- 6. Modification of Applicative Programs.- 6.1 Merging of Computations.- 6.2 Inverting the Flow of Computation.- 6.3 Storing of Values Instead of Recomputation.- 6.4 Computation in Advance.- 6.5 Simplification of Recursion.- 6.6 Examples.- 6.7 Exercises.- 7. Transformation of Procedural Programs.- 7.1 From Tail Recursion to Iteration.- 7.2 Simplification of Imperative Programs.- 7.3 Examples.- 7.4 Exercises.- 8. Transformation of Data Structures.- 8.1 Implementation of Types in Terms of Other Types.- 8.2 Implementations of Types for Specific Environments.- 8.3 Libraries of Implementations.- 8.4 Transformation of Type Systems.- 8.5 Joint Development.- 8.6 An Example: Cycles in a Graph.- 8.7 Exercises.- 9. Complete Examples.- 9.1 Warshall’s Algorithm.- 9.2 The Majority Problem.- 9.3 Fast Pattern Matching According to Boyer and Moore.- 9.4 A Text Editor.- References.
R. Gastmans, Tai Tsun Wu, Belgium) Gastmans, R. (Professor, Institute for Theoretical Physics, University of Leuven, and Research Director, Professor, Institute for Theoretical Physics, University of Leuven, and Research Director, National Fund for Scientific Research, USA) Tai Tsun Wu (Gordon Mackay Professor of Applied Physics, Gordon Mackay Professor of Applied Physics, Harvard University, GASTMANS, Gastmans