函數式編程語言的「天然支持並行與並發」是不是吹牛？

希望能有實際的例子，請不要用f(g(x))這種等級的來做例子

---

不知道怎樣算天然，舉個例子吧，來源：Haskell in Production: Bdellium

將這一行代碼

map outputParticipant parts


改成

map outputParticipant parts `using` parListChunk 10 rdeepseq


在4核機器上速度快了3.7倍。

---

不是

這是純函數式編程的確定性/不變性所決定的。

當然什麼範式都扛不住SB程序員胡來。

---

函數式的"天然並行化", 之所以不容易開發, 其中原因是並行的粒度太細. 也就是說, 可以並行的部分太多, 規劃不好, 但凡能夠並行的都給並行的話, 開銷會異常恐怖.

譬如f(a,b,c,d,e), 傳入的參數全是整型參量, 也許理論上可以證明a,b,c,d,e是可以並行求值的. 如果對這些參量並行求值再傳入, 那麼因為這是很細粒度的並行, 並行通訊的開銷就會遠大於串列執行...

以上的信息是在一本90年代的鄭緯民寫的&<函數程序設計語言&>里講的.

函數程序設計語言--計算機模型、編譯技術、系統結構 (豆瓣)

書看上去不錯...不過買不到, 只在學校圖書館有.

函數式程序設計語言領域一個很重要的議題就是如何規劃並行粒度

一點更新，似乎函數式語言中，細粒度的並行性如果用到數字電路設計中，就不會那麼難以挖掘，比如我最近用來做了幾個課程設計的CλaSH - From Haskell to Hardware ，就可以把haskell語言編譯成verilog，vhdl，systemverilog，做到硬體電路上時，基本上是能夠並行的就並行了，我用它在FPGA上實現了堆排序、Dikjstra、N皇后問題等一些演算法。

用Haskell實現的可以運行在FPGA上的N皇后問題

Alaya-in-Matrix/clash-haskell-fpga · GitHub

---

我個人認為是吹牛

並發和並行在編程語言理論上是很虛的概念，一切都是編程範式的問題。

當然函數式編程不允許全局變數、無副作用這些語言級別的限制在編譯期就約束了程員，使得大家可以更好的做這件事情

（能在函數級別自動並行的語言，如Parallel Clean，也沒人用嘛，看看那本書就知道為啥沒人用了）

---

看到關於「map outputParticipant parts」的答案，想到我在用 Intel TBB 或者 Apple 的 GCD 在 C/C++ 里實現並行化也是類似的方法（評論里有人提到 OpenMP 更類似，勸一句搞工程的千萬別碰 OpenMP。這東西對 link 選項特別挑剔）。函數式語言在這方面的優勢可能有兩點：第一是明確了哪裡沒有 side-effect。這個工作在把串列 code 改寫成基於 TBB/GCD 的代碼時很費神。第二是 default lazy 語言里就少寫一些 closure。歸結到底還是 no fear refactor 的特性。

---

感覺現有的答案都沒說到點子上。

並發其實在計算複雜性那門課裡面是有明確定義的（上班時間答題，就不翻書了）。其中最容易為大家忽略的就是，並發並不是為了快，而是為了可擴展性。

就像前面 陳文龍 答案下 zhenghui zhou 的評論說的，修改之後的代碼，在單核上不一定比原版的快。修改之後的代碼的最大優勢在於，如果部署在多核的cpu上，不至於浪費其他cpu。

一個並發的程序，究竟能不能並行，取決於具體部署的物理設備。這就是並發與並行的區別。也就是廣為流傳的：「並發是指程序的結構，並行是指程序的部署」

簡單地說，並行是運維工程師的事情，程序猿只要考慮並發就行了。

一個真實世界的問題，有沒有對應一個可以解決它的並發的程序。這個是計算機科學領域的一個難題，據說比NP/P難題還要難。

為什麼這麼難，主要是因為這個問題是一個全稱命題。因為一個問題的解法可能有多個（比如排序就有多種演算法），這麼多演算法實現成代碼就更多了（這麼多編程語言，這麼多體系結構）。

在這種情況下，怎麼能斷定一個問題就沒有並行的程序可以來解決它呢？找不到並不能說明不存在啊。

舉個簡單的例子。我曾經認為足夠簡單的問題應該是原子的，不可能再拆，也無法並發了。比如自然數的加法。但是偶然間看到一篇論文，說的是並行加法器的設計。其大概原理是把數字x表示成 （x mod 3, x mod 5）這樣一個二元組（只能表示15以下的數字）。二元組的兩個分量就可以並行的去做加法操作。

