C++的函數式革命

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++社區已經準備好進行改變的表現。

閱讀原文 ?