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 的 Array.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