序

函數(shù)式編程語(yǔ)言有很多種定義，寬泛的認(rèn)為支持高階函數(shù)（higher-order function）就算函數(shù)式語(yǔ)言的話，大多數(shù)現(xiàn)代語(yǔ)言都是支持函數(shù)式編程的，例如C/C++，java，C#，lua，python，JavaScript，Scala等等。收緊一下定義的話，加入函數(shù)式語(yǔ)言要求的模式匹配、無(wú)副作用等要求，那么剩下的就是純函數(shù)式語(yǔ)言，比較常見(jiàn)的有Haskell，Clean等。

副作用是什么和為什么有些語(yǔ)言想在設(shè)計(jì)上避免副作用這個(gè)問(wèn)題，google能搜出好多博文，這里就不多說(shuō)了。避免副作用可以帶來(lái)一些實(shí)際的好處，比如幫你大量改寫(xiě)代碼什么的（誤），而且連gcc都有 _ _ attribute _ _((pure/const))的函數(shù)擴(kuò)展嘛~。比如像erlang這種依賴于副作用編程的語(yǔ)言，雖然有著變量不可變這個(gè)特性，但是仍然可以讀寫(xiě)process攜帶的全局變量，而且又沒(méi)有一個(gè)好的類型系統(tǒng)，所以在編譯的時(shí)候也不會(huì)怎么大改你的代碼，大多還是直譯成字節(jié)碼。

注：這篇文章不是**軟文**，不會(huì)用個(gè)g(f(x))就當(dāng)例子給大家說(shuō)無(wú)副作用多么多么好，可緩存結(jié)果拉(just a lie)~原生支持并行拉(just another lie)，這些都是扯淡而且不實(shí)際的。（有機(jī)會(huì)再寫(xiě)個(gè)博客專門(mén)談?wù)勥@個(gè)）

正文

首先，純函數(shù)式的語(yǔ)言強(qiáng)調(diào)沒(méi)有副作用，它不會(huì)改變?nèi)魏螌?shí)際的東西，當(dāng)然也沒(méi)有（全局的）狀態(tài)，這樣的程序如果不配上代表副作用的輸入輸出當(dāng)然是什么都干不了的。那么如何把副作用嵌入到本不該有副作用的語(yǔ)言設(shè)計(jì)中那？當(dāng)然不能直接賦值，不然。。不然。。就變成命令式語(yǔ)言了，而且函數(shù)式語(yǔ)言編譯中引以為豪的各種優(yōu)化pass幾乎都不能用了。那么把有副作用的函數(shù)標(biāo)注出來(lái)？當(dāng)然是一個(gè)辦法。還有就是把副作用的表達(dá)式都包含在context中，隨著函數(shù)傳遞，保證順序而且要保證引用的唯一性。

作為純函數(shù)式語(yǔ)言的代表，Haskell和Clean對(duì)于副作用的設(shè)計(jì)實(shí)現(xiàn)上差別很大，下面就簡(jiǎn)單說(shuō)一下它們的實(shí)現(xiàn)，刨根究底，其實(shí)它們做的還是同一件事情。

haskell

Haskell中有一個(gè)很重要的概念：Monad，取名自范疇論，可以粗淺的認(rèn)為它就是定義了一系列的行為準(zhǔn)則（>>= , return）。Haskell中大多數(shù)語(yǔ)法糖都是為了這個(gè)發(fā)明來(lái)的。Haskell的標(biāo)準(zhǔn)庫(kù)中有很多關(guān)于副作用的類庫(kù)封裝，比如IORef，MVar，IOMonad等等，他們的內(nèi)部實(shí)現(xiàn)都會(huì)歸結(jié)到ST Monad（State Thread Monad）上，正是這個(gè)與forall關(guān)鍵字的結(jié)合，從而在語(yǔ)法上保證了副作用嵌入在（純）Haskell中的正確性。
ST Monad里面主要的定義是：

 newtype ST s a = ST (STRep s a)
 type STRep s a = State# s -> (# State# s, a #)
 data STRef s a = STRef (MutVar# s a)

 runST :: (forall s. ST s a) -> a
 runSTRep :: (forall s. STRep s a) -> a
 

其中最關(guān)鍵的是ST s a 與 STref s a 這兩個(gè)數(shù)據(jù)結(jié)構(gòu)。

先看看這個(gè)用法，let a0 = runST $ newSTRef 0，會(huì)引發(fā)一個(gè)type error。因?yàn)閞unST的類型是(forall s.ST s a) -> a ，參數(shù)(newSTRef 0)的類型是forall s. ST s (STRef s Int)，最后求值后的結(jié)果是a0::STRef s Int，顯然s脫離了原本的定義域（也就是那層forall之外，forall是Haskell中提供**RankNType**的關(guān)鍵字）。從而用戶就只能使用下面的方式：

sumST :: Num a => [a] -> a
sumST xs = runST $ do          
    n <- newSTRef 0             
    forM_ xs $ \x -> do        
    modifySTRef n (+x)     
    readSTRef n     

不用標(biāo)出標(biāo)出具體實(shí)現(xiàn)，大家就能看出他做的事情就是做了一層wrapper，在type checker上保證被box之后不會(huì)被用戶取出來(lái)亂改。至于如何做到destructive in-place update，這就屬于編譯器的黑魔法了，語(yǔ)言這層只需保證語(yǔ)義就好。（**注：**ghc的實(shí)現(xiàn)中，ST Monad標(biāo)準(zhǔn)庫(kù)用到了ghc的unsafe打頭的內(nèi)置函數(shù)）

Clean

Clean語(yǔ)言用的策略是線性類型系統(tǒng)（linear type system），是Substructural type sysytem的一種。在Curry-Howard同構(gòu)中對(duì)應(yīng)Substructrual logic。這類類型系統(tǒng)中，不但可以決定一個(gè)變量是什么類型，還可以約束被使用的次數(shù)與順序。在Mozilla出的Rust語(yǔ)言中，也可以看到線性類型的影子。

先舉個(gè)栗子~

transform :: (Int -> Int) *{#Int} -> *{#Int} 
transform f s
 | size s == 0 = s
 | otherwise   = if (s.[0] == 0)
                   {f i \\ i <-: s}
                   {f i \\ _ <-: s & i <- [s.[0]..]}

（不要在意奇怪的語(yǔ)法，｛｝里面其實(shí)就是list comprehension）

其中*就是uniqueness type的標(biāo)注，這個(gè)函數(shù)的類型用haskell寫(xiě)出來(lái)就是transform :: (Int -> Int) -> *[Int] -> *[Int]。這個(gè)函數(shù)雖然沒(méi)有很好的看出uniqueness type的特性和傳播性，但是作為簡(jiǎn)單的例子，差不多就是這么回事。
對(duì)于uniqueness type最直觀的理解就是帶有這個(gè)標(biāo)識(shí)的類型是不能參與到以后Graph Reduction中，而且會(huì)檢測(cè)會(huì)不會(huì)有多個(gè)“變量”指向他。上面這個(gè)函數(shù)中就不會(huì)存在多個(gè)[Int]及相關(guān)的副本等著被回收，而是會(huì)直接在（ReadWorld中的）內(nèi)存上更新數(shù)據(jù)。

最后

其實(shí)已經(jīng)看出，在上面Haskell與Clean的做法中，一個(gè)是利用forall關(guān)鍵字與ST Monad+編譯器黑魔法，另一個(gè)是build-in在類型系統(tǒng)中，但是本質(zhì)都是做了一件事情，就是保證RealWorld中的對(duì)象不會(huì)存在多個(gè)引用，而且在Graph Reduction中不會(huì)被編譯器搞亂順序，這樣就能融入到整個(gè)純函數(shù)式的大體系中了。