tnomuraのブログ

Text.Parsec.Prim: 継続渡し

ParsecT モナドのフィールドに収められている無名関数は次のような形をしている。

\s cok cerr eok eerr -> some function

この関数のうち s は State 型のパーサ状態 parser state だが、あとの４つは関数を受け取る。つまり、高階関数だ。

また、s 以外の４つの関数は、関数の戻り値を計算する関数だ。この無名関数から値が戻されるとき、データが cok cerr eok eerr のどれかの関数に渡されて最終的な戻り値に変換される。この様な高階関数の使い方を、継続渡しスタイルと言うらしい。継続とはその後の処理を受け持つ関数のことだ。もとの関数の最終的な処理を継続（関数）にまかせてしまうやり方だ。

例えば、階乗の計算のプログラムは次のようになるが、

Prelude> {fact 0 = 1; fact n = n * fact (n-1)}
Prelude> fact 5
120

これを継続渡しスタイルで書くと次のようになる。

Prelude> {fact 0 cont = cont 1; fact n cont = fact (n-1) (\x -> cont (n * x))}
Prelude> fact 5 id
120

cont という余計な引数が増えているが、この引数には fact n の戻り値を処理する関数が渡される。上の例では cont = id なので単純な階乗の計算になったが、cont = (*2) とすると、階乗の値が２倍になる。

Prelude> fact 5 (*2)
240

わざと計算をややこしくしているようだが、通常の再帰的定義ではできない動作を継続を利用して実現できる。例えば、fact n cont の計算を6 以上の数については中止して 0 にしたいとする。このような場合には次のようにプログラムすると良い。

Prelude> {fact 0 cont = cont 1; fact 6 cont = 0; fact n cont = fact (n-1) (\x -> cont (n * x))}
Prelude> fact 5 id
120
Prelude> fact 6 id
0
Prelude> fact 7 id
0

継続のような抽象的なプログラム技術はなかなか理解できないが、継続でないと実現できない制御構造があるとなると、避けては通れない。

これらの例では、継続として受け取る関数は一つだけだったが、次のように複数とることもできる。

Prelude> foo n cont1 cont2 = if n == 0 then cont1 1 else cont2 n
Prelude> foo 0 (\_ -> "zero") (\_ -> "non-zero")
"zero"
Prelude> foo 1 (\_ -> "zero") (\_ -> "non-zero")
"non-zero"

この foo を使って階乗の計算をすると次のようになる。

Prelude> fact_cps n = foo n (\_ -> 1) (\x -> x * fact_cps (x-1))
Prelude> fact_cps 5
120

ただし、これは厳密な意味での継続渡しスタイルではないのかもしれない。継続についてはいろいろな説明を読んだが、まだ消化できていないような気がする。しかし、再帰的定義のように制御構造の一つだと考えると、継続渡しスタイルの制御構造を多数書いているうちに自由に使えるようになるのだろう。再帰的定義のやり方も最初は意味不明だったが、最近は空気を呼吸するように楽に書けるようになった。継続渡しスタイルも使う回数が増えればそういう風になるかもしれない。

継続渡しスタイルの関数は、関数の戻り値を外部からコントロールできるので、抽象的な値を返すジェネリックプログラミングであるとも言えるかもしれない。ジェネリックプログラミングの解説を読むと sum [a] のような多形性の関数のことを言うようなのでこれも意味が違うかもしれないが... 。

ソースプログラムを読むためには、プログラミング技術にまで必要な予備知識が広がるので、読みこなすのが難しいのだろう。

参考サイト

お気楽 Haskell プログミング入門

C++ジェネリックプログラミング入門

Text.Parsec.Prim: parserBind その２

parserBind は ParsecT モナドの >>= 演算子の定義だ。parserBind m k は、m >>= k と同じ意味で、ParsecT モナド m :: ParsecT s u m a と モナド関数 k :: a -> ParsecT s u m b から、これらを合成した新しいモナド ParsecT s u m b を作り出す。ソースコードは次のようになる。

parserBind :: ParsecT s u m a -> (a -> ParsecT s u m b) -> ParsecT s u m b

{-# INLINE parserBind #-}
parserBind m k
..= ParsecT $ \s cok cerr eok eerr ->
....let
........-- consumed-okay case for m
........mcok x s err =
............let
................ -- if (k x) consumes, those go straigt up
................ pcok = cok
................ pcerr = cerr

................ -- if (k x) doesn't consume input, but is okay,
................ -- we still return in the consumed continuation
................ peok x s err' = cok x s (mergeError err err')

................ -- if (k x) doesn't consume input, but errors,
................ -- we return the error in the 'consumed-error'
................ -- continuation
................ peerr err' = cerr (mergeError err err')
............in..unParser (k x) s pcok pcerr peok peerr

........-- empty-ok case for m
........meok x s err =
............let
................-- in these cases, (k x) can return as empty
................pcok = cok
................peok x s err' = eok x s (mergeError err err')
................pcerr = cerr
................peerr err' = eerr (mergeError err err')
............in..unParser (k x) s pcok pcerr peok peerr
........-- consumed-error case for m
........mcerr = cerr

........-- empty-error case for m
........meerr = eerr

....in unParser m s mcok mcerr meok meerr

知りたいのは、このコードでどうして m >>= k という新しい ParsecT が作れるかだ。これは m によるマッチが成功してモナド値 ParsecT _ _ _ a が戻ってきたときそれをどうやって a -> ParsecT _ _ _ b に渡すことができるかを知れば理解できる。そこで、n = m >>= k でできるパーサは何かを考えてみた。それは、次のようになる。

n = ParsecT {unParser = \s cok cerr eok eerr -> unParser m s mcox merr meok meerr}

このパーサの状態 s についてのマッチングを計算するには、アクセサ unParser を使って n のフィールドのデータの無名関数を取り出し、それに実引数 s cok* cerr* eok* eerr* を与えればいい。

unParser n s cok* cerr* eok* eerr*

これは結局のところ、

unParser m s mcok merr meok meerr

を計算することになる。ParsecT モナド m の状態 s についてのパターンマッチが成功した場合、マッチした文字（列）x 、新しい状態 s' 、エラーメッセージ err が mcok に渡され次の関数が実行される。

mcok x s' err

ところが、

mcok x s' err = unParser (k x) s' pcok pcerr peok peerr

だから、m を s に適用したときの戻り値 x が k に渡され ParsecT モナド (k x) の フィールドの関数 unParser (k x) に対し実引数 s' pcok pcerr peok peerr が渡される。このことは m と s のマッチングで計算された文字 x と状態 s' が無事に k に渡されていることを示している。このことは計算の順序が次のように行われることを示している。

パーサ m と状態 s のマッチング => x, s', err が計算され => mcox に渡される => unParser (k x) s' pcok pcerr peok peerr が計算される。

ポイントは mcok という関数のなかに (k x) s' ... というもう一つのパーサの計算が仕込まれているところだ。cok に渡す関数にはこのように別のパーサへのデータの受け渡しもコーディングすることができるのだ。関数型の引数の恐るべき能力だ。

Text.Parsec.Prim: 関数型引数を使う理由

Parsec のパーサ ParsecT s u m a の実態は、唯一のフィールド unParser の中の無名関数だ。

ParsecT {unParser = \s cok cerr eok eerr -> some_funciton}

言い換えると、実態は関数なのにモナドとして取り扱うために代数的データ型 ParsecT に閉じ込めてあると考えてもいいだろう。

ところで、ParsecT のパーサ p のフィールド内の関数を利用したいときは、unParser アクセサで取り出してこれに実引数を渡すことになる。

unParser p s cok cerr eok eerr

このとき、引数 cok cerr eok eerr に渡される関数の型は ParsecT の newtype 宣言の時に定義されている。

newtype ParsecT s u m a
....= ParsecT {unParser :: forall b .
................ State s u
..............-> (a -> State s u -> ParseError -> m b) -- consumed ok
..............-> (ParseError -> m b).................. -- consumed err
..............-> (a -> State s u -> ParseError -> m b) -- empty ok
..............-> (ParseError -> m b).................. -- empty err
..............-> m b
............ }

これを見ると例えば cok に与える関数は、

cok a s err

となる。a の方は任意、s :: State s u、err :: ParseError である。cok はこれらの引数をとり、m b 型のモナド値を返す。逆に言えば、cok に外部から与えることのできる関数は、この型の関数しかない。それは a, s, err に割り当てる実引数の供給源が (unParser p) 関数の内部にあるからだ。

cok に与えられる引数は、a, s, err だが、ユーザは cok に適合する型の関数なら何でも割り当てることができる。つまり、(unParser p) 関数を呼んだとき cok の引数 a, s, err をユーザがコントロールすることはできないが、引数として与える cok 関数を変えることで結果的に (unParser p) 関数の振る舞いを変えることができる。関数型の引数はいわば抽象的な引数で、それに具体的な関数を割り当てることで (unParser p) 関数本体の動作をコントロールすることができるのだ。

こういう関数型の引数をもつ関数の定義は、次のような抽象的な定義になる。

Prelude> foo x test baseCase recursiveCase = if test x then baseCase x else recursiveCase x

この関数の引数に実際の関数を割り当てることによって、foo の内部に手を入れることなく様々な関数を定義することができる。

Prelude> oddEven x = foo x odd (*10) (^2)
Prelude> oddEven 3
30
Prelude> oddEven 4
16

Prelude> fact x = foo x (==0) (\_->1) (\s -> s * fact (s-1))
Prelude> fact 5
120

Prelude> summation x = foo x (==0) (\_->0) (\s -> s + summation (s-1))
Prelude> summation 10
55

このように関数を引数とする関数、すなわち、高階関数は関数の定義を変えずに引数の関数を変えることで変幻自在にユーザによって定義できるという特徴がある。

ParsecT パーサの正体は、高階関数だった。

Text.Parsec.Prim: many

many コンビネータは、パーサ p を引数にとり、p の０回以上の繰り返しにマッチするパーサを返す。

Prelude> :m Text.Parsec
Prelude Text.Parsec> parseTest (many letter) "foo123"
"foo"

また、skipMany コンビネータは、パーサ p を引数にとり、p の０回以上の繰り返しを読み飛ばす。

Prelude Text.Parsec> parseTest (skipMany letter *> getInput) "foo123"
"123"

この many と skipMany は 同じ manyAccum 関数を使って定義されている。

many :: ParsecT s u m a -> ParsecT s u m [a]
many p
..= do xs <- manyAccum (:) p
...... return (reverse xs)

-- | @skipMany p@ applies the parser @p@ /zero/ or more times, skipping
-- its result.
--
-- >..spaces..= skipMany space

skipMany :: ParsecT s u m a -> ParsecT s u m ()
skipMany p
..= do _ <- manyAccum (\_ _ -> []) p
...... return ()

manyAccum は第１引数に \x xs -> f x xs :: a -> [a] -> [a] 型の関数を、第２引数にパーサ p を取り、パーサ p のパターンマッチが成功する限り、その結果を \x xs -> f x xs で蓄積したデータを戻り値として返す。再帰的に定義されているので、戻り値はパターンマッチの順序とは逆になる。

Prelude Text.Parsec> parseTest (manyAccum (\x xs -> x:x:xs) letter) "abc123"
"ccbbaa"

manyAccum のソースは次のようになる。

manyAccum :: (a -> [a] -> [a])
..........-> ParsecT s u m a
..........-> ParsecT s u m [a]
manyAccum acc p =
....ParsecT $ \s cok cerr eok _eerr ->
....let walk xs x s' _err =
............unParser p s'
..............(seq xs $ walk $ acc x xs)..-- consumed-ok
..............cerr........................-- consumed-err
..............manyErr.................... -- empty-ok
..............(\e -> cok (acc x xs) s' e) -- empty-err
....in unParser p s (walk []) cerr manyErr (\e -> eok [] s e)

manyErr :: a
manyErr = error "Text.ParserCombinators.Parsec.Prim.many: combinator 'many' is applied to a parser that accepts an empty string."

複雑に見えるが、中心部分は、walk xs x s' という再帰的なパターンマッチを行う関数だ。

....let walk xs x s' _err =
............unParser p s'
..............(seq xs $ walk $ acc x xs)..-- consumed-ok
..............cerr........................-- consumed-err
..............manyErr.................... -- empty-ok
..............(\e -> cok (acc x xs) s' e) -- empty-err

このうち再帰的なパターンマッチを行う部分を抜き出してみると次のようになる。

walk xs x s' _err = unParser p s' (acc x xs) cerr manyErr (\e -> cok (acc x xs) s' e)

さらに、cerr, manyErr はエラー処理なので walk の動作の実質部分を担っている部分を抜き出すと次のようになる。

walk xs x s' = unParser p s' (acc x xs) (\e -> cok (acc x xs) s' e)

これは、つぎのような再帰関数と似た動作をする。

foo x test recusiveCase baseCase = if (test x) then (recusiveCase x) else (baseCase x)

Prelude Text.Parsec> fact x = foo x (>0) (\s -> s * fact (s-1)) (\_ -> 1)
Prelude Text.Parsec> fact 5
120

つまり walk xs 関数はパーサ p をパーサ状態 s にパターンマッチして成功したときにその戻り値を xs のリストに集積しパターンマッチが失敗した時点で集積したデータを返すという動作をする関数になっている。このことを踏まえると

....in unParser p s (walk []) cerr manyErr (\e -> eok [] s e)

の意味が分かる。最初の p s のパターンマッチが成功した時点で walk [] に結果が渡され、その後は walk [] xs x s' 関数がパターンマッチの繰り返しを実行して、その値を manyAccum の戻り値として返す。

実際のコードはもっと入り組んでいるので分かりづらいが、本質的には、上のような再帰関数を利用したコードだ。

unParser p s cok cerr eok eerr

という関数の使い方の解釈は、抽象性が高いのでかなり難しい。しかし、これも一つのプログラミングテクニックと考えると、複雑な動作のコードを劇的に短くしてくれる技術のように見える。再帰関数の定義も解釈しようとすると難しいが、簡単な再帰関数を作って動作を確認しているうちに再帰関数の発想が頭の中にできてくる。

このような抽象的なプログラムテクニックを習得するためには、簡単な例を作って体に馴染むまで実験する必要がある。

Text.Parsec.Prim: 関数のフィールドデータの扱い方

ParserT モナドの実体は、唯一のフィールドに無名関数を入れる代数的データ型だ。newtype 宣言で次のように定義されている。

newtype ParsecT s u m a
....= ParsecT {unParser :: forall b .
................ State s u
..............-> (a -> State s u -> ParseError -> m b) -- consumed ok
..............-> (ParseError -> m b).................. -- consumed err
..............-> (a -> State s u -> ParseError -> m b) -- empty ok
..............-> (ParseError -> m b).................. -- empty err
..............-> m b
............ }

このデータ構造には２つの特徴がある。一つはフィールドのデータが無名関数であることだが、もう一つは、引数の型が関数であるということだ。この意味がなかなか分かりづらかったので、同様のデータ型を作ってどういう動作をするのか試してみた。

まず、フィールドのデータが無名関数で、その引数が関数型であるような代数的データ型 Foo a を作ってみた。Foo はフィールド名 unpack のフィールドに無名関数を収める。無名関数の引数は第１引数が数値で第２引数と第３引数が関数だ。戻り値は数値になる。

Prelude> data Foo a = Foo {unpack :: a -> (a -> a) -> (a -> a) -> a}

そこで次のような Foo 型のデータ foo を作った。foo の unpack フィールドには \x f g -> if odd x then f x else g x という無名関数を入れた。この関数は x が odd なら f x を戻り値として返し、そうでない場合は g x を戻り値として返す。

Prelude> foo = Foo $ \x f g -> if odd x then f x else g x

これに実引数を渡して動作を確認した。

Prelude> unpack foo 3 (*10) (^2)
30
Prelude> unpack foo 4 (*10) (^2)
16

これを見ると Foo の unpack フィールドの関数が x の値で戻り値を切り替えるという抽象的な動作をする関数であることが分かる。この x の値次第で戻り値を切り替えるという性質を利用すると再帰関数も定義できる。これを検証するために、x の値が 0 のときと、それ以外の場合に振り分ける Foo 型のデータ baz を定義する。

Prelude> baz = Foo $ \x f g -> if x == 0 then f x else g x

この baz が x が 0 のときは f x を実行し、それ以外のときは g x を実行するという抽象的な性質に注目すると、次のように再帰関数も記述することができる。

Prelude> fact x = unpack baz x (\_ -> 1) (\s -> s * fact (s-1))
Prelude> fact 5
120

Foo のフィールドの関数は通常の関数だったが、モナド値を返すモナド関数にすることができる。そこで、Foo 型に似ているが Maybe a 型を返す関数を収めるデータ型 Bar を定義してみた。

Prelude> data Bar a = Bar {unpack :: a -> (a -> Maybe a) -> (a -> Maybe a) -> Maybe a}

foo と同じような Bar 型のデータ bar を次のように定義する。無名関数の本体のコードは foo の場合と全く同じだがこれは関数の抽象的な性質を考えると驚くべきことではない。

Prelude> bar = Bar $ \x f g -> if odd x then f x else g x

bar に実引数を与えた結果を次に示すが、関数の引数の部分のプログラムをモナドで記述することができる。

Prelude> unpack bar 3 (return) (\_ -> Nothing)
Just 3
Prelude> unpack bar 4 (return) (\_ -> Nothing)
Nothing

無名関数をフィールドデータとするデータ型や、引数が関数型の関数を自前で作って動作させてみたら、この形式のデータの扱いが少し分かってきた。Text.Parsec.Prim のパーサのプログラムの意味もなんとなく掴めた気がする。

Text.Parsec.Prim: State 型のデータを操作するパーサ

ParsecT s u m a 型のパーサはただ一つの unParser フィールドに無名関数を収めた次のような形をしている。

ParsecT { unParser = \s cok cerr eok eerr -> ... }

このうち、cok cerr eok eerr などの引数の実引数はいずれもデータをモナドにラッピングする関数で Parsec のシステムで与えられる。s はユーザが与えた入力文字列、処理対象の位置情報、ユーザ状態の３つをフィールドに持つ代数的データ型 State s u 型である。したがって、Parsec のパターンマッチは State s u 型に対して行われる。したがって、State s u 型のデータの動きを理解すれば、Parsec 内部で何が行われているかが理解できる。State s u 型は次のようになっている。

data State s u = State {stateInput :: s, statePos :: !SourcePos, stateUser :: !u}

Text.Parsec.Prim モジュールにはこの State s u 型のデータを操作する関数が多数定義されている。

getPosition :: Monad m => ParsecT s u m SourcePos
getInput :: Monad m => ParsecT s u m s
setPosition :: Monad m => SourcePos -> ParsecT s u m ()
setInput :: Monad m => s -> ParsecT s u m ()
getParserState :: Monad m => ParsecT s u m (State s u)
setParserState :: Monad m => State s u -> ParsecT s u m (State s u)
updateParserState :: (State s u -> State s u) -> ParsecT s u m (State s u)
getState :: Monad m => ParsecT s u m u
putState :: Monad m => u -> ParsecT s u m ()
modifyState :: Monad m => (u -> u) -> ParsecT s u m ()
setState :: Monad m => u -> ParsecT s u m () .... 互換性のため。 putState と同じ。
updateState :: Monad m => (u -> u) -> ParsecT s u m () ..... 互換性のため。modifyState と同じ。

これらを実験してみるが、まず、以前の記事にも使った parsec.ghci 設定ファイルで GHCi の設定をする。

Prelude> :script parsec.ghci

次に、State s u 型は Show クラスのインスタンスではないので、文字列に変換する showState 関数を定義する。

Parsec> showState x = show (stateInput x) ++ show (statePos x) ++ show (stateUser x)

ついでに、State s u 型を Show クラスのインスタンスにして、show = showState で show 関数を定義する。

Parsec> :t showState
showState :: (Show s, Show a) => State s a -> [Char]
Parsec> instance (Show s, Show a) => Show (State s a) where show = showState

こうすると、GHCi のコマンドラインで State s u 型のデータが表示できるようになる。

Parsec> st
"input stream""SourceName" (line 1, column 1)"user state"

これで準備ができたので、上述の関数を試してみることにする。

パーサのState 型データ parser state のフィールドのデータを処理する。

Parsec> runParser (getPosition) () "SourceName" "hello"
Right "SourceName" (line 1, column 1)
Parsec> runParser (getInput) () "SourceName" "hello"
Right "hello"

Parsec> runParser (setPosition (newPos "foo" 1 5)) () "SourceName" "hello"
Right ()
Parsec> runParser (setPosition (newPos "foo" 1 5) *> getPosition) () "SourceName" "hello"
Right "foo" (line 1, column 5)
Parsec> runParser (setInput "world") () "SourceName" "hello"
Right ()
Parsec> runParser (setInput "world" *> getInput) () "SourceName" "hello"
Right "world"

パーサの State 型データ parser state をまるごと操作する。

Parsec> runParser (getParserState) () "SourceName" "hello"
Right "hello""SourceName" (line 1, column 1)()

Parsec> runParser (setParserState (State "world" (newPos "bar" 1 1) ())) () "SourceName" "hello"
Right "world""bar" (line 1, column 1)()
Parsec> runParser (updateParserState (\s -> s {stateInput = "world"})) () "SourceName" "hello"
Right "world""SourceName" (line 1, column 1)()

ユーザ状態 user state を操作する。

Parsec> runParser (getState) 0 "SourceName" "hello"
Right 0

Parsec> runParser (putState 5) 0 "SourceName" "hello"
Right ()
Parsec> runParser (putState 5 *> getState) 0 "SourceName" "hello"
Right 5
Parsec> runParser (modifyState (*2)) 3 "SourceName" "hello"
Right ()
Parsec> runParser (modifyState (*2) *> getState) 3 "SourceName" "hello"
Right 6

Parsec のソースを読むのは大変だったが、自分が何を操作しているのかが分かるようになったのが利点だ。

Text.Parsec.Pos: updatePosChar, updatePosString

Parsec パーサのマッチングでマッチが成功し入力文字列の消費が起きたときは、SourcePos データの更新が必要だ。１文字消費されたときは列番号 sourceColune が１つ増加し、消費された文字列が '/n' のときは行番号 sourceLine が一つ増加する。また、消費された文字列が '\t' のときは列番号が 8 の倍数に揃えて増加する。これを行うのが updatePosChar 関数だ。

Parsec> pos
"SourceName" (line 1, column 1)
Parsec> updatePosChar pos 'a'
"SourceName" (line 1, column 2)
Parsec> updatePosChar pos '\n'
"SourceName" (line 2, column 1)
Parsec> updatePosChar pos '\t'
"SourceName" (line 1, column 9)

文字列が消費されるときは、上の動作をそれぞれの文字列に対して行う。こうすれば、文字列の中に '\n' や '\t' が含まれていても対応できる。これを行うのが updatePosString 関数だ。

Parsec> updatePosString pos "foo"
"SourceName" (line 1, column 4)
Parsec> updatePosString pos "foo\nbar"
"SourceName" (line 2, column 4)

この２つの関数があれば、文字列の消費のあらゆる場合に対応できる。

updatePosChar 関数は、Text.Parsec.Pos モジュールに定義されている。

updatePosString :: SourcePos -> String -> SourcePos
updatePosString pos string
....= foldl updatePosChar pos string

-- | Update a source position given a character. If the character is a
-- newline (\'\\n\') or carriage return (\'\\r\') the line number is
-- incremented by 1. If the character is a tab (\'\t\') the column
-- number is incremented to the nearest 8'th column, ie. @column + 8 -
-- ((column-1) \`mod\` 8)@. In all other cases, the column is
-- incremented by 1.

updatePosChar.. :: SourcePos -> Char -> SourcePos
updatePosChar (SourcePos name line column) c
....= case c of
........'\n' -> SourcePos name (line+1) 1
........'\t' -> SourcePos name line (column + 8 - ((column-1) `mod` 8))
........_....-> SourcePos name line (column + 1)

上に述べたアルゴリズムがそのまま記述されているだけだ。Haskell の魅力の一つは if ~ then ~ else ~ 文に邪魔されずに、アルゴリズムをそのまま記述できることが多いことだ。

Text.Parsec: State 型の扱い方

parsec.ghci スクリプト

前回、Parsec の色々なデータ型を調べたが、今回からはそれらを操作する関数を利用して実際にどのようにそれらのデータ型が使われているかを実験していく。たくさんのコンストラクタや関数があるので、複数回の記事になると思う。これらのサブモジュールの関数は Text.Parsec ではインポートされないものも多いので、次のようなスクリプト parsec.ghci で予め必要なモジュールをインポートしたり、サンプルのデータを作ったりしてから実験を始める。

{- ghci configulation for Text.Parsec -}

import Control.Monad.Identity
import Text.Parsec.Pos
import Text.Parsec.Error
import Text.Parsec.Prim
import Text.Parsec.Char
import Text.Parsec.Combinator

:set prompt "Parsec> "
:set prompt2 "Parsec| "

s = "input stream"
u = "user state"
pos = newPos "SourceName" 1 1
st = State s pos u
msg = "hello, parsec"

設定スクリプトを ghci で利用するためには、次のように :script コマンドを使う。

Prelude> :script parsec.ghci
Parsec>

最初は Message 型だ。これはエラー情報を収める ParseError の構成要素の一つになる。Message 型はエラーの情報を与えるエラーメッセージの文字列を保持しているが、エラーの種類によって４つの種類がある。

エラーの種類によってデータ・コンストラクタが分けられているために、どのようなエラーメッセージを補足するかは (UnExpcted string) のようにパターンマッチで知ることができる。また、異なる種類のエラーメッセージを Message 型としてリストにすることもできる。リストの要素は同じ型でないといけないのでこのようにエラーメッセージを抽象的に扱えるのは重要だ。

代数的データ型の利点は、異なる種類のデータを抽象的なデータ型として一括して扱えるところだ。

Message 型のデータ宣言は次のようになる。

data Message = SysUnExpect !String -- @ library generated unexpect
............ | UnExpect....!String -- @ unexpected something
............ | Expect......!String -- @ expecting something
............ | Message.... !String -- @ raw message
....deriving ( Typeable )

このデータ型は、Typeable クラスのインスタンスである。Typeable クラスのインスタンスにしたデータ型は任意の型について実行時の情報を作れるということだが、よく意味がわからなかった。Message 型は Show クラスのインスタンスではないので、show 関数で文字列に変換できない。ghci のコマンドラインでも :t コマンドによる型表示しかできない。上の定義に分かるように、Message データ型を作るには、４種類のデータ・コンストラクタを使い分ける。

Parsec> :t SysUnExpect "foo"
SysUnExpect "foo" :: Message
Parsec> :t UnExpect "foo"
UnExpect "foo" :: Message
Parsec> :t Expect "foo"
Expect "foo" :: Message
Parsec> :t Message "foo"
Message "foo" :: Message

Message 型のフィールドから（どのタイプであっても）文字列を取り出す関数は messageString である。

Parsec> messageString (UnExpect "foo")
"foo"

SourcePos 型

SourcePos 型は、ソースの位置を表す抽象的データ型である。ソース名、行番号、列番号を保持している。SourcePos 型のデータ宣言は次のようになっている。

type SourceName = String
type Line...... = Int
type Column.... = Int

data SourcePos = SourcePos SourceName !Line !Column
....deriving ( Eq, Ord, Data, Typeable)

SourcePos 型は Eq, Ord, Data, Typeable クラスのインスタンスである。同等性や大小の比較ができる。data 宣言では drive サれていないが Show クラスのインスタンスのようで show 関数が使える。

Parsec> show pos
"\"SourceName\" (line 1, column 1)"
Parsec> pos
"SourceName" (line 1, column 1)

SourcePos のフィールドを操作する関数がいろいろと定義されている。
newPos :: SourceName -> Line -> Column -> SourcePos
initialPos :: SourceName -> SourcePos
sourceName :: SourcePos -> SourceName
sourceLine :: SourcePos -> Line
sourceColumn :: SourcePos -> Column
incSourceLine :: SourcePos -> Line -> SourcePos
incSourceColumn :: SourcePos -> Column -> SourcePos
setSourceName :: SourcePos -> SourceName -> SourcePos
setSourceLine :: SourcePos -> Line -> SourcePos
setSourceColumn :: SourcePos -> Column -> SourcePos

updatePosChar :: SourcePos -> Char -> SourcePos
updatePosString :: SourcePos -> String -> SourcePos

実験してみる。

Parsec> newPos "foo" 1 1
"foo" (line 1, column 1)
Parsec> initialPos "foo"
"foo" (line 1, column 1)
Parsec> sourceName pos
"SourceName"
Parsec> sourceLine pos
1
Parsec> sourceColumn pos
1
Parsec> incSourceLine pos 2
"SourceName" (line 3, column 1)
Parsec> incSourceColumn pos 5
"SourceName" (line 1, column 6)
Parsec> setSourceName pos "bar"
"bar" (line 1, column 1)
Parsec> setSourceLine pos 5
"SourceName" (line 5, column 1)
Parsec> setSourceColumn pos 5
"SourceName" (line 1, column 5)

Parsec> pos
"SourceName" (line 1, column 1)
Parsec> updatePosChar pos 'a'
"SourceName" (line 1, column 2)
Parsec> updatePosChar pos '\n'
"SourceName" (line 2, column 1)
Parsec> updatePosChar pos '\t'
"SourceName" (line 1, column 9)
Parsec> updatePosString pos "foo"
"SourceName" (line 1, column 4)

ParseError 型

ParseError 型はパースエラーを表す抽象的データ型。ソースのエラー位置 SourcePos型、エラーのメッセージ Message型 のリストを保持している。ParseError 型のデータ宣言は次のようになっている。

data ParseError = ParseError !SourcePos [Message]
....deriving ( Typeable )

ParseError データ・コンストラクタは Text.Parsec.Error サブモジュールからもエクスポートされていないので、直接作成することはできない。また Show クラスのインスタンスでもないので show 関数で文字列に変換することもできない。ParseError 型のフィールドを操作する関数には次のようなものがある。

errorPos :: ParseError -> SourcePos
errorMessages :: ParseError -> [Message]
errorIsUnknown :: ParseError -> Bool
newErrorMessage :: Message -> SourcePos -> ParseError
newErrorUnknown :: SourcePos -> ParseError
addErrorMessage :: Message -> ParseError -> ParseError
setErrorPos :: SourcePos -> ParseError -> ParseError
setErrorMessage :: Message -> ParseError -> ParseError
mergeError :: ParseError -> ParseError -> ParseError

上の関数をテストするためにパースエラー型のデータ pe を作ってみる。

Parsec> pe = newErrorMessage (Message "foo") pos
Parsec> :t pe
pe :: ParseError

pe を使って上記の関数の実験をしてみた。

Parsec> errorPos pe
"SourceName" (line 1, column 1)
Parsec> map messageString $ errorMessages pe
["foo"]
Parsec> errorIsUnknown pe
False
Parsec> pe2 = newErrorMessage (Message "bar") (setSourceColumn pos 5)
Parsec> errorPos pe2
"SourceName" (line 1, column 5)
Parsec> map messageString $ errorMessages $ addErrorMessage (UnExpect "baz") pe
["baz","foo"]
Parsec> map messageString $ errorMessages $ setErrorMessage (Message "bar") pe
["bar"]
Parsec> pe3 = mergeError pe pe2
Parsec> map messageString $ errorMessages pe3
["bar"]
Parsec> map messageString $ errorMessages pe
["foo"]
Parsec> map messageString $ errorMessages pe2
["bar"]

State 型

State 型は Parsec の処理の中心となるデータ型である。StateT s u m a 型のパーサモナドの実体は次のように唯一のフィールドである unParser フィールドに無名関数を収めた単純な代数的データ型である。

ParsecT { unParser = \s cok cerr eok eerr -> ... }

無名関数の引数のうち、ユーザが提供するものを収めているのが State 型のデータ s である。他の引数の実引数は Parsec のシステムが提供する。

State 型のフィールドには入力の文字列 (stateInput) s、入力の位置 (statePos) SourcePos、ユーザ状態 (stateUser) uｇが収められる。

data State s u = State {
......stateInput :: s,
......statePos.. :: !SourcePos,
......stateUser..:: !u
....}
....deriving ( Typeable )

State 型はデータ・コンストラクタ State で作ることができる。ただし、Show クラスのインスタンスではないので文字列に変換できない。

State
....stateInput :: s
....statePos :: !SourcePos
....stateUser :: !u

実験してみる。

Parsec> :t State "hello" pos ()
State "hello" pos () :: State [Char] ()

State 型のフィールドにはフィールド名でアクセスできる。parsec.ghci で予め定義した State 型のデータ st があるのでそれを使って実験してみる。

Parsec> stateInput st
"input stream"
Parsec> statePos st
"SourceName" (line 1, column 1)
Parsec> stateUser st
"user state"

ParsecT パーサで行われる様々なパターンマッチはこの State 型のデータに対して行われる。パーサの中には、この State 型のデータを操作するパーサが多数用意されている。Parsec のパターンマッチの動作を理解するために、State 型の知識は欠かせない。

また、ParseError 型のデータはパターンマッチが失敗したときの情報を持っている。

State 型と ParseError 型のデータの振る舞いをイメージできれば Parsec パーサの動作をほぼ理解できる。

Text.Parsec.Prim: 代数的データ型

Text.Parsec.Prim に現れる代数的データ型をソースの出現順に列挙してみた。他のモジュールに定義してあるものも含めてある。かなり大きな構成だが、一覧にすると構造が分かりやすい。しかし、簡単には習得できなさそう。

Message 型

抽象的なエラーメッセージを表わすデータ型。４種類の型からなっている。

data Message = SysUnExpect !String -- @ library generated unexpect
............ | UnExpect....!String -- @ unexpected something
............ | Expect......!String -- @ expecting something
............ | Message.... !String -- @ raw message
....deriving ( Typeable )

Message 型を操作するデータ・コンストラクタや関数には次のようなものがある。

SysUnExpect !String
UnExpect !String
Expect !String
Message !String
messageString :: Message -> String

SourcePos 型

ソースの位置を表す抽象的データ型。ソース名、行番号、列番号を保持している。

type SourceName = String
type Line...... = Int
type Column.... = Int

data SourcePos..= SourcePos SourceName !Line !Column
....deriving ( Eq, Ord, Data, Typeable)

SourcePos のフィールドを操作する関数がいろいろと定義されている。
newPos :: SourceName -> Line -> Column -> SourcePos
initialPos :: SourceName -> SourcePos
sourceName :: SourcePos -> SourceName
sourceLine :: SourcePos -> Line
sourceColumn :: SourcePos -> Column
incSourceLine :: SourcePos -> Line -> SourcePos
incSourceColumn :: SourcePos -> Column -> SourcePos
setSourceName :: SourcePos -> SourceName -> SourcePos
setSourceLine :: SourcePos -> Line -> SourcePos
setSourceColumn :: SourcePos -> Column -> SourcePos

ParseError 型

パースエラーを表す抽象的データ型。ソースのエラー位置 SourcePos型、エラーのメッセージ Message型 のリストを保持している・

data ParseError = ParseError !SourcePos [Message]
....deriving ( Typeable )

ParseError 型のデータを操作する関数には以下のようなものがある。

errorPos :: ParseError -> SourcePos
errorMessages :: ParseError -> [Message]
errorIsUnknown :: ParseError -> Bool
newErrorMessage :: Message -> SourcePos -> ParseError
newErrorUnknown :: SourcePos -> ParseError
addErrorMessage :: Message -> ParseError -> ParseError
setErrorPos :: SourcePos -> ParseError -> ParseError
setErrorMessage :: Message -> ParseError -> ParseError
mergeError :: ParseError -> ParseError -> ParseError

ParsecT 型

ParsecT モナドトランスフォーマ、パーサ型

newtype ParsecT s u m a
....= ParsecT {unParser :: forall b .
................ State s u
..............-> (a -> State s u -> ParseError -> m b) -- consumed ok
..............-> (ParseError -> m b).................. -- consumed err
..............-> (a -> State s u -> ParseError -> m b) -- empty ok
..............-> (ParseError -> m b).................. -- empty err
..............-> m b
............ }
.... deriving ( Typeable )

Parsec 型

モナド型のパーサ

type Parsec s u = ParsecT s u Identity

Consumed 型

パーサによるパターンマッチが入力の消費した場合に Consumed に、入力を消費しなかったときに Empty のフィールドに値を収める。

data Consumed a..= Consumed a
................ | Empty !a
....deriving ( Typeable )

Reply 型

パーサによるパターンマッチが成功したときに OK に、失敗したときに Error 型のフィールドに値を収める。

data Reply s u a = Ok a !(State s u) ParseError
................ | Error ParseError
....deriving ( Typeable )

State 型

State 型は入力の文字列 (stateInput) s、入力の位置 (statePos) SourcePos、ユーザ状態 (stateUser) u を保持する。

data State s u = State {
......stateInput :: s,
......statePos.. :: !SourcePos,
......stateUser..:: !u
....}
....deriving ( Typeable )

State 型を操作するコンストラクタ、関数は次のようなものがある。

Constructors
State

....stateInput :: s
....statePos :: !SourcePos
....stateUser :: !u

主に Functor クラス、Applicative クラス、Monad クラスなどの関数を定義するのに用いられる補助関数。
parsecMap :: (a -> b) -> ParsecT s u m a -> ParsecT s u m b
parserReturn :: a -> ParsecT s u m a
parserBind :: ParsecT s u m a -> (a -> ParsecT s u m b) -> ParsecT s u m b
mergeErrorReply :: ParseError -> Reply s u a -> Reply s u a
parserFail :: String -> ParsecT s u m a
parserZero :: ParsecT s u m a
parserPlus :: ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
(<?>) :: ParsecT s u m a -> String -> ParsecT s u m a infix 0
(<|>) :: ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a infixr 1
label :: ParsecT s u m a -> String -> ParsecT s u m a
labels :: ParsecT s u m a -> [String] -> ParsecT s u m a
lookAhead :: Stream s m t => ParsecT s u m a -> ParsecT s u m a

Stream クラス

Stream クラスのインスタンスは uncons メッドが使える。

class (Monad m) => Stream s m t | s -> t where
....uncons :: s -> m (Maybe (t,s))

PasecT s u m a モナドを操作する関数は次のようになる。

tokens :: (Stream s m t, Eq t) => ([t] -> String) -> (SourcePos -> [t] -> SourcePos) -> [t] -> ParsecT s u m [t]
try :: ParsecT s u m a -> ParsecT s u m a

token
:: Stream s Identity t
=> (t -> String).........Token pretty-printing function.
-> (t -> SourcePos)......Computes the position of a token.
-> (t -> Maybe a)........Matching function for the token to parse.
-> Parsec s u a

自前で ParsecT s u m a パーサを作るための関数。

tokenPrim

:: Stream s m t

=> (t -> String)........Token pretty-printing function.
-> (SourcePos -> t -> s -> SourcePos)......Next position calculating function.
-> (t -> Maybe a).......Matching function for the token to parse.
-> ParsecT s u m a

tokenPrimEx :: Stream s m t => (t -> String) -> (SourcePos -> t -> s -> SourcePos) -> Maybe (SourcePos -> t -> s -> u -> u) -> (t -> Maybe a) -> ParsecT s u m a

パーサコンビネータ
many :: ParsecT s u m a -> ParsecT s u m [a]
skipMany :: ParsecT s u m a -> ParsecT s u m ()
skipMany p applies the parser p zero or more times, skipping its result.
manyAccum :: (a -> [a] -> [a]) -> ParsecT s u m a -> ParsecT s u m [a]

モナドプログラムを引数にとり実行する関数群

runPT :: Stream s m t => ParsecT s u m a -> u -> SourceName -> s -> m (Either ParseError a)
runP :: Stream s Identity t => Parsec s u a -> u -> SourceName -> s -> Either ParseError a
runParserT :: Stream s m t => ParsecT s u m a -> u -> SourceName -> s -> m (Either ParseError a)
runParser :: Stream s Identity t => Parsec s u a -> u -> SourceName -> s -> Either ParseError a
parse :: Stream s Identity t => Parsec s () a -> SourceName -> s -> Either ParseError a
parseTest :: (Stream s Identity t, Show a) => Parsec s () a -> s -> IO ()

パーサコンビネータ群

getPosition :: Monad m => ParsecT s u m SourcePos
getInput :: Monad m => ParsecT s u m s
setPosition :: Monad m => SourcePos -> ParsecT s u m ()
setInput :: Monad m => s -> ParsecT s u m ()
getParserState :: Monad m => ParsecT s u m (State s u)
setParserState :: Monad m => State s u -> ParsecT s u m (State s u)
updateParserState :: (State s u -> State s u) -> ParsecT s u m (State s u)
getState :: Monad m => ParsecT s u m u
putState :: Monad m => u -> ParsecT s u m ()
modifyState :: Monad m => (u -> u) -> ParsecT s u m ()
setState :: Monad m => u -> ParsecT s u m ()
updateState :: Monad m => (u -> u) -> ParsecT s u m ()

Text.Parsec.Char に定義されたパーサ群

alphaNum
anyChar
char 'c'

crlf
digit
endOfLine
hexDigit
letter
lower
newline
noneOf
octDigit
oneOf
satisfy :: (Char -> Bool) -> ParsecT s u m Char
space
spaces
string "foo"
tab
upper

Text.Parsec.Combinator に定義されたパーサコンビネータ群

choice :: Stream s m t => [ParsecT s u m a] -> ParsecT s u m a
count :: Stream s m t => Int -> ParsecT s u m a -> ParsecT s u m [a]
between :: Stream s m t => ParsecT s u m open -> ParsecT s u m close -> ParsecT s u m a -> ParsecT s u m a
option :: Stream s m t => a -> ParsecT s u m a -> ParsecT s u m a
optionMaybe :: Stream s m t => ParsecT s u m a -> ParsecT s u m (Maybe a)
optional :: Stream s m t => ParsecT s u m a -> ParsecT s u m ()
skipMany1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m ()
many1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m [a]
sepBy :: Stream s m t => ParsecT s u m a -> ParsecT s u m sep -> ParsecT s u m [a]
sepBy1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m sep -> ParsecT s u m [a]
endBy :: Stream s m t => ParsecT s u m a -> ParsecT s u m sep -> ParsecT s u m [a]
endBy1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m sep -> ParsecT s u m [a]
sepEndBy :: Stream s m t => ParsecT s u m a -> ParsecT s u m sep -> ParsecT s u m [a]
sepEndBy1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m sep -> ParsecT s u m [a]
chainl :: Stream s m t => ParsecT s u m a -> ParsecT s u m (a -> a -> a) -> a -> ParsecT s u m a
chainl1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m (a -> a -> a) -> ParsecT s u m a
chainr :: Stream s m t => ParsecT s u m a -> ParsecT s u m (a -> a -> a) -> a -> ParsecT s u m a
chainr1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m (a -> a -> a) -> ParsecT s u m a
eof :: (Stream s m t, Show t) => ParsecT s u m ()
notFollowedBy :: (Stream s m t, Show a) => ParsecT s u m a -> ParsecT s u m ()
manyTill :: Stream s m t => ParsecT s u m a -> ParsecT s u m end -> ParsecT s u m [a]
lookAhead :: Stream s m t => ParsecT s u m a -> ParsecT s u m a
anyToken :: (Stream s m t, Show t) => ParsecT s u m t

Text.Parsec.Prim: tokenPrim

Text.Parsec.Prim モジュールで定義されている tokenPrim 関数は自前のパーサを作るための関数だ。tokenPrim 関数の型は次のようになっている。

tokenPrim
..:: Stream s m t
..=> (t -> String)........................Token pretty-printing function.
..-> (SourcePos -> t -> s -> SourcePos)...Next position calculating function.
..-> (t -> Maybe a).......................Matching function for the token to parse.
..-> ParsecT s u m a

第１引数は、トークンを文字列に変換する関数。第２引数は次のキャラクタポインタを計算する関数。第３引数は入力の先頭の文字がパーサのパターンにマッチするかどうかの関数だ。使い方は、次の実例を見れば分かる。

char c
.. = tokenPrim showChar nextPos testChar
.. where
.... showChar x........= "'" ++ x ++ "'"
.... testChar x........= if x == c then Just x else Nothing
.... nextPos pos x xs..= updatePosChar pos x

上のソースで updatePosChar という関数があるが、これは Text.Parsec.Pos で定義されている関数で、パーサが１文字消費したときに次のキャラクタポインタを返す関数だ。

Parsec> :t updatePosChar
updatePosChar :: SourcePos -> Char -> SourcePos
Parsec> pos
"SourceName" (line 1, column 1)
Parsec> updatePosChar pos 'a'
"SourceName" (line 1, column 2)

そこで、tokenPrim のソースを読んでみた。

tokenPrim showToken nextpos test = tokenPrimEx showToken nextpos Nothing test

tokenPrimEx showToken nextpos Nothing test
..= ParsecT $ \(State input pos user) cok _cerr _eok eerr -> do
......r <- uncons input
......case r of
........Nothing -> eerr $ unexpectError "" pos
........Just (c,cs)
........ -> case test c of
..............Just x -> let newpos = nextpos pos c cs
............................newstate = State cs newpos user
........................in seq newpos $ seq newstate $
.......................... cok x newstate (newErrorUnknown newpos)
..............Nothing -> eerr $ unexpectError (showToken c) pos

tokenPrim 関数は tokenPrimEx 関数の別名だ。引数が tokenPrimEx のほうが一つ多いが tokenPrim 関数では Nothing に束縛されている。

tokenPrim 関数は ParsecT s u m a モナドのフィールドに \s cok cerr eok eerr -> ... 型の無名関数を収める仕事をしている。\s eok _cerr _eok eerr の様に引数の cerr と eerr にアンダーバーがついているのは、プログラムの中でこれらの引数を使わないからだ。すなわち、tokenPrim で作成されるパーサはパターンがマッチしたときには文字の消費が起きるが、マッチしないときは消費が起きないことを示している。

さて、無名関数の本体の定義であるが、最初に do キーワードがあるのでこれは do 記法によるモナドのプログラムだ。何のモナドかというと m (Consumed (m (Reply s u a))) モナドを戻り値として返すプログラムだ。do 記法の最初の行の r <- uncons input だが、uncons は Text.Parsec.Prim に定義されている関数で、入力の先頭の文字と、その後の文字列のペアを m (Maybe (t, s)) にして返す。

Parsec> :t uncons
uncons :: Stream s m t => s -> m (Maybe (t, s))
Parsec> uncons "hello"
Just ('h',"ello")

次に case r of ... で、先頭の文字列の取得に失敗した場合 (r == Nothing) と、成功した場合 ( r == Jus (c, cs) ) の場合の条件分岐をおこなう。r == Nothing のときは、eerr 関数で unExpectedError "" pos で作られたメッセージを返す。

r == Just (c, cs) のときは、更に文字 c について case test c of ... でさらに条件分岐が行われる。test 関数はユーザがパターンとして与えた関数で test c が成立するときは Just x を返し、パターンマッチが失敗したら Nothing を返す。

パターンマッチが成功しなかったときを先にみると、eerr 関数で unExpectedError (showTok c) pos で作ったメッセージを返す。

c == Just x でパターンマッチが成功した場合、

seq newpos $ seq newstate $ cok x newstate (newErrorUnknown newpos)

なので newpos と newstate を正格評価した cok x newstate (newErrorUnknown newpos) を返す。要するにパターンマッチ時の戻り値と新しい入力の状態（文字の消費後）と新しいキャラクタポインタの位置を含むエラーメッセージを cok 関数でモナドにラッピングして返す。

このことから、tokenPrim 関数がパターンマッチが成功したら文字列を消費して成功の戻り値を返すが、パターンマッチが失敗したら文字の消費はせず、エラー情報のみを返すパーサを作ることが分かる。

ここまでの一連の記事で、

１．ParsecT s u m a パーサがモナドであること

２．do 記法で記述される複数のモナドによるプログラムは bind 演算子によって結び付けられてただ一つのモナド値として扱うことができること。

３．ParsecT s u m a の実体は唯一のフィールドに無名関数 \s cok cerr eok eerr -> ... を収めた ParsecT {unParser :: \s cok cerr eok eerr -> ... } データコンストラクタのデータであること

４．パーサ p のプログラムを実行するのは ParsecT p s 関数であること

５．ParsecT p s 関数はパターンマッチの情報を収めた m (Consumed (m (Reply s u a))) モナドを戻り値として返すこと

６．runP, runParser, runPT, runParserT などの関数は ParsecT 関数の戻り地を加工してそれぞれの目的に使っていること

などを知ることができる。Parsec のモナドが return 関数と >>= 演算子を持つという単純な条件だけで、Parsec のパーサを用いたプログラムがあたかも言語内言語のような働きができるようになるというのは驚くべきことだ。副作用の隔離という目的から IO モナドが作られたのかもしれないが、その目的を超えて、モナドのプログラムに置ける重要性ははるかに大きいものかもしれない。