同樣的，這種方法初看有點傻，還沒直接加快呢。但是重申前面的要點：並發不是為了快，而是為了可擴展性。

從並行加法器這個例子，也可以看到一點，其實表示方式對問題的解決思路有非常大的影響。也就是維特根斯坦說的：一切都是語言的問題。（當然這裡不是他本來的意思，但是領會精神吧。。。）

回到這個問題本身，「天然支持並行與並發」這種話當然是在吹牛，這可是世界級難題啊，可不是一個什麼世界上最好的語言就能解決的。當然使用函數式編程語言在這方面確實是有一些便利，其他答案都有說，就不再啰嗦了。

---

天然支持並行是可以的，天然支持並發是不可能的。

說天然支持並行是map等操作天生就可以並行，和非函數式的for each相比，因為沒有副作用，所以map等可以天然並行。對應的範例可以看spark的wordcount，它的map等部分是可以在不修改代碼的情況下並行到不同機器去。

file = spark.textFile("hdfs://...")
counts = file.flatMap(lambda line: line.split(" "))
.map(lambda word: (word, 1))
.reduceByKey(lambda a, b: a + b)
counts.saveAsTextFile("hdfs://...")


所有的並發都要求程序員要關注共享變數，函數式可以減少並發程序出現意外問題的概率，但是無法做到單線程和多線程執行的代碼一樣。所以我不認為可以叫做天然支持。

總結一下，我對於天然支持的理解是單線程的代碼可以不修改（或者極少的修改）就改為多線程跑。從這個標準來說，並行的天然支持是有的，並發是不可能的。

---

現有機器架構下所謂的並行，就是那幾種模式的。

據我個人所知，並行也就 鎖/原子，不可變，隔離，這幾種方案。

C，C++ 是默認不優先使用任何一種而已。

Rust只是默認用了 不可變 ，提供了 鎖/原子 而已。

Go和erlang是默認提供 隔離 方式，然後基於隔離又提供了一套通訊機制。

D 是 默認隔離。
所謂並發語言，也就是提供了優選機制，把此機制用語法糖 好用了而已。

C/C++ 這些機制同樣可以的，你也可以封裝庫提供類似的糖的。

函數式數據是不可變的，函數一般也要求無副作用。像erlang還是隔離的，提供一整套通訊機制。

---

並發

並發是多個線程一塊跑，並發的問題是數據爭用，解決數據爭用的一個辦法是鎖。

然而鎖是有問題的，性能開銷大，避免不了死鎖。

然而數據爭用的原因是多線程要訪問同一個可變變數。而純函數式編程沒有可變變數，自然就沒有問題。

並行

並行是把一個計算任務分配到多個處理器上，縮短計算時間。

命令式編程是低級抽象，考慮的是讀內存，運算，寫內存，指令跳轉，本質上是對馮諾依曼機的抽象。這種程序是無法並行的。

而函數式語言是基於數學函數的，關心做什麼，而非怎麼做，其中的不可變值，是可以通過變數替換完成的，理論上是可以通過λ演算進行計算，而不一定要通過馮諾依曼機。

由於函數式編程沒有副作用，可以調多次，由於參考透明，可以將計算的順序打亂。比如函數式語言的集合類提供的操作。後台是可以分成多個部分放到不同的處理器上做，再匯聚起來。

比如：

scala&> val numbers = List(1, 2, 3, 4)
numbers: List[Int] = List(1, 2, 3, 4)

scala&> numbers.map(x=&>x*2)
res3: List[Int] = List(2, 4, 6, 8)


程序員完全不關心，列表中的元素是從前到後依次計算的，還是從後到前依次計算的，是順序計算的，還是並行進行的計算。

更多請參見：什麼是函數式編程思維？ - 用心閣的回答

---

給右席 @裴文謙 一個贊，因為看到他博客有提到過，正如他所說的，It"s just a lie。

函數式因為沒有副作用的限制，可以實現某種程度的自動並行化，比如F(a, b)，這裡的a，b可以同時計算。

但是實際上並行化考慮的遠遠不止這些因素，誰能告訴編譯器，這裡的a和b到底是並行還是不並行好呢。何況談到自動並行化，我們還有更後現代的concurrent c呢。

更何況，談到並行，我們還有順序，同步的概念，否則在底層基於狀態的基礎上，這種並行化是毫無意義的。即便是再普通的語言，只要支持並行設施，誰都能把不相干的事情分解出來，而無需超人的腦力。

所以，在並行的基礎設施沒有充分保證並行的效率前提下，奢談並行都是無根之木，無源之水。

當然，函數式這種範式促進了自頂向下的思維，從而更利於並行演算法的構建，這是目前可見的實際好處，比如map reduce等並行演算法的出現。

