睡不著爬起來寫blog,明天要早起的說 Orz
git是一套目前非常流行的分散式版本控制系統
相信很多人和我一樣,熟析git後就不會想用svn或cvs來管理源碼
我最近碰到這樣的問題:
專案主要使用svn做版本控制,但是我個人想用git管理
大家第一個想到的應該是git-svn
但git-svn對於svn external的支援並不完善
然而我目前的專案大量的使用了svn:external
src/
src/A => external to another project
src/B => external to another project
src/C => external to another project
更糟的是,因為專案開發時間的因素
A,B,C專案與主專案是共同開發的
有的時候我必需修改external library的API,並commit回去
有時其他人修改了external library,主專案必需跟著修改
(I know it doesn't sound good, but it's real world problem...)
我試過不管是單純的使用git-svn,或者借助一些shell script
都無法順利的處理這個工作流程
直到今天我想到一個實在是很瞎的方法:
mkdir gitrepo
cd gitrepo
git init
svn checkout svn://my-svn-repo-addr svnrepo
echo .svn > .gitignore
git add .
git commit
git chekcout -b svn-tracker
白話解釋一下:
在gitrepo/ 開一個git repository
在gitrepo/svnrepo 開一個svn repository
把.svn ignore掉 =.=
做一個名為svn-tracker的branch
這個看來愚蠢的方法 (對我目前的環境) 出手意料的好用
在改code時我都切換到其他branch (並且忘了svn的存在)
做任何svn操作時,我先切回svn-tracker branch
要做svn update的話就是
svn update
git add .
git commit -a
要commit自己的東西回svn mainstream就是
git merge work-branch
svn add *
svn commit
當然這些事可以寫shell script來完成
目前最大的缺點大概是沒法將git branch對應到svn branch (很麻煩)
不過還好我沒有很在乎....反正mainstream svn上沒有人在用branch & tag 功能,大家都只改trunk
這樣做還得到了意外的好處:
當要回退到舊版本時,如果沒有特別指定external的revision
就算update trunk to older revision,external還是會是最新版的
這樣會造成舊trunk + 新external,版本不相容的問題 (如果external行為或API有變)
上面的流程,每跑一次svn update
就等於把當時的情況做一次snapshot存進git
之後也就可以正確地回退版本....
我的網誌已搬家至blog.miaout17.net,本網誌將不再更新
2009年8月21日 星期五
2009年7月28日 星期二
2009年7月26日 星期日
Murmuring....
又開始覺得blogger貼code有點麻煩了,有點想轉回自架的wordpress
用內建的Editor縮排常會跑掉,對python和haskell這種indention關鍵的語言是很嚴重的
貼gist還OK,可是有時候三四行的東西還要貼gist去做syntax highlight很麻煩。
另外覺得最近github好慢,在一篇文章裡放好幾個embed gist,載入時會一直卡在gist那邊
考慮一下要不要搬回自架的wordpress
用內建的Editor縮排常會跑掉,對python和haskell這種indention關鍵的語言是很嚴重的
貼gist還OK,可是有時候三四行的東西還要貼gist去做syntax highlight很麻煩。
另外覺得最近github好慢,在一篇文章裡放好幾個embed gist,載入時會一直卡在gist那邊
考慮一下要不要搬回自架的wordpress
2009年7月25日 星期六
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下觀察一下:
putStr是一個函數,給予String後就會吐出一個IO ()型別的資料。let a = putStr "Hello",這個Monadic value不是什麼可怕的指令,既不會動也不會咬人,更不會主動地破壞美好的函數世界。一直到a這個值被evaluate,才會真正地與外在世界互動。
那為什麼要說Monadic value通常記載了狀態的改變呢?讓我們從State Monad開始討論吧。ghc標準庫中Control.Monad.State.State的定義為
s為該State Monad記住的狀態型別,a為附帶的回傳值之型別。我們可以看到,一個State Monadic value中只有一種資料:給定一個狀態,得到一個新的狀態,並且回傳一個附帶的值。Monadic value本身描述了「狀態如何轉移」。
讓我舉個實例:
這個例子簡單地使用Int做為狀態,並且定義了一些狀態的轉移。inc為將原本的整數加一,twice為將原本的整數乘以二。calculate則是狀態轉移的合併:乘以二,加一,再乘以二。
模組化
這個沒啥好講的,就把重複利用的資料結構汎化而已。完全透過吃TapeList吐TapeList的pure function來操作。
HBF.CharIO模組
這個模組很簡單,但卻是重頭戲。Brainfuck需要兩種IO指令:一次輸入一個字元、一次輸出一個字元。在Haskell我們會盡量希望pure (functional) code和impure code分離。理論上Brainfuck的確需要輸入輸出,但我卻希望能將VM與標準IO解耦,讓後端的VM code同時可以達到兩種效果:
首先,這個class是Monad的subclass。putCh為輸出字元的動作,是不會失敗的。但getCh的動作可能會因無法讀取而失敗(原因後述),因此我們將其形別定為m (Maybe Char)。
接下來,我們將標準IO橋接至CharIO。方法很簡單,將IO變成CharIO的Instance即可:
putCh直接接到putChar,非常簡單明瞭。另外,在標準輸入中我們不考慮讀取失敗的情況,所以就直接c $lt;- getChar再return $ Just c。這樣就完成了CharIO及標準IO的橋接工作。
接下來,考慮要怎樣「模擬」出一套字元輸入輸出的環境,首先來看看資料結構:
MockIOData是模擬程式運行時IO的資料結構。我假設所有輸入資料都在程式運行前準備好了,放在moInput中。而moOutput在程式運行開始時是空的,準備要將東西放進去。
資料結構定義好了,接下來該將MockIO橋接到CharIO:
首先,CharIO必需要是Monad,於是我就借用了標準庫中的State Monad。putCh時就簡單的將字元接在moOutput尾端。getCh時檢查有input queue中還有沒有值,有值就回傳Just c,沒值就回傳Nothing。
HBF.VM模組
終於輪到Monad變形金鋼....ㄜ....是Monad Transformer出場了。基本上Brainfuck Interpreter的架構跟上一版差不多,但為了橋接IO,我們必需使用StateT(State Monad Transformer)。
基本的資料結構:
注意VMState的型別:他是一個以VMData為狀態型別的State Monad Transformer。這樣說可能會很混亂,請聽我慢慢解釋......讓我們從一個函數型別開始看吧:
fwdCode及backCode的用途是將指令碼前進或後退一格。先讓我們回憶一下,在上一個沒有用Monad Transformer的例子中,這些函式的形別大概是這樣的:
fwdCode是一個Monadic value,在狀態轉移時會回傳empty tuple ()。
VMState m ()其實就是StateT VMData m ()....
讓我們拆解這個型別的意義:fwdCode是一個monadic value,表示了一個VMData的狀態轉移 (將指令碼向前移動),並且會回傳一個型別 m ()的資料 (這句話不精確,但請容我先這麼敘述) ,其中m會是CharIO的instace。 (更,講完我頭都昏了)
不涉及IO操作的function,大概只要單純將State VMData換成StateT VMData m就好了,沒啥特別的。讓我們看看涉及IO操作的function:
雖然code有點亂,先注意lift這個指令就好。在outputCh中,putCh的型別原本是CharIO m => Char -> m (),透過lift函式,我們要把它提升到CharIO m => StateT VMData m () 這個型別。
如果以上的東西看不懂也沒關係,雖然過程複雜,結果確是簡單漂亮的。HBF.VM只對外匯出兩個極為簡單的函式,讓我們來看看:
runBF函式吃進一個字串,內容為Brainfuck code,回傳一個 (CharIO m) => m ()
別被嚇到,這個型別一點都不複雜了
為什麼(CharIO m) => m () 可以直接執行呢?因為IO其實是CharIO的Instance,而在ghci環境中下的指令是會被視為在IO Monad中被evaluate的。
或許這樣會更清楚:
那另外一個指令呢?
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的讚美及抱怨就等以後有空再寫吧....
以上有問題歡迎指教
我看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本身描述了「狀態如何轉移」。
讓我舉個實例:
這個例子簡單地使用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
模組化
- HBF.TapeList : 如同上一篇文章所述,我們在記憶code及memory時都需要一個類似磁帶的結構。TapeList將這個結構及其運算抽象化。
- HBF.CharIO : Brainfuck只需要用到兩種IO:字元輸入及字元輸出。CharIO定義了一個class將這件事抽象化,以方便Brainfuck Interpreter橋接到IO及pure function。
- HBF.VM : Brainfuck Virtual Machine (事實上只是Interpreter核心而已,我沒有做複雜的事)。
- HBF.Test.xxx : 單元測試。
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同時可以達到兩種效果:
- 正常地使用標準IO運行
- 化為pure function,給定輸入及要運行的BF程式,得到輸出字串,類似這樣的效果:
run :: String -> String -> String
run code input = xxx output
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即可:
instance CharIO IO where
getCh = do
c <- getChar
return $ Just c
putCh = putCharputCh直接接到putChar,非常簡單明瞭。另外,在標準輸入中我們不考慮讀取失敗的情況,所以就直接c $lt;- getChar再return $ Just c。這樣就完成了CharIO及標準IO的橋接工作。
接下來,考慮要怎樣「模擬」出一套字元輸入輸出的環境,首先來看看資料結構:
data MockIOData = MockIOData {
moInput :: [Char],
moOutput :: [Char]
}MockIOData是模擬程式運行時IO的資料結構。我假設所有輸入資料都在程式運行前準備好了,放在moInput中。而moOutput在程式運行開始時是空的,準備要將東西放進去。
資料結構定義好了,接下來該將MockIO橋接到CharIO:
首先,CharIO必需要是Monad,於是我就借用了標準庫中的State Monad。putCh時就簡單的將字元接在moOutput尾端。getCh時檢查有input queue中還有沒有值,有值就回傳Just c,沒值就回傳Nothing。
HBF.VM模組
終於輪到Monad變形金鋼....ㄜ....是Monad Transformer出場了。基本上Brainfuck Interpreter的架構跟上一版差不多,但為了橋接IO,我們必需使用StateT(State Monad Transformer)。
基本的資料結構:
data VMData = VMData {
vmMem :: TapeList Word8,
vmCode :: TapeList Char,
isRunning :: Bool
} deriving(Show)
type VMState = StateT VMData
注意VMState的型別:他是一個以VMData為狀態型別的State Monad Transformer。這樣說可能會很混亂,請聽我慢慢解釋......讓我們從一個函數型別開始看吧:
fwdCode, backCode :: CharIO m => VMState m ()fwdCode及backCode的用途是將指令碼前進或後退一格。先讓我們回憶一下,在上一個沒有用Monad Transformer的例子中,這些函式的形別大概是這樣的:
fwdCode, backCode :: State VMData ()fwdCode是一個Monadic value,在狀態轉移時會回傳empty tuple ()。
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:
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只對外匯出兩個極為簡單的函式,讓我們來看看:
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
!!!!!!!!!!*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的讚美及抱怨就等以後有空再寫吧....
以上有問題歡迎指教
2009年7月23日 星期四
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 (實作一源碼)。先來看看資料結構:
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去操作資料。我們先略去函式的定義,觀察一些函式的型別
可以發現,底層大部份的操作都寫成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來討論好了:
我先簡化了一下資料結構,將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函式負責將直譯器推進一個指令。看看
是不是回到了我們熟悉的Imperative programming的寫法?fwdCode看似造成了side effect (雖然這個side effect是被封裝在monad內的) 。
進ghci觀查一下型别,我們可以發現一下有趣的事。
我們可以將這些函式串起來,將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的例子剛好會對,我也懶得修了。另外輸入的指令其實沒有實作)
接下來應該要講正題了,第三個範例:
先放source code:有稍微切一下module,應該沒有前兩個範例那麼亂
source code available at Github
和之前一樣,選了Brainfuck Interpreter這個題目開刀。這也是我第一次寫Haskell application,coding手法上還很生疏。以下的例子分成三個版本。第一個版本是簡單的實作,第二個版本加入了State Monad。第三個版本是最完整的實作,加入了Monad Transformer, Unit Test並切分模組。
編程環境:GHC 6.10.3
首先,我試著完全不使用Monad,實作了第一個版本的Brainfuck Interpreter (實作一源碼)。先來看看資料結構:
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去操作資料。我們先略去函式的定義,觀察一些函式的型別
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來討論好了:
我先簡化了一下資料結構,將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函式負責將直譯器推進一個指令。看看
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
先放source code:有稍微切一下module,應該沒有前兩個範例那麼亂
source code available at Github
2009年6月20日 星期六
Apache下以不同uid及pid執行不同VirtualHost
這篇的東西我沒有很確定是對的,筆記一下,有錯請指正喔。
考慮以下情境:
網路上可以找到一些解法:
這個問題我google了一下,有點抓不到正確得關鍵字,於是直接上irc freenode#TOSSUG發問,感謝snowian pct的回答,最後找到了這個東西:
(找方法找了很久,找到後花三分鐘就搞定了)
另外,看到2007年的mailing list上的問題:會跟mod_python相衝。不知道這個問題解決了沒,我可能會在上面跑Django
考慮以下情境:
- 在一台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....
這個問題我google了一下,有點抓不到正確得關鍵字,於是直接上irc freenode#TOSSUG發問,感謝snowian pct的回答,最後找到了這個東西:
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.在debian下的設置很簡單:
# apt-get install libapache2-mpm-itk
# vi /etc/apache2/sites-available/a-site
加上
AssignUserID a a (分別是userid, groupid)
即可(找方法找了很久,找到後花三分鐘就搞定了)
另外,看到2007年的mailing list上的問題:會跟mod_python相衝。不知道這個問題解決了沒,我可能會在上面跑Django
2009年5月30日 星期六
在Linux/Mac作業系統上運行Blogtrans
這篇文章說明如何在其他作業系統上運行Blogtrans。
目前Blogtrans只固定製作Windows版的執行檔。在其他平台上運行Blogtrans可能麻煩一些,以下也假設讀者對於這些作業系統的操作有一定的認知。
筆者無法允諾有空一一回復相關問題。筆者並非微軟教徒,但考慮Windows使用人數眾多,Blogtrans在Windows上應該算是經過相當的測試。如果使用上還是有問題,借個有灌Windows的電腦來用似乎是最穩定的選擇。
如果有人要幫忙做Linux和Mac的Build我也是很樂意啦....
環境設定
目前Blogtrans只相依於兩個東西:
(舊版本曾經用過gdata,現在的Blogger Atom XML是硬寫出來的)
以ubuntu (debain) 為例:
sudo apt-get install python
sudo apt-get install python-wxaddons
我手邊沒有Mac (之前有Mac桌機但賣掉了) , 不過Mac印像中也是內建Python2.5,應該灌個wxPython-unicode就OK吧......
執行Blogtrans
然後去Github的Blogtrans頁面抓取程式源始碼,目前穩定的程式碼都放在master branch。如果會使用git的話可以用git抓,否則直接抓tarball下來解壓縮也可以。
之後進到shell,切換到blogtrans目錄,執行python blogtrans.py即可。
在Ubuntu上運行Blogtrans的截圖:

