早上收到網友email，說無名的網誌備份檔用我的程式打不開
看了一下，找到問題並這樣回復該網友：

用記事本打開您的備份檔
搜尋 2003-02-29
改成 2003-02-28
即可開啟

(註：2003年不是潤年，沒有29號，無名的程式真的很厲害)

又開始覺得blogger貼code有點麻煩了，有點想轉回自架的wordpress

用內建的Editor縮排常會跑掉，對python和haskell這種indention關鍵的語言是很嚴重的
貼gist還OK，可是有時候三四行的東西還要貼gist去做syntax highlight很麻煩。
另外覺得最近github好慢，在一篇文章裡放好幾個embed gist，載入時會一直卡在gist那邊

考慮一下要不要搬回自架的wordpress

承上篇，今天來解釋第三個版本的實作(源碼)。

我看Monad

在解釋下面的東西前，必需先多討論一下Monad。

Haskell的文件並不多，大部份介紹Monad的文章都是從fail, Computation, Maybe Monad下手。我用一句話來說明我「目前」對Monad的領悟：「Monadic value是一種靜態資料，通常表示了一種狀態的轉移」我不知道這個領悟是否完全正確，如果有錯的話歡迎指教討論。

初學Haskell時，我將IO Monad視為一種神奇的指令。在一切都是純函數的世界中，只有IO Monad是特立獨行的。像是putStr getStr這些指令，當出現在程式碼中時，IO Monad會主動去破壞純粹函數的世界，造成side effect….blah blah。

在多看一些書和文件之後，我了解到IO Monad也是單純的靜態資料。在ghc下觀察一下：

Prelude> :t putStr
putStr :: String -> IO ()
Prelude> :t putStr "Hello"
putStr "Hello" :: IO ()
Prelude> let a = putStr "Hello"
Prelude> :t a
a :: IO ()
Prelude> a
Hello
Prelude>

putStr是一個函數，給予String後就會吐出一個IO ()型別的資料。let a = putStr “Hello”，這個Monadic value不是什麼可怕的指令，既不會動也不會咬人，更不會主動地破壞美好的函數世界。一直到a這個值被evaluate，才會真正地與外在世界互動。

那為什麼要說Monadic value通常記載了狀態的改變呢？讓我們從State Monad開始討論吧。ghc標準庫中Control.Monad.State.State的定義為 newtype State s a = State { runState :: (s -> (a,s)) } s為該State Monad記住的狀態型別，a為附帶的回傳值之型別。我們可以看到，一個State Monadic value中只有一種資料：給定一個狀態，得到一個新的狀態，並且回傳一個附帶的值。Monadic value本身描述了「狀態如何轉移」。

讓我舉個實例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import Control.Monad.State

type IntState = State Int

inc :: IntState ()
inc = do
  v <- get
  put (v + 1)

twice :: IntState ()
twice = modify ( * 2 )

calculate = do
  twice
  inc
  twice

這個例子簡單地使用Int做為狀態，並且定義了一些狀態的轉移。inc為將原本的整數加一，twice為將原本的整數乘以二。calculate則是狀態轉移的合併：乘以二，加一，再乘以二。

*Main> :t inc
inc :: IntState () -- inc是IntState ()的Monadic value
*Main> :t calculate
calculate :: IntState () -- calculate也是
*Main> execState calculate 1 -- 將原本的state(1)經過calculate的狀態轉換
6
*Main> execState calculate 3 -- 將原本的state(3)經過calculate的狀態轉換
14
*Main> let c = calculate >> calculate -- 將兩個calculate疊加起來，產生一個新的狀態轉換
*Main> execState c 3 -- 將c這個狀態轉換施加於3上
58

模組化

1. HBF.TapeList : 如同上一篇文章所述，我們在記憶code及memory時都需要一個類似磁帶的結構。TapeList將這個結構及其運算抽象化。
2. HBF.CharIO : Brainfuck只需要用到兩種IO：字元輸入及字元輸出。CharIO定義了一個class將這件事抽象化，以方便Brainfuck Interpreter橋接到IO及pure function。
3. HBF.VM : Brainfuck Virtual Machine (事實上只是Interpreter核心而已，我沒有做複雜的事)。
4. HBF.Test.xxx : 單元測試。

