使用递归函数类型的一种 CPS 状态机写法

go 可以定义直接递归的复合类型，也就是在类型的定义中，使用正在定义的类型名。

而函数是类型的一种，所以可以定义一个函数类型，它的返回值的类型是这个函数本身。

例如：

type Proc func() Proc

上面这个类型，可以用来表示状态机中的一个状态，结合 CPS 手法，就可以实现一种协程。

计数状态机

一个例子，从1数到10：

package main

import "fmt"

type Proc func() Proc

func Count10(n int, cont Proc) Proc {
	return func() Proc {
		fmt.Printf("%d\n", n)
		if n == 10 {
			return cont
		}
		return Count10(n+1, cont)
	}
}

func main() {
	proc := Count10(1, nil)
	for proc != nil {
		proc = proc()
	}
}

上面的 main 函数中，for 语句如果换成

	proc = proc()
	proc = proc()
	proc = proc()
	proc = proc()

则只会打印1到4，这个状态机的步进是可控的。

多个 Proc 也可以实现并发乱序执行：

func main() {
	rand.Seed(int64(time.Now().UnixNano()))
	var procs []Proc
	for i := 0; i < 128; i++ {
		procs = append(procs, Count10(1, nil))
	}
	for len(procs) > 0 {
		n := rand.Intn(len(procs))
		if cont := procs[n](); cont != nil {
			procs[n] = cont
		} else {
			procs = append(procs[:n], procs[n+1:]...)
		}
	}
}

如果需要更多状态，可以将状态放入 struct，然后定义 Proc 为该 struct 的方法，这样就能在 Proc 内读写状态。一个例子是：https://github.com/reusee/sb/blob/cdbe32270fd478df2d5e6b1a603c22497e70e8d6/marshal.go#L11

生成器

对 Proc 的类型稍作修改，可以实现一种生成器

type Proc func() (int, Proc)

上面这个类型，可用于实现 int 序列的生成器。例如 fib 序列：

package main

import "fmt"

type Proc func() (int, Proc)

func FibGen() func() int {
	proc := func() (int, Proc) {
		return 1, func() (int, Proc) {
			return 1, fib(1, 1, nil)
		}
	}
	return func() (ret int) {
		ret, proc = proc()
		return
	}
}

func fib(a int, b int, cont Proc) Proc {
	return func() (int, Proc) {
		return a + b, fib(b, a+b, cont)
	}
}

func main() {
	gen := FibGen()
	for i := 0; i < 10; i++ {
		fmt.Printf("%d\n", gen())
	}
}

连续调用 gen，可以生成 fib 序列。

一个完整的生成器的例子是：https://github.com/reusee/sb/blob/bbd151e5dcae0ab38515793de3f1133920dd7e74/marshal.go#L11

后记

能实现这种写法，需要几个语言机制的配合。一是递归的类型定义，一是函数字面量，一是方法可以作为值传递。不是每门语言都有这些特性，尤其是递归类型定义，一些新出的语言也没有。所以并不是语言有很多 fancy 的东西，就是好。基础不牢，地动山摇。语言特性做得正交，容易组合使用，不会出现某个特性很难和另一个特性结合使用这种情况，显然是更高明的语言设计哲学。