序

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

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

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

正文

首先，純函數式的語言強調沒有副作用，它不會改變任何實際的東西，當然也沒有（全局的）狀態，這樣的程序如果不配上代表副作用的輸入輸出當然是什么都干不了的。那么如何把副作用嵌入到本不該有副作用的語言設計中那？當然不能直接賦值，不然。。不然。。就變成命令式語言了，而且函數式語言編譯中引以為豪的各種優化pass幾乎都不能用了。那么把有副作用的函數標注出來？當然是一個辦法。還有就是把副作用的表達式都包含在context中，隨著函數傳遞，保證順序而且要保證引用的唯一性。

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

haskell

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

其中最關鍵的是ST s a 與 STref s a 這兩個數據結構。

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

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

不用標出標出具體實現，大家就能看出他做的事情就是做了一層wrapper，在type checker上保證被box之后不會被用戶取出來亂改。至于如何做到destructive in-place update，這就屬于編譯器的黑魔法了，語言這層只需保證語義就好。（**注：**ghc的實現中，ST Monad標準庫用到了ghc的unsafe打頭的內置函數）

Clean

Clean語言用的策略是線性類型系統（linear type system），是Substructural type sysytem的一種。在Curry-Howard同構中對應Substructrual logic。這類類型系統中，不但可以決定一個變量是什么類型，還可以約束被使用的次數與順序。在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的標注，這個函數的類型用haskell寫出來就是transform :: (Int -> Int) -> *[Int] -> *[Int]。這個函數雖然沒有很好的看出uniqueness type的特性和傳播性，但是作為簡單的例子，差不多就是這么回事。
對于uniqueness type最直觀的理解就是帶有這個標識的類型是不能參與到以后Graph Reduction中，而且會檢測會不會有多個“變量”指向他。上面這個函數中就不會存在多個[Int]及相關的副本等著被回收，而是會直接在（ReadWorld中的）內存上更新數據。

最后

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