大貓共和國

Meow

Haskell Monad : 以Brainfuck Interpreter為例 (上)

斷斷續續的看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

Comments