在控制流中存储数据
原创
在设计并发程序时，反复出现的一个决定是将程序状态表示为控制流还是表示为数据。这篇文章是关于这个决定意味着什么以及如何接近它。如果做得好，将存储在数据中的程序状态存储在控制流中，可以使程序比其他方式更清晰、更易于维护。
在说更多之前，重要的是要注意并发性不是并行性。
- 并发是关于你如何编写程序，关于能够编写独立执行的控制流，无论你称它们为进程、线程还是 goroutine，这样你的程序就可以同时处理很多事情，而不会变成一团糟。
- 另一方面，并行性是关于你如何执行程序，允许多个计算同时运行，这样你的程序就可以有效地同时做很多事情。
并发性自然适合并行执行，但本文的重点是如何使用并发来编写更干净的程序，而不是更快的程序。
并发程序和非并发程序的区别在于，并发程序可以编写为同时执行多个独立的控制流。较小的控制流的名称因语言而异：线程、任务、进程、纤程、协程、goroutine 等。不管名称如何，这篇文章的基本观点是，根据多个独立执行的控制流编写程序，允许您将程序状态存储在一个或多个控制流的执行状态中，特别是在程序计数器（该部分正在执行的行）和堆栈上。控制流状态始终可以保留为显式数据，但显式数据形式实质上是在模拟控制流。大多数情况下，使用编程语言中内置的控制流功能比在数据结构中模拟它们更容易理解、推理和维护。
本文的其余部分通过一些具体的例子来说明我一直在做的关于在控制流中存储数据的相当抽象的主张。它们恰好是用 Go 编写的，但这些想法适用于任何支持编写并发程序的语言，基本上包括所有现代语言。
这是一个看似微不足道的问题，它演示了在控制流中存储程序状态意味着什么。假设我们正在从文件中读取字符，并希望扫描 C 样式的双引号字符串。在这种情况下，我们有一个非并行程序。这里没有并行性的机会，但正如我们将看到的，并发性仍然可以发挥有用的作用。
如果我们不担心检查字符串中的确切转义序列，那么匹配正则表达式 "([^"\\]|\\.)*" 就足够了，它匹配一个双引号，然后是零个或多个字符的序列，然后是另一个双引号。在引号之间，字符是不是引号或反斜杠的任何内容，或者是反斜杠后跟任何内容（包括引号或反斜杠）。
每个正则表达式都可以编译成有限自动机或状态机，因此我们可以使用一个工具将该规范转换为以下 Go 代码：
state := 0
for {
c := read()
switch state {
case 0:
if c != '"' {
return false
}
state = 1
case 1:
if c == '"' {
return true
}
if c == '\\' {
state = 2
} else {
state = 1
}
case 2:
state = 1
}
}该代码有一个名为表示 state 自动机状态的变量。for 循环读取一个字符并一遍又一遍地更新状态，直到找到字符串的末尾或语法错误。这是程序会编写的代码，只有程序才能喜欢。人们很难阅读，人们也很难维持。
这个程序如此不透明的主要原因是它的程序状态被存储为数据，特别是在名为 state 的变量中。当可以在代码中存储状态时，这通常会导致程序更清晰。为了了解这一点，让我们将程序（一次一小步）转换为等效但更易于理解的版本。
我们可以先将 read 调用复制到交换机的每个案例中：
state := 0 state := 0
for { for {
c := read()
switch state { switch state {
case 0: case 0:
c := read()
if c != '"' { if c != '"' {
return false return false
} }
state = 1 state = 1
case 1: case 1:
c := read()
if c == '"' { if c == '"' {
return true return true
} }
if c == '\\' { if c == '\\' {
state = 2 state = 2
} else { } else {
state = 1 state = 1
} }
case 2: case 2:
c := read()
state = 1 state = 1
} }
} }（在此显示和随后的所有显示中，旧程序位于左侧，新程序位于右侧，未更改的行以灰色文本打印。
现在，我们可以使用代码标签和 goto 语句，而不是写入 state 然后立即再次绕过 for 循环来查找在该状态下要做什么：
state := 0 state0:
for {
switch state {
case 0:
c := read() c := read()
if c != '"' { if c != '"' {
return false return false
} }
state = 1 goto state1
case 1: state1:
c := read() c := read()
if c == '"' { if c == '"' {
return true return true
} }
if c == '\\' { if c == '\\' {
state = 2 goto state2
} else { } else {
state = 1 goto state1
} }
case 2: state2:
c := read() read()
state = 1 goto state1
}
} 然后我们可以进一步简化程序。标签前面的 goto state1 state1 右边是空操作，可以删除。我们可以看到，只有一种方法可以到达 state2，所以我们不妨用 state2 中的实际代码替换： goto state2
state0: state0:
c := read() c := read()
if c != '"' { if c != '"' {
return false return false
} }
goto state1
state1: state1:
c := read() c := read()
if c == '"' { if c == '"' {
return true return true
} }
if c == '\\' { if c == '\\' {
goto state2
} else {
goto state1
}
state2:
read() read()
goto state1 goto state1
} else {
goto state1
}然后，我们可以从 if 语句的两个分支中分解“goto state1”。
state0: state0:
c := read() c := read()
if c != '"' { if c != '"' {
return false return false
} }
state1: state1:
c := read() c := read()
if c == '"' { if c == '"' {
return true return true
} }
if c == '\\' { if c == '\\' {
read() read()
goto state1 }
} else { goto state1
goto state1
} 然后我们可以删除未使用的 state0 标签，并用实际的循环替换循环 state1 。现在我们有了一个看起来像真实程序的东西：
state0:
c := read() c := read()
if c != '"' { if c != '"' {
return false return false
} }
state1: for {
c := read() c := read()
if c == '"' { if c == '"' {
return true return true
} }
if c == '\\' { if c == '\\' {
read() read()
} }
goto state1 }我们可以进一步简化，消除一些不必要的变量，我们可以将最终引号 （ c == "" ） 的检查作为循环终止符。
c := read() if read() != '"' {
if c != '"' {
return false return false
} }
for { var c byte
c := read() for c != '"' {
if c == '"' { c = read()
return true
}
if c == '\\' { if c == '\\' {
read() read()
} }
} }
return true最终版本是：
func parseQuoted(read func() byte) bool {
if read() != '"' {
return false
}
var c byte
for c != '"' {
c = read()
if c == '\\' {
read()
}
}
return true
}早些时候，正则表达式，说它“匹配一个双引号，然后是零个或多个字符的序列，然后是另一个双引号。在引号之间，字符是任何不是引号或反斜杠的东西，或者是反斜杠后面跟着任何东西。很容易看出，这个程序正是这样做的。
手写程序也有机会使用控制流。例如，这是一个人可能手写的版本：
if read() != '"' {
return false
}
inEscape := false
for {
c := read()
if inEscape {
inEscape = false
continue
}
if c == '"' {
return true
}
if c == '\\' {
inEscape = true
}
}可以使用相同类型的小步骤将布尔变量 inEscape 从数据转换为控制流，以相同的清理版本结束。
无论哪种方式，原始 state 变量现在都由程序计数器隐式表示，这意味着程序的哪个部分正在执行。此版本中的注释表示原始变量 state （或 inEscape ）变量的隐式值：
func parseQuoted(read func() byte) bool {
// state == 0
if read() != '"' {
return false
}
var c byte
for c != '"' {
// state == 1 (inEscape = false)
c = read()
if c == '\\' {
// state == 2 (inEscape = true)
read()
}
}
return true
}从本质上讲，原始程序使用显式 state 变量作为程序计数器来模拟此控制流，跟踪正在执行的行。如果可以将程序转换为在控制流中存储显式状态，那么该显式状态只是对控制流的笨拙模拟。
在广泛支持并发性之前，这种笨拙的模拟通常是必要的，因为程序的不同部分希望改用控制流。
例如，假设正在分析的文本是解码 base64 输入的结果，其中四个 6 位字符序列（从 64 个字符的字母表中提取）解码为三个 8 位字节。该解码器的核心如下所示：
for {
c1, c2, c3, c4 := read(), read(), read(), read()
b1, b2, b3 := decode(c1, c2, c3, c4)
write(b1)
write(b2)
write(b3)
}如果我们希望这些 write 调用馈送到上一节的解析器中，我们需要一个可以一次调用一个字节的解析器，而不是一个需要 read 回调的解析器。此解码循环不能显示为 read 回调，因为它一次获取 3 个输入字节，并使用其控制流来跟踪已写入的字节。由于解码器在其控制流中存储自己的状态， parseQuoted 因此不能。
在非并发程序中，这个 base64 解码器 parseQuoted 将陷入僵局：人们将不得不放弃对控制流状态的使用，而是回退到某种模拟版本。
要重写 parseQuoted ，我们必须重新引入 state 变量，我们可以用 Write 方法将其封装在结构中：
type parser struct {
state int
}
func (p *parser) Init() {
p.state = 0
}
func (p *parser) Write(c byte) Status {
switch p.state {
case 0:
if c != '"' {
return BadInput
}
p.state = 1
case 1:
if c == '"' {
return Success
}
if c == '\\' {
p.state = 2
} else {
p.state = 1
}
case 2:
p.state = 1
}
return NeedMoreInput
}该 init 方法初始化状态，然后每个 Write 加载状态，根据状态和输入字节执行操作，然后将状态保存回结构。
对于 parseQuoted ，状态机非常简单，这可能完全没问题。但也许状态机要复杂得多，或者算法最好以递归方式表达。在这些情况下，调用方一次传递一个字节的输入序列意味着在模拟原始控制流的数据结构中显式显示所有状态。
并发性消除了程序不同部分之间的争用，这些部分可以在控制流中存储状态，因为现在可以有多个控制流。
假设我们已经有了这个 parseQuoted 函数，它又大又复杂，经过测试和正确，我们不想改变它。我们可以通过编写这个包装器来完全避免编辑该代码：
type parser struct {
c chan byte
status chan Status
}
func (p *parser) Init() {
p.c = make(chan byte)
p.status = make(chan Status)
go p.run()
<-p.status // always NeedMoreInput
}
func (p *parser) run() {
if !parseQuoted(p.read) {
p.status <- BadSyntax
} else {
p.status <- Success
}
}
func (p *parser) read() byte {
p.status <- NeedMoreInput
return <-p.c
}
func (p *parser) Write(c byte) Status {
p.c <- c
return <-p.status
}请注意 parseQuoted ， run 在方法中使用 ，完全不加修饰。现在，base64 解码器可以使用 p.Write 并保留其程序计数器和局部变量。
Init 创建的新 goroutine 将运行该 p.run 方法，该方法使用 的适当实现调用原始 parseQuoted 函数 read 。在开始 p.run 之前，分配两个通道用于在 p.run 方法之间进行通信， Init 在它自己的 goroutine 中运行，以及任何 goroutine 调用 p.Write （例如 base64 解码器的 goroutine）。通道 p.c 承载从 Write 到 的 read 字节，通道 p.status 承载状态更新。每次 parseQuoted 调用 read 时， p.read 发送 NeedMoreInput p.status on 并等待 上的 p.c 输入字节。 p.Write 每次调用时，它都会执行相反的操作：它发送输入字节 c on p.c ，然后等待并从 返回更新的状态 p.status 。这两个调用轮流来回，一个在执行，一个在任何给定时刻等待。
为了让这个循环继续下去，该 Init 方法执行初始接收 ， p.status 这将对应于 parseQuoted 中的第一个 read 。第一次更新的实际状态是保证的 NeedMoreInput ，并且被丢弃。为了结束这个循环，我们假设当返回 或 时 Write 调用方知道不再调用 Write 。 BadSyntax Success 如果呼叫者错误地继续呼叫 Write ，则发送将 p.c 永久阻止，因为 parseQuoted 已完成。当然，我们会在生产实现中使其更加健壮。
通过创建新的控制流（新的 goroutine），我们能够保留基于代码状态的 base64 解码器的 parseQuoted 实现以及基于代码状态的 base64 解码器。我们避免了必须了解任何一种实现的内部结构。在这个例子中，两者都是微不足道的，重写一个并不是什么大问题，但在一个更大的程序中，能够编写这种适配器而不必对现有代码进行更改可能是一个巨大的胜利。正如我们稍后将讨论的那样，转换并不是完全免费的——我们需要确保额外的控制流得到清理，我们需要考虑上下文切换的成本
base64 解码器的控制流状态不仅包括程序计数器，还包括两个局部变量。如果必须将解码器更改为不使用控制流状态，则必须将这些内容提取到结构中。程序可以通过使用其调用堆栈来使用任意数量的局部变量。例如，假设我们有一个简单的二叉树数据结构：
type Tree[V any] struct {
left *Tree[V]
right *Tree[V]
value V
}如果你不能使用控制流状态，那么要在这个树上实现迭代，你必须引入一个显式的“迭代器”：
type Iter[V any] struct {
stk []*Tree[V]
}
func (t *Tree[V]) NewIter() *Iter[V] {
it := new(Iter[V])
for ; t != nil; t = t.left {
it.stk = append(it.stk, t)
}
return it
}
func (it *Iter[V]) Next() (v V, ok bool) {
if len(it.stk) == 0 {
return v, false
}
t := it.stk[len(it.stk)-1]
v = t.value
it.stk = it.stk[:len(it.stk)-1]
for t = t.right; t != nil; t = t.left {
it.stk = append(it.stk, t)
}
return v, true
}另一方面，如果可以使用控制流状态，确信程序中需要自己状态的其他部分可以在其他控制流中运行，则可以在没有显式迭代器的情况下实现迭代，作为为每个值调用 yield 函数的方法：
func (t *Tree[V]) All(f func(v V)) {
if t != nil {
t.left.All(f)
f(t.value)
t.right.All(f)
}
}这种方法 All 显然是正确的。 Iter 版本的正确性不那么明显。最简单的解释是 Iter ，就是模拟 All 。该 NewIter 方法设置的循环 stk 正在模拟连续 t.left 分支中的 t.All(f) 递归。 Next 弹出并保存堆栈顶部的 t ，然后模拟向下连续 t.left 分支中的 t.right.All(f) 递归，为下一个 Next .最后，它从堆栈 t 顶部返回值，模拟 f(value) 。
我们可以编写这样的 NewIter 代码，并通过解释它模拟一个简单的函数来 All 论证它的正确性。我宁愿写， All 就此止步。
比较二叉树
有人可能会争辩说，这 NewIter 比 All 更好，因为它不使用任何控制流状态，因此它可以在已经使用其控制流来保存其他信息的上下文中使用。例如，如果我们想同时遍历两个二叉树，检查它们是否具有相同的值，即使它们的内部结构不同，该怎么办？对于 NewIter ，这是 straighforward：
func SameValues[V any](t1, t2 *Tree[V]) bool {
it1 := t1.NewIter()
it2 := t2.NewIter()
for {
v1, ok1 := it1.Next()
v2, ok2 := it2.Next()
if v1 != v2 || ok1 != ok2 {
return false
}
if !ok1 && !ok2 {
return true
}
}
}这个程序不能像使用那样容易地编写，因为 SameValues 想要使用 All 自己的控制流（以同步的方式推进两个列表），而控制流不能被 All 的控制流（对树的递归）所取代。但这是一个错误的二分法，与我们看到 parseQuoted 的 base64 解码器相同。如果两个不同的函数对控制流状态有不同的要求，它们可以在不同的控制流中运行。
在我们的例子中，我们可以这样写：
func SameValues[V any](t1, t2 *Tree[V]) bool {
c1 := make(chan V)
c2 := make(chan V)
go gopher(c1, t1.All)
go gopher(c2, t2.All)
for {
v1, ok1 := <-c1
v2, ok2 := <-c2
if v1 != v2 || ok1 != ok2 {
return false
}
if !ok1 && !ok2 {
return true
}
}
}
func gopher[V any](c chan<- V, all func(func(V))) {
all(func(v V) { c <- v })
close(c)
}该函数 gopher 用于 all 遍历一棵树，将每个值宣布到一个通道中。步行后，它关闭了通道。
SameValues 启动两个并发的地鼠，每个地鼠遍历一棵树并将值宣布到一个通道中。然后 SameValues 执行与之前完全相同的循环来比较两个值流。
请注意，这 gopher 绝不是特定于二叉树的：它适用于任何迭代函数。也就是说，启动 goroutine 来运行该 All 方法的一般思路适用于将任何基于代码状态的迭代转换为增量迭代器。我的下一篇文章“Coroutines for Go”扩展了这个想法。
局限性
这种在控制流中存储数据的方法不是万能的。以下是一些注意事项：
- 如果状态需要以不自然映射到控制流的方式发展，那么通常最好将状态保留为数据。例如，分布式系统中节点维护的状态通常不能最好地表示在控制流中，因为超时、错误和其他意外事件往往需要以不可预测的方式调整状态。
- 如果需要为快照或通过网络发送等操作序列化状态，则使用数据通常比使用代码更容易。
- 当确实需要创建多个控制流来保存不同的控制流状态时，需要关闭帮助程序控制流。当返回 false 时
SameValues，它会阻止两个并发gophers，等待发送它们的下一个值。相反，它应该取消阻止它们。这需要在另一个方向进行沟通，告诉gopher要早点停止。“围棋协程”表明了这一点。 - 在多线程情况下，切换成本可能很高。在我的笔记本电脑上，C 线程切换需要几微秒。通道操作和 goroutine 开关便宜一个数量级：几百纳秒。优化的协程系统可以将成本降低到几十纳秒或更短。
通常，在控制流中存储数据是编写干净、简单、可维护程序的宝贵工具。像所有工具一样，它对某些工作非常有效，而对其他工作则不然。
使用并发性来对齐一对二叉树的想法已有 50 多年的历史。它首次出现在查尔斯·普伦纳（Charles Prenner）的“ECL的控制结构设施”（ACM SIGPLAN通知，第6卷，第12期，1971年12月;见第106-109页）。在题为“使用协程的树漫步”的演讲中，问题在于采用两个节点数相同的二叉树 A 和 B，并将值序列从 A 复制到 B 中，尽管两者具有不同的内部结构。它们提出了一种基于协程的简单变体。
Brian Smith 和 Carl Hewitt 在他们的 “A Plasma Primer”（1975 年 3 月;参见第 61-62 页）的草稿中引入了简单比较两个 Lisp 风格的缺点树（其中内部节点不带值）的问题。对于这个问题，他们将其命名为“samefringe”，他们使用基于连续性的 actor 在两棵树上运行一对“边缘”actor（归功于 Howie Shrobe），并将节点报告回比较循环。
杰拉尔德·萨斯曼（Gerald Sussman）和盖伊·斯蒂尔（Guy Steele）在《Scheme： An Interpreter for Extended Lambda Calculus》（1975年12月;见第8-9页）中再次提出了相同的边缘问题，代码大致相同（灵感来自Smith，Hewitt和Shrobe）。他们将其称为“大多数编程语言中难以解决的经典问题”。
1976 年 8 月，ACM SIGART Bulletin 发表了 Patrick Greussay 的“An Iterative Lisp Solution to the Samefringe Problem”，这促使 Tim Finin 和 Paul Rutler 在 1976 年 11 月刊（见第 4-5 页）上回复了一封信，指出 Greussay 的解决方案在二次时间和内存中运行，但也指出“众所周知，SAMEFRINGE 问题被过度用作协程的理由。约翰·麦卡锡（John McCarthy）在1977年2月号上发表了一封回复信（见第4页）。
在题为“另一个相同的边缘”的回应中，McCarthy给出了以下LISP解决方案：
(DE SAMEFRINGE (X Y)
(OR (EQ X Y)
(AND (NOT (ATOM X))
(NOT (ATOM Y))
(SAME (GOPHER X) (GOPHER Y)))))
(DE SAME (X Y)
(AND (EQ (CAR X) (CAR Y))
(SAMEFRINGE (CDR X) (CDR Y))))
(DE GOPHER (U)
(COND ((ATOM (CAR U)) U)
(T (GOPHER (CONS (CAAR U)
(CONS (CDAR U) (CDR U)))))))用现代术语来说，麦卡锡 GOPHER 循环应用右边的树旋转，直到最左边的节点位于树的顶部。 SAMEFRINGE 应用于 GOPHER 两棵树，比较顶部，然后循环以考虑其余部分。
可以将 McCarthy GOPHER 的 -ized 树视为同一堆栈的编码，该 NewIter 堆栈保持但以树形式存在。正确性遵循同样的原因：它模拟的是一个简单的递归遍历。这很 GOPHER 聪明，但它只适用于树木。如果你不是 John McCarthy，那么编写递归遍历会更容易，然后依靠我们之前看到的基于 gopher 并发的一般遍历来完成剩下的工作。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