---

我覺得sicp的的3.4部分說得非常好了，可以參考

---

immutable跟哪個p，不管是oop還是fp，沒有必然聯繫

其實lock也一樣，只是很多人把java==oop了，因為java現階段（不算正在做的value type的話）沒有immutable（除了string），而fp因為要避開副作用等原因，導致很多人認為有immutable==fp了，這種認識都是錯誤的

所以說天然支持blablabla，基本上都可以認為是吹牛

沒有什麼是天然支持的，這點看vert.x就很清楚了

管它什麼語言，不同語言的p不一樣，但是verticle之間一通信，就需要immutable和lock

一般實現的工具用lock，比如eventbus用concurrent hashmap，但是message用immutable

java以及各種腳本這種還沒有immutable type的腫么辦呢？

做成indeed immutable，拷貝一下就行了，看message codec的transform方法的實現

java好一點，可以用string或者原始數據類型，這都是immutable

如果不是，則要在傳送的時候，做一次拷貝，這樣就做成了indeed immutable

所以你要回答一個問題，有時候不能局限於某一個特定的語言

比如當你把環境限制為java vs clojure的話，甚至是把java narrow成spring的話

你就會認為因為clj == fp spring==oop -&> clj比spring更容易寫並發代碼 -&> fp天然支持並發

可以看出這個過程中充斥著各種概念上的扭曲和替換

但是如果你把你的視野打開，在vert.x這個平台上看這麼多種語言的對比

你就會發現很多問題，這個時候你就會知道，哦，原來這個是吹牛

你就會明白immutable!=fp獨有，oop也可以有immutable，比如java的string

coroutine就不是go獨佔，kt也能做

async／await也不是什麼很神奇的東西，一旦實現了協程，什麼語言也都能做

而這一切，都跟什麼p沒有必然的聯繫，跟什麼特定語言也沒有關係

只是有可能有些語言沒有，比如java暫時還沒有value type

腳本的話，沒有的就更多了

因為對比多了嘛，這就是vert.x為什麼好

想知道更多關於vert.x以及其他的知識，關注專欄：白木城全棧

---

假如認為Erlang是函數式編程語言的話, 並行和並發並不是吹牛.

應為它最多的應用環境是電話交換機、空中交通控制.

---

Clojure

For parallel: pmap

For concurrency: immutable data structure, atom, agent

---

純函數式編程語言適合併發和並行，這並不完全是吹牛。

首先限定一下，我本人在這個討論中要到的一些詞語的理解：

1. 純函數式，意思是無副作用，相同輸入必然得到相同輸出。
2. 高並發和高並行程度並不一定暗示高性能。

答題思路是，為什麼無副作用意味著適合併行，能夠做到高並發。我會從本人最近思考關於 Actor 模型的一些問題開始，記錄和演繹這個思考過程，從而達到對這個結論的理解。

也就是說，這個答案並不是一個證明過程，而僅僅是理解過程，並不具有完備性和通用性。並且寫作本文的時候，本人並沒有用過多少函數式編程語言作為編程主力。

一、從 Actor 死鎖開始談起

我一開始思考的問題是，Actor 能不能給自身發送消息？如果 Actor 要給自己發送消息為什麼不會死鎖，或者說為什麼不會死鎖。

想到這個問題是因為最近在嘗試用 C# 實現一個，「幫助一些普通類實現具有 Actor 特徵」 的簡單工具類。其實現原理是這樣的，利用 CPU 支持的原子性操作實現用戶態的 Semaphore（信號量），當搶佔失敗的時候利用 C# 的 TPL (Task Parallel Library) 實現非同步等待。從而，達到在物理上的效果是，儘可能少地讓線程被 OS 調度到 等待狀態。代碼寫起來大概是這樣的：

public async Task DoSthAsync(T1 p1, T2 p2) {
await this.actorHelper.ExecuteAsync(async () =&> {
await this.InternalDoSthAsync(p1, p2);
var c = await this.InternalDoAnotherAsync();
});
}

public async Task& DoAnotherAsync() {
return await this.actorHelper.ExecuteAsync(async () =&> {
return await this.InternalDoAnotherAsync();
});
}


和使用 Java 關鍵字 synchronized 時，代碼的形式是差不多的 。可以簡單理解為就是對當前對象加鎖，執行完事務之後再解鎖。在這裡，就是執行完 ExecuteAsync 所接收的 lambda 之後解鎖。

然而，就像所有的 加鎖解鎖機制一樣，偶爾會遇到死鎖問題。對我的 actorHelper 來說，只要在 ExecuteAsync 中嘗試調用其他有可能最終調用到 另一個 actorHelper 所加持的 方法，就會有可能死鎖。以下是一個死鎖的例子：

