Common use of CSP Clause in Contracts

CSP. ‌ The language of CSP was first described by Hoare [Hoa85]. It is a pro- cess algebra that can be used to describe systems composed by interacting components, which are independent self-contained entities (called processes) with particular interfaces that are used to interact with the environment. In [Ros98], a new version of CSP was presented: it differs from Hoare’s ver- sion only on the treatment of alphabets. It is the later version that forms the basis of FDR, a tool that model-checks a machine-processable subset of CSP, called CSPM, which is a combination of an ASCII version of CSP with an expression language inspired on functional languages. A link between the CSP and CSPM syntaxes can be found in [Ros98]. In what follows, we briefly describe the most important CSP constructs. → The two most basic CSP processes are STOP and SKIP ; the former dead- locks, and the latter does nothing and terminates. If P is a CSP process, and a an event, then the prefixing a P is initially able to perform only a, and after performing a it behaves as P . A boolean guard may be associated with a process: given a predicate g , if the condition g is true, the process g & P behaves like P ; it deadlocks otherwise. Processes P 1 and P 2 can be combined in sequence using the sequence operator: P 1; P 2. This process executes the process P 2 after the execution of P 1 terminates. The external choice P 1 Q P 2 initially offers events of both processes. The performance of the first event resolves the choice in favour of the process that performs \ | | H | | |

CSP. ‌ The language of CSP was first described by Hoare [Hoa85]. It is a pro- cess algebra that can be used to describe systems composed by interacting components, which are independent self-contained entities (called processes) with particular interfaces that are used to interact with the environment. In [Ros98], a new version of CSP was presented: it differs from Hoare’s ver- sion only on the treatment of alphabets. It is the later version that forms the basis of FDR, a tool that model-checks a machine-processable subset of CSP, called CSPM, which is a combination of an ASCII version of CSP with an expression language inspired on functional languages. A link between the CSP and CSPM syntaxes can be found in [Ros98]. In what follows, we briefly describe the most important CSP constructs. → | | The two most basic CSP processes are STOP and SKIP ; the former dead- locks, and the latter does nothing and terminates. If P is a CSP process, and a an event, then the prefixing a P is initially able to perform only a, and after performing a it behaves as P . A boolean guard may be associated with a process: given a predicate g , if the condition g is true, the process g & P behaves like P ; it deadlocks otherwise. Processes P 1 and P 2 can be combined in sequence using the sequence operator: P 1; P 2. This process executes the process P 2 after the execution of P 1 terminates. The external choice P 1 Q P 2 initially offers events of both processes. The performance of the first event resolves the choice in favour of the process that performs it. Differently from the external choice, the environment has no control over the internal choice P 1 P 2, in which the process internally (nondetermin- istically) resolves the choice. The sharing parallel composition P 1 [ cs ] P 2 synchronises P 1 and P 2 on the channels in the set cs; events that are not \ | | H | listed occur independently. Differently, in the alphabetised parallel composi- tion P 1 [cs1 cs2] P 2, the processes P 1 and P 2 synchronise on the channels that are in the intersection between cs1 and cs2; events that are not in this intersection occur independently. Processes can also be composed in inter- leaving: in P 1 P 2, both processes run independently. The event hiding operator P cs is used to encapsulate the events that are in the channel set cs. This removes these events from the interface of P , which become no longer visible to the environment. CSP also provides finite iterated operators that can be used to generalise the binary operators of sequence, external and internal choice, parallel composition, and interleaving. A few other process constructors are available in CSP but omitted here for conciseness. Further- more, we also omit the syntax of the expression language accepted in CSP, which can be found in [Ros98]. By way of illustration, we consider the development of a parking spot pre- sented in Figure 2. In CSP, every channel used in the specification must be declared. For instance, channel enter, leave declares the channels enter and leave, which indicate that a customer has entered the parking spot and left it, respectively. Our abstract specification of a parking spot, PARKING SPOT only requires that two customers cannot enter in sequence; the first one must leave before the next one enters. Using FDR’s assertion commands, we can verify that the abstract specification of the parking spot is deadlock free, divergence free, and deterministic. This is indicated in FDR with a C on the channel enter, leave | | PARKING SPOT = enter → leave → PARKING SPOT datatype ALPHA = a b datatype ID = Letter.ALPHA unknown channel cash, ticket, change : ID MACHINE = cash?id → ▇▇▇▇▇▇.▇▇ → ▇▇▇▇▇▇.▇▇ → MACHINE CUSTOMER(id ) = (enter → cash!id → (▇▇▇▇▇▇.▇▇ → ▇▇▇▇▇▇.▇▇ → SKIP Q ▇▇▇▇▇▇.▇▇ → ▇▇▇▇▇▇.▇▇ → SKIP )); leave → CUSTOMER(id ) (CUSTOMER(Letter.a) |[{| cash, ticket, change |}]| MACHINE ) \ {| cash, ticket, change |} Figure 2: A Simple CSP Example left of the assertion in Figure 1. | | Our concrete parking spot, PAID PARKING SPOT is a paid version of a public parking spot with a pay and display parking permit machine that accepts cash, and issues tickets and change. First, we declare a datatype that represents simple identifications. Datatypes can be divided into two groups: basic datatypes and complex datatypes. The former is defined in terms of simple constants and the latter uses constructors that are applied to types. In Figure 2, datatype ALPHA = a b defines a datatype ALPHA: ▇▇▇▇- ▇▇▇▇▇ of type ALPHA can assume either value a or b. On the other hand, datatype ID = Letter.ALPHA unknown defines a ID that represents iden- tifications. The constructors Letter receives an ALPHA value and returns a value of type ID (for example, Letter.a); another possibility is the unknown ID. Next, we declare all the new channels that are used in the concrete specifica- tion. Then, we declare the MACHINE process, which implements the func- tions of issuing tickets and change, after receiving the cash. After entering the parking spot, a CUSTOMER must interact with the ticket MACHINE by inserting the cash into it. The CUSTOMER can then pick the ticket and the change in any order, and finally, leave the parking spot. In order to uniquely identify each customer, we parameterise the process CUSTOMER with an identification, which is used to identify this customer while interact- ing with the machine via channels cash, ticket , and change. This guarantees that the machine will only issue the ticket and the change to the customer who inserted the cash. The paid parking spot is modelled by the process PAID PARKING SPOT . It is a parallel composition of the processes CUSTOMER and MACHINE ; they synchronise on cash, ticket and change, which are hidden from the en- vironment. The specification PAID PARKING SPOT must always allow only one customer to enter, and then to leave the parking spot. The asser- tion assert PARKING SPOT [FD = PAID PARKING SPOT captures the failures divergence refinement check to be carried out. 2.1.1 CSP semantic models‌ CSP offers a number of semantical approaches. A process written in CSP may be understood in terms of operational semantics (where the process is transformed to a labelled transition system, with transitions representing communications); or in terms of algebraic semantics (where properties of a process – such as equivalence to some other process – may be deduced by syntactic transformations on the process text following a set of algebraic laws); or in terms of denotational semantics (where the process corresponds to a value in some mathematical model, typically a complete partial order or a complete metric space). The latter is the one of particular interest for our work. In what follows we briefly describe the three denotational models: traces, failures and failures-divergences [Ros98].