Communicating Sequential Processes

Processes 1

1.1 Introduction

Forget for a while about computers and computer programming, and think instead about objects in the world around us, which act and interact with us and with each other in accordance with some characteristic pattern of behaviour. Think of clocks and counters and telephones and board games and vending machines. To describe their patterns of behaviour, first decide what kinds of event or action will be of interest; and choose a different name for each kind. In the case of a simple vending machine, there are two kinds of event:

coin—the insertion of a coin in the slot of a vending machine;
choc—the extraction of a chocolate from the dispenser of the machine.

In the case of a more complex vending machine, there may be a greater variety of events:

in1p—the insertion of one penny;
in2p—the insertion of a two penny coin;
small—the extraction of a small biscuit or cookie;
large—the extraction of a large biscuit or cookie;
out1p—the extraction of one penny in change.

Note that each event name denotes an event class; there may be many occurrences of events in a single class, separated in time. A similar distinction between a class and an occurrence should be made in the case of the letter ‘h’, of which there are many occurrences spatially separated in the text of this book.

The set of names of events which are considered relevant for a particular description of an object is called its alphabet. The alphabet is a permanent predefined property of an object. It is logically impossible for an object to engage in an event outside its alphabet; for example, a machine designed to sell chocolates could not suddenly deliver a toy battleship. But the converse does not hold. A machine designed to sell chocolates may actually never do so—perhaps because it has not been filled, or it is broken, or nobody wants chocolates. But once it is decided that choc is in the alphabet of the machine, it remains so, even if that event never actually occurs.

The choice of an alphabet usually involves a deliberate simplification, a decision to ignore many other properties and actions which are considered to be of lesser interest. For example, the colour, weight, and shape of a vending machine are not described, and certain very necessary events in its life, such as replenishing the stack of chocolates or emptying the coin box, are deliberately ignored—perhaps on the grounds that they are not (or should not be) of any concern to the customers of the machine.

The actual occurrence of each event in the life of an object should be regarded as an instantaneous or an atomic action without duration. Extended or time-consuming actions should be represented by a pair of events, the first denoting its start and the second denoting its finish. The duration of an action is represented by the interval between the occurrence of its start event and the occurrence of its finish event; during such an interval, other events may occur. Two extended actions may overlap in time if the start of each one precedes the finish of the other.

Another detail which we have deliberately chosen to ignore is the exact timing of occurrences of events. The advantage of this is that designs and reasoning about them are simplified, and furthermore can be applied to physical and computing systems of any speed and performance. In cases where timing of responses is critical, these concerns can be treated independently of the logical correctness of the design. Independence of timing has always been a necessary condition to the success of high-level programming languages.

A consequence of ignoring time is that we refuse to answer or even to ask whether one event occurs simultaneously with another. When simultaneity of a pair of events is important (e.g. in synchronisation) we represent it as a single- event occurrence; and when it is not, we allow two potentially simultaneous event occurrences to be recorded in either order.

In choosing an alphabet, there is no need to make a distinction between events which are initiated by the object (perhaps choc) and those which are initiated by some agent outside the object (for example, coin). The avoidance of the concept of causality leads to considerable simplification in the theory and its application.