public async Task DoSthAsync(T1 p1, T2 p2) {
await this.actorHelper.ExecuteAsync(async () =&> {
await this.InternalDoSthAsync(p1, p2);
// 這裡從 InternalDoAnotherAsync 改為直接調用上述的 DoAnotherAsync
var c = await this.DoAnotherAsync();
// 就會毫無疑問地死鎖
});
}


死鎖的原因很簡單：因為在 DoSthAsync 還沒有釋放鎖的時候，DoAnotherAsync 就已經開始執行，並嘗試去等待鎖的釋放。而 DoSthAsync 要執行完成，必須先等待 DoAnotherAsync 執行完成。於是形成了死鎖。

所以，這個 actorHelper 需要改進。

雖然這個例子跟成熟的 Actor 模型實現框架相去甚遠，但是 Actor 模型也是要面臨相同的問題的。兩個問題的邏輯形式是一樣的。

因為 Actor 也是按照順序穿行地處理消息的，如果一個 Actor 在處理一個消息 A 的過程中，發送又一個消息 B 給這個 Actor 自身，並且要依賴 處理消息 B 的結果，那麼 Actor 肯定也是會死鎖的。

二、消息的組合不是一個消息

要怎麼做才能很方便地，讓 Actor 可以給自己發送消息呢？抑或說，Actor 給自己發消息本身就是反模式的呢？如果我們非要讓 Actor 自身能夠給自身發送消息，應該怎麼做？

事實上，有這麼一個說法：

當一個actor接收到消息後，它能做如下三件事中的一件：

* Create more actors; 創建其他actors

* Send messages to other actors; 向其他actors發送消息

* Designates what to do with the next message. 指定下一條消息到來的行為

作者：時見疏星

鏈接：http://www.jianshu.com/p/449850aa8e82

來源：簡書

著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

顯然這種說法認為 Actor 不應該給自己發消息。但是在 OO 的角度看來，方法就是拿來複用的，憑啥自己不能復用自己的消息處理邏輯呢？

如果非要這麼做，其中一個直觀的思路是這樣，可以讓 actorHelper 的功能更複雜一點，不僅僅是 ExecuteAsync 這麼一個功能，譬如說增加一個 ExecuteInternalAsync ，使得執行一段功能的時候不需要獲得鎖；或者是構造一個 內部鎖專門用於內部調用，要求先獲得第一階段鎖，再獲取第二階段鎖。

這個直觀思路隱含的假設其實是這樣的，Actor 本身需要先知道要執行的內容是什麼，或者 Actor 本身知道它需要處理的消息是誰發送過來的，以此來做區別性對待。

譬如說，如果 Actor 知道某個消息是自己發送給自己的，那麼 actorHelper 在處理這個消息的時候，就不需要加鎖了，這樣就避免死鎖了；又譬如說，如果知道要執行的東西實際上不處於有潛在競爭的環境中，那麼也可以不加鎖…… 很遺憾， Actor 並不是那麼聰明，所以這些事情都得留給程序員自己去判斷。

要滿足這兩種隱含假設，都是破壞 actorHelper 對其適用環境的假設。自己給自己發送的消息可能不會死鎖，事實上在 lambda 內調用的各種 DoInternal 就是一種隱式的內部消息，然而你不太可能將這些消息暴露給外界使用，因為你不能保證這些內部消息能夠在時間上和邏輯上都符合一定的先後順序；

需要預先知道執行的內容，這個就更……

等等，我們好像發現了什麼？預先知道執行內容的話，這不就是事務 (Transaction) 嗎？

實際上，一連串的消息處理，就是在執行一個事務，就像在 Actor 內部實現中的內部方法一樣，它們都是在一個被保證串列的環境中被執行的。在 Actor 模型中，一些簡單的功能能夠用一個個的消息來表示，在處理這些單個消息的時候，能夠保證它們不會被意外擾亂。也就是說，Actor 在處理單個消息時能夠保證其原子性。

實際上從 Actor 的角度來看，處理一個外部消息就是在執行多個內部消息的組合所形成的事務。只不過對於單一Actor 類來說，每個 Actor 所能執行的事務，是預先定義好的，也就是 Actor 所能響應的各種單個的外部消息。

但，如果需要保證的是外部消息的組合 所形成的事務呢？並且這些 外部消息 並不能全由一類 Actor 所能響應的呢？