目前Blogtrans只固定製作Windows版的執行檔。在其他平台上運行Blogtrans可能麻煩一些,以下也假設讀者對於這些作業系統的操作有一定的認知。
筆者無法允諾有空一一回復相關問題。筆者並非微軟教徒,但考慮Windows使用人數眾多,Blogtrans在Windows上應該算是經過相當的測試。如果使用上還是有問題,借個有灌Windows的電腦來用似乎是最穩定的選擇。
如果有人要幫忙做Linux和Mac的Build我也是很樂意啦....
環境設定
目前Blogtrans只相依於兩個東西:
(舊版本曾經用過gdata,現在的Blogger Atom XML是硬寫出來的)
以ubuntu (debain) 為例:
sudo apt-get install python
sudo apt-get install python-wxaddons
我手邊沒有Mac (之前有Mac桌機但賣掉了) , 不過Mac印像中也是內建Python2.5,應該灌個wxPython-unicode就OK吧......
執行Blogtrans
然後去Github的Blogtrans頁面抓取程式源始碼,目前穩定的程式碼都放在master branch。如果會使用git的話可以用git抓,否則直接抓tarball下來解壓縮也可以。
之後進到shell,切換到blogtrans目錄,執行python blogtrans.py即可。
在Ubuntu上運行Blogtrans的截圖:
2009年5月22日 星期五
Blogtrans 更新 090522
今天赫然發現一件事,在上次的更新中我以為已經修正無名文章日期的問題了。結果發現修改的程式忘記commit,上次壓出來的版本日期還是有問題的。所以今天又壓了一個版本,只更新了無名日期這件事。
離無名關閉備份只剩四天。
有需要者請至Sourceforge抓取最新版本。
離無名關閉備份只剩四天。
有需要者請至Sourceforge抓取最新版本。
2009年5月11日 星期一
Blogtrans雜記
先聲明,筆者跟無名沒啥深仇大恨,也不在Web界工作。更不是其他BSP的打手,我與任何BSP沒有利益關係。
Blogtrans專案的起源是幫朋友(終於變成女友XD)搬Blog寫的一個console小程式,後來閒暇時補上UI放出來給想搬家的人使用。這也是我剛第一個嘗試用Python寫的中小型應用程式 (所以程式架構很亂,有人要trace的話別笑我 Orz)。
維護這隻程式算是吃力不討好的工作。無名的規格問題層出不窮:在XML檔案後面添加HTML碼的做法是一大經典,而且這是推出備份服務的後來才加上去的,我懷疑這是刻意讓企圖讀取無名備份檔的程式無法運作。另外在XML檔中可以出現不合法的XML字元,還有現在的備份檔不完全問題。 (Well, 我必需承認無名匯出檔根本是封閉格式,或許該慶幸他沒有用亂七八糟的binary format再加個密?) 另外也有些MT匯出檔的格式不依標準 。最麻煩的是上傳到Blogger,我花了許多時間在測試上傳Blogger備份檔上。
話說回來,無名從以前到現在的做法著實另人惱火,我相當不相信「關閉備份是為了專注在其他更好的服務」。
筆者在思考是不是該在無名關畢備份服務後,再寫另一個轉出無名的功能。要達到私密文章備份,這次可能就要靠HTTP認證,再從前台或後台撈HTML出來了。跟之前的作法比,可能這樣的做法更為麻煩。只要站方稍稍變動規格,撈文章的parser就可能失效。
我另一方面也希望國內其他BSP可以繼續做到這樣的功能 (撇開轉出Blogger部份不提的話,pixnet一直提供了比Blogtrans更穩定的轉出無名功能)。畢竟跟商業(又有幾位程設能力超強大神在)的BSP比,筆者一人利用空閒時間的力量是相當有限的。
Blogtrans專案的起源是幫朋友(終於變成女友XD)搬Blog寫的一個console小程式,後來閒暇時補上UI放出來給想搬家的人使用。這也是我剛第一個嘗試用Python寫的中小型應用程式 (所以程式架構很亂,有人要trace的話別笑我 Orz)。
維護這隻程式算是吃力不討好的工作。無名的規格問題層出不窮:在XML檔案後面添加HTML碼的做法是一大經典,而且這是推出備份服務的後來才加上去的,我懷疑這是刻意讓企圖讀取無名備份檔的程式無法運作。另外在XML檔中可以出現不合法的XML字元,還有現在的備份檔不完全問題。 (Well, 我必需承認無名匯出檔根本是封閉格式,或許該慶幸他沒有用亂七八糟的binary format再加個密?) 另外也有些MT匯出檔的格式不依標準 。最麻煩的是上傳到Blogger,我花了許多時間在測試上傳Blogger備份檔上。
話說回來,無名從以前到現在的做法著實另人惱火,我相當不相信「關閉備份是為了專注在其他更好的服務」。
筆者在思考是不是該在無名關畢備份服務後,再寫另一個轉出無名的功能。要達到私密文章備份,這次可能就要靠HTTP認證,再從前台或後台撈HTML出來了。跟之前的作法比,可能這樣的做法更為麻煩。只要站方稍稍變動規格,撈文章的parser就可能失效。
我另一方面也希望國內其他BSP可以繼續做到這樣的功能 (撇開轉出Blogger部份不提的話,pixnet一直提供了比Blogtrans更穩定的轉出無名功能)。畢竟跟商業(又有幾位程設能力超強大神在)的BSP比,筆者一人利用空閒時間的力量是相當有限的。
2009年5月10日 星期日
無名小站備份檔問題
按,我家樓下常有外國人在開轟趴,半夜一點多大聲說話,吵到我關著窗子都聽的到。剛快睡著結果被吵起來寫blog,考慮下次再被吵要不要去暱名檢舉了....
言歸正傳,昨天收到一位網友來信,說Blogtrans無法匯入他的備份檔。他的網誌有九百多篇文章,但是從無名試著匯出好幾次備份檔,使用Blogtrans匯入時都不成功。使用Notepad++打開他的備份檔,檢視檔案尾端,大鳥眉頭一皺,發現案情並不單純 (對不起我老梗了):

