patternMinor
Why do some authors not include summation in the $\pi$-Calculus?
Viewed 0 times
whythecalculusincludeauthorssomesummationnot
Problem
In Robin Milner's book "Communicating and Mobile Systems: the $\pi$-Calculus", on page 87, the set of expressions of the $\pi$-Calculus is defined as
$$P ::= \sum_{i\in I} \pi_i.P_i\ {\huge|}\ P_1|P_2 \ {\huge|}\ \operatorname{new} a P\ {\huge|}\ !P$$
So in Milner's formulation, the summation of processes is included, just as in CCS. However, some authors do not include it: in Mathew Hennessy's book, "A Distributed $\pi$-Calculus", summation is not used (section 2.1 deals with the language, and summation isn't there).
The Wikipedia article on $\pi$-Calculus also doesn't include summation.
Why is summation not included in these descriptions? Was it somehow abandoned because it can be expressed using the other primitives? If so, how would it be done?
$$P ::= \sum_{i\in I} \pi_i.P_i\ {\huge|}\ P_1|P_2 \ {\huge|}\ \operatorname{new} a P\ {\huge|}\ !P$$
So in Milner's formulation, the summation of processes is included, just as in CCS. However, some authors do not include it: in Mathew Hennessy's book, "A Distributed $\pi$-Calculus", summation is not used (section 2.1 deals with the language, and summation isn't there).
The Wikipedia article on $\pi$-Calculus also doesn't include summation.
Why is summation not included in these descriptions? Was it somehow abandoned because it can be expressed using the other primitives? If so, how would it be done?
Solution
To answer this question, it's best to reflect on the meaning of sums in process calculi. Essentially sums express a lack of knowledge. The process $P + Q$ means something along the lines of "either $P$ or $Q$ is active, but I have absolutely no information which". Note that this is related to, but different from a probabilistic sum like
$P +_{0.5} Q$ which also expresses uncertainty about which process is active, but quantifies the uncertainty by stating that both outcomes are equally likely. So $P+Q$ expresses less information than $P +_{0.5} Q$.
A specific case of using sums to express uncertainty is the input process
$$
x(v).P
$$
Cleary an process waiting on an input on channel $x$ is uncertain what input will be received, for otherwise there would not be a need to input something. Hence
input can be seen as a sum over all possible inputs, e.g. if we expect to get a natural $n$, then $
x(v).P
$ really is the sum:
$$
\Sigma_{n \in \mathbb{N}} xn.P\{n/v\}
$$
Here $xn.P$ is the process that inputs the number $n$ (seen as a constant) on $x$ and becomes $P$.
With this understanding of sums as an expression of uncertainty, the question
whether to include sums, and what kind of sum
depends what you use the $\pi$-calculus for. There are two main uses.
If you use it as an idealised programming language, then you don't need sums other than the input prefix $x(v).P$ (and possibly its replicated variant). Indeed what computation would $P+Q$ express?
If you use it to specify program behaviour, then you typically don't want to specify everything and instead express uncertainty by using sums of processes, e.g. $P + Q$. Typically you don't know exactly what the environment of a process is going to do, and use non-determinism to formalise this lack of knowledge.
$P +_{0.5} Q$ which also expresses uncertainty about which process is active, but quantifies the uncertainty by stating that both outcomes are equally likely. So $P+Q$ expresses less information than $P +_{0.5} Q$.
A specific case of using sums to express uncertainty is the input process
$$
x(v).P
$$
Cleary an process waiting on an input on channel $x$ is uncertain what input will be received, for otherwise there would not be a need to input something. Hence
input can be seen as a sum over all possible inputs, e.g. if we expect to get a natural $n$, then $
x(v).P
$ really is the sum:
$$
\Sigma_{n \in \mathbb{N}} xn.P\{n/v\}
$$
Here $xn.P$ is the process that inputs the number $n$ (seen as a constant) on $x$ and becomes $P$.
With this understanding of sums as an expression of uncertainty, the question
whether to include sums, and what kind of sum
depends what you use the $\pi$-calculus for. There are two main uses.
If you use it as an idealised programming language, then you don't need sums other than the input prefix $x(v).P$ (and possibly its replicated variant). Indeed what computation would $P+Q$ express?
If you use it to specify program behaviour, then you typically don't want to specify everything and instead express uncertainty by using sums of processes, e.g. $P + Q$. Typically you don't know exactly what the environment of a process is going to do, and use non-determinism to formalise this lack of knowledge.
Context
StackExchange Computer Science Q#56295, answer score: 9
Revisions (0)
No revisions yet.