乐趣区

xzza0-xwyw0-yvvu0

jiezi

这篇文章的标题是一个 π 表达式，结尾是一段 JavaScript 代码，和这个表达式的含义完全一致，或者说，完成了这个表达式的估值。

π 演算（π calculus）是一种表达并发过程（process）的数学语言，和 λ 在形式上有很多类似之处；λ 已经是公认的计算模型，它和图灵机或递归理论（Recursion Theory）描述的计算模型是等价的，但是这个计算模型无法描述并发计算。

π 没有 λ 那样的地位；它只是描述并发计算的模型之一，在计算数学领域科学家们还没有对并发计算模型达成一致，每一种并发计算模型都强调了并发计算的某些方面的特性但还没有一个模型成为 λ 那样的经典模型可以解释其他所有模型，或者证明其等价性；数学家们选择使用不同的模型研究他们感兴趣的并发计算特性。

π 是并发计算模型中最精简的一个，具有最小的概念元素集；它只包含两个概念：过程（process）和通讯（channel）。过程是一个计算单元，计算是通过通讯来完成的。

“计算是通过通讯完成的”对于不熟悉数学理论的人来说不容易理解；这里也没有更好的解释；推荐看一点关于 λ 的介绍，感受一下计算是如何通过变量名 binding 和替换（substitution）完成的。

在数学上，λ 可以被 encode 在 π 里，但是不该对 encode 一词产生基于其自然语言含义的联想，如果想了解它的确切含义，请系统学习 λ 和 π 的相关理论。

题目是一个 π 表达式，也可以看作是用 π 演算写下的一段程序，即把 π 当作一种编程语言，虽然这个表达式没有什么实际用处，也没有人会打算用 π 作为编程语言写下实际的程序；但是在对照了题目的 π 表达式和文中的 JavaScript 代码之后，我相信你会获得一些新感受，关于对并发的理解，什么是描述并发的最小概念集。

这篇文章是一个起点，如果我有时间，还会逐步解释在 JavaScript 里的 callback，emitter，promise，async/await，等等，都不是在并发计算模型意义上的最小概念，它们更多的考虑了实际使用中最常用需求、最简洁书写、最容易学习等工程特性或需求，但同时也会遇到一些棘手的问题；而这篇文章，就是在探索对并发编程而言，最原始（primitive）的东西是什么。

解释表达式

和 λ 一样简单的是，在 π 里只有 name，name 表示一个 channel。

标题里的 π 表达式 (π-term) 没有包含所有的 π 符号，只包含了其中的一部分；解释如下：

  • x(z)的意思是从 channel x 接收到 z
  • z<a> 的意思是向 channel z 发送 a
  • x(z)和 z <a> 都称为 π 前缀（prefix），分别是 input prefix 和 output prefix，是 π 里最重要的两个前缀；
  • '.'（dot）可以被理解为继续（continuation），或者反过来理解，阻塞（blocking）；它的意思是前缀必须先完成通讯，即接收或发送完成，'.'之后的表达式才可以开始执行，或者称为估值；这是 π 里唯一表达顺序（order）的地方；

你可以给一个表达式取一个名字，习惯上使用大写字母 P, Q, R…

例如：

如果 P = z<a>.0，最左侧的表达式就可以写成 x(z).P；

如果 P = x(z).z<a>.0，则最左侧的表达式就可以写成 P；

如果

  • P = x(z).z<a>.0
  • Q = x<w>.y<w>.0
  • R = y(v).v(u).0

则整个标题的表达式可以写成 P | Q | R

有时候我们采用 π.P 的写法表示一个通用的 π 表达式，而不关心这个表达式里的 π 具体是那种前缀；

当然也可以定义: U = P | Q | R，它仍然是 π 表达式。

每个 π 表达式都表达了一个过程。

'|'（vertical pipe）在 π 里的含义是 并发 组合，可以看作过程的运算符；U = P | Q | R 就可以理解为过程 U 是由三个过程并发组成的。

