状态机与函数式编程

最后更新日期：2023-12-22

　　在编程中，我们常用的迭代器（iterator）与我今天要说的状态机（state machine）都是对“流”（stream）的抽象，只不过一个是拉（pull），一个是推（push）。

　　迭代器的定义一般是这样的：

class Iterator[T] {
  T next();
}

　　即调用一个函数，它不断返回流中的下一个元素。通常还需要其他机制来指示迭代结束，比如添加一个 bool hasNext() 方法（Java），返回两个值，第二个 bool 值表示迭代是否结束（js），抛一个特定异常（Python）等。

　　任何数据流都有生产者（Producer）和消费者（Consumer），迭代器是生产者的一种抽象，那如果我们把消费者抽象出来，会是什么样的？

• 在计算机科学中，称这种东西称为状态机（state machine）或自动机（automata）
• Rx 框架称其为 Observer ，也就是可以订阅由 Observable 发出的事件的东西，由 OnNext, OnComplete, OnError 三个回调函数构成，只不过 Rx 框架更强调自己是异步的
• 一个更函数式的抽象是从 (状态, 输入) 变换成新的状态，比如 reducer
• Haskell 将它抽象为 iteratee

　　我这篇文章还是使用计算机科学的术语，称其为状态机。我理解的状态机的接口定义是这样的：

class Pusher[T] {
  void Push(T); // 将一个元素推给状态机
  void Flush(); // 标记一个阶段结束
}

　　如果跟 Go 语言中的 io.Writer 接口对比，是不是非常相似？事实上，我认为 Go 的 io.Reader 可以类比为迭代器，io.Writer 可以类比为状态机。

　　下面就是有意思的部分了：如果我们可以在迭代器的接口上实现各种函数式编程的操作（如 filter, map ），那我们能否在状态机的接口上实现同样的操作呢（只不过是以 push 的视角）？答案是肯定的。

　　当然，Rx 框架也可以看作一种实现，只不过我认为它太复杂了，还不如我自己实现。

　　下面是我用 Go 语言实现的简易 Pusher 及其 filter 定义：

type Pusher[T any] interface {
  Push(T)
  Flush()
}

type PusherFilter[A any] struct {
  next   Pusher[A]
  filter func(A) bool
}

func NewPusherFilter[A any](f func(A) bool, next Pusher[A]) *PusherFilter[A] {
  return &PusherFilter[A]{next, f}
}

func (t *PusherFilter[A]) Push(a A) {
  if t.filter(a) {
    t.next.Push(a)
  }
}

func (t *PusherFilter[A]) Flush() {
  t.next.Flush()
}

pusher := NewPusherFilter(func(item *Item) bool { return productSet[item.Product] }, files)

　　这种东西有什么用？我们通常更习惯使用迭代器和基于迭代器的函数式操作，但很多时候，设计一个基于迭代器的流式接口可能是很麻烦的。考虑一个例子：遍历文件目录树，流式地返回每个文件的信息。如果一定要做成迭代器，调用一个函数才返回下一个文件信息，那我们不得不手动构造一个栈（stack）来保存中间状态，程序写起来并不直观。

　　但如果我们用状态机来设计这个东西的接口又如何？我们可能会得到如下接口：

void walk_dir(string dirname, Pusher[FileInfo] pusher);

　　这样做的好处是让 walk_dir 可以用递归来实现。这里的 pusher 就是一个状态机，你也可以把它近似地看成一个回调函数，但跟回调函数的不同之处在于，Pusher 是可组合（composable）的！我们可以通过 map 、filter 等组合子（combinators）构造出新的匿名 Pusher 。这种可组合性（composability）跟迭代器如出一辙。当然也有不好的一面：失去了迭代器的可以在中间任意位置停下来的能力。

　　回到 Go 语言本身，由于 Go 语言的迭代器接口还遥遥无期，我这里提出的 Pusher 是一种围魏救赵的办法。关于 pull 和 push 的对偶性（duality），也可以参考 Go 语言核心开发者 rsc 的讨论：user-defined iteration using range over func values · golang/go · Discussion #56413 。

相关文章：