HBF.TapeList模組

1
2
3
4

data TapeList a = TapeList {
  leftTP :: [a],
  rightTP :: [a]
} deriving(Show)

這個沒啥好講的，就把重複利用的資料結構汎化而已。完全透過吃TapeList吐TapeList的pure function來操作。

HBF.CharIO模組

這個模組很簡單，但卻是重頭戲。Brainfuck需要兩種IO指令：一次輸入一個字元、一次輸出一個字元。在Haskell我們會盡量希望pure (functional) code和impure code分離。理論上Brainfuck的確需要輸入輸出，但我卻希望能將VM與標準IO解耦，讓後端的VM code同時可以達到兩種效果：

1. 正常地使用標準IO運行
2. 化為pure function，給定輸入及要運行的BF程式，得到輸出字串，類似這樣的效果：

1
2

run :: String -> String -> String
run code input = xxx output

要達到這樣的效果，第一件要做的事就是將IO抽象化。我們先定義一個class：

1
2
3

class (Monad m) => CharIO m where
  getCh :: m (Maybe Char)
  putCh :: Char -> m ()

首先，這個class是Monad的subclass。putCh為輸出字元的動作，是不會失敗的。但getCh的動作可能會因無法讀取而失敗(原因後述)，因此我們將其形別定為m (Maybe Char)。

接下來，我們將標準IO橋接至CharIO。方法很簡單，將IO變成CharIO的Instance即可：

1
2
3
4
5

instance CharIO IO where
  getCh = do
  c <- getChar
  return $ Just c
  putCh = putChar

putCh直接接到putChar，非常簡單明瞭。另外，在標準輸入中我們不考慮讀取失敗的情況，所以就直接c <- getChar再return $ Just c。這樣就完成了CharIO及標準IO的橋接工作。

接下來，考慮要怎樣「模擬」出一套字元輸入輸出的環境，首先來看看資料結構：

1
2
3
4

data MockIOData = MockIOData {
  moInput :: [Char],
  moOutput :: [Char]
}

MockIOData是模擬程式運行時IO的資料結構。我假設所有輸入資料都在程式運行前準備好了，放在moInput中。而moOutput在程式運行開始時是空的，準備要將東西放進去。

資料結構定義好了，接下來該將MockIO橋接到CharIO：

1
2
3
4
5
6
7
8
9
10
11
12

type MockIO = State MockIOData

instance CharIO MockIO where
  getCh = do
    d <- get
    case d of
      MockIOData (i:is) o -> do
        put $ MockIOData is o
        return $ Just i
      MockIOData [] _ ->
        return Nothing
  putCh c = modify $ \s -> s{moOutput = moOutput s ++ [c]}

首先，CharIO必需要是Monad，於是我就借用了標準庫中的State Monad。putCh時就簡單的將字元接在moOutput尾端。getCh時檢查有input queue中還有沒有值，有值就回傳Just c，沒值就回傳Nothing。

HBF.VM模組

終於輪到Monad變形金鋼….ㄜ….是Monad Transformer出場了。基本上Brainfuck Interpreter的架構跟上一版差不多，但為了橋接IO，我們必需使用StateT(State Monad Transformer)。

基本的資料結構：

1
2
3
4
5
6
7

data VMData = VMData {
  vmMem :: TapeList Word8,
  vmCode :: TapeList Char,
  isRunning :: Bool
} deriving(Show)

type VMState = StateT VMData

注意VMState的型別：他是一個以VMData為狀態型別的State Monad Transformer。這樣說可能會很混亂，請聽我慢慢解釋……讓我們從一個函數型別開始看吧：

1

fwdCode, backCode :: CharIO m => VMState m ()

fwdCode及backCode的用途是將指令碼前進或後退一格。先讓我們回憶一下，在上一個沒有用Monad Transformer的例子中，這些函式的形別大概是這樣的：

1