我們固然可以形而上地將 外部消息的組合，視作一個消息，但這對於寫代碼的人來說根本就是毫無意義的思維方式。因為外部消息的組合，隱含的意思就是，沒有辦法在寫需求的那一刻就預計到這些消息具體怎麼組合。但事實就是，如果我們真的就有這麼抽象的需求，你說怎麼辦吧。

而編程語言及其工具，就是解決這類需求的軟體。

所以，理論上說，我們確實可以將各種消息組合而成的事務，當作一個消息發送給 Actor；但同時我們也必須意識到，這樣的消息的組合而形成的高級消息，如果要保證其靈活性、實際可用性，這個消息的解析複雜度，至少相當於編譯並執行一個簡單的編程語言。

但別忘了，我們本身就是在使用某種編程語言，來實現 Actor 框架，並且打算用這些 Actor 來做某些事情。現在我們討論到，這些 Actor 怎樣才能靈活地完成各種事務。

很明顯，讓一個或多個 Actor 都具有這麼強大的能力（接收並編譯運行一個完整的編程語言所寫的代碼段），這是不符合經濟效益的。

於是，按照分治的理念，我們可以讓 Actor 只理解並執行這種服務於我們的事務處理的編程語言的一部分指令，另一種 Actor 理解並執行另一部分指令，並且每一種 Actor 都能夠理解這個代碼段被執行到哪裡了，並能夠把指令派發給執行下一條指令的 Actor…… 這樣，我們就能夠有一個可以隨時隨地計算任意事務中的任意一部分的 Actor 集群。

媽的，這些不就是 CPU ，CPU 指令集，調用棧、和棧寄存器么……只不過在 Actor 模型的語境裡面，這些 CPU 指令的威力比較大，不是簡單地對數值進行運算；而處在棧寄存器角色的 Actor 要記住的也不僅僅是所程序片段當前執行的指令，在內存中的偏移量。

更重要的是，這個 CPU 的是多少核的、內存有多大，是完全可以線性增長的。只要我們為每一種指令的執行單元——Actor 配備的數量足夠多，再通過足夠告訴的網路鏈接起來，那麼這些就是單元之間的組合就是一個 CPU 和內存。

三 純函數式編程和 Actor 事務集群的形式相似性

終於可以說到正題了。用多種 Actor 來實現事務，是怎麼跟純函數式編程扯上關係的。

從上述虛構的 Actor 集群中觀察到，如果要使我們的業務語言能夠支持高並發甚至並行的方式，在不同 Actor 中傳遞，我們必須假設同一類型的 Actor 之間是等價的，因此執行事務中的上一個指令的 Actor 可以任意地將事務作為一個消息整體傳遞給下一個指令。

為了保證事務的原子性，那就需要保證傳遞給每個 Actor 執行的事務的每一條指令，必須是連續執行的，中間不能被外部狀態干擾。但是一個 Actor 肯定是要多次接收相同的若干種指令的啊，那怎麼可能做到呢？

我們可以改變一下思維方式，如果 Actor 內部的狀態不可控，那麼就應該保證事務的狀態在執行過程中是可控的。也就是說，用多個 Actor 實現事務，不僅僅要在給 Actor 的消息中包含指令，還必須包含完整的狀態，並且要保證 Actor 自身的狀態不會意外地干涉到事務的狀態，除非這種干涉是有計劃的——

也就是說，對於相同事務的相同指令，不同 Actor 的執行結果應該是一樣的，不然指令就不太可能任意指派給同類型的任意 Actor。

希望這樣，可以理解到純函數式的編程語言，為何天然地支持高並發。

1. 任何函數都不能干涉計算本身，除非該函數本身是 IO 相關的
2. 把整個計算邏輯任務和狀態（即指令和數據），傳給計算過程中的所有函數。

於是並發或者並行的能力上限只取決於 CPU 核數、CPU計算速度、IO 速度、以及數據傳遞的速度。計算過程中的任意一個子過程都可以參與復用，提高並發或者並行的能力。

---

參見erlang

---

唉 我記得在說這個的時候說的是不可變性吧。。也就是函數式語言提供的不可變數據結構天然支持並行和並發。。。

---

是。

我覺得，並行的基礎不是不可變，而是向量化。

---

當然不是吹牛，只不過只適用於簡單的並行場景。

並發/並行要想有用就離不開I/O，就必然有狀態。「蠢函數式」要求無狀態，所以一旦涉及到I/O就需要各種歪門邪道，單線程情況下還行，想靠純FP來並行？可以，只要不做有用的事，不涉及I/O，無狀態，純計算，那就真的和宣稱的那樣，隨便並行。

---

為什麼VHDL和Verilog不算併發語言？為什麼一定要Functional Programming Language？

---

推薦閱讀：