π 里的另一个组合过程的运算符是'+'，summation，我们暂不介绍。

标题的表达式里还有一个符号 0，0 表示一个无行为的过程（inaction）。

Free name

这一段可以在看了后面的代码之后再回来对照理解。

Free name 的含义和 λ 或编程语言里的定义一致；它是 bound name 的反义词；bind 的意思和 λ 也是一致的（λx)；

在 π 里有两个符号会 bind name，标题里的表达式只出现了一个，即输入前缀，例如：x(z)。这很容易理解，在 JavaScript 代码里我们常用 listener 函数接收消息：

emitter.on('data', data => {// do something with data})

这里的 data 变量的 scope 就是在这个匿名函数内的，即 bound name。一个过程 P 的 Free name 是它和外部角度的唯一方式。

这里是 π process 教材里的描述：

The free names of a process circumscribe its capabilities for action: for a name x, in order for P to send x, to send via x, or to receive via x, it must be that x ∈ fn(P). Thus in order for two processes to interact via a name, that name must occur free in both of them, in one case expressing a capability to send, and in the other a capability to receive.

from π calculus by Davide Sangiorgi and David Walker

译：

一个过程的 free name 决定了它的行为能力，对于过程 P 中的 name x，如果 P 能够：

  1. 发送 x
  2. 通过 x 发送其他 name
  3. 通过 x 接收其他 name

x 必须是 P 的 free name。所以如果两个过程需要通过一个 name 交互，这个 name 必须在两个过程中都是 free name，其中一方用于发送，另一方用于接收。

Reduction

这个词在编程界被用烂了。但是它的含义没有什么高大上的地方。一个数学公式的形式变换就是 reduction，当然我们正常情况下是希望它越变越简洁的（所以叫 reduce），除了你的阴险的数学老师会在出题时有个相反的邪恶目的。

π 只有一个 reduction:

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

含义是 y 从 channel x 发送出去之后，P 才可以继续执行；同时 x(z)前缀收到了 y，Q 得以继续执行，此时 Q 里的所有 z 都要替换成 y。

在编程中：

x(z).Q 意味着如果 x 尚未收到数据，Q 不能开始执行；这个 input prefix 在程序语言里很容易实现，就是常见的 listener 或者 callback。

x<y>.P 意味着只有 y 被读走，P 才会开始执行；这类似 lazy 实现的 stream，在数据没有被读走之前，不会再向 buffer 填充数据；在编程语言里实现这个表达式，和实现 readable stream 时，收到 drain 事件才开始填充数据类似。

代码

我们先假定存在一个构造函数或工厂方法，可以构造一个 channel 对象；我们先不回答 channel 如何构造，以及它内部是什么。

我们要求 channel 对象有一对接口方法，按照 π 的逻辑应该叫做 send 和 receive；

注意在 π 里我们没有类型和值的概念，一切变量皆 channel，写成代码就是一切变量皆 channel 对象，通过 channel 传递的变量也是 channel，这是 π 系统的重要特性之一：pass channel via channel（因为它会让 name 突破一个 scope 使用）。

我们首先发现这个表达式里的 free name 都得先声明（why？）；x，y，w，a 都声明成 channel（a 在这个例子中没有实际用于通讯，可以是任何东西）。

第一段代码就是这个样子。

class Channel {// placeholder}

const channel = () => new Channel()

const x = channel()
const y = channel()
const w = channel()
const a = channel()

'.'（dot）所表达的继续，我们可以用调用一个函数来实现；.0，可以用调用空函数（() => {}）表示；

第一个表达式：x(z).z<a>.0，可以这样写：

x.receive(z => z.send(a, () => {}))

receive 方法形式上是提供一个函数 f 作为参数，channel x 在接收到值 z 的时候调用这个函数f(z)；

第二个表达式：x<w>.y<w>.0，可以这样写：

x.send(w, () => y.send(w, () => {}))

注意这里要 send 成功之后才能继续而不是调用 send 后就继续，所以不能写成：

x.send(w)
y.send(w)

最后一个表达式：y(v).v(u).0

y.receive(v => v.receive(u => (() => {})()))

到这里我们写完了使用者代码；在使用的时候我们也给 Channel 类的接口下了定义；如果你问哪个表示并发的 vertical pipe（|）哪里去了？你想一下，我在文章的最后给出问题的答案。

在实现 Channel 类之前我们还要考虑一个顺序问题。

π 里的 reduction 是两个并发过程之间发生的；在 reduction 的时候我们要调用两个函数实现 '.' 表示的继续，分别是发送者继续和接收者继续，我们是否应该约定一个固定的顺序？

答案是不应该；对于这里写下的玩具代码我们甚至故意加入了随机性，这才是并发的含义，并发过程之间木有固定执行顺序。

我们先定义一个 reduce 函数；它的前提是 send 和 receive 两个方法都被调用过了；这里存在两种顺序可能性：如果 receive 先被调用了，f 被保存下来直到 send 被调用，这和常见的 listener 没有区别；但 π 也允许反过来的顺序，send 先被调用了，则 c 和 f 都被保存下来，等到 receive 调用的时候再使用，这就是 π 里的两个前缀会 block 后面的表达式估值的实现。

无论 send 和 receive 的实际调用顺序如何，我们都希望 reduce 可以随机执行 sender 和 receiver 提供的回调函数。

class Channel {reduce () {if (!this.sendF || !this.receiveF) return
        let rnd = Match.random()
        if (rnd >= 0.5) {this.sendF()
            this.receiveF(this.c)
        } else {this.receiveF(this.c)
            this.sendF()}
    }

    send (c, f) {
        this.c = c
        this.sendF = f
        this.reduce()}

    receive (f) {
        this.receiveF = f
        this.reduce()}
}

写出 reduce 之后 send 和 receive 就是无脑代码了；在标题的表达式里每个 channel 都只用了一次，所以我们不用在这里纠结如果重复发送和接受的情况如何解决；各种参数检查和错误处理也先不管了，先跑起来试试。

最后所有的代码都在这里，加了一点打印信息，你可以运行起来感受一下，也思考一下：

  • π 系统 capture 了并发编程里哪些最重要的特性？没有 capture 下来哪些？这段代码里有什么东西是可能在实际编程问题上可以派上用场？
  • callback，emitter，promise，async/await 能用 Channel 表达或者实现吗？如果能，大概会是什么样？
  • rx 和这个 Channel 有什么异同？
class Channel {constructor (name) {this.name = name}

  reduce () {if (!this.sendF || !this.receiveF) return
    console.log(`passing name ${this.c.name} via channel ${this.name}`)
    let rnd = Math.random()
    if (rnd >= 0.5) {this.sendF()
        this.receiveF(this.c)
    } else {this.receiveF(this.c)
        this.sendF()}
  }

  send (c, f) {console.log(`${this.name} sending ${c.name}`)
    this.c = c
    this.sendF = f
    this.reduce()}

  receive (f) {console.log(`${this.name} receiving`)
    this.receiveF = f
    this.reduce()}
}

const channel = name => new Channel(name)
const x = channel('x')
const y = channel('y')
const w = channel('w')
const a = channel('a')

x.receive(z => z.send(a, () => console.log('term 1 over')))
x.send(w, () => y.send(w, () => console.log('term 2 over')))
y.receive(v => v.receive(u => (() =>
  console.log(`term 3 over, received ${u.name} finally`))()))

答案

为什么 vertical pipe 表示的并发组合没了呢？因为连续执行上面代码段里最后三句的时候，就是并发了；一定要说语言上什么符号对应了 '|' 的话，对于 JavaScript 就是 ; 号了；它本来在语言上是 statement 的顺序组合，在我们这个代码里，就是并发组合了。

退出移动版