FPer對OO批評最多的是：由于OO允許在運(yùn)行時修改狀態(tài)遥金，從而無法做到引用透明(Referiential Transparency)临燃。換句話說：對于同一個函數(shù)睛驳，使用相同的輸入?yún)?shù)，每次調(diào)用返回的結(jié)果卻不相同谬俄。比如：
struct Foo
{
int inc(int b)
{
a += b;
return a;
}
private:
int a = 1;
};
void f()
{
Foo foo;
std::cout << foo.inc(2) << std::endl; // 3
std::cout << foo.inc(2) << std::endl; // 5
}
但是柏靶，OO社區(qū)的人對此卻并不買賬。認(rèn)為對象的狀態(tài)雖然允許修改溃论，但其實(shí)并沒有改變引用透明性屎蜓。因?yàn)楹瘮?shù)Foo::inc事實(shí)上有一個隱藏參數(shù)this。站在這個角度钥勋，兩次調(diào)用的輸入?yún)?shù)其實(shí)并不相同炬转。反過來辆苔，對于狀態(tài)完全相同的兩個對象，如果其它輸入?yún)?shù)也相同扼劈，其輸出也必然相同驻啤。Nothing Different！
但是荐吵，在多線程模式下骑冗，如果兩個線程同時持有同一個可修改狀態(tài)的對象，那么程序運(yùn)行結(jié)果將會處于不確定狀態(tài)先煎。除非像FP那樣贼涩，將對象修改為不可變的，每次計算都產(chǎn)生一個新的對象來作為輸出薯蝎。比如：
struct Foo
{
Foo(int a) : a(a) {}
Foo inc(int b) const
{
return a + b;
}
private:
int a = 1;
};
這就是多線程模式下的Shared Nothing策略遥倦。
另外，對于支持惰性求值（Lazy Evaluation）的語言占锯，不可變性（Immutability）是必須被保證的袒哥。因?yàn)樵?strong>非嚴(yán)格（non-strict）、惰性求值的語言里消略，表達(dá)式都是按需求值（call-by-need）的堡称。換句話說，對于任意兩個表達(dá)式疑俭，其估值順序很可能是不確定的粮呢。這就意味著，如果兩個表達(dá)式持有同一個可修改狀態(tài)的對象钞艇，那么計算結(jié)果也會隨著求值順序的變化而變化啄寡。這也喪失了引用透明性。
當(dāng)然哩照，并不是所有的FP語言都支持惰性求值挺物。而惰性求值本身也是個充滿爭議的選擇。因而飘弧，對于嚴(yán)格求值的語言识藤，不可變性的價值就僅限于并行計算。
因而次伶，OO程序員的觀點(diǎn)是：并行計算真正需要的是Shared Nothing痴昧。而Shared Nothing有更為廉價的手段來滿足。而不是只有代價高昂的不可變性這一種選擇冠王。
比如赶撰，多線程間可以全部通過消息來通信，同樣可以達(dá)到線程間Shared Nothing的目的。同時線程內(nèi)部允許修改狀態(tài)豪娜，又能夠避免不必要的性能損失餐胀。兩全其美！
而這正是多核時代絕大多數(shù)程序員的選擇瘤载。這也是go-lang的并發(fā)策略：
Do not communicate by sharing memory; instead, share memory by communicating.
當(dāng)然否灾，F(xiàn)Per可以繼續(xù)闡述不可變性的好處：由于其絕大部分代碼天然就是Shared Nothing的，可以更容易的將任何一段代碼投入并行運(yùn)算鸣奔。
這確實(shí)是一個無可比擬的優(yōu)勢墨技。但在現(xiàn)實(shí)項目中，需要發(fā)揮這種優(yōu)勢的概率有多高溃蔫，卻是一個值得思考的問題健提。畢竟琳猫，不可變性不是免費(fèi)的伟叛。在考慮它能發(fā)揮的價值的同時，也必須要為之付出的代價脐嫂，把兩個因素放到一起统刮，結(jié)合項目的實(shí)際情況，做出務(wù)實(shí)的選擇账千，才是一個合格的工程師應(yīng)該具備的態(tài)度侥蒙。
性能永遠(yuǎn)都是一個問題
很多FPer為了鼓吹FP在描述算法方面的優(yōu)勢時，總愛舉這個例子：
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
確實(shí)優(yōu)雅的無與倫比匀奏。
對比之下鞭衩，C語言版本的實(shí)現(xiàn)就就冗長的多：
void qsort(int a[], int lo, int hi)
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);
a[hi] = a[l];
a[l] = p;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
不過那些FPer沒有告訴你們故事的另一面：相對于C語言版本，那份看起來很優(yōu)雅的Haskell實(shí)現(xiàn)娃善，無論在時間效率還是空間效率方面论衍，都糟糕的一塌糊涂。
Haskell是一門默認(rèn)惰性求值的FP語言聚磺。從理論上坯台，惰性求值可以可以讓程序員可以站在更高抽象層面寫程序，不用關(guān)心程序的執(zhí)行順序瘫寝，語言的runtime會自動避免掉那些不必要的計算蜒蕾。
但惰性求值也不是免費(fèi)的，對于暫時無需求值的表達(dá)式焕阿，需要以thunk的形式在內(nèi)存中駐留咪啡，這就會導(dǎo)致不可控的空間占用。另外暮屡，由于需要不斷的對是否已經(jīng)求值進(jìn)行判斷撤摸，惰性求值也會付出一定的性能代價。
更為麻煩的是，作為一門惰性求值語言愁溜，正如我們之前所描述的疾嗅，即便不考慮并行運(yùn)算，只是因?yàn)槠淝笾淀樞虻牟淮_定冕象，就會導(dǎo)致：即便在局部范圍代承，每一個變量的不可變性也是必須的。
而這種不可變性對于性能的損耗渐扮，在很多“狀態(tài)修改密集型”的算法面前论悴，已經(jīng)到了讓人無法容忍的地步。
為了解決這類問題墓律，不得不引入局部狀態(tài)可修改的機(jī)制膀估。其中之一，就是Monad.ST耻讽。
Monad.ST
Monad.ST的思想察纯，就是引入引用的概念。也就是說针肥，在一段計算中饼记，不同的表達(dá)式，可以通過引用慰枕，指向同一個可修改的數(shù)據(jù)具则。不同表達(dá)式都可以根據(jù)需要對數(shù)據(jù)直接修改，而不是創(chuàng)建一份新數(shù)據(jù)的拷貝具帮。
-- A MutVar# behaves like a single-element mutable array.
data MutVar# s a
-- Create MutVar# with specified initial value in specified state thread.
newMutVar# :: a -> State# s -> (# State# s, MutVar# s a #)
-- Read contents of MutVar#. Result is not yet evaluated.
readMutVar# :: MutVar# s a -> State# s -> (# State# s, a #)
-- Write contents of MutVar#.
writeMutVar# :: MutVar# s a -> a -> State# s -> State# s
這是個GHC編譯器內(nèi)部實(shí)現(xiàn)的MutVar#博肋，從它的名字就可以看出，這是一個Mutable Variable蜂厅。而其后綴符號\\#則說明匪凡，這是一個Unboxed Type。其三個主要函數(shù)用到了另外一個類型State#葛峻，也是一個GHC編譯器內(nèi)部實(shí)現(xiàn)的Unboxed Type锹雏。
data State# s
MutVar#是一個類型構(gòu)造器，有兩個參數(shù)：a是要存儲的數(shù)據(jù)類型术奖。而s則代表是狀態(tài)礁遵。從邏輯上，MutVar#自身是一個引用采记，其引用的數(shù)據(jù)類型為a佣耐，而空間則從s所管理的存儲上分配。如下圖所示唧龄。
因而兼砖，我們可以寫出下面的代碼：
calc' :: (Num a) => State# s -> a -> a
calc' initS initV =
let (# s1, ref #) = newMutVar# initV initS
(# s2, v1 #) = readMutVar# ref s1
s3 = writeMutVar# ref (v1*10) s2
(# s4, v2 #) = readMutVar# ref s3
s5 = writeMutVar# ref (v2+20) s4
(# _finalS, finalV #) = readMutVar# ref s5
in finalV
從這段代碼，可以清晰的看出一個三部曲操作模式：
- 在初始狀態(tài)分配一個內(nèi)容為初始值的數(shù)據(jù)，然后得到一個引用讽挟，以及被修改的狀態(tài)懒叛；
- 不斷通過引用，讀寫數(shù)據(jù)內(nèi)容耽梅；注意薛窥，中間狀態(tài)也在不斷改變和傳遞；
- 最后眼姐，丟棄最終狀態(tài)诅迷，從引用里讀出數(shù)據(jù)返回。
在各個步驟間众旗，變量的依賴罢杉，保證了即便在惰性求值下它們也會按照順序處理。由于變化的是狀態(tài)贡歧，狀態(tài)依次在步驟間傳遞滩租，這樣的模式，是一種典型的State Monad艘款。
newtype ST s a = ST (STRep s a)
type STRep s a = State# s -> (# State# s, a #)
instance Monad (ST s) where
return x = ST (\\\\ s -> (# s, x #))
(ST m) >>= k
= ST $ \\\\s ->
case (m s) of { (# new_s, r #) ->
case (k r) of { ST k2 -> (k2 new_s) }}
為了方便于Monad內(nèi)部的代碼編寫持际，以及類型系統(tǒng)的約束，再提供如下輔助函數(shù)：
data STRef s a = STRef (MutVar# s a)
newSTRef :: a -> ST s (STRef s a)
newSTRef init = ST $ \\\\s1# ->
case newMutVar# init s1# of { (# s2#, var# #) ->
(# s2#, STRef var# #) }
readSTRef :: STRef s a -> ST s a
readSTRef (STRef var#) = ST $ \\\\s1# -> readMutVar# var# s1#
writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef (STRef var#) val = ST $ \\\\s1# ->
case writeMutVar# var# val s1# of { s2# ->
(# s2#, () #) }
modifySTRef :: STRef s a -> (a -> a) -> ST s ()
modifySTRef ref f = writeSTRef ref . f =<< readSTRef ref
然后就可以這樣來寫代碼：
calc' :: Int -> ST s Int
calc' initV = do
ref <- newSTRef initV
v1 <- readSTRef ref
writeSTRef $ v1 * 10
v2 <- readSTRef ref
writeSTRef $ v2 + 20
readSTRef ref
需要特別指出的是哗咆，由于State和initV都是calc'函數(shù)的參數(shù)，因而calc'依然是個pure function益眉，因而具備pure function的一切特質(zhì)晌柬。比如引用透明。 其中每個步驟都是一個State Transformer郭脂，通過>>=,>>組合為一個更大的State Transformer年碘，這也正是是ST名字的由來。
不過展鸡，calc'的結(jié)果依然還保存在ST Monad里屿衅。好在除了IO Monad之外，其它Monad的數(shù)據(jù)都可以從Monad里逃出莹弊。對于ST Monad涤久，則是通過runST：
runST :: (forall s. ST s a) -> a
runST st = runSTRep (case st of { ST st_rep -> st_rep })
runSTRep :: (forall s. STRep s a) -> a
runSTRep st_rep = case st_rep realWorld# of
(# _, r #) -> r
在runST里，一個具體的狀態(tài)實(shí)例作為參數(shù)傳給了State Transformer忍弛。而這個實(shí)例响迂，則是GHC編譯器提供的readWorld#，其類型為GHC內(nèi)置的ReadWorld#细疚。
因而我們的例子可以寫成：
calc :: Int -> Int
calc initValue = runST $ calc' initValue
對命令式的模仿
runST是一個重要的邊界：它創(chuàng)建了一個初始狀態(tài)蔗彤，傳遞給State Transformer，然后得到一個最終狀態(tài)，以及計算的結(jié)果然遏。最后贫途，拋棄掉最終狀態(tài)，僅保留計算結(jié)果待侵。
如果我們把這一系列的機(jī)制和命令式語言對應(yīng)起來潮饱，可以看出，這完全是對命令式語言局部變量處理的模擬诫给。
對于命令式語言香拉，所有的局部變量都是在線程的棧上分配，從而修改了Stack的狀態(tài)中狂。隨后所有的讀寫操作也都在棧上進(jìn)行凫碌，不斷修改Stack的狀態(tài)。在一個函數(shù)處理結(jié)束后胃榕，在棧上分配的局部變量都會自動釋放盛险，關(guān)心的數(shù)據(jù)則當(dāng)作函數(shù)的返回值返回。如下圖所示勋又。
而在ST Monad里苦掘，runST對應(yīng)的是命令式語言的函數(shù)，而Stack對應(yīng)的則是State：在計算開始時楔壤，提供一個State鹤啡，計算在State上分配數(shù)據(jù)，存取State的狀態(tài)蹲嚣，等計算結(jié)束后递瑰，State的最終狀態(tài)被拋棄，返回計算結(jié)果隙畜。如下圖所示抖部。
這樣的模仿，相對于命令式語言的局部變量可變性议惰，并未得到任何額外的好處慎颗。但很明顯，命令式語言在這類問題上的處理要簡潔的多言询。同時也說明了俯萎，允許局部變量的可修改性，對于引用透明和線程安全沒有任何影響倍试，只會帶來簡潔和性能讯屈。
Rank 2 Type
我們設(shè)想一下，在命令式語言里县习，在一個函數(shù)調(diào)用結(jié)束后涮母，如果其在棧里的分配的數(shù)據(jù)不釋放谆趾，可以被隨后的函數(shù)訪問，那么那些數(shù)據(jù)就與全局變量無異了叛本。我們都知道沪蓬，全局變量是違背Shared Nothing原則的。
通過上述對照来候，我們知道State是對Stack的模仿跷叉。在runST結(jié)束后，State也必須像Stack一樣被釋放营搅，避免被其它計算繼續(xù)使用云挟，這才能保證線程安全。
可是转质，如果我們寫下這樣的代碼：
f1 :: STRef s a -> ST s a
f1 ref = do
v <- readSTRef ref
writeSTRef $ v * 10
readSTRef ref
let ref = runST $ newSTRef 10
v1 = runST $ readSTRef ref
v2 = runST $ f1 ref
in ...
這就造成了ref在多個runST之間傳遞园欣。對于惰性求值的語言而言，runST的求值順序是不確定的休蟹，從而導(dǎo)致v1和v2計算結(jié)果的不確定沸枯。這就像多線程程序共享同一份數(shù)據(jù)，卻沒有任何措施來保證對共享數(shù)據(jù)訪問的序列化一樣赂弓，是一個嚴(yán)重的問題绑榴。
不過，ST設(shè)計者通過引入Rank 2 Types解決了這個問題盈魁。Rank 2 Types不屬于Hindley-Milner類型系統(tǒng)的范疇翔怎。也不在haskell 98里。但這對于很多設(shè)計卻又是比不可少的备埃。
在Rank 1 Type的一個函數(shù)里姓惑，每個類型變量，只能被綁定為一個類型按脚。這就導(dǎo)致了，如果一個高階函數(shù)的某個參數(shù)是一個參數(shù)化多態(tài)（Parametric Polymorphism）函數(shù)敦冬，那么在這個高階函數(shù)里辅搬，無論那個參數(shù)化多態(tài)函數(shù)被調(diào)用多少次，其類型變量所綁定的類型都必須是一致的脖旱。比如下面的代碼就無法通過編譯：
g :: (a -> a) -> (Bool, Char)
g f = (f True, f 'c')
因?yàn)椋?code>f在同一個函數(shù)g的上下文里堪遂，兩次調(diào)用里，其類型變量a被綁定的類型是不同的：一個是Bool萌庆，一個是Char溶褪。
這明顯是一個給程序員帶來麻煩的問題。因而践险，GHC給出了一個擴(kuò)展猿妈，叫Rank2Types吹菱。它允許程序員通過將上面例子中函數(shù)g的類型修改為：
g :: (forall a. a -> a) -> (Bool, Char)
某種程度上，你可以將Rank 2 Types理解為C++的Template Template Parameter技術(shù)彭则，比如：
template <typename T, typename G,
template <typename E> class Container >
struct Foo
{
Container<T> tContainer;
Container<G> gContainer;
};
下面我們來看看為何Rank 2 Type可以解決runST狀態(tài)泄漏的問題鳍刷。我們先來推導(dǎo)一下表達(dá)式runST $ newSTRef 10的類型：
runST :: (forall s. ST s a) -> a
newSTRef 10 :: forall s. ST s (STRef s Int)
[STRef s Int ~ a]
因而，
runST $ newSTRef 10 :: (forall s. ST s (STRef s Int)) -> STRef s Int
其中俯抖，s已經(jīng)出現(xiàn)在\\\\(\\forall s\\\\)的限定范圍之外输瓜，因而編譯器將不會通過編譯。
但是芬萍，如果runST的類型為forall s. ST s a -> a尤揣，上述類型則變?yōu)椋?/p>
runST $ newSTRef 10 :: forall s. ST s (STRef s Int) -> STRef s Int
在這個類型里，兩個s都在同一個限定符的作用范圍內(nèi)柬祠，因而它能夠通過編譯北戏。
反過來，假設(shè)ref = runST $ newSTRef 10這樣的代碼通過了編譯瓶盛，它將被代入的表達(dá)式：runST $ readSTRef ref：
\\ \\ Int})
由此可見最欠，s是環(huán)境中的自由變量，readVar ref的類型與runST所需的\\\\(\\forall s. ST\\ \\ s\\ \\ a\\\\)類型不匹配惩猫，因而也無法通過編譯芝硬。
因此，借助于Rank 2 Types的類型檢查轧房，程序員不可能寫出能夠讓state從一個runST泄露的代碼拌阴。從而保證了安全性。
模仿C語言算法
搞定了ST Monad之后奶镶，我們終于可以使用它所提供的機(jī)制來模仿C語言算法了：
import Control.Monad (when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray
qsort :: (IArray a e, Ix i, Enum i, Ord e) => a i e -> a i e
qsort arr = processArray quickSort arr
processArray :: (IArray a e, IArray b e, Ix i)
=> (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e
processArray f (arr :: a i e) = runST $ do
arr' <- thaw arr :: ST s (STArray s i e)
f arr'
unsafeFreeze arr'
quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m ()
quickSort arr = qsort' =<< getBounds arr
where
qsort' (lo, hi) | lo >= hi = return ()
| otherwise = do
p <- readArray arr hi
l <- mainLoop p lo hi
swap l hi
qsort' (lo, pred l)
qsort' (succ l, hi)
mainLoop p l h | l >= h = return l
| otherwise = do
l' <- doTil (\\\\l' b -> l' < h && b <= p) succ l
h' <- doTil (\\\\h' b -> h' > l' && b >= p) pred h
when (l' < h') &\\\\$& do
swap l' h'
mainLoop p l' h'
doTil p op ix = do
b <- readArray arr ix
if p ix b then doTil p op (op ix) else return ix
swap xi yi = do
x <- readArray arr xi
readArray arr yi >>= writeArray arr xi
writeArray arr yi x
這個版本迟赃，相對于C語言版本，已經(jīng)比C的寫法還要繁雜厂镇。但不幸的是纤壁，即便經(jīng)過這樣的努力，此版本的性能捺信，雖然相對于之前那個簡介而優(yōu)雅的版本酌媒，得到了一定的提升，但其性能依然得到了這樣的評價：
The program below is working very very slowly. It's probably slowsort... :o)
終于迄靠，有高手看不過去了秒咨，干脆祭出unsafe大法：通過放棄編譯器檢查的安全性，來提高程序的性能掌挚，然后得到了這個版本：
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST
myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
| lo < hi = do
let lscan p h i
| i < h = do
v <- unsafeRead a i
if p < v then return i else lscan p h (i+1)
| otherwise = return i
rscan p l i
| l < i = do
v <- unsafeRead a i
if v < p then return i else rscan p l (i-1)
| otherwise = return i
swap i j = do
v <- unsafeRead a i
unsafeRead a j >>= unsafeWrite a i
unsafeWrite a j v
sloop p l h
| l < h = do
l1 <- lscan p h l
h1 <- rscan p l1 h
if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
| otherwise = return l
piv <- unsafeRead a hi
i <- sloop piv lo hi
swap i hi
myqsort a lo (i-1)
myqsort a (i+1) hi
| otherwise = return ()
終于雨席，得到了這樣的評價：是C語言版本運(yùn)行時間的2倍以內(nèi)。
... reports that this version runs within 2x of the C version.
結(jié)論
對于命令式語言而言吠式，對于一個函數(shù)內(nèi)的局部變量的修改陡厘，并不會引入任何副作用抽米，因?yàn)槊總€線程都有自己的棧，不同線程會從自己的棧上為局部變量分配空間雏亚。因而線程間也是100%的Shared Nothing缨硝。
但FP對于不可變性的堅持，讓程序員在這類問題上也不得不付出不必要的代價罢低。為了解決這類的問題查辩，F(xiàn)P也不得不去模擬在命令式語言的行為。這這類的模擬行為必須有編譯器的內(nèi)建支持网持，否則宜岛，在Pure FP自身的語義下，是不可能存在reference to mutable variable這樣的元素的功舀。而這一切的努力萍倡，在命令式語言里，不過是再自然不過的內(nèi)建支持辟汰。另外列敲，即便付出這樣的努力，由于FP自身的特點(diǎn)帖汞，其性能依然比C語言要慢的多戴而。
由于變量的缺位，F(xiàn)P只能以遞歸的方式來處理循環(huán)問題翩蘸。但一些FPer卻把這種不得不為之的結(jié)果鼓吹為: 遞歸是描述問題最自然的方式所意。
但事實(shí)上，確實(shí)一些問題用遞歸描述起來更加自然催首，但同樣也有一些問題扶踊，用迭代的方式描述起來更加自然。更不用說郎任，在性能約束面前秧耗，很多無法自然描述為尾遞歸問題的算法，不得不修改為迭代算法舶治，卻又受語言能力所限绣版，不得不用遞歸的語法表述迭代算法，讓代碼看起來更加晦澀歼疮。
而命令式語言，同時支持遞歸和迭代兩種方式诈唬，其中一些（比如C++)也支持對于尾遞歸的優(yōu)化韩脏。這就讓程序員擁有了更加自由的選擇≈酰可以根據(jù)不同問題域做出最合理的決策赡矢。
因而杭朱，給出靈活度和自由度，讓程序員自己根據(jù)需要做出決策吹散，要比強(qiáng)制程序員必須在所有情況下都必須遵守某種方式要更有價值弧械。
