4
$\begingroup$

The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial:

It is important to see what the rules do not allow. First, they do not allow reductions underneath prefix, or sum; for example we have $$u(v).(x(y)\ |\ \bar{x}z )\not\rightarrow$$ Thus prefixing imposes an order upon reduction. This constraint is not necessary. However, the calculus changes non-trivially if we relax it, and we shall not consider the possibility further in this paper.

I haven't seem yet a reference discussing the possibility of a compatible reduction relation (though one is used in Yoshida's Strong Normalisation in the $\pi$-Calculus). So, my question is: how exactly does having a compatible relation change the calculus, as Milner puts it? Are there any references that study this possibility I could refer to?

(I do assume one of Milner's papers must mention this, but I couldn't find which one, if any.)

$\endgroup$

2 Answers 2

3
$\begingroup$

I don't know "exactly" how it changes the calculus, in the sense that I don't have a formal statement measuring the difference (and I am not aware that there exists one), but allowing reduction under prefixes does change the semantics of the calculus "non-trivially", as the following example shows.

Let

$\qquad P\ :=\ \nu(x,y,z)(x(w).(w \mathrel| \overline w.a \mathrel| \overline{y}.b) \mathrel| \overline{x}y \mathrel| \overline xz.c)$

$\qquad S\ :=\ \tau.(\tau.a+\tau.b)+\tau.(\tau.a\mathrel|c)$

$\qquad S'\ :=\ \tau.(\tau.a+\tau.(a\mathrel|c))+S$

Whatever definition of reduction you choose, $S$ and $S'$ are not bisimilar. Now, in Milner's calculus, $P$ is bisimilar to $S$. If you allow reduction under prefix, $P$ becomes bisimilar to $S'$.

(Intuitively, the difference between $S$ and $S'$ is that $S'$ may "lose" the barb on $b$ without necessarily exposing a barb on $c$, which is what $S$ must do instead.

Technically, $S$ and $S'$ are not weakly barbed bisimilar, which implies that they are not weakly barbed congruent, which implies that they are not weakly bisimilar, or anything stroger. Indeed, opponent can always win the barbed bisimilarity game against me (player) by starting with the reduction $$S'\to \tau.a+\tau.(a\mathrel|c)\ =:\ S_1'.$$ To respond, I need to reduce $S$ (arbitrarily many times, including none) ending up on a term having the same weak barbs as $S_1'$, which are $a$ and $c$. Now, the reducts of $S$ having exactly $a$ and $c$ as weak barbs are $\tau.a\mathrel|c$ and its immediate reduct $a\mathrel| c$. Whichever I choose, opponent's next move is going to select the reduction $S_1'\to a$, ending on a process whose only barb is $a$. There is no way for me to match this reduction, because any process I may reduce to will have barbs on both $a$ and $c$, and so I'm toast).

Forbidding reduction under input prefixes corresponds to the fact that read/receive operations are blocking, which is quite natural in programming languages. When we are waiting for some information to be received and we decide to proceed without, we might make "bad" choices. In the example, we proceed as if $w$ could not become equal to $y$. If you think about passing values other than names (for example, integers), the phenomenon should become even more apparent intuitively.

In a deterministic context (like the $\lambda$-calculus), proceeding without knowing the value of an input parameter (like reducing $M$ in $\lambda x.\!M$) is fine, but in a concurrent context it is not a good idea.

The story is different for output prefixes and, in fact, many do consider them to be non-blocking, to the point that they force $\mathbf 0$ (the inactive process) to be the only process allowed under an output prefix. This is known as the asynchronous $\pi$-calculus and its expressiveness with respect to the synchronous version is well understood, in the sense that there are synchronous processes which may be simulated asynchronously only introducing divergence (see especially the work by Catuscia Palamidessi about this).

$\endgroup$
4
  • $\begingroup$ Thank you for your example. I've checked the reductions and indeed it seems correct. But, wouldn't that be the case just for strong bisimilarity? I mean, wouldn't $S$ and $S'$ be weakly bisimilar? It also appears to me that, e.g., if $a\rightarrow b$ by reducing a redex under a prefix, $a$ and $b$ would still be barbed bisimilar (I assume that allowing inner reductions doesn't change the observational power of barbed bisimilarity either). That's why I'm seeking a reference about reductions inside prefixes on the $\pi$-calculus (I'd actually like to cite it on a draft I'm working on). $\endgroup$ May 26, 2022 at 23:22
  • 1
    $\begingroup$ Actually, $S$ and $S'$ are not weakly bisimilar. I edited the answer to add an explanation about this. $\endgroup$ May 27, 2022 at 7:11
  • $\begingroup$ About references, unfortunately I don't have any off of the top of my head. Like I said in my answer, the fact that input prefixes are "blocking" is so natural that, I think, hardly anyone ever considered doing otherwise. $\endgroup$ May 27, 2022 at 7:31
  • $\begingroup$ Ohh, I get it. I was ignoring silent transitions, instead seeing $S$ as if it were (up to $\equiv$) simply $a + b + (a\ |\ c)$, in which you'd have to pick one of the three options right away (which appear to be the same options given in $S'$). That's why I assumed $S$ and $S'$ could be weakly bisimilar (and perhaps they'd be in a calculus with only input and output as prefixes, without explicit silent actions, but I'd have to check). Thank you, your example was really helpful. $\endgroup$ May 27, 2022 at 7:57
3
$\begingroup$

Interesting question.

As Damiano says, while syntactically trivial a change, the π-calculus with non-blocking inputs is a different model of computing. (A very different one, and an extremely interesting one that has not, so far, received the attention it deserves.) How computation changes if you can reduce under an input is subtle, and depends in detail on the rest of the model of computing we are talking about. My intuition is that without input prefixing, sequential behaviour becomes difficult to implement.

About 20 years ago, people studied π-like calculi, called Solos [1] that can reduce under inputs. See [2] for some related work.

The "Strong normalisation ..." paper you mention does not remove blocking input prefixing from the underlying π-calculus (simplifying a bit, the typing system in that paper has type erasure), but rather proves that non-blocking input is semantically sound against the chosen (and natural) notion of process equivalence (for which we give a bisimulation characterisation). This means no well-typed observer can distinguish a process that did 'reduce' under input from one that did not. To phrase this in yet another way, the equations between processes that come from reduction under input are in the bisimulation. This all holds because of the strong restriction linearity places on what is typable. Basically: if you have a linear output, potentially suppressed under a blocking input, somewhere in a well-typed process, then this output is guaranteed eventually to synchronise with its corresponding input, since the (linear) input that blocks the linear output will eventually also be unblocked (by linearity). As soon as you loose linearity (e.g. by moving to an affine setting), this stops being true. The "Strong normalisation ..." paper gives a full-abstraction result for a compilation of the simply-typed λ-calculus into the π-calculus, and you can reduce under a λ so, it order to get a precise model of the SLTC in π we must restrict the latter to an unusually small fragment of the calculus.


  1. C. Laneve, B. Victor, Solos in Concert. https://user.it.uu.se/~victor/tr/solos-final.pdf

  2. L. Wischik, Fusions - overview. http://wischik.com/lu/research/fusions.html

$\endgroup$
7
  • 1
    $\begingroup$ I just came back to this, as I'm writing about it now, and shamefully only now I've noticed who had written this answer (one of the authors!), sorry about that. Anyway, your remark that you don't actually extend the reduction relation, but rather show it is sound within the type system, is very helpful. So thank you. $\endgroup$ May 2 at 3:08
  • 1
    $\begingroup$ @paulotorrens No worries. About 99% of that paper's readers thought we changed the reduction relation. We should have made this more clear. Semantically defining such relations is a very powerful proof technique and works in more contexts when you have linear types. $\endgroup$ May 2 at 7:13
  • 1
    $\begingroup$ I had written this question precisely because of the relation you had used on that paper, as I was very curious about it. I thought I'd came up with it at first, for a different calculus (Thielecke's CPS-calculus), then I found it out in your paper. Later I found out the exact same rules as compiler optimizations in another paper, and then again in a paper about explicit substitution, only to later realize these rules are justified by cut elimination rules on linear proof nets. They seem to have a deep connection (which I'm writing about now). $\endgroup$ May 2 at 7:30
  • 1
    $\begingroup$ There is a deep connection, which Kohei and Olivier wrote about in perso.ens-lyon.fr/olivier.laurent/picppn.pdf (there was some more unpublished work along those lines, but it never got published because of Kohei's untimely death). Regarding Thielecke's CPS-calculus, you might find my work martinfriedrichberger.net/fsen09.html which started from Thielecke's work, although I then drove it in a different direction (Hoare logic). $\endgroup$ May 2 at 8:31
  • 1
    $\begingroup$ What is the compiler optimisation work you mention? (A lot of techniques are discovered by logicians, and, independently, by compiler research.) $\endgroup$ May 2 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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