Hoare CSP 1978 — 把并发看成会对话的小程序

是什么

Communicating Sequential Processes（CSP）是一种把并发程序拆成许多小顺序程序、再让它们用输入输出互相同步的思想。日常类比：像厨房里几位厨师不能抢同一个案板写便签，而是必须当面交接食材；一方递出，另一方接住，这次交接才算发生。

Hoare 这篇 1978 年论文的关键主张是：输入、输出、并发组合应该是编程语言的一等原语。一个进程内部仍然按顺序执行，但进程之间不靠共享变量乱改状态，而靠 ? 输入和 ! 输出传值。

这不是今天的完整 CSP 形式化理论，而是一篇语言设计论文。它用一堆小练习展示：协程、子程序、数据表示、监视器、信号量、缓冲区、哲学家就餐，都可以从“进程 + 同步通信 + 守卫选择”组合出来。

为什么重要

不理解 CSP，下面这些事会很难解释：

• 为什么 Go 的无缓冲 channel 会让发送方和接收方互相等待，而不是自动把消息扔进无限队列
• 为什么 Erlang / Actor 模型和 CSP 都在反对“大家一起改同一块内存”，但通信语义又不完全一样
• 为什么并发 bug 常常不是某一行算错，而是两个过程在“谁等谁”上卡住，也就是死锁
• 为什么语言设计里会反复讨论“同步通信、缓冲通信、共享内存”这三种并发世界观

核心要点

CSP 的直觉可以拆成 三步：

1. 顺序进程：每个小程序内部还是一步一步做事。类比：每个厨师有自己的菜谱，不会同时执行两行。

2. 同步通信：X!v 表示给 X 发送值，Y?x 表示从 Y 接收值；两边都准备好时，值才真正移动。类比：交接单必须两个人同时签字。

3. 守卫选择：进程可以写多个“如果这个输入准备好了就做这件事”的分支，哪个先可执行就选哪个。类比：前台同时等电话和门铃，谁先来就先处理谁。

这三步把并发从“共享变量上的混战”改成“明确命名的对话”。

实践案例

案例 1：把一个字符流从西边转到东边

论文里的 COPY 进程可以写成：

X :: *[c:character; west?c -> east!c]

逐部分解释：

• west?c：X 等 west 交出一个字符，并把它放进变量 c
• east!c：X 再把这个字符交给 east
• *[]：不断重复，直到 west 结束，输入失败，循环自然停下

这个例子说明 CSP 的基本味道：中间进程不偷看全局状态，只做一次次清楚的交接。

案例 2：缓冲区不是魔法队列，而是一个普通进程

论文用一个进程 X 表示最多放 10 个元素的缓冲区：

X ::
buffer:(0..9) portion;
in,out:integer; in := 0; out := 0;
*[in < out + 10; producer?buffer(in mod 10) -> in := in + 1
[]out < in; consumer?more() -> consumer!buffer(out mod 10);
    out := out + 1
]

逐部分解释：

• producer?buffer(...)：只有缓冲没满时，才接收生产者的新东西
• consumer?more()：只有缓冲不空时，才回应消费者的取货请求
• 两个分支都可做时，选择取决于谁先准备好，语言定义不承诺固定顺序

所以“缓冲”不是隐藏在运行时里的神秘机制，而是可以用 CSP 原语写出来的协议。

案例 3：在 Go 里感受同步 channel 的影子

Go 的无缓冲 channel 不是 Hoare 论文的原样实现，但直觉很接近：

ch := make(chan int)
go func() {
    ch <- 42
}()
x := <-ch
fmt.Println(x)

逐部分解释：

• ch <- 42 会等到有人接收，发送才完成
• <-ch 会等到有人发送，接收才完成
• 和论文不同的是，Go 的 channel 是值，可以传来传去；Hoare 1978 更强调静态命名的进程

