283
edits
Pipe-calculus: Difference between revisions
→Process calculus
KalmanKeri (talk | contribs) |
KalmanKeri (talk | contribs) |
||
| Line 135: | Line 135: | ||
'''[[wikipedia:process_calculus | Process calculi]]''' (or '''process algebras''') is an approach for formally modeling concurrent systems. ''Process'' refers to the behavior of a system. The word ''algebra'' denotes an algebraic approach in talking about behavior, while the word ''calculus'' emphasizes the computational aspect of processes. | '''[[wikipedia:process_calculus | Process calculi]]''' (or '''process algebras''') is an approach for formally modeling concurrent systems. ''Process'' refers to the behavior of a system. The word ''algebra'' denotes an algebraic approach in talking about behavior, while the word ''calculus'' emphasizes the computational aspect of processes. | ||
<ref> | <ref> | ||
[https://pdf.sciencedirectassets.com/271538/1-s2.0-S0304397500X05853/1-s2.0-S0304397505000307/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEN%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJIMEYCIQCMZBB4AA1udjrVniZfBXgYqHN4EiFJ94RntrWOYPy56AIhAN9Xlt44hS | J.C.M. Baeten: [https://pdf.sciencedirectassets.com/271538/1-s2.0-S0304397500X05853/1-s2.0-S0304397505000307/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEN%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJIMEYCIQCMZBB4AA1udjrVniZfBXgYqHN4EiFJ94RntrWOYPy56AIhAN9Xlt44hS A brief history of process algebra.], Theoretical Computer Science 335 (2005) 131 – 146 | ||
</ref> | </ref> | ||
There are lots of implementations | There are lots of implementations | ||
| Line 149: | Line 149: | ||
* Actions are the units of behavior. | * Actions are the units of behavior. | ||
* Sequence and nondeterministic choice form basic process algebra (BPA). <ref> | * Sequence and nondeterministic choice form basic process algebra (BPA). <ref> | ||
[https://www.cs.vu.nl/~wanf/BOOKS/procalg.pdf | Wan Fokkink: [https://www.cs.vu.nl/~wanf/BOOKS/procalg.pdf Introduction to Process Algebra], Springer-Verlag | ||
</ref> | </ref> | ||
* The pipe operation can be seen as a restricted, unidirectional parallel composition. | * The pipe operation can be seen as a restricted, unidirectional parallel composition. | ||
| Line 155: | Line 155: | ||
However there are notable differences. | However there are notable differences. | ||
* Communication primitives in mainstream process calculi often unify two conceptual steps: the selection of a communication target (e.g. a channel or another process) and the act of message sending. The two steps are unseparable. For example [[wikipedia:pi-calculus|Π-calculus]] defines ''input prefixing'' <math>c\left(x\right).P</math> and ''output prefixing'' <math>\overline{c} \langle y \rangle.P</math> to denote receiving a name via channel <math>c</math> and sending a name via channel <math>c</math> respectively, before proceeding as <math>P</math>. Although one can introduce as a convention '''synchronization''' where the communicated message is ignored, and '''broadcast''' where a group of processes are receiving messages on the same channel. In pipe-calculus these steps are separated by design. | * Communication primitives in mainstream process calculi often unify two conceptual steps: the selection of a communication target (e.g. a channel or another process) and the act of message sending. The two steps are unseparable. For example [[wikipedia:pi-calculus|Π-calculus]] <ref> Joachim Parrow: [https://courses.cs.vt.edu/~cs5204/fall05-kafura/Papers/PICalculus/parrow~2.pdf An Introduction to the Π-Calculus], chapter to appear in Handbook of Process Algebra, ed. Bergstra, Ponse and Smolka, | ||
Elsevier</ref> defines ''input prefixing'' <math>c\left(x\right).P</math> and ''output prefixing'' <math>\overline{c} \langle y \rangle.P</math> to denote receiving a name via channel <math>c</math> and sending a name via channel <math>c</math> respectively, before proceeding as <math>P</math>. Although one can introduce as a convention '''synchronization''' where the communicated message is ignored, and '''broadcast''' where a group of processes are receiving messages on the same channel. In pipe-calculus these steps are separated by design. | |||
* In pipe-calculus there is no counterpart of '''hiding''' that prevents interference between two groups of processes that are using the same channel name for communication. Since there is no general, bidirectional parallel composition, we don't need a hiding primitive. The pipe operation naturally restricts communication to a pipeline. | * In pipe-calculus there is no counterpart of '''hiding''' that prevents interference between two groups of processes that are using the same channel name for communication. Since there is no general, bidirectional parallel composition, we don't need a hiding primitive. The pipe operation naturally restricts communication to a pipeline. | ||
* In pipe-calculus, if a process fails to synchronize, it is aborted. This is different from the usual implementation where a process that fails to synchronize does not evolve, it keeps "waiting" for a message. This semantics opens up the possibility for asynchronous communication. As a consequence, communication in pipe-calculus is inherently synchronous. | * In pipe-calculus, if a process fails to synchronize, it is aborted. This is different from the usual implementation where a process that fails to synchronize does not evolve, it keeps "waiting" for a message. This semantics opens up the possibility for asynchronous communication. As a consequence, communication in pipe-calculus is inherently synchronous. | ||