因為沒有取得轉錄同意,雖然原文是公開的,應該在合理引用的範圍,我還是把文字消音了。
注意紅框的地方,一個E9的特殊字元中斷了備份檔。我試著手動修復備份檔,發現無名只匯出了七百多篇文章,留言全都不見了。
假設不是該網友在下載的過程中遇到特殊問題,那就是無名的備份功能真的有Bug,導致匯出時闕漏了文章和留言。
該位網友去信無名,客服的回應為
或許無名是對的:關閉服務是因為他們沒有能力維護。
你還放心住在無名嗎?

(對不起我又老梗了)
言歸正傳,昨天收到一位網友來信,說Blogtrans無法匯入他的備份檔。他的網誌有九百多篇文章,但是從無名試著匯出好幾次備份檔,使用Blogtrans匯入時都不成功。使用Notepad++打開他的備份檔,檢視檔案尾端,大鳥眉頭一皺,發現案情並不單純 (對不起我老梗了):
因為沒有取得轉錄同意,雖然原文是公開的,應該在合理引用的範圍,我還是把文字消音了。
注意紅框的地方,一個E9的特殊字元中斷了備份檔。我試著手動修復備份檔,發現無名只匯出了七百多篇文章,留言全都不見了。
假設不是該網友在下載的過程中遇到特殊問題,那就是無名的備份功能真的有Bug,導致匯出時闕漏了文章和留言。
該位網友去信無名,客服的回應為
會幫他調整Blog,請他清除網路暫存檔試試看(顯然沒用?)
或許無名是對的:關閉服務是因為他們沒有能力維護。
你還放心住在無名嗎?