这能帮你把“channel 会阻塞”理解成一次同步握手，而不是普通函数调用。

踩过的坑

1. 把 CSP 当成共享内存加锁：CSP 的核心是避免进程互相改全局变量，原因是共享写入会把正确性证明变得很乱。

2. 以为 ! 一定立刻发送成功：Hoare 1978 默认没有自动缓冲，原因是发送和接收要同时准备好才发生。

3. 忽略守卫选择的任意性：多个输入都可执行时，语言只说选一个，原因是不同进程的相对速度本来就未定义。

4. 把这篇当成完整工程语言：Hoare 明确说它只是语言片段，原因是还缺少证明方法、优化策略、库机制和更实际的实现约束。

适用 vs 不适用场景

适用：

• 想理解 channel、actor、消息传递这些并发模型的共同直觉
• 想把协程、缓冲区、监视器、信号量看成协议，而不是硬编码设施
• 想训练“谁在等谁、消息从哪到哪”的并发程序阅读能力

不适用：

• 需要直接指导高性能实现时，论文自己也承认没有解决优化问题
• 需要动态创建无限多进程时，1978 版本要求文本里能看出进程数量上界
• 需要长期运行的服务语义时，论文更偏向可终止程序，对公平性也很谨慎
• 需要完整形式化验证体系时，要继续读后来的 CSP 理论、进程代数和模型检查

历史小故事（可跳过）

• 1960s：ALGOL、SIMULA、Fortran、UNIX 协程等语言设施各自解决一部分程序组织问题。
• 1975 年前后：Dijkstra 的守卫命令给 Hoare 提供了“用条件控制非确定选择”的灵感。
• 1977 年：论文收到并修订，目标不是造一门成品语言，而是找一组更小的并发原语。
• 1978 年：论文发表在 CACM，把“输入输出是基本编程原语”放到并发语言设计中心。
• 后来：Occam、形式化 CSP、Go channel、Erlang 哲学都能看到这条思想线的影子，但各自语义并不等同。

学到什么

1. 并发可以先从通信看，而不是先从锁看：进程之间传消息，状态留在各自内部。
2. 同步通信是一种强约束：它让程序员直接面对等待、终止和死锁，而不是让缓冲区替你遮住问题。
3. 很多高级设施可以由少数原语组合出来：缓冲区、信号量、监视器都能写成进程协议。
4. 论文的价值不在语法，而在世界观：把并发程序读成一组明确命名的对话，这个视角仍然好用。

延伸阅读

• 论文 PDF：Hoare 1978 — Communicating Sequential Processes
• csp-hoare-1978 —— 已写过的同题旧 slug，可对照迁移口径和术语选择
• monitors-1974 —— Hoare 1974 监视器路线，和 CSP 的消息通信形成对照
• kahn-natural-semantics —— Kahn 的函数式并发语义，论文第 7 节专门拿来比较
• milner-pi-calculus —— 后来的进程代数继续研究“会通信的进程”如何移动和组合
• erlang-otp —— 工业系统里“用消息隔离故障”的代表性实践

关联

• hoare-logic —— 同一作者的正确性思想背景，帮助理解他为什么关心可证明的程序结构
• dijkstra-goto-1968 —— 结构化编程的历史氛围，CSP 也在寻找更清楚的控制结构
• monitors-1974 —— 共享资源同步的另一条经典路线，论文把监视器重写成一个进程
• hewitt-actor-model —— 同样反对共享内存混战，但 actor 通常强调异步消息和邮箱
• kahn-natural-semantics —— 展示函数式并发的另一种语义取向，和 Hoare 的命令式取向不同
• milner-pi-calculus —— 把通信本身继续抽象成可推理的代数系统
• erlang-otp —— 让“进程隔离 + 消息传递”成为可运行、可维护的工程体系

反向链接

• dijkstra-1965 —— Dijkstra 1965 — N 个进程怎么轮流上厕所而且谁也别卡死