Formal Approaches to Computing and Information Technology (FACIT) – serie

The Idea of Program Refinement Programs are complex. They are typically so complex, that they go beyond the full comprehension even of the programmer or team who designed them, with all the consequences this has. How can we cope with such complexity in a satisfactory way? An approach, advocated for a long time, is to separate a concise specification of a program - the "what" - from a possibly involved implementation - the "how". Once a specification is obtained from the set of requirements on the program, there can still be a large gap to an efficient implementation. The development from specification to implementation can then proceed by a succession oflayers, such that each layer is a refinement of the previous one. Design decisions can be introduced in refinement steps one at a time. By this, the refinement steps can be kept small and manageable. Still, the set of all requirements can be far too large to be taken completely into account in the initial specification. Even if they could, they might obscure issues more than clarify them. For example: • An information system for stored goods needs to produce an error message on il­ legal input. Yet, the exact wording - and even the language - of those messages is irrelevant for an understanding of the essence of the system. • A banking application interacts with customers with a graphical interface. Yet the specification of the graphical layout is secondary compared to the specification of the possible transactions.

Objectives of this Book This book is an introduction to a set of software specification methods. Its tar­ geted audience are readers who do not wish to read pages of definitions in order to understand the basics of a method. The same case study is used to introduce each method, following a rigorously uniform presentation format. Special care has been devoted to ensure that specifications do not deviate from the case study text. As much as the method allows, what is specified is what appears in the case study text. The benefits are two-fold. First, the reader can easily switch from one method to another, using his knowledge of the case study as a leverage to understand a new method. Second, it becomes easier to compare methods, because the same behavior is specified in each case. Each method presentation follows the same pattern. The concepts are pro­ gressively introduced when they are needed. To illustrate the specification pro­ cess, questions that the specifier should raise during the analysis of the case study are stated. Answers are provided as if they were given by an imaginary client. The question/answer process guides the derivation of the specification. Interestingly, the questions raised depend on the method, which is illustrative of the differences between them.

This volume presents twelve case studies that use RAISE - Rigorous Approach to Industrial Software Engineering - to construct, analyse, develop and apply formal specifications. The case studies cover a wide range of application areas including government finance, case-based reasoning, multi-language text processing, object-oriented design patterns, component-based software design and natural resource management. By illustrating the variety of uses of formal specifications, the case studies also raise questions about the creation, purpose and scope of formal models before they are built. Additional resources and complete specifications for all of the case studies and the RAISE tools used to process them, are available on the World Wide Web. This book will be of particular interest to software engineers, especially those responsible for the initial stages of requirements engineering and software architecture and design. It will also be of interest to academics and students on advanced formal methods courses.

Industrial Strength Formal Methods in Practice provides hands-on experience and guidance for anyone who needs to apply formal methods successfully in an industrial context. Each chapter is written by an expert in software engineering or formal methods, and contains background information, introductions to the techniques being used, actual fragments of formalised components, details of results and an analysis of the overall approach. It provides specific details on how to produce high-quality software that comes in on-time and within budget. Aimed mainly at practitioners in software engineering and formal methods, this book will also be of interest to the following groups; academic researchers working in formal methods who are interested in evidence of their success and in how they can be applied on an industrial scale, and students on advanced software engineering courses who need real-life specifications and examples on which to base their work.

Systems, Models and Measures seeks to bridge the gap between the 'classical' and the newer technologies by constructing a systematic measurement framework for both. The authors use their experience as consultants in systems, software and quality engineering to take the subject from concept and theory, via strategy and procedure, to tools and applications. The book clarifies the key notions of system, model, measurement, product, process, specification and design. Practical examples demonstrate the 'architecture' of measurement schemes, extending them to object-oriented and subjective measurement. A detailed case study provides a measurement strategy for formal specifications, including Prolog, Z and VDM. The reader will be able to formulate problems in measurable terms, appraise and compare formal specifications, assess and enhance existing measurement practices, and devise measurement schemes for describing objective characteristics and expressing value judgements.

Formal specifications were first used in the description of program­ ming languages because of the central role that languages and their compilers play in causing a machine to perform the computations required by a programmer. In a relatively short time, specification notations have found their place in industry and are used for the description of a wide variety of software and hardware systems. A formal method - like VDM - must offer a mathematically-based specification language. On this language rests the other key element of the formal method: the ability to reason about a specification. Proofs can be empioyed in reasoning about the potential behaviour of a system and in the process of showing that the design satisfies the specification. The existence of a formal specification is a prerequisite for the use of proofs; but this prerequisite is not in itself sufficient. Both proofs and programs are large formal texts. Would-be proofs may therefore contain errors in the same way as code. During the difficult but inevitable process of revising specifications and devel­ opments, ensuring consistency is a major challenge. It is therefore evident that another requirement - for the successful use of proof techniques in the development of systems from formal descriptions - is the availability of software tools which support the manipu­ lation of large bodies of formulae and help the user in the design of the proofs themselves.

Notations for Software Design aims to explain formal specification and design to practitioners in software development, and to set out the ingredients of a sound software design process. It examines COLD-1, which is currently being implemented by Philips in many of its business centres. The fact that it is a wide-spectrum language which supports many styles of specification makes it an excellent basis for the volume. It also examines some widely-used informal techniques, such as Venn diagrams and Petri nets, thus creating a strong link between current and future practice. Rather than proposing new pictorial notations the authors place existing ones into a coherent framework, and explain practical ways of exploiting them in conjunction with COLD-1.

On the Refinement Calculus gives one view of the development of the refinement calculus and its attempt to bring together - among other things - Z specifications and Dijkstra's programming language. It is an excellent source of reference material for all those seeking the background and mathematical underpinnings of the refinement calculus.

Rationale Software engineering aims to develop software by using approaches which en­ able large and complex program suites to be developed in a systematic way. However, it is well known that it is difficult to obtain the level of assurance of correctness required for safety critical software using old fashioned program­ ming techniques. The level of safety required becomes particularly high in software which is to function without a break for long periods of time, since the software cannot be restarted and errors can accumulate. Consequently programming for mission critical systems, for example, needs to address the requirements of correctness with particular care. In the search for techniques for making software cheaper and more reliable, two important but largely independent influences have been visible in recent years. These are: • Object Technology • Formal Methods First, it has become evident that objects are, and will remain an important concept in software. Experimental languages of the 1970's introduced various concepts of package, cluster, module, etc. giving concrete expression to the importance of modularity and encapsulation, the construction of software com­ ponents hiding their state representations and algorithmic mechanisms from users, exporting only those features (mainly the procedure calling mechanisms) which were needed in order to use the objects. This gives the software com­ ponents a level of abstraction, separating the view of what a module does for the system from the details of how it does them.

Formal Object-Oriented Development provides a comprehensive overview of the use of formal object-oriented methods; it covers how and where they should be introduced into the development process, how they can be introduced selectively for critical parts of an application, and how to incorporate them effectively into existing deveopmental practices.The text is extensively illustrated, both with tutorial and self-assessment excercises and with examples of industrial applications from the reactive systems domain. This book will be of interest to academic and industrial researchers, software engineering practitioners and consultants, and will also provide invaluable reading material for students learning Z++ and VDM++.

B is one of the few formal methods which has robust, commercially-available tool support for the entire development lifecycle from specification through to code generation. This volume provides a comprehensive introduction to the B Abstract Machine Notation, and to how it can be used to support formal specification and development of high integrity systems. A strong emphasis is placed on the use of B in the context of existing software development methods, including object-oriented analysis and design. The text includes a large number of worked examples, graduated exercises in B AMN specification and development (all of which have been class-tested), two extended case studies of the development process, and an appendix of proof techniques suitable for B. Based on material which has been used to teach B at postgraduate and undergraduate level, this volume will provide invaluable reading a wide range of people, including students, project technical managers and workers, and researchers with an interest in methods integration and B semantics.

Formal methods have already been shown to improve the development process and quality assurance in system design and implementation. This is an examination of whether these benefits also apply to the field of human-computer interface design and implementation, and whether formal methods can offer useful support in usability evaluation and obtaining more reliable implementations of user requirements. The main aim of this text is to compare the different approaches and examine which particular type of implementation and problem each one is best suited to. To enable the reader to compare and contrast the approaches as easily as possible, each one is applied to the same case study - the specification of an ideal Netscape-like Web browser and HTML page server.

A Theory and Practice of Program Development provides a comprehensive introduction to a software development method based on VDM-SL. Each development step is rigorously justified, and the strategies and transformations used are justified and explained ma thematically. The approach provides the formal semantics of a simple, but powerful, wide-spectrum programming language and gives a formal definition of both algorithmic and data refinement. Unlike other texts, it covers both the theory and practice of program development. Although based on VDM-SL, no knowledge of this language is assumed, thus making it widely accessible. A Theory and Practice of Program Development is intended for 3rd/4th year undergraduate and postgraduate students taking formal methods and software engineering; software developers involved in the production of provably correct computer systems and reusa ble design and the problems of reusable code.

This volume provides a companion to "Proof in VDM: a Practitioner's Guide". Using the proof theory presented in that volume, it examines a variety of realistic case studies which illustrate different aspects of the use of proof in formal development. Rather than concentrating on the construction of formal specifications, it devotes two chapters to validation using proof, describing how proofs in VDM can be constructed via installations of the PVS and Isabelle theorem provers. The book provides reference material for practitioners of formal methods who need to construct proofs, students requiring a detailed introduction to the practicalities of proof, and researchers interested in the role of theorem proving in formal development and relevant tool support.