fwdCode, backCode :: State VMData ()

fwdCode是一個Monadic value，在狀態轉移時會回傳empty tuple ()。

1

fwdCode, backCode :: CharIO m => VMState m ()

VMState m ()其實就是StateT VMData m ()…. 讓我們拆解這個型別的意義：fwdCode是一個monadic value，表示了一個VMData的狀態轉移 (將指令碼向前移動)，並且會回傳一個型別 m ()的資料 (這句話不精確，但請容我先這麼敘述) ，其中m會是CharIO的instace。 (更，講完我頭都昏了)

不涉及IO操作的function，大概只要單純將State VMData換成StateT VMData m就好了，沒啥特別的。讓我們看看涉及IO操作的function：

1
2
3
4
5
6

outputCh = getMem >>= lift . putCh . word8ToChar
inputCh = do
  d <- lift getCh
  case d of
    Just c -> setMem $ charToWord8 c
    Nothing -> terminate

雖然code有點亂，先注意lift這個指令就好。在outputCh中，putCh的型別原本是CharIO m => Char -> m ()，透過lift函式，我們要把它提升到CharIO m => StateT VMData m () 這個型別。

如果以上的東西看不懂也沒關係，雖然過程複雜，結果確是簡單漂亮的。HBF.VM只對外匯出兩個極為簡單的函式，讓我們來看看：

1
2
3
4

runBF :: CharIO m => String -> m ()
runBF code =
  let vmData = newVMData code
  in do runStateT runVM vmData >> return ()

runBF函式吃進一個字串，內容為Brainfuck code，回傳一個 (CharIO m) => m () 別被嚇到，這個型別一點都不複雜了

*HBF.VM> :t runBF "+++++++++++++++++++++++++++++++++.........."
runBF "+++++++++++++++++++++++++++++++++.........." :: (CharIO m) => m ()
*HBF.VM> runBF "+++++++++++++++++++++++++++++++++.........."
!!!!!!!!!!

為什麼(CharIO m) => m () 可以直接執行呢？因為IO其實是CharIO的Instance，而在ghci環境中下的指令是會被視為在IO Monad中被evaluate的。

或許這樣會更清楚：

*HBF.VM> let r = runBF "+++++++++++++++++++++++++++++++++.........." :: IO ()
*HBF.VM> :t r
r :: IO () -- 是的，r就是我們熟悉的IO ()神奇指令
*HBF.VM> r
!!!!!!!!!!*

那另外一個指令呢？

1
2
3

runMockBF :: String -> String -> String
runMockBF code input =
  runMockIO input (runBF code)

runMockIO 的第二個參數型別為MockIO ()，所以runBF code的型別也會被deduction到MockIO ()。我們終於達成我們另一個目標：使用pure function來執行brainfuck interpreter，而且pure function的性質還是從compiler層次可證明的。

HBF.Test.xxx

我選用HUnit做單元測試 (我的case沒啥QuickCheck的用武之地)，試了一下，總覺得沒有python or ruby的測試工具好用 (而且差了一大截)，這就不提了。

這裡就看runBFMock這個BF interpreter pure function和unittest的表演啦。我們可以模擬BF VM的輸入輸出，運行程式，再以pure function的性質保證其沒有side effect，不管運行幾次都會是對的。 (不過這樣有意義嗎? XD)

尾聲：我沒有要傳教

研究這個單純是好玩，我沒有要喊啥Haskell Rocks, Monad Rules之類的話 XD

寫haskell好累，可能是因為我是新手的關係？腦力激蕩還滿有趣的，把Monad了解到一個程度也是非常高興的一件事，看著型別轉來轉去變成pure function也很賞心悅目。Haskell我大概還是會抽空繼續研究，可是現在要我拿這個語言當practical的主力還太困難了，同樣的時間我大概可以用Python, Ruby, C, C++, JavaScript各Implement一遍還有剩吧….XD

先寫到這邊，對於Haskell的讚美及抱怨就等以後有空再寫吧….

以上有問題歡迎指教