(對不起我又老梗了)
2009年5月3日 星期日
Blogtrans版本更新:090503
遵守之前的承諾,在這個週末放出Blogtrans更新。這次的更新主要是針對這些問題:
- 匯入無名小站時,文章時間是最後修改時間,而非發佈時間
已修正 - 無名小站無法匯入的一些問題
主要問題是當文章中有不合法的XML字元時,無名仍會將這些字元匯出到XML檔中。
已解決 - 簡體中文電腦無法使用Blogtrans的問題
- 原本程式中有些地方很蠢的將字串先以CP950轉成Unicode,在簡體中文電腦就會產生錯誤,我全部改成Unicode了。
- 看到MT檔中,日期欄位是「DATE: 07/11/2004 07:39:17 下午」,出現中文字當然與MT規格不符,暴力的replace /上午/AM/ /下午/PM/
已解決 - 匯出至Blogger留言會不見的問題
這個問題我懷疑是Blogger自己的問題,之前匯出留言到Blogger是沒有問題的。我做了這樣的實驗:從Blogger官方匯出有留言的文章,再匯入回去,留言竟然也有機率會不見。
暫時提供一個比較暴力的解決方法:將所有留言合併到文章內文之中。
選擇這個選項之後,所有留言會被合併到文章之中,當作文章的一部份處理。這樣做的壞處是留言會被視為文章的一部份,而無法在側邊欄中顯示。
這個問題若是持續存在,我會在有空時做詳細的測試再回報給Blogger。
目前無法完全解決,提供克難的替代方案。
090504更新:感謝Asher網友,將留言選項調成「任何人都可以留言」似乎就沒問題了。我還沒時間做詳細的測試,暫時先告知使用者有這個方法可以嘗試。
目前最新版的是Build-090503,一樣請至sourceforge下載。有問題請回報,祝大家成功逃離丁丁星球。
2009年4月30日 星期四
Blogtrans已知問題
似乎因為無名又做了微妙的決定,最近想要搬Blog的人又變多了,我收到不少Blogtrans有關的Bug。
Blogtrans現在有一些已知的問題:
(背景音樂:不用麻煩了,不用麻煩了,阿宅很忙的),應該會趁這周末的時間(5/1~5/3)修正這些問題。如果E-mail給我沒有回音,可以下周一後再過來看看有沒有更新。
Blogtrans現在有一些已知的問題:
- 匯入無名備份檔時可能會卡住 (應該是無名匯出格式不知道偷偷做了什麼變動)
- 匯出至Blogger時留言會不見 (這個以前可以的,應該是Blogger改了讀備份檔的機制)
- 無法正常處理簡體中文
2009年4月26日 星期日
Ruby V.S. Python: Operator +=
剛剛在Godfat的Blog看到這篇文章,比較了Ruby和Python在對於list進行+=運算子操作的差異:
這個結果同樣的出乎我的意料之外,所以花了些時間研究一下。以下分別討論a=b=[]; a+=[1]在Ruby和Python的運作狀況。
先看看a=b=[]。毫無疑問,不管在Ruby或Python,這個敘述都是「造一個空list,並讓a和b指向同一個list」。如果你被上面的例子迷惑了,試試:
再來,先討論Python
Python的a+=[1]等價於a.__iadd__([1])
對呼叫a+=[1]的block,變數a所綁定的物件不會改變
既然a和b所綁定的物件相同,那a和b的內容理所當然也會一樣
再來看看Ruby的a+=[1]
雖然Ruby可以覆載運算子,但+=運算子是不能被覆載的
簡單的試試
Ruby的method可以名為+,可以以=結尾,就是不能名為+=。同理,-=, *=, /=, &&=, ||=之類的也不行。參考Programming Ruby
差異就在這邊,對呼叫a+=[1]的block來說,a+[1]造出了一個新物件,再綁定到變數a上,所以a和b指向不一樣的東西。
這裡或許值得注意的是,要是Ruby中+=是一個member method,那a+=[1]就很難不影響到b。因為對呼叫a+=[1]的block來說,他只是去呼叫a的一個member method。完成之後a與b還是指向同一個object。像a<<b就是這樣的例子。
另外,這些敘述應該是等價的:
我個人是Python和Ruby都有在用,在這個小地方上我比較喜歡Python的作法:將+=視為member function,operator的left operand所綁定的目標不會改變。知道這點的話,Python應該是易了解又有一致性。
[~/test]# irb
irb(main):001:0> a = b = []
=> []
irb(main):002:0> a += [1]
=> [1]
irb(main):003:0> a
=> [1]
irb(main):004:0> b
=> []
irb(main):005:0>
Python 2.5.1
>>> a = b = []
>>> a += [1]
>>> a
[1]
>>> b
[1]
這個結果同樣的出乎我的意料之外,所以花了些時間研究一下。以下分別討論a=b=[]; a+=[1]在Ruby和Python的運作狀況。
先看看a=b=[]。毫無疑問,不管在Ruby或Python,這個敘述都是「造一個空list,並讓a和b指向同一個list」。如果你被上面的例子迷惑了,試試:
irb(main):001:0> a = b = []
=> []
irb(main):002:0> a << 1
==> [1]
irb(main):003:0> a
=> [1]
irb(main):004:0> b
=> [1]
irb(main):005:0>
再來,先討論Python
Python的a+=[1]等價於a.__iadd__([1])
對呼叫a+=[1]的block,變數a所綁定的物件不會改變
既然a和b所綁定的物件相同,那a和b的內容理所當然也會一樣
再來看看Ruby的a+=[1]
雖然Ruby可以覆載運算子,但+=運算子是不能被覆載的
簡單的試試
Ruby的method可以名為+,可以以=結尾,就是不能名為+=。同理,-=, *=, /=, &&=, ||=之類的也不行。參考Programming Ruby
In common with many other languages, Ruby has a syntactic shortcut: a=a+2 may be written as a+=2.可以得到結論:a+=[1]只是一個Syntax sugar,可以想像他parse時就變成了a=a+[1],而不是由a去invoke一個名為+=的member function。
差異就在這邊,對呼叫a+=[1]的block來說,a+[1]造出了一個新物件,再綁定到變數a上,所以a和b指向不一樣的東西。
這裡或許值得注意的是,要是Ruby中+=是一個member method,那a+=[1]就很難不影響到b。因為對呼叫a+=[1]的block來說,他只是去呼叫a的一個member method。完成之後a與b還是指向同一個object。像a<<b就是這樣的例子。
另外,這些敘述應該是等價的:
- Python的a+=[b]
- Python的a.append(b)
- Ruby的a<<b
- Ruby的a.push b
我個人是Python和Ruby都有在用,在這個小地方上我比較喜歡Python的作法:將+=視為member function,operator的left operand所綁定的目標不會改變。知道這點的話,Python應該是易了解又有一致性。
2009年4月8日 星期三
JustFuck, A x86 Just-In-Time Compiler for Brainfuck
前陣子看到Jserv介紹asmjit的文章,一直想找機會試試看。另外,最近ptt的programming版上的一個thread出現了很多esoteric programming language,讓我想到可以試試寫個Brainfuck JIT Compiler。於是,這個專案就誕生了?
JustFuck, A x86 Just-In-Time Compiler for Brainfuck
我不是故意罵髒話的啊....他的縮寫很自然就這樣啊....(大誤)
一位不知名的鳥類程式設計師評論道:「真是太神奇了,我從未見過腦幹語言運行的如此飛快,嘎嘎。」
因為最近開始學git,所以放github上:Project page。
Source code只有一個檔案,三百行。學習Brainfuck, asmjit, git的實驗品,大概懶得再重構更新了。
JustFuck, A x86 Just-In-Time Compiler for Brainfuck
我不是故意罵髒話的啊....他的縮寫很自然就這樣啊....(大誤)
一位不知名的鳥類程式設計師評論道:「真是太神奇了,我從未見過腦幹語言運行的如此飛快,嘎嘎。」
因為最近開始學git,所以放github上:Project page。
Source code只有一個檔案,三百行。學習Brainfuck, asmjit, git的實驗品,大概懶得再重構更新了。
訂閱:
文章 (Atom)