大貓共和國

Meow

Haskell Monad : 以Brainfuck Interpreter為例 (下)

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

我看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的讚美及抱怨就等以後有空再寫吧….

以上有問題歡迎指教

Comments