π-calculus
≈ 6 min read
Names in other languages
- РусскийПи-исчисление
- Bahasa IndonesiaKalkulus pi
- ItalianoPi calculus
- Englishπ-calculus
- EspañolCálculo pi
- caCàlcul Pi
- DeutschPi-Kalkül
- FrançaisPi-calcul
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In theoretical computer science, the -calculus (or pi-calculus) is a process calculus. The -calculus allows channel names to be communicated along the channels themselves, and in this matter, it is able to describe concurrent computations whose network configuration may change during the computation. The -calculus has few terms and is a small, yet expressive language (see ). Functional programs can be encoded into the -calculus, and the encoding emphasises the dialogue nature of computation, drawing connections with game semantics. Extensions of the -calculus, such as the spi calculus and applied , have been successful in reasoning about cryptographic protocols . Beside the original use in describing concurrent systems, the -calculus has also been used to reason through business processes, molecular biology. and autonomous agents in artificial intelligence.
In theoretical computer science, the -calculus (or pi-calculus) is a process calculus. The -calculus allows channel names to be communicated along the channels themselves, and in this matter, it is able to describe concurrent computations whose network configuration may change during the computation. The -calculus has few terms and is a small, yet expressive language (see ). Functional programs can be encoded into the -calculus, and the encoding emphasises the dialogue nature of computation, drawing connections with game semantics. Extensions of the -calculus, such as the spi calculus and applied , have been successful in reasoning about cryptographic protocols . Beside the original use in describing concurrent systems, the -calculus has also been used to reason through business processes, molecular biology. and autonomous agents in artificial intelligence. P, Q ::= & \; x(y).P \,\,\, \, \, & \text{Receive on channel }x\text{, bind the result to }y\text{, then run }P \\ & \; | \; \overline{x} \langle y \rangle.P \,\,\, \, \, &\text{Send the value }y\text{ over channel }x\text{, then run }P \\ & \; | \; P|Q \,\,\, \, \, \, \, \, \, &\text{Run }P\text{ and }Q\text{ simultaneously} \\ & \; | \; (\nu x)P \,\,\, &\text{Create a new channel }x\text{ and run }P \\ & \; | \; !P \,\,\, &\text{Repeatedly spawn copies of }P \\ & \; | \; 0 & \text{Terminate the process} \end{align} In the concrete syntax below, the prefixes bind more tightly than the parallel composition (|), and parentheses are used to disambiguate. Names are bound by the restriction and input prefix constructs. Formally, the set of free names of a process in –calculus are defined inductively by the table below. The set of bound names of a process are defined as the names of a process that are not in the set of free names. A test for name equality [x=y]P can be added to the syntax. This match operator can proceed as P if and only if and y are the same name. Similarly, one may add a mismatch operator for name inequality. Practical programs which can pass names (URLs or pointers) often use such functionality: for directly modeling such functionality inside the calculus, this and related extensions are often useful. The asynchronous -calculus allows only outputs with no continuation, i.e. output atoms of the form \overline{x}\langle y \rangle , yielding a smaller calculus. However, any process in the original calculus can be represented by the smaller asynchronous -calculus using an extra channel to simulate explicit acknowledgement from the receiving process. Since a continuation-free output can model a message-in-transit, this fragment shows that the original -calculus, which is intuitively based on synchronous communication, has an expressive asynchronous communication model inside its syntax. However, the nondeterministic choice operator defined above cannot be expressed in this way, as an unguarded choice would be converted into a guarded one; this fact has been used to demonstrate that the asynchronous calculus is strictly less expressive than the synchronous one (with the choice operator). The polyadic -calculus allows communicating more than one name in a single action: \overline{x}\langle z_1,...,z_n\rangle.P (polyadic output) and x(z_1,...,z_n).P (polyadic input). This polyadic extension, which is useful especially when studying types for name passing processes, can be encoded in the monadic calculus by passing the name of a private channel through which the multiple arguments are then passed in sequence. The encoding is defined recursively by the clauses \overline{x}\langle y_1,\cdots,y_n\rangle.P is encoded as (\nu w) \overline{x}\langle w \rangle.\overline{w}\langle y_1\rangle.\cdots.\overline{w}\langle y_n\rangle.[P] x(y_1,\cdots,y_n).P is encoded as x(w).w(y_1).\cdots.w(y_n).[P] All other process constructs are left unchanged by the encoding. In the above, [P] denotes the encoding of all prefixes in the continuation P in the same way. The full power of replication !P is not needed. Often, one only considers replicated input ! x(y).P , whose structural congruence axiom is ! x(y).P \equiv x(y).P | !x(y).P . Replicated input process such as !x(y).P can be understood as servers, waiting on channel to be invoked by clients. Invocation of a server spawns a new copy of the process P[a/y] , where a is the name passed by the client to the server, during the latter's invocation. A higher order -calculus can be defined where not only names but processes are sent through channels. The key reduction rule for the higher order case is \overline{x}\langle R \rangle.P | x(Y).Q \rightarrow P | Q[R/Y] Here, Y denotes a process variable which can be instantiated by a process term. Sangiorgi established 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. The -calculus is a universal model of computation. This was first observed by Milner in his paper "Functions as Processes", in which he presents two encodings of the lambda-calculus in the -calculus. One encoding simulates the eager (call-by-value) evaluation strategy, the other encoding simulates the normal-order (call-by-name) strategy. In both of these, the crucial insight is the modeling of environment bindings – for instance, " is bound to term M " – as replicating agents that respond to requests for their bindings by sending back a connection to the term M . The features of the -calculus that make these encodings possible are name-passing and replication (or, equivalently, recursively defined agents). In the absence of replication/recursion, the -calculus ceases to be Turing-complete. This can be seen by the fact that bisimulation equivalence becomes decidable for the recursion-free calculus and even for the finite-control -calculus where the number of parallel components in any process is bounded by a constant.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371914202 under CC BY-SA 4.0; modifications have been made.