斷斷續續的看Haskell也有一段時間了，也拿它來寫過一些解數學題的小程式，但是關於Type System, Monad之類的東西一直沒有靜下心來好好研究。直到最近開始看Real World Haskell這本書，才對於Monad有了一些基本的領悟。不過沒動手寫過，總會覺得不是真正的了解這些東西。於是我就想要寫一個小小的application。

和之前一樣，選了Brainfuck Interpreter這個題目開刀。這也是我第一次寫Haskell application，coding手法上還很生疏。以下的例子分成三個版本。第一個版本是簡單的實作，第二個版本加入了State Monad。第三個版本是最完整的實作，加入了Monad Transformer, Unit Test並切分模組。

編程環境：GHC 6.10.3

首先，我試著完全不使用Monad，實作了第一個版本的Brainfuck Interpreter (實作一源碼)。先來看看資料結構：

1
2
3
4
5
6
7
8
9
10
11

data BFData = BFData {
  curr :: Word8,
  left :: [Word8],
  right :: [Word8]
} deriving(Show)

data BFState = BFState {
  codeLeft :: [Char],
  codeRight :: [Char],
  bfData :: BFData
} deriving(Show)

BFData表示Brainfuck運行時的Memory，Word8是Haskell中的8-bit unsigned integer。Brainfuck在運行時，記憶體像是被單一指標指著的陣列，我使用兩個list及一個數值表示這樣的資料結構：curr表示目前的值，right表示指標位置右側的值，left表示指標位置左側的值。當指標向右移動的時候，將curr的值塞到left的前端，將right的head塞到curr中。眼尖的人或可發現：left中的值排放順序是相反的。這樣可以在常數時間內做完指標移動的動作。

BFState為整個Brainfuck interpreter的狀態。codeLeft和codeRight使用了和data相似的資料表示方式：未執行及已執行的code。BFState裡也包括了BFData的資料結構。

再來是函數的定義，版本一中盡量都是以pure function去操作資料。我們先略去函式的定義，觀察一些函式的型別：

1
2
3
4
5

fwd :: BFData -> BFData -- 資料指標前進
back :: BFData -> BFData -- 資料指標後退
modifyValue :: Word8 -> BFData -> BFData -- 修改資料指標
output :: BFData -> Char -- 讀取資料指標
blockBack :: BFState -> BFState -- 遇到右括號 (branch on nonZero) 時回退

可以發現，底層大部份的操作都寫成pure function。將一個資料轉為令一個資料，no side-effect, no implicit state。

在這個版本中我刻意的不做兩件事：不使用Monad記住狀態，不使用function呼叫的轉移來表示程式進行的狀態轉移(Erlang idiom)。寫一寫我才理解到為什麼Monad是重要的。Haskell是一個Single-assignment，大部份變數immutable的語言 (如同Erlang) 。在這樣的語言中，要修改一個複雜的狀態常常是很麻煩的，會出現x’ = f(x); x” = g(x’); x”’ = h(x”)之類的敘述。另外就是錯誤狀態的傳遞 (ex. Maybe Monad)。這些東西通常使用Imperative Language更容易描述。

Update: 這段話我寫的不夠好。剛剛回去看Josh Ko部落格，他做了更精確的解釋。引述一下他的說法：

把全部的 states 都寫出來，就不會為了顧及 implicit states 而在推理轉換時絆手絆腳； 但當 state 規模變大時，處理起來就不那麼順手了，此時 imperative programs 的專門語法反而比較方便。

在下一個例子我們可以看到如何使用State Monad來打造Imperative的環境，但再更高階的地方仍保有Pure functional的性質。

接下來，我實作了第二個版本，這個版本使用了State Monad (實作二源碼) 。

節錄一部份的Code來討論好了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

data BFState = BFState {
    dataLeft :: [Word8],
    dataRight :: [Word8],
    codeLeft :: [Char],
    codeRight :: [Char],
    bfOutput :: [Char]
    }

