Pi calculus
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 | and can be run at the same time. | |
Input prefix | The process waits for input that is sent over the communication channel . The name is bound. | |
Output prefix | The name is sent over the channel before the process begins. | |
Silent Prefix | ||
Replication | The process can make a copy of . | |
New name | can create a new constant within . This is a new communication channel. | |
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:
Translated into words this means:
- Receive on the channel , connect the result and start
- send the value of over the channel and start
- start and at the same time
- create a new channel and start
- make a copy of
- finish the process.
example
An example shows three concurrent processes, whereby the name is only known to the first two components.
The first two components can communicate over the channel , the name is bound to.
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
- ↑ Concurrent programming: practice and semantics. 2011, accessed October 8, 2018 .
- ↑ a b PI calculus process algebra. Retrieved October 8, 2018 .