3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hennessy has a match statement, which is essentially an if. This enables a choice. $P+Q$ is a purely nondeterministic choice, which is harder to reason about and justify as realistic. $\endgroup$ – Dave Clarke Apr 21 '16 at 13:12
  • $\begingroup$ @DaveClarke Match, unlike general choice, expresses computation. $\endgroup$ – Martin Berger Apr 21 '16 at 13:17
  • $\begingroup$ @MartinBerger: Like if. $\endgroup$ – Dave Clarke Apr 21 '16 at 13:23
  • $\begingroup$ @DaveClarke Yes, and unlike the unconstrained sum. $\endgroup$ – Martin Berger Apr 21 '16 at 13:27
  • 2
    $\begingroup$ @josh That's a deep question. Like time and other things, I know it when I see it. If and match are easily implemented on any CPU, by comparing bits. In contrast, $P+Q$ in essence says: I have absolutely no reason to prefer $P$ over $Q$ or vice versa, so, by definition, I cannot implement an decision mechanism. A bit like Buridan's ass. $\endgroup$ – Martin Berger Apr 21 '16 at 13:37
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand - thank you for this explanation! But what if I need both? Suppose I'll start modeling a concurrent programming language, and later I will want to use its specification to reason about program behaviour? $\endgroup$ – josh Apr 21 '16 at 13:34
  • $\begingroup$ Conceptually, you are using two calculi, one to express the computation, on to express the specification. Given that they are so similar, it might be convenient to ignore the distinction and use one calculus only that has the means to do everything you want, and handwave ... $\endgroup$ – Martin Berger Apr 21 '16 at 13:38
3
$\begingroup$

The problem with summation is that it is a powerful and thus difficult/expensive/impossible to implement feature. It's especially difficult in asynchronous contexts.

If you have $x(y).\!P + x(y).\!Q$, when $x(z)$ occurs, exactly one of $P$ or $Q$ proceeds and neither is waiting afterwords. Consider what would be required to ensure that in a distributed context when the summands are not co-located. The point is non-trivial sums require coordination, and coordination is expensive. Even in non-distributed contexts, this is true. Also, in many theoretical contexts the purpose is to explain coordination, so it doesn't make sense to assume it. This is also part of the popularity of the asynchronous variant of the $\pi$-calculus, as the rendezvous semantics of the synchronous variant don't usually match the systems being modeled and require an undesirable level of coordination.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.