fwdCode, backCode :: State BFState ()
fwdCode =  modify $ \s@(BFState{codeLeft=ls, codeRight=r:rs}) -> s{codeLeft=r:ls, codeRight=rs}
backCode = modify $ \s@(BFState{codeLeft=l:ls, codeRight=rs}) -> s{codeLeft=ls, codeRight=l:rs}

fwdData, backData :: State BFState ()
fwdData =  modify $ \s@(BFState{dataLeft=ls, dataRight=r:rs}) -> s{dataLeft=r:ls, dataRight=rs}
backData = modify $ \s@(BFState{dataLeft=l:ls, dataRight=rs}) -> s{dataLeft=ls, dataRight=l:rs}

runBF :: State BFState ()
runBF = do
  r <- running
  if not r then return () else do
    stepBF
    runBF

stepBF :: State BFState ()
stepBF = do
  c <- currCode
  d <- getData
  fwdCode
  case c of
    '+' -> incData
    '-' -> decData
    '>' -> fwdData
    '<' -> backData
    _ -> return ()

我先簡化了一下資料結構，將code及data都放在BFState的資料結構中。為了實作方便，這個版本不吃standard input，而把output丟到一個字串當中(bfOutput)。這個偷吃步可以完全隔離IO，並簡單地直接使用State Monad。

再來，觀查fwdCode, backCode, fwdData, backData四個函式，其型別都是State BFState ()。State其實是Control.Monad.State提供的Type Constructor。State s a即是一個內部狀態為s，回傳值為a的State Monad。這些東西我就不細述了，有興趣的話請去參考文件吧。

stepBF函式負責將直譯器推進一個指令。看看這一段源碼：

1
2
3

c <- currCode
d <- getData
fwdCode

是不是回到了我們熟悉的Imperative programming的寫法？fwdCode看似造成了side effect (雖然這個side effect是被封裝在monad內的) 。

進ghci觀查一下型别，我們可以發現一下有趣的事。

*Main> :t bfOutput . snd . execBF
bfOutput . snd . execBF :: [Char] -> [Char]

我們可以將這些函式串起來，將State Monad的型別消掉，得到一個顯然的pure function：給定一個brainfuck code的字串，得到一個輸出的字串。而Pure function對測試顯然是有利的，我們可以保證每次的運行結果都一樣，不會受外在環境影響。

這個版本的缺點是：沒有辦法綁定標準IO。如果可能，我們會希望BFState的狀態機與輸入輸出可以解除耦合，透過形別系統可以同時綁定在標準IO/模擬的IO上。BFState綁定在標準IO時當然是Impure的：程式運行會受外部輸入影響。當透過模擬的IO時，我們可以將整個BFState的運行化為Pure Function。下個範例會顯示如何做到這一點。

(註：前兩個版本的Brainfuck interpreter algorithm其實是錯的：左括號當值為零的時候忘了向右branch，只是跑hello, world的例子剛好會對，我也懶得修了。另外輸入的指令其實沒有實作)

接下來應該要講正題了，第三個範例：

• Haskell Brainfuck Interpreter
• Monad Transformer：以Control.Monad.State.StateT為例
• 使用StateT切割IO，同時以IO及pure function形式執行brainfuck interpreter
• 在Unit Test中以pure function運行brainfuck interpreter

不過進入正題前就打了一堆字，拖稿等下集吧 (不知道什麼時候有空寫 XD)。

先放source code：有稍微切一下module，應該沒有前兩個範例那麼亂 source code available at Github

這篇的東西我沒有很確定是對的，筆記一下，有錯請指正喔。

• 在一台Linux主機上執行Apache伺服器
• 主機上有兩個使用者：a及b
• 使用Apache VirtualHost將a.gaaga.com導向/home/a/www，將b.gaaga.com導向/home/b/www

• chmod 777 -R www (超危險暴力法，強力不推薦使用)
• chgrp -R www-data www; chmod -R g+a www
• etc….
  

apache2-mpm-itk (just mpm-itk for short) is an MPM (Multi-Processing Module) for the Apache web server. mpm-itk allows you to run each of your vhost under a separate uid and gid — in short, the scripts and configuration files for one vhost no longer have to be readable for all the other vhosts.