Springer International Publishing AG 2017
Benjamin Weyers , Judy Bowen , Alan Dix and Philippe Palanque (eds.) The Handbook of Formal Methods in Human-Computer Interaction HumanComputer Interaction Series 10.1007/978-3-319-51838-1_1
1. State of the Art on Formal Methods for Interactive Systems
Abstract
This chapter provides an overview of several formal approaches for the design, specification, and verification of interactive systems. For each approach presented, we describe how they support both modelling and verification activities. We also exemplify their use on a simple example in order to provide the reader with a better understanding of their basic concepts. It is important to note that this chapter is not self-contained and that the interested reader should get more details looking at the references provided. The chapter is organized to provide a historical perspective of the main contributions in the area of formal methods in the field of humancomputer interaction. The approaches are presented in a semi-structured way identifying their contributions alongside a set of criteria. The chapter is concluded by a summary section organizing the various approaches in two summary tables reusing the criteria previously derived.
1.1 Introduction
Building reliable interactive systems has been identified as an important and difficult task from the late 1960s on (Parnas ) and methods and techniques developed in computer science have been applied, adapted, or extended to fit the need of interactive systems since then. Those needs have been thoroughly studied over the years, and the complexity of interactive systems has followed or even pre-empted the non-interactive part of computing systems. Such evolution is mainly due to the technological progression of input and output devices and their related interaction techniques.
Another important aspect is related to the intrinsic nature of the interactive systems as clearly identified in Peter Wegners paper (Wegner ) as the input chain is not defined prior to the execution and the output chain is processed (by the users) before the machine (in the meaning of Turing machine) halts.
Two books (Harrison and Thimbleby ) have been published to gather contributions related to the adaptation and extension of computer science modelling and verification techniques to the field of interactive systems. Contributions in these books were covering not only the interaction side, the computation side (usually called functional core), but also the human side by presenting modelling techniques applied, for instance, to the description of the users mental models.
Over the years, the community in Engineering Interactive Computing Systems has been investigating various ways of using Formal Methods for Interactive Systems but has also broadened that scope proposing architectures, processes, or methods addressing the needs of new application domains involving new interaction techniques. Simultaneously, the Formal Methods for Interactive Systems community has been focusing on the use of formal methods in the area of interactive computing systems.
This chapter summarises selected contributions from those two communities over the past years. For each approach presented, we describe how they both support modelling as well as verification activities. We also exemplify their use on a simple example in order to provide the reader with a better understanding of their basic concepts. It is important to note that this chapter is not self-contained and that the interested reader should get more details looking at the references provided. This chapter is organized to provide a historical perspective of the main contributions in the area of formal methods in the field of humancomputer interaction. Lastly, the approaches are presented in a semi-structured way identifying their contributions alongside a set of criteria. This chapter is concluded by a summary section organizing the various approaches in two summary tables reusing the criteria previously used.
1.2 Modelling and Formal Modelling
In systems engineering, modelling activity consists of producing a theoretical view of the system under study. This modelling activity takes place using one or several notations. The notation(s) allows engineers to capture some part of the system while ignoring other ones. The resulting artefact is called a model and corresponds to a simplified view of the real system.
In the field of software engineering, modelling is a well-established practice that was very successfully adopted in the area of databases (Chen ) moved away from modelling considering that on-time delivery of software is a much more important quality than correct functioning, as bugs can always be fixed in the next delivered version.
However, building models in the analysis, specification, design, and implementation of software bring a lot of advantages (Booch ):
to abstract away from low-level details;
to focus on some aspects while avoiding others (less relevant ones);
to describe and communicate about the system under design with the various stakeholders;
to better understand the system under development and the choices that are made; and
to support the identification of relationships between various components of the system.
Beyond these advantages, modelling (when supported by notations offering structuring mechanisms) helps designers to break complex applications into smaller manageable parts (Navarre et al. ).
When the notation used for building models has rigorous theoretical foundations, these models can be analysed in order to check soundness or detect flaws. Such activity, which goes beyond modelling, is called verification and validation and is detailed in the next section.
1.3 Verification and Validation
The notation used for describing models can be at various levels of formality that can be classified as informal, semi-formal, and formal (Garavel and Graf ):
Informal models are expressed using natural language or loose diagrams, charts, tables, etc. They are genuinely ambiguous, which means that different readers may have different understanding of their meaning. Those models can be parsed and analysed (e.g. spell checkers for natural text in text editors), but their ambiguity will remain and it is thus impossible to guarantee that they do not contain contradictory statements.
Semi-formal models are expressed in a notation that has a precise syntax but has no formal (i.e. mathematically defined) semantics. Examples of semi-formal notations are UML class diagrams, data flow diagrams, entity relationship graphical notation, UML state diagrams, etc.