Haskell: ミニコンパイラの解体

前のエントリで、Haskellで実装したミニコンパイラを紹介しました。今回はこのミニコンパイラの字句解析のパーツだけを取り出して動かしてみます。必要最小限なコードを切り出して動作させてみたかったので、今回対応する計算式は「自然数の足し算」のみです。ミニコンパイラから、そのような興味のあるコードだけを抜き出してみると、以下のようになりました。

% vim calc.hs
import Char

data Token
    = NUM Int | PLUS

instance Show Token where
    showsPrec p (NUM num) = showString "NUM " . shows num
    showsPrec p (PLUS)    = showString "PLUS"

tokenise :: [Char] -> [Token] 
tokenise [] = [] 
tokenise ('+':rest) = PLUS : (tokenise rest)
tokenise (ch:rest)
    | isDigit ch = let (n, rest2) = convert(ch:rest)
                   in      
                        (NUM n):(tokenise rest2)

convert :: [Char] -> (Int, [Char]) 
convert str
    = let   
        conv' [] n = (n, []) 
        conv' (ch : str) n
            | isDigit ch = conv' str ((n*10) + digitToInt ch)
            | otherwise  = (n, ch : str)
    in 
        conv' str 0

main :: IO ()
main = do
    expr <- getLine 
    putStrLn(show(tokenise expr))

ghcでコンパイルして実行すると、以下のようになります。期待通りに字句解析できていますね。

% ghc -o calc calc.hs
% ./calc
1+2+3
[NUM 1,PLUS,NUM 2,PLUS,NUM 3]

Haskellの理解度はまだまだ低いですが、解体作業をしていて、以下がポイントだと思いました。

• import Char: isDigit関数とdigitToInt関数を利用するために必要
• data Token ... : トークンを表現するためにTokenというデータ構造を定義
• instance Show Token ... : Token型を文字列に変換できるように(JavaのtoString()的な考え方)
• tokenise関数
  • 文字列の先頭1文字と残りに分解して処理する考え方 (例: tokenise ('+':rest) ...)
  • 入力文字列を完全に消費するまで再帰的にtokenise関数を適用
  • 関数の引数のパターンマッチングと再帰を利用することで、手続き型言語の「変数(状態)」という考え方が不要に

また、今回解体作業をしていて、動作保証されたお手本のコードから興味のあるコードを取り出して、それを動作するまで試行錯誤するというアプローチは、とても勉強になると思いました。Haskellを使いこなせるようになるまでの道のりは険しいと思いますが、少しずつ頑張ればなんとかなるような気がします。