一个小例子按惯例我们还是从一个例子开始。想一下如果给定一组文件名要求数一下文件里的总文本行数你会怎么做我们先规定一下函数的原型int count_lines(const char** begin, const char** end);也就是说我们期待接受两个 C 字符串的迭代器用来遍历所有的文件名返回值代表文件中的总行数。要测试行为是否正常我们需要一个很小的 main 函数int main(int argc, const char** argv) { int total_lines count_lines( argv 1, argv argc); cout Total lines: total_lines endl; }最传统的命令式编程大概会这样写代码int count_file(const char* name) { int count 0; ifstream ifs(name); string line; for (;;) { getline(ifs, line); if (!ifs) { break; } count; } return count; } int count_lines(const char** begin, const char** end) { int count 0; for (; begin ! end; begin) { count count_file(*begin); } return count; }我们马上可以做一个简单的“说明式”改造。用 istream_line_reader 可以简化 count_file 成int count_file(const char* name) { int count 0; ifstream ifs(name); for (auto line : istream_line_reader(ifs)) { count; } return count; }在这儿要请你停一下想一想如何进一步优化这个代码。然后再继续进行往下看。如果我们使用之前已经出场过的两个函数transform [1] 和 accumulate [2]代码可以进一步简化为int count_file(const char* name) { ifstream ifs(name); istream_line_reader reader(ifs); return distance(reader.begin(), reader.end()); } int count_lines(const char** begin, const char** end) { vectorint count(end - begin); transform(begin, end, count.begin(), count_file); return accumulate( count.begin(), count.end(), 0); }这个就是一个非常函数式风格的结果了。上面这个处理方式恰恰就是 map-reduce。transform 对应 mapaccumulate 对应 reduce。而检查有多少行文本也成了代表文件头尾两个迭代器之间的“距离”distance。函数式编程的特点在我们的代码里不那么明显的一点是函数式编程期望函数的行为像数学上的函数而非一个计算机上的子程序。这样的函数一般被称为纯函数pure function要点在于会影响函数结果的只是函数的参数没有对环境的依赖返回的结果就是函数执行的唯一后果不产生对环境的其他影响这样的代码的最大好处是易于理解和易于推理在很多情况下也会使代码更简单。在我们上面的代码里count_file 和 accumulate 基本上可以看做是纯函数虽然前者实际上有着对文件系统的依赖但 transform 不行因为它改变了某个参数而不是返回一个结果。下一讲我们会看到这会影响代码的组合性。我们的代码中也体现了其他一些函数式编程的特点函数就像普通的对象一样被传递、使用和返回。代码为说明式而非命令式。在熟悉函数式编程的基本范式后你会发现说明式代码的可读性通常比命令式要高代码还短。一般不鼓励甚至完全不使用可变量。上面代码里只有 count 的内容在执行过程中被修改了而且这种修改实际是 transform 接口带来的。如果接口像之前展示的 fmap 函数一样返回一个容器的话就可以连这个问题都消除了。C 毕竟不是一门函数式编程语言对灵活性的追求压倒了其他考虑。高阶函数既然函数对象可以被传递、使用和返回自然就有函数会接受函数作为参数或者把函数作为返回值这样的函数就被称为高阶函数。我们现在已经见过不少高阶函数了如sorttransformaccumulatefmapadder事实上C 里以 algorithm算法名义提供的很多函数都是高阶函数。许多高阶函数在函数式编程中已成为基本的惯用法在不同语言中都会出现虽然可能是以不同的名字。我们在此介绍非常常见的三个map映射、reduce归并和 filter过滤。Map 在 C 中的直接映射是 transform在 头文件中提供。它所做的事情也是数学上的映射把一个范围里的对象转换成相同数量的另外一些对象。这个函数的基本实现非常简单但这是一种强大的抽象在很多场合都用得上。Reduce 在 C 中的直接映射是 accumulate在 头文件中提供。它的功能是在指定的范围里使用给定的初值和函数对象从左到右对数值进行归并。在不提供函数对象作为第四个参数时功能上相当于默认提供了加法函数对象这时相当于做累加提供了其他函数对象时那当然就是使用该函数对象进行归并了。Filter 的功能是进行过滤筛选出符合条件的成员。它在当前 CC20 之前里的映射可以认为有两个copy_if 和 partition。这是因为在 C20 带来 ranges 之前在 C 里实现惰性求值不太方便。上面说的两个函数里copy_if 是把满足条件的元素拷贝到另外一个迭代器里partition 则是根据过滤条件来对范围里的元素进行分组把满足条件的放在返回值迭代器的前面。另外remove_if 也有点相近通常用于删除满足条件的元素。它确保把不满足条件的元素放在返回值迭代器的前面但不保证满足条件的元素在函数返回后一定存在然后你一般需要使用容器的 erase 成员函数来将待删除的元素真正删除。命令式编程和说明式编程传统上 C 属于命令式编程。命令式编程里代码会描述程序的具体执行步骤。好处是代码显得比较直截了当缺点就是容易让人只见树木、不见森林只能看到代码啰嗦地怎么做how而不是做什么what更不用说为什么why了。说明式编程则相反。以数据库查询语言 SQL 为例SQL 描述的是类似于下面的操作你想从什么地方from选择select满足什么条件where的什么数据并可选指定排序order by或分组group by条件。你不需要告诉数据库引擎具体该如何去执行这个操作。事实上在选择查询策略上大部分数据库用户都不及数据库引擎“聪明”正如大部分开发者在写出优化汇编代码上也不及编译器聪明一样。这并不是说说明式编程一定就优于命令式编程。事实上对于很多算法命令式才是最自然的实现。以快速排序为例很多地方在讲到函数式编程时会给出下面这个 Haskell一种纯函数式的编程语言的例子来说明函数式编程的简洁性quicksort [] [] quicksort (p:xs) (quicksort left) [p] (quicksort right) where left filter ( p) xs right filter ( p) xs这段代码简洁性确实没话说但问题是上面的代码的性能其实非常糟糕。真正接近 C 性能的快速排序在 Haskell 里写出来一点不优雅反而更丑陋。所以我个人认为说明式编程跟命令式编程可以结合起来产生既优雅又高效的代码。对于从命令式编程成长起来的大部分程序员我的建议是写表意的代码不要过于专注性能而让代码难以维护——记住高德纳的名言“过早优化是万恶之源。”使用有意义的变量但尽量不要去修改变量内容——变量的修改非常容易导致程序员的思维错误。类似地尽量使用没有副作用的函数并让你写的代码也尽量没有副作用用返回值来代表状态的变化——没有副作用的代码更容易推理更不容易出错。代码的隐式依赖越少越好尤其是不要使用全局变量——隐式依赖会让代码里的错误难以排查也会让代码更难以测试。使用知名的高级编程结构如基于范围的 for 循环、映射、归并、过滤——这可以让你的代码更简洁更易于推理并减少类似下标越界这种低级错误的可能性。这些跟函数式编程有什么关系呢——这些差不多都是来自函数式编程的最佳实践。学习函数式编程也是为了更好地体会如何从这些地方入手写出易读而又高性能的代码。不可变性和并发在多核的时代里函数式编程比以前更受青睐一个重要的原因是函数式编程对并行并发天然友好。影响多核性能的一个重要因素是数据的竞争条件——由于共享内存数据需要加锁带来的延迟。函数式编程强调不可变性immutability、无副作用天然就适合并发。更妙的是如果你使用高层抽象的话有时可以轻轻松松“免费”得到性能提升。拿我们这一讲开头的例子来说对代码做下面的改造启用 C17 的并行执行策略 [5]就能自动获得在多核环境下的性能提升int count_lines(const char** begin, const char** end) { vectorint count(end - begin); transform(execution::par, begin, end, count.begin(), count_file); return reduce( execution::par, count.begin(), count.end()); }我们可以看到两个高阶函数的调用中都加入了 execution::par来启动自动并行计算。要注意的是我把 accumulate 换成了 reduce [6]原因是前者已经定义成从左到右的归并无法并行。reduce 则不同初始值可以省略操作上没有规定顺序并反过来要求对元素的归并操作满足交换律和结合率加法当然是满足的即当然在这个例子里一般我们不会有海量文件即使有海量文件并行读取性能一般也不会快于顺序读取所以意义并不是很大。下面这个简单的例子展示了并行 reduce 的威力#include chrono #include execution #include iostream #include numeric #include vector using namespace std; int main() { vectordouble v(10000000, 0.0625); { auto t1 chrono:: high_resolution_clock::now(); double result accumulate( v.begin(), v.end(), 0.0); auto t2 chrono:: high_resolution_clock::now(); chrono::durationdouble, milli ms t2 - t1; cout accumulate: result result took ms.count() ms\n; } { auto t1 chrono:: high_resolution_clock::now(); double result reduce(execution::par, v.begin(), v.end()); auto t2 chrono:: high_resolution_clock::now(); chrono::durationdouble, milli ms t2 - t1; cout reduce: result result took ms.count() ms\n; } }在我的电脑Core i7 四核八线程上的某次执行结果是accumulate: result 625000 took 26.122 msreduce: result 625000 took 4.485 ms执行策略还比较新还没有被所有编译器支持。我目前测试下来MSVC 没有问题Clang 不行GCC 需要外部库 TBBThreading Building Blocks[7] 的帮助。我上面是用 GCC 编译的命令行是g-9 -stdc17 -O3 test.cpp -ltbbY 组合子限于篇幅这一讲我们只是很初浅地探讨了函数式编程。对于 C 的函数式编程的深入探讨是有整本书的而今天讲的内容在书的最前面几章就覆盖完了。在后面我们还会探讨部分的函数式编程话题今天我们只再讨论一个有点有趣、也有点烧脑的话题Y 组合子。第一次阅读的时候如果觉得困难可以跳过这一部分。不过我并不打算讨论 Haskell Curry 使用的 Y 组合子定义——这个比较复杂需要写一篇完整的文章来讨论而且在 C 中的实用性非常弱。我们只看它解决的问题如何在 lambda 表达式中表现递归。回想一下我们用过的阶乘的递归定义int factorial(int n) { if (n 0) { return 1; } else { return n * factorial(n - 1); } }注意里面用到了递归所以你要把它写成 lambda 表达式是有点困难的auto factorial [](int n) { if (n 0) { return 1; } else { return n * ???(n - 1); } }下面我们讨论使用 Y 组合子的解决方案。我们首先需要一个特殊的高阶函数定义为显然这个定义有点奇怪。事实上它是会导致无限展开的——而它的威力也在于无限展开。我们也因此必须使用惰性求值的方式才能使用这个定义。然后我们定义阶乘为假设 fact 可以表示成 y(F)那我们可以做下面的变形再把 y(F) 替换成 f我们从上面的第二个式子得到我们得到了 F 的定义也就自然得到了 fact 的定义。而且这个定义是可以用 C 表达出来的。下面是完整的代码实现#include functional #include iostream #include type_traits #include utility using namespace std; // Y combinator as presented by Yegor Derevenets in P0200R0 // url:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html template class Fun class y_combinator_result { Fun fun_; public: template class T explicit y_combinator_result( T fun) : fun_(std::forwardT(fun)) { } template class... Args decltype(auto) operator()(Args... args) { // y(f) f(y(f)) return fun_( std::ref(*this), std::forwardArgs(args)...); } }; template class Fun decltype(auto) y_combinator(Fun fun) { return y_combinator_result std::decay_tFun( std::forwardFun(fun)); } int main() { // 上面的那个 F auto almost_fact [](auto f, int n) - int { if (n 0) return 1; else return n * f(n - 1); }; // fact y(F) auto fact y_combinator(almost_fact); cout fact(10) endl; }这一节不影响后面的内容看不懂的可以暂时略过。内容小结本讲我们对函数式编程进行了一个入门式的介绍希望你对函数式编程的特点、优缺点有了一个初步的了解。然后我快速讨论了一个会烧脑的话题Y 组合子让你对函数式编程的威力和难度也有所了解。