C++ 中的 Continuation-Passing Style

最后更新日期：2021-04-05

　　先说一下何为 Continuation-Passing Style 。在我的理解中，Continuation-Passing Style 是指，一个函数想要返回一个结果，但并不是通过 return 返回，而是将结果传给一个回调函数。

　　考虑一个基本问题：将一个整数序列化成 ASCII 编码的字符串，或者更广义的如何序列化对象的问题。一个简单的想法是返回一个 std::string ，但如果要序列化的对象比较大，占用内存较多，同时如果这个对象序列化后是写入 stdout 或文件 / 网络，那为什么不直接 write 呢，这样还可以省去内存分配。

　　所以我们的问题变成了：如何编写一个通用的序列化函数，可以同时用于序列化到内存缓冲区和用户终端（以及其他任意对象 / 网络 / 文件）？。

　　下面我给出一种方案：

#include <string>

/**
 * @param padTo 结果前面用 0 补齐的位数
 */
template<class Yield>
void formatInt(unsigned int n, uint8_t padTo, Yield&& yield) {
    if (n == 0) {
        if (padTo == 0) {
            yield('0');
        } else {
            for (; padTo > 0; padTo--) {
                yield('0');
            }
        }
        return;
    }
    static constexpr int BUF_SIZE = sizeof(unsigned int) * 8;
    char buf[BUF_SIZE];
    int pos = BUF_SIZE;
    while (n > 0) {
        int r = n % 10;
        pos--;
        assert(pos >= 0);
        buf[pos] = '0' + r;
        n /= 10;
    }
    const int len = BUF_SIZE - pos;
    for (; padTo > len; padTo--) {
        yield('0');
    }
    yield(std::string_view(buf + pos, BUF_SIZE - pos));
}

　　这里的重点不是具体的序列化算法，而是其中叫“yield”的模板参数。相信你已经看出来了，这里的 yield 就是很多现代编程语言都有的 coroutine / generator 中的 yield ，它表示：从协程中返回一个值。但我们的程序只是借鉴了这个概念，并未真正用到协程。

　　下面给出输出到 std::cout 的代码，很简单：

formatInt(42, 4, [](auto&& a) { std::cout << a; }); // => 0042

输出到 std::string 要稍微复杂一些，需要一个辅助类 StringPusher：

class StringPusher {
    std::string& str;
public:
    StringPusher(std::string& str): str(str) {}
    void operator()(char c) {
        str.push_back(c);
    }
    void operator()(std::string_view buf) {
        str.append(buf.data(), buf.size());
    }
};

std::string s;
StringPusher push(s);

formatInt(42, 4, push); // => 0042

　　总结一下就是：这个序列化函数并不是返回 string ，而是返回 Generator[byte] ，即一个字节序列的生成器。而 std::cout 或 StringPusher 则起到字节序列的接收器的作用。套用生产者-消费者模型来说，formatInt 是生产者，std::cout 或 StringPusher 是消费者。

　　考虑另一个常见问题：将一个字符串按指定的分隔符分割。应该如何设计这个函数的接口？

　　常规的做法是返回一个字符串数组，如 js 的 String.prototype.split 和 Java 的 String.split ，而 boost::algorithm::split 要求传入一个容器的左值引用作为输出参数，本质上跟返回数组没什么区别。

　　在 C++ 中返回数组并非最优设计，因为用户可能只需要一边生成一边使用，用完就销毁，并不需要把所有字符串存起来。所以我们可以不用返回字符串数组，而是返回字符串生成器，即 Generator[string] 。但这里我们仍旧只是借用协程的思想，并不实际使用协程，因为真正的协程代价还是比较高。generator 翻译成 C++ 标准库的语言则是 OutputIterator ，用 CPS 风格来表述则是回调函数。

　　如下是一个使用回调函数作为输出的 split 的简单实现：

/**
 * 会保留最后一个空串，例：
 * ",".split(',') -> ["", ""]
 */
class Split {
    char delim;
public:
    Split(char delim): delim(delim) {}
    template<class Yield>
    const char* operator()(const char* first, const char* last, Yield&& yield) {
        const char* start = first;
        const char* i = std::find(start, last, delim);
        while (i != last) {
            yield(std::string_view(start, i - start));
            start = i + 1;
            i = std::find(start, last, delim);
        }
        yield(std::string_view(start, last - start));
        return last;
    }
};

　　使用：

std::string_view s("a,b");

int i = 0;
Split(',')(s.data(), s.data() + s.size(), [&](std::string_view part) {
    std::cout << "item " << i << ": " << part << std::endl;
    i++;
});

　　每个 part 都是随用随销毁，没有多余的内存分配。体现出了 generator / 回调函数风格的高效。

　　不过有个问题在回调函数风格中可能会比普通风格中麻烦一点：如果处理到中间的某个地方，想要直接退出，怎么办？

　　一个简单粗暴的解决方案是使用异常。我们可以约定一个异常，专门用来表示退出 coroutine ，比如名字叫 ExitCo 。这就要求相关代码是异常安全的，如果使用了外部资源，应该用 RAII 包装。

struct ExitCo {};

　　使用：

try {
    int i = 0;
    Split(',')(s.data(), s.data() + s.size(), [&](std::string_view part) {
        // 最多处理前 5 个
        if (i >= 5) {
            throw ExitCo();
        }
        std::cout << "item " << i << ": " << part << std::endl;
        i++;
    });
} catch (const ExitCo&) {}

　　总结：个人认为 C++ 中凡是需要返回数组的时候，都可以考虑使用回调函数来避免多余的内存分配。

　　如果你更喜欢传统的 C++ ，也可以使用 Output Iterator（参考 std::transform）。但 Output Iterator 的缺点在于必须采用运算符重载的方式实现，会多一层 proxy object 。而用 Yield 模板参数的好处是，如果你想用真正的 coroutine ，可以直接传入 boost::coroutines2::coroutine::push_type ，代码不用做任何改动。

　　相关概念的对比表：

名称	boost coroutines2	CPS 风格	C++ 标准库	GC 语言（js / Python / Java / Go）	多线程（生产者-消费者模式）
接收器	push-coroutine	回调函数	Output Iterator	状态机（state machine） / reducer / Iteratee	消费者
生成器	pull-coroutine	自己实现类似 java.util.Iterator 的一个类	两个 Input Iterator: first, last	generator, java.util.Iterator	生产者
缓冲区	无	返回容器	用容器保存中间结果	返回数组	Disruptor / concurrent queue / go channel / actor mailbox

　　回调函数相当于一个大小为 0 的 go channel ，而大小为 0 的 go channel 相当于一个 condition variable 。