Editing Process calculus (section)

== Mathematics of processes ==

To define a '''process calculus''', one starts with a set of ''names'' (or ''[[Channel (programming)|channels]]'') whose purpose is to provide means of communication.  In many implementations, channels have rich internal structure to improve efficiency, but this is abstracted away in  most theoretic models.  In addition to names, one needs a means to form new processes from old ones. The basic operators, always present in some form or other, allow:<ref>{{cite conference|last1=Baeten |first1=J.C.M. |first2=M. | last2=Bravetti |title=A Generic Process Algebra 
  | book-title = Algebraic Process Calculi: The First Twenty Five Years and Beyond (BRICS Notes Series NS-05-3)
  | publisher=BRICS, Department of Computer Science, University of Aarhus 
  |date=August 2005
  | location = Bertinoro, Forlì, Italy|
url=http://www.brics.dk/NS/05/3/ |access-date=2007-12-29}}</ref>

* parallel composition of processes
* specification of which channels to use for sending and receiving data
* sequentialization of interactions
* hiding of interaction points
* recursion or process replication

=== Parallel composition ===
Parallel composition of two processes <math>\mathit{P}</math> and <math>\mathit{Q}</math>, usually written <math>P \vert Q</math>, is the key primitive distinguishing the process calculi from sequential models of computation. Parallel composition allows computation in <math>\mathit{P}</math> and <math>\mathit{Q}</math> to proceed simultaneously and independently. But it also allows interaction, that is synchronisation and flow of information from <math>\mathit{P}</math> to <math>\mathit{Q}</math> (or vice versa) on a channel shared by both. Crucially, an agent or process can be connected to more than one channel at a time.

Channels may be synchronous or asynchronous. In the case of a synchronous channel, the agent sending a message waits until another agent has received the message. Asynchronous channels do not require any such synchronization.  In some process calculi (notably the [[π-calculus]]) channels themselves can be sent in messages through (other) channels, allowing the topology of process interconnections to change. Some process calculi also allow channels to be ''created'' during the execution of a computation.

=== Communication ===
Interaction can be (but isn't always) a ''directed'' flow of information.  That is, input and output can be distinguished as dual interaction primitives. Process calculi that make such distinctions typically define an input operator (''e.g.'' <math>x(v)</math>) and an output operator (''e.g.'' <math>x\langle y\rangle</math>), both of which name an interaction point (here <math>\mathit{x}</math>) that is used to synchronise with a dual interaction primitive.

Should information be exchanged, it will flow from the outputting to the inputting process. The output primitive will specify the data to be sent. In <math>x\langle y\rangle</math>, this data is <math>y</math>.  Similarly, if an input expects to receive data, one or more [[bound variables]] will act as place-holders to be substituted by data, when it arrives. In <math>x(v)</math>, <math>v</math> plays that role. The choice of the kind of data that can be exchanged in an interaction is one of the key features that distinguishes different process calculi.

=== Sequential composition ===

Sometimes interactions must be temporally ordered. For example, it might be desirable to specify algorithms such as: ''first receive some data on <math>\mathit{x}</math> and then send that data on <math>\mathit{y}</math>''.  ''Sequential composition'' can be used for such purposes. It is well known from other models of computation. In process calculi, the sequentialisation operator is usually integrated with input or output, or both. For example, the process <math>x(v)\cdot P</math> will wait for an input on <math>\mathit{x}</math>. Only when this input has occurred will the process <math>\mathit{P}</math> be activated, with the received data through <math>\mathit{x}</math> substituted for identifier <math>\mathit{v}</math>.

=== Reduction semantics ===
The key operational reduction rule, containing the computational essence of process calculi, can be given solely in terms of parallel composition, sequentialization, input, and output. The details of this reduction vary among the calculi, but the essence remains roughly the same. The reduction rule is:

:<math>
x\langle y\rangle \cdot P \; \vert \; x(v)\cdot Q  \longrightarrow P \; \vert \; Q[^y\!/\!_v]
</math>

The interpretation to this reduction rule is:
# The process <math>x\langle y\rangle \cdot P</math> sends a message, here <math>\mathit{y}</math>, along the channel <math>\mathit{x}</math>. Dually, the process <math>x(v)\cdot Q</math> receives that message on channel <math>\mathit{x}</math>.
# Once the message has been sent, <math>x\langle y\rangle \cdot P</math> becomes the process <math>\mathit{P}</math>, while <math>x(v)\cdot Q</math> becomes the process <math>Q[^y\!/\!_v]</math>, which is <math>\mathit{Q}</math> with the place-holder <math>\mathit{v}</math> substituted by <math>\mathit{y}</math>, the data received on <math>\mathit{x}</math>.
The class of processes that <math>\mathit{P}</math> is allowed to range over as the continuation of the output operation substantially influences the properties of the calculus.

=== Hiding ===
Processes do not limit the number of connections that can be made at a given interaction point. But interaction points allow interference (i.e. interaction). For the
synthesis of compact, minimal and compositional systems, the ability to restrict interference is crucial. ''Hiding'' operations allow control of the connections made between interaction points when composing
agents in parallel. Hiding can be denoted in a variety of ways. For example, in the [[π-calculus]] the hiding of a name <math>\mathit{x}</math> in <math>\mathit{P}</math> can be expressed as <math>(\nu\; x)P</math>, while in [[Communicating sequential processes|CSP]] it might be written as <math>P \setminus \{x\}</math>.
<!--
(Commented out because "Figure" is missing - can the Figure be added?)
Figure shows the effect of going from ''P'' to (''ν'' ''x'')''P''.  The process ''P'' on the left can interact with the outside world on ''x'', ''y'' and ''z''. In contrast, (''ν'' ''x'')''P'' on the right can only use ''y'' and ''z'' for this purpose. The restriction does not prevent usage of ''x'' inside ''P''. But what happens if ''x'' gets sent to a process outside of (''ν'' ''x'')''P'', as may happen in (''ν'' ''x'')(''y''<''x''> | ''Q''), provided ''x'' \neq ''y''?  Whether or not it is possible to communicate a name hidden this way is another important point of divergence between different calculi.
-->

=== Recursion and replication ===
The operations presented so far describe only finite interaction and are consequently insufficient for full computability, which includes non-terminating behaviour. ''[[Recursion]]'' and ''[[Replication (computing)|replication]]'' are operations that allow finite descriptions of infinite behaviour.  Recursion is well known from the sequential world. Replication <math>!P</math> can be understood as abbreviating the parallel composition of a countably infinite number of <math>\mathit{P}</math> processes:

:<math>
!P = P \mid !P

</math>

=== Null process ===
Process calculi generally also include a ''null process'' (variously denoted as <math>\mathit{nil}</math>, <math>0</math>, <math>\mathit{STOP}</math>, <math>\delta</math>, or some other appropriate symbol) which has no interaction points. It is utterly inactive and its sole purpose is to act as the inductive anchor on top of which more interesting processes can be generated.