π-演算

在理论计算机科学中，π-演算（或 pi-演算）是一种过程演算。 π-演算允许通道名称沿着通道本身进行通信，这样它就能够描述并发计算，其网络配置可能在计算过程中发生变化。

π-演算的术语很少，是一种小而富有表现力的语言（参见§语法）。 函数式程序可以编码成 π-演算，编码强调计算的对话性质，与游戏语义建立联系。 π-演算的扩展，例如 spi 演算和应用 π，已经成功地推理了密码协议。 除了最初用于描述并发系统之外，π-演算还被用于推理业务流程和分子生物学。

π-演算属于过程演算家族，是描述和分析并发计算属性的数学形式。 事实上，π-演算和 λ-演算一样，非常小，不包含数字、布尔值、数据结构、变量、函数等原语，甚至不包含通常的控制流语句（如 if-then- 否则，同时）。

π-演算的核心是名字的概念。 微积分的简单性在于名称作为通信渠道和变量的双重作用。

微积分中可用的过程结构如下（下一节给出了精确的定义）：

• 并发，写成 P ∠ Q {\displaystyle P\mid Q} ，其中 P {\displaystyle P} 和 Q {\displaystyle Q} 是两个并发执行的进程或线程。
• 沟通，在哪里
  • 输入前缀 c ( x ) 。 P {\displaystyle c\left(x\right).P} 是一个等待消息的进程，该消息在名为 c {\displaystyle c} 的通信通道上发送，然后作为 P {\displaystyle P} ，将收到的名称绑定到名称 x。 通常，此模型要么是一个期望来自网络的通信的进程，要么是一个只能通过 goto c 操作使用一次的标签 c。
  • 输出前缀 c¯ ⟨ y ⟩ 。 P {\displaystyle {\overline {c}}\langle y\rangle .P} 描述名称 y {\displaystyle y} 在继续作为 P { \displaystyle P} 。 通常，这会模拟在网络上发送消息或 goto c 操作。
• 复制，书面！ P {\displaystyle !\,P} ，可以看作是一个过程，它总是可以创建 P {\displaystyle P} 的新副本。 通常，这会为等待任意数量的 goto c 操作的网络服务或标签 c 建模。
• 创建一个新名称，写作 ( ν x ) P {\displaystyle \left(\nu x\right)P} ，这可以看作是在 P { displaystyle P} 。 π-演算的常量仅由它们的名称定义，并且始终是通信通道。 在流程中创建新名称也称为限制。
• nil 进程，写为 0 {\displaystyle 0} ，是一个执行完成并已停止的进程。

虽然 π-演算的极简主义让我们无法写出正常意义上的程序，但微积分很容易扩展。 特别是，很容易定义控制结构（如递归、循环和顺序组合）和数据类型（如一阶函数、真值、列表和整数）。 此外，已经提出了考虑分布或公钥密码学的 π-算法的扩展。 由于 Abadi 和 Fournet [1] 而应用的 π-演算通过使用任意数据类型扩展 π-演算，将这些不同的扩展置于正式的基础上。

下面是一个由三个并行组件组成的流程的小例子。 通道名称 x 只有前两个组件知道。

前两个组件能够在通道 x 上通信，名称 y 绑定到 z。

请注意，剩余的 y 不受影响，因为它是在内部范围内定义的。第二个和第三个并行组件现在可以在通道名称 z 上进行通信，并且名称 v 绑定到 x。