序

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

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

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

正文

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

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

haskell

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

先看看這個用法，let a0 = runST $ newSTRef 0，會引發(fā)一個type error。因為runST的類型是(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)出具體實現(xiàn)，大家就能看出他做的事情就是做了一層wrapper，在type checker上保證被box之后不會被用戶取出來亂改。至于如何做到destructive in-place update，這就屬于編譯器的黑魔法了，語言這層只需保證語義就好。（**注：**ghc的實現(xiàn)中，ST Monad標(biāo)準(zhǔn)庫用到了ghc的unsafe打頭的內(nèi)置函數(shù)）

Clean

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

先舉個栗子~

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]..]}

（不要在意奇怪的語法，｛｝里面其實就是list comprehension）

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

最后

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