C++的函数式革命

jopen 10年前

C++就像是巨型油轮,转变航向非常耗时。但是随着多核时代的到来,想继续维持地位,C++不仅仅需要并发性(花了6年时间在C++11标准里加入这一点),它更需编程范式的大转变。

为什么要新的编程范式?在面向对象的基础上做点修改不行吗?要说这个不得不谈一谈编程的本质:可组合性(composability)。作为人类, 我们解决复杂问题的办法是把它分解为更小的子问题。这是一个递归式的过程,问题不断分解,直到子问题可以直接转变为代码,最后再组合。可组合性的关键就在 于每一层次都要隐藏复杂性。这也是面向对象编程成功的秘诀。对象内部复杂,但接口简单。你通过接口来组装部件,解决复杂问题。

但是对于并发性这个问题,对象隐藏了错误的细节。它们隐藏了共享(sharing)和变化(mutation)。数据竞争的定义是这样:2个或更多 线程同时访问同一段内存,至少1个写入。换句话说,共享+变化=数据竞争。对象的接口不会告诉你对象内部可能发生了共享和变化。每个对象自身内部可能不存 在数据竞争,但是它们的组合将不可避免的产生竞争。而如果不仔细分析每一次内存访问,你是发现不了问题的。

Java尝试用互斥锁(mutex)来缓解这个问题:每个对象都可以声明synchronized方法来调用这个锁。这不是一个可伸缩 (scalable)的解决方案,它产生了不能忽略的性能开销,所以程序员要对各种对象的内部细节了如指掌才能应用自如,而这恰恰是面向对象编程范式竭力 避免的。

更重要的是,锁机制(locking)本身是不可以组合的。一个经典例子是银行账户的存方法和取方法,这两个方法通过一个锁来同步。如果你试着把一 个账户的钱转到另外一个账户,问题出现了:如果不把锁暴露出来,“钱已经从A帐号扣除,但还未存入B帐号”这个临时状态就无法避免。而如果锁暴露在外,转 账过程中两把锁被同一资源占用,就可以能发生死锁。[软件事务性内存(Software Transactional Memory)对此提供了一个可组合(composable)的解决方案,但是除了Haskell和Clojure,其他语言没有实现能力。]

总之,如果我们想利用多核来提升性能,锁机制绝对不是好办法。我们要新方法。既然并发性的核心问题是共享和改变的冲突,解决办法就是对它们进行控 制。只要没共享,我们就能对关键内容进行修改。比如修改局部变量;或者通过深拷贝(deep copies)确定资源独占性,使用Move语义(move semantics),或者使用unique_ptr。资源独占在消息传递中扮演重要角色,可在线程间轻松传递大量数据。

多核编程的真正关键在于控制改变(mutation)。这就是函数式编程在并发和并行领域稳步上升的秘密。一句话,函数式程序员找到了一种用看起来 像是不可变数据(immutable data)来编程的方法。命令式程序员(imperative programmer)遇上不可变性(immutability),就如同烤肉师傅进了素食厨房,而C++标准库的几乎所有数据结构都不适合这种编程方 式,标准vector尤甚。一段连续的内存非常适合随机或者连续存取,但如果内存有改变,你就不能把它共享给两个线程。你可以用锁来控制vector,但 是就如之前所讲,用了锁你就别想要性能和可组合性了。

函数式数据结构的优势就在于它们表现得不可改变,所以多线程访问无需同步。改变被构建(construction)取代:你建立一个新对象,是对原 对象的复制,但进行了应有的改动。显然,如果你想对vector进行如上操作,你会需要大量的拷贝。但是函数式数据结构本身就是为最大化共享而设计的,所 以函数式的对象会与原始对象共享大部分数据。这种共享是透明的,因为原始对象是真正不可变的。

单链表就是这样一个绝不简单的典型数据结构。在链头插入一个元素,只需要建立一个新节点,存入数值和原链表的指针即可(原链表不可改变)。还有很多易于克隆和修改的树状结构,比如红黑树、左偏树。用函数式数据结构来实现并星算法更容易,因为程序员完全不用考虑同步问题。

函数式数据结构,又称为“持久性”(persistent)数据结构,天然具有可组合性。这是因为不可变的数据有可组合性,你可以用不变的小对象构 建不变的大对象。而且用构建(construction)的方式来改变(mutate)也可以很好的组合。一个组合的持久性对象可以被克隆-改变,只记录 改变的部分,其他不变的部分可以安全的共享。

并行还带来了不标准的控制流。大体上说,程序不再顺序执行。程序员需要应对控制流的反向,从一个句柄(handler)跳到另一个句柄,对共享的已 改变的状态进行追踪,等等。在函数式编程中这不是什么罕见的事。函数是一等公民,他们可以用多种方式组合。一个句柄(handler)只不过是一种延续传 递方式(continuation passing style)。延续(continuation)可以组合,虽然是以一种命令式程序员不熟悉的方式。函数式程序员有一个强大的组合型工具:单子 (monad),与别的工具一道,它们可以使逆向的控制流线性化(linearize inverted flow of control)。一旦你弄懂了这个,你就会更加理解并发编程的库的设计。

向函数式编程范式转变是一件不可避免的事,而且越来越多的C++程序员正在意识到这一点。以前我是一个在C++讨论会上聊Haskell和 monads的怪人,现在情况变了。今年的C++大会变化很大,最酷的人都在讨论函数式编程,“C++函数式数据结构”让我赢得了最具启迪奖。我认为这是 C++社区已经准备好进行改变的表现。

阅读原文 »

来自:http://top.jobbole.com/856/