Talk:Π-calculus/Archive 1

Archive 1

Pi- and n-calculus

I'm confused - the article is supposed to discuss the pi-calculus, but half of it explain the n-calculus instead. Why? Which is which and how do they differ? --134.102.204.196 10:44, 25 January 2006 (UTC)

I believe you'll find that the article is discussing the π-calculus (as in the Greek letter pi), rather than the "n-calculus". Pi-calculus == π-calculus, but the latter is the form that π-calculus researchers like Milner, Parrow, and Sangiorgi tend to use, so that's what appears in this article. Perhaps it just isn't rendering well in your browser. --Allan McInnes 16:23, 25 January 2006 (UTC)

Parallel languages

The article states that the lambda calculus has been used to model parallel languages. While that may be true, in some strict sense, wouldn't it a better comparison with pi-calculus to say that lambda-calculus models _sequential_ programming languages? —The preceding unsigned comment was added by 83.72.35.16 (talk • contribs) .

I think you'll find that the article originally did say that, and was changed by User:CarlHewitt as part of what appears (to me) to be a campaign to make widely known his opinions about the relative capabilities of the Actor model and λ-calculus to model concurrency. I agree that "sequential programs" is less confusing — I'll switch it back now. --Allan McInnes 23:17, 28 January 2006 (UTC)

Usefulness of pi-calculus?

Articles with a red discussion link are either very very good or substandard. It is as yet completely unclear to me how the pi-calculus can be used to do anything useful. It has the zero process. You can run two of them concurrently, but isn't 0|0 = 0 ? And also !0 = 0 ? How then do you build processes that _do_ anything? Or do you use lambda calculus for this? Also I am mystified by the deduction rule "if P -> Q then also P|E -> Q|E". And by the way -> is not explained anywhere. We have "if x<y>.P | x(z).Q, then also P | Q[y/z]" thus

(x<y>.P | x(z).Q) -> (P | Q[y/z]) implies

(x<y>.P | x(z).Q | x<a>.P) -> (P | Q[y/z] | x<a>.P) but also by symmetry

(x<y>.P | x(z).Q | x<a>.P) -> (P | Q[a/z] | x<y>.P) .

This does not seem right. Anyone? MarSch 16:06, 14 Apr 2005 (UTC)

As stated in the article, Pi-calculus in not a programming language; its purpose is to model concurrent processes. This end is achieved with creating and communicating names. I believe -> means "can be reduced to". Your example is absolutely right and contains no contradiction: you have three concurrent processes, two of which send a message on channel x, and one of them blocks waiting for a message on that channel. Obviously, the "listener" process can receive either one of the two messages, as illustrated by your example. --146.6.101.9 17:58, 2 May 2005 (UTC)

Not finished reading this interesting article yet, but I'd like to suggest changing the BNF syntax description for readability. The "|" sign is used in different meanings. It is used as the BNF "or" and in the Pi-calculus itself. I suggest changing one sign or quoting the blocks. -- Helmut 84.133.58.203 17:42, 19 December 2005 (UTC)

I’ve tried to make it a bit more readable without changing the | symbols. If it is sufficiently less ambiguous now, then the spacing hint should be better than a change of either grammar. (After all, formal definitions are supposed to make things clear, not confusing…)

However, I am a bit unsure about whether the grammar and the immediately subsequent discussion is entirely accurate. Rather than try to pick out inaccuracies (difficult for me due to not having enough knowledge about the topic), I’ll just ask whether it might be a good idea to make the formal definition more similar to the one in chapter 2 of Milner’s tutorial. I’ll see if I can get back to the article with a good book, but help is appreciated. --xyzzy_n 23:12, 16 February 2006 (UTC)

Shouldn't Occam-Pi be added to the implementations list? --Sergiu.dumitriu 01:36, 4 January 2006 (UTC)

Notation for Early and Late bisimilarity unexplained.

The section on early and late bisimilarity left me lost, mainly, I believe because of the unexplained notation. Why is a(x) used sometimes and $\alpha$ used other places?

For example:

${\begin{matrix}&a(x)&\\p&\rightarrow &p'\\\end{matrix}}$

VS

${\begin{matrix}&\alpha &\\p&\rightarrow &p'\\\end{matrix}}$

And to what might the x in a(x) refer - especially as the text seems to talk about a binary relation?

I think you'll find that, if you look further up in the article, $a(x)$ indicates that a value should be received through channel $a$, and bound to the name $x$ in the following process. Thus the need to break out the bisimulation definition involving $a(x)$ separately from the definitions for every other kind of action (every other kind of action being denoted $\alpha$): the definition for $a(x)$ actions requires the additional rule that $(p'[y/x],q'[y/x])\in R$, i.e. that p' and q' both perform the same substitution of received values (y) for previously unbound names (x).

I'm not sure it's a good idea to repeat the symbol definitions given in the syntax section again in the bisimilarity section. But if you feel that the surrounding text could explain things better, I'd be interested in hearing suggestions. --Allan McInnes (talk) 16:49, 13 June 2006 (UTC)

Error in ``FAQ on π-Calculus" (linked from this page)

I believe there is an error in ``FAQ on π-Calculus" (linked from this page), normally in this scenario I would contact the external page holder, however he is not the original author of the document so I will provide the information here.

I believe

3. Could you be a little more concrete?
...
a(x).P denotes a process that waits to read a value x from the channel a and then, having received it, behaves like P.

Should read:

a(x).P denotes a process that waits to read a value from the channel a stores it as x and then, having received it, behaves like P.

Or something similar —The preceding unsigned comment was added by 147.188.192.41 (talk) 16:27, 5 January 2007 (UTC).

Barbed bisimulation

Is the symbol for barbed bisimulation displayed correctly? Shouldn't the $\sim$ be a bit larger? A part from that, the part on barbed congruence relation contained a typo. —The preceding unsigned comment was added by 193.205.213.166 (talk) 08:16, 24 April 2007 (UTC).

Suggestion for explanation of restriction operator

Here, the operator written (vx) is explained intuitively as "creation of a new name". Elsewhere (appendex A, definition 1; that paper is about modeling biological processes), I've seen it described as

"The restriction denotes a private channel x on which the two molecules can synchronise to split the complex."

I found this notion of (vx) creating a "private channel" helpful for my intuition and suggest that some phrase like that be added to the "Process constructs" where (vx) is introduced.

But I am just learning about the pi-calculus now, so I may not know what I'm talking about. I have not edited the actual page due to my ignorance. Bayle Shanks 07:25, 25 July 2007 (UTC)

"full power of replication not needed"?

From the article:

The full power of replication !P is not needed. Often, one only considers replicated input...

Not needed for what? For Turing universality? Does replicated input suffice for Turing universality? Or is this a typo; should it be that "the full power of replication is often not needed"? Thanks, Bayle Shanks 07:45, 25 July 2007 (UTC)

Sangiorgi's result

If anyone has the citation for this, it would be neat to add it to the article. Thanks Bayle Shanks 07:51, 25 July 2007 (UTC)

Sangiorgi established the surprising result that the ability to pass processes does not increase the expressivity of the π-calculus: passing a process P can be simulated by just passing a name that points to P instead.

Axioms for replication?

The article presents no structural congruence or reduction axioms for replication. Was something forgotten? Bayle Shanks 07:40, 25 July 2007 (UTC)

I noticed this too. It looks like it was mentioned as a note in the semantics of replication in an earlier revision, which was removed since there was already a semantics section above it (that didn't mention the congruence). I believe it makes more sense as a structural congruence axiom than a reduction axiom, so I have added it there. —Preceding unsigned comment added by 204.60.66.146 (talk) 23:25, 28 December 2007 (UTC)

goto c?

References to "goto c" appear in the section "Process constructs". What does this mean? Are you talking about goto in the context of languages like C, where "c" is some label or address? If so, that doesn't make sense according to what has been explained thus far in the article; what does instruction jumping have to do with passing values along links and binding names? indil (talk) 07:56, 23 October 2008 (UTC)

Continuations

The article uses the term "continuation". However, continuations have a technical meaning in computer science. Is the word word use in this meaning? If not, I suggest that it be replaced by another word, or that the ambiguity be clarified. —The preceding unsigned comment was added by 130.37.24.218 (talk) 14:42, 19 December 2006 (UTC).

The usage appears roughly similar to more general computer science. In a process X.P, where X is one of the defined process constructs (excluding nil), P is the continuation of X. The term could probably use more explanation in the context of pi calculus. (This is a naive guess based on how the term is used in the article, so I'm not going to edit the article to reflect this belief.) --66.92.73.217 06:20, 17 March 2007 (UTC)

The original poster is correct. I've removed the uses of the word continuation that I spotted. Clements (talk) 02:28, 28 October 2009 (UTC)

Compare pi-calculus and turing-machine.

How does pi-calculus compares to turing-machines? —Preceding unsigned comment added by 90.80.39.42 (talk) 13:51, 2 September 2009 (UTC)

The article refers to work by Milner showing that the pi-calculus can model the lambda calculus. This implies that the pi-calculus is turing-complete. Clements (talk) 02:47, 28 October 2009 (UTC)

Section 1.2 "A small example" not helpful

It is not clear from the definition in the previous section how the examples work, and thus they convey no better understanding. I suspect what's missing is an explanation of the idea of computation in the pi calculus and how it differs from that of the languages deriving from the lambda calculus or register machine. For example, is the pi calculus a rewrite system like the lambda calculus? If so, how do you reduce terms? indil (talk) 08:05, 24 May 2008 (UTC)

The entry shows reduction rules for the pi-calculus. So: yes, the pi-calculus is a system like the lambda calculus, and you can reduce terms using the given reduction rules. Clements (talk) 02:48, 28 October 2009 (UTC)

Requested move

Withdrawn, but moved so as to remove hyphen per discussion comments. --Cybercobra (talk) 03:54, 15 November 2009 (UTC)

Pi-calculus → π-calculus — We have the Unicode support to make this work, but it's hitting the title blacklist for some reason; I don't see why we can't give this its technically correct name. --Cybercobra (talk) 09:19, 13 November 2009 (UTC)

• How about Pi calculus, like lambda calculus? Septentrionalis PMAnderson 15:09, 13 November 2009 (UTC)
• I am not keen on "π-calculus" for an article title. It's not really necessary. I'm happy with Septentrionalis's suggestion. The notation "π" has led to confusion already (see Talk:Pi-calculus#Pi- and n-calculus). Plenty of people do use "pi calculus", for instance Matthew Hennessy's recent book, and Abadi and Fournet's "applied pi calculi". ComputScientist (talk) 16:03, 13 November 2009 (UTC)
• Oppose the move. This is an example of excessive precision, and would only result in a difficult title. How is the average user supposed to write 'π-calculus' at all? On the other other hand Support a move towards Pi calculus (and keeping the other two as redirects). Flamarande (talk) 17:46, 13 November 2009 (UTC)
  • They wouldn't have to type it, there'd be a redirect obviously. --Cybercobra (talk) 09:23, 14 November 2009 (UTC)
    • The article should use the name more commonly used by the users (ie: the most common English name). In this particular case the letter "π" doesn't even appear in the English/Latin alphabet (and keyboards) at all making this case way even clearer. The users will always use 'Pi calculus' or something similar. Flamarande (talk) 02:50, 15 November 2009 (UTC)
• Oppose I see no advantage in using Greek over English. 76.66.197.2 (talk) 06:56, 14 November 2009 (UTC)

Need to disambiguate the syntax

The BNF does not make the priorities of the operators clear. Neither does it explain parentheses. —Preceding unsigned comment added by RJBotting (talk • contribs) 20:13, 3 October 2010 (UTC)

Good point, I've tried to clarify this. The BNF doesn't define concrete syntax, but abstract syntax. This is usual in process algebra, but you weren't to know. ComputScientist (talk) 09:13, 4 October 2010 (UTC)

Errors in the examples

The section "The example revisited" seems to have extra open parentheses or be lacking close parentheses. I'm not confident enough in my grasp of the material to correct them, so could someone experienced take a look? --Lemur821 17:29, 6 August 2006 (UTC)

Thanks for noticing that! I’m no expert either, but it looked like there was a bad opening parenthesis, so I removed it. Does it work now? —xyzzy_n 17:51, 6 August 2006 (UTC)

The examples are still wrong. The scope of the bindings for receives should extend to the closing parenthesis. That is,

$x(y).P$

should consider all free variables $y$ in $P$ to be replaced. This means that

$(\nu x)(0|{\overline {z}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0$

should have been

$(\nu x)(0|{\overline {z}}\langle x\rangle .x(z).0)|z(v).{\overline {v}}\langle v\rangle .0$

I also suggest to explain scope extrusion in more detail.

Update: the bound variable scoping is clarified and the example is fine now in the revision. — Preceding unsigned comment added by Robert van Engelen (talk • contribs) 16:31, 22 December 2011 (UTC)

--Robert van Engelen 21:50, 6 December 2006 (UTC)

Error in "Extensions and variants"

That section states that the asynchronous pi caclculus can simulate the standard ( synchronous) one. This seems to be disproven by a 1997 POPL article: http://arxiv.org/abs/cs/9809008 — Preceding unsigned comment added by Ringesherre (talk • contribs) 18:48, 1 July 2012 (UTC)

Naming - Why?

Why is it called pi calculus and what does it have to do with pi? — Preceding unsigned comment added by 41.13.212.50 (talk) 15:11, 12 January 2015 (UTC)

(vx) notation

It seems that because v occurs in neither the bound names of (vx).P nor the free names of (vx).P, v is not a name/variable in (vx).P and is instead purely notational. If so, why is v chosen to play this role? And why then is v used as a variable in examples, when its double usage adds to confusion? Maybe I am misunderstanding the usage of v in (vx). Also I was wondering whether (vx), a(x), and a<x> are themselves members of the set of valid pi-calculus expressions as they seem to be only used as prefixes acting on P in the definition. My final confusion is the usage of the phrase "binds more closely" in the formal definition section, which I believe is meant to convey something about the order of application of operations in the pi-calculus. However this is vocabulary I am unfamiliar with.2600:1017:B10A:508F:B804:758C:BFF4:ABAF (talk) 18:35, 27 November 2017 (UTC)

"v" is really supposed to be the lower-case greek letter Nu, hich sounds like "new". The way you read (vx).P is "new x in P".

Jake.gillberg (talk) 15:03, 8 May 2018 (UTC)

Broken link

The link 16 is broken

Nash, A.; Kalvala, S. (2009). "A Framework Proposition for Cellular Locality of Dictyostelium Modelled in π-Calculus" (PDF). CoSMoS 2009.

This is the broken link : https://cosmos-research.org/docs/cosmos2009-proceedings.pdf

This is archived version works : http://web.archive.org/web/20201003014038/https://cosmos-research.org/docs/cosmos2009-proceedings.pdf — Preceding unsigned comment added by 2001:861:3A04:E320:998E:AD24:5959:ACAA (talk) 01:45, 13 February 2022 (UTC)