Pi calculus

This article or section is not worded in a generally understandable manner. The shortcomings are described under Discussion: Pi Calculus . If you remove this block, it is founded, please visit the article talk page, and fill up the project page section created automatically Wikipedia: Incomprehensible Item # pi-calculus to{{ Done | 1 = ~~~~}}.

The π-calculus is a process calculus that was developed by Robin Milner , Joachim Parrow and David Walker in the 1990s as the successor to the Calculus of Communicating Systems (CCS). With the π-calculus, concurrent systems that change during runtime can be described. Despite its simple syntax , it is very expressive; functional programming can be expressed in it. Extensions such as the spi calculus and “applied π” have been used successfully to break encryption protocols .

One application purpose of this type of method is the simulation of concurrency such as threads or processes on modern multi-core processors, since when programming software that uses this functionality, complex boundary conditions come into play that can be more easily managed with such a simulation are. Further applications have arisen in molecular biology and for modeling business processes .

Constructs

The process algebra of the π-calculus is strongly linked to names . The double role of names as communication channels and variables ensures easy application.

construct	syntax	description
Concurrency	${\displaystyle P\mid Q}$	${\displaystyle P}$and can be run at the same time. ${\displaystyle Q}$
Input prefix	${\displaystyle c\left(x\right).P}$	The process waits for input that is sent over the communication channel . The name is bound. ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle c}$ ${\displaystyle x}$
Output prefix	${\displaystyle {\overline {c}}\langle y\rangle .P}$	The name is sent over the channel before the process begins. ${\displaystyle y}$ ${\displaystyle c}$ ${\displaystyle P}$
Silent Prefix	${\displaystyle \tau .P}$
Replication	${\displaystyle !\,P}$	The process can make a copy of . ${\displaystyle P}$ ${\displaystyle P}$
New name	${\displaystyle \left(\nu x\right)P}$	${\displaystyle P}$can create a new constant within . This is a new communication channel. ${\displaystyle x}$ ${\displaystyle P}$
Zero process	0	The process has been completed and stopped.

On the one hand, this minimal definition of the π-calculus prevents programs in the usual sense. On the other hand, it is easy to add the missing control structures and branches.

Formal definition

Let X be a set of names and let x and y be elements of this set. The following grammar in Backus-Naur form then describes the language of the π-calculus:

${\displaystyle {\begin{aligned}P,Q::=\,&x(y).P\,\,\,\\|\,\,\,&{\overline {x}}\langle y\rangle .P\,\,\,\\|\,\,\,&P|Q\,\,\,\\|\,\,\,&(\nu x)P\,\,\,\\|\,\,\,&!P\,\,\,\\|\,\,\,&0\end{aligned}}}$

Translated into words this means:

• Receive on the channel , connect the result and start ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle P}$
• send the value of over the channel and start ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle P}$
• start and at the same time ${\displaystyle P}$ ${\displaystyle Q}$
• create a new channel and start ${\displaystyle x}$ ${\displaystyle P}$
• make a copy of ${\displaystyle P}$
• finish the process.

example

An example shows three concurrent processes, whereby the name is only known to the first two components. ${\displaystyle x}$

${\displaystyle {\begin{aligned}(\nu x)&\;(\;{\overline {x}}\langle z\rangle .\;0\\&\;|\;x(y).\;{\overline {y}}\langle x\rangle .\;x(y).\;0\;)\\&\;|\;z(v).\;{\overline {v}}\langle v\rangle .0\end{aligned}}}$

The first two components can communicate over the channel , the name is bound to. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$

literature

• Robin Milner: Communicating and Mobile Systems: the Pi-Calculus , Cambridge University Press, 1999, ISBN 0-521-65869-1
• Robin Milner: The Polyadic π-Calculus: A Tutorial , Logic and Algebra of Specification, 1993.
• Davide Sangiorgi and David Walker: The Pi-calculus: A Theory of Mobile Processes , Cambridge University Press, ISBN 0-521-78177-9

Web links

• PiCalculus
• Calculi for Mobile Processes
• FAQ on Pi-Calculus (PDF file; 196 kB)
• Concurrent programming: practice and semantics
• Modeling of biological processes

Individual evidence

1. ↑ Concurrent programming: practice and semantics. 2011, accessed October 8, 2018 . 
2. ↑ ^{a b} PI calculus process algebra. Retrieved October 8, 2018 .