tnomuraのブログ

継続渡しスタイルプログラミングの例２

Text.Parsec.Prim の継続渡しプログラミングの例の続き。

label コンビネータ

label :: ParsecT s u m a -> String -> ParsecT s u m a
label p msg
.. = labels p [msg]

label コンビネータはパーサ p がパターンマッチに失敗したときのエラーメッセージを第２引数のメッセージで置き換える。プログラムは、エラーメッセージを引数として与えたメッセージのリストと置き換える labels コンビネータを利用している。

Prelude Text.Parsec> parseTest digit "foo"
parse error at (line 1, column 1):
unexpected "f"
expecting digit
Prelude Text.Parsec> parseTest (label digit "bar") "foo"
parse error at (line 1, column 1):
unexpected "f"
expecting bar

labels コンビネータ

labels :: ParsecT s u m a -> [String] -> ParsecT s u m a
labels p msgs =
.... ParsecT $ \s cok cerr eok eerr ->
.... let eok' x s' error = eok x s' $ if errorIsUnknown error
.................. then error
.................. else setExpectErrors error msgs
........ eerr' err = eerr $ setExpectErrors err msgs

.... in unParser p s cok cerr eok' eerr'

. where
... setExpectErrors err []........ = setErrorMessage (Expect "") err
... setExpectErrors err [msg]......= setErrorMessage (Expect msg) err
... setExpectErrors err (msg:msgs)
....... = foldr (\msg' err' -> addErrorMessage (Expect msg') err')
......... (setErrorMessage (Expect msg) err) msgs

labels コンビネータはパーサ p がパターンマッチに失敗したときにエラーメッセージを第２引数で与えるメッセージリストと置き換える。ParsecT s u m a パーサのフィールドの無名関数の body 部分が unParser p s cok cerr eok' eerr' になっている。パターンマッチの結果が cok と cerr の場合はパーサ p の結果をそのまま返すが、eok と eerr のときはパターンマッチの結果が eok と eerr ではなく eok' と eerr' に渡される。どちらもパーサ p から返されるパラメータの err を引数として与えたメッセージリストに置き換えている。このことから labels コンビネータはパーサ p から継続に渡されるデータが Empty のときだけ p の動作を変えることが分かる。

Prelude Text.Parsec> parseTest (labels digit ["foo", "bar", "baz"]) "hello"
parse error at (line 1, column 1):
unexpected "h"
expecting bar, baz or foo

Prelude Text.Parsec> parseTest (labels (string "hi") ["foo", "bar", "baz"]) "hello"
parse error at (line 1, column 1):
unexpected "e"
expecting "hi"

try コンビネータ

try :: ParsecT s u m a -> ParsecT s u m a
try p =
.... ParsecT $ \s cok _ eok eerr ->
.... unParser p s cok eerr eok eerr

try コンビネータは引数のパーサ p のパターンマッチの結果が cerr のときのみパラメータを eerr 継続に渡す。cerr の行動を eerr の行動に置き換えることになる。eerr に渡されるパーサ状態はパーサ p のパターンマッチの前の s なので、パーサ位置が変わらず、入力文字列の消費が起きない。

Prelude Text.Parsec> parseTest (string "hi") "hello"
parse error at (line 1, column 1):
unexpected "e"
expecting "hi"

Prelude Text.Parsec> parseTest (try (string "hi")) "hello"
parse error at (line 1, column 1):
unexpected "e"
expecting "hi"

Prelude Text.Parsec> parseTest (string "hi" <|> string "hello") "hello"
parse error at (line 1, column 1):
unexpected "e"
expecting "hi"

Prelude Text.Parsec> parseTest (try (string "hi") <|> string "hello") "hello"
"hello"

lookAhead コンビネータ

lookAhead :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m a
lookAhead p =
....ParsecT $ \s _ cerr eok eerr -> do
........let eok' a _ _ = eok a s (newErrorUnknown (statePos s))
........unParser p s eok' cerr eok' eerr

lookAhead コンビネータでは unParser p s eok' cerr eok' eerr だから、パーサ p のパターンマッチが失敗した場合はパーサ p の cerr eerr 継続がそのまま使われる。cok eok の場合はどちらも eok' 継続が使われる。eok に渡されるパラメータはパーサ状態はパーサ p によるパターンマッチが行われる前のパーサ状態 s でエラーメッセージは UnknownError になる。

Prelude Text.Parsec> parseTest (string "foo" *> getPosition) "foo bar"
(line 1, column 4)
Prelude Text.Parsec> parseTest (lookAhead (string "foo") *> getPosition) "foo bar"
(line 1, column 1)

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."

manyAccum コンビネータはパーサ p が消費マッチする間、パーサ p のパターンマッチを繰り返す。manyAccum acc p で作られるパーサのフィールドの関数の body 部分が unParser p s (walk []) cerr manyErr (e->eok[] s e) なので、パーサ p でパターンマッチした結果が ConsumedOK の場合はパラメータが eok ではなく walk [] に渡される。walk xs x s' _eerr 関数はパターン p の ConsumedOk マッチが繰り返される間再帰的に呼び出されその戻り値の集積が xs に積まれる。最後に EmptyErro になったときパラメータが (\e -> eok (acc x xs) s' e) に渡されて xs の値が eok に戻される。

Prelude Text.Parsec> parseTest (manyAccum (:) letter) "foo bar"
"oof"

"foo" が逆順になっているが、再帰呼出しの結果だ。

この manyAccum を使って、many コンビネータと skipMany コンビネータは定義されている。

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

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

manyAccum acc p の戻り値は ParsecT s u m a モナドなので many と skipMany は do 記法でプログラムできる。実行例は次のようになる。

Prelude Text.Parsec> parseTest (many letter) "hello, world"
"hello"

Prelude Text.Parsec> parseTest (skipMany letter *> getInput) "hello, world"
", world"

updateParserState コンビネータ

updateParserState :: (State s u -> State s u) -> ParsecT s u m (State s u)
updateParserState f =
....ParsecT $ \s _ _ eok _ ->
....let s' = f s
....in eok s' s' $ unknownError s'

updateParserState コンビネータはパーサ状態に関数を適用する。パーサの状態に f を関数適用しそれを eok 継続に渡すだけの動作だ。これを利用して、getParserState, getInput などがプログラムされている。

getParserState :: (Monad m) => ParsecT s u m (State s u)
getParserState = updateParserState id

getInput :: (Monad m) => ParsecT s u m s
getInput = do state <- getParserSta
..............return (stateInput state)

getInput の実行例は次のようになる。

Prelude Text.Parsec> parseTest (getInput) "hello, world"
"hello, world"

Text.Parsec.Prim で使われている継続渡しスタイルプログラミングはこれで全部だ。その他のコンビネータは、コンビネータの戻り値が Parsec s u m a モナドであることを利用して、do 記法でプログラムされている。

継続渡しスタイルプログラミングとひとくくりにすると抽象的でわかりにくいが、要するに、パーサ p は条件の判断と分岐だけを行う抽象的な関数であり、分岐後の処理は、継続（関数）をプログラムすることによって実動するプログラムを作っていくというやり方のようだ。

継続渡しスタイルプログラミングの例

Text.Parsec.Prim モジュールのコンビネータプログラムは、継続渡しスタイルプログラミングでプログラムされている。ParsecT s u m パーサのフィールドの関数が継続渡しスタイルの関数なので、パーサを引数にとり新しいパーサを作るコンビネータのプログラムは、パーサに渡す継続（関数）をプログラムすることで行われる。

継続をプログラムすることで複雑な動作がプログラム可能なのは、parserBind 関数のプログラムが全て継続（関数）のプログラムで行われていることでも分かる。m >>= k のように、パーサ m のパタンマッチの結果をモナド関数 k に渡し、そのリターン値 x を使って (k x) パーサのパターンマッチを行うのも、全て継続をプログラムすることによって実現している。

このように Text.Parsec.Prim モジュールのコンビネータがどのように継続渡しプログラミングスタイルを活用しているかを調べてみた。

unexpected コンビネータ

unexpected :: (Stream s m t) => String -> ParsecT s u m a
unexpected msg
.... = ParsecT $ \s _ _ _ eerr ->
...... eerr $ newErrorMessage (UnExpect msg) (statePos s)

unexpected コンビネータは、引数に State s u m a パーサはとらない。メッセージの文字列を引数にとり、Unexpected エラーメッセージとして返すエラー処理パーサを作る。unexpected コンビネータの作るパーサは err 継続のみを使用し、err に Unexpceted エラーメッセージを渡す。実際の動作は次のようになる。

Prelude> :m Text.Parsec
Prelude Text.Parsec> parseTest (unexpected "hello") "world"
parse error at (line 1, column 1):
unexpected hello

parsecMap コンビネータ

parsecMap :: (a -> b) -> ParsecT s u m a -> ParsecT s u m b
parsecMap f p
.... = ParsecT $ \s cok cerr eok eerr ->
...... unParser p s (cok . f) cerr (eok . f) eerr

parserMap コンビネータは ParsecT s u m モナドの Functor クラスの fmap 関数の本体だ。引数にリターン値を加工する関数 f とパーサ p を取り、パターンマッチが成功した場合に使われる cok と cok 継続を、(cok . f) と (eok . f) に変更している。このため、parserMap コンビネータを適用されたモナドのリターン値は (f x) になる。

Prelude Text.Parsec> parseTest (parsecMap ("hello, " ++) (string "foo")) "foo bar"
"hello, foo"

parserReturn コンビネータ

parserReturn :: a -> ParsecT s u m a

parserReturn x
.... = ParsecT $ \s _ _ eok _ ->
...... eok x s (unknownError s)

Parsec s u m モナドの return 関数の本体だ。引数にモナドのリターン値のみをとる。継続のうち eok だけを用いて、eok 継続にリターン値 x とパーサ状態 s と unknownError エラーを返す。

Prelude Text.Parsec> parseTest (parserReturn "hello") "world"
"hello"

parserBind コンビネータ

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

parserBind m k
.. = ParsecT $ \s cok cerr eok eerr ->
.... let
........ mcok x s err =
............ let
................ pcok = cok
................ pcerr = cerr
................ peok x s err' = cok x s (mergeError err err')
................ peerr err' = cerr (mergeError err err')
............ in..unParser (k x) s pcok pcerr peok peerr
........ meok x s err =
............ let
................ 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
........ mcerr = cerr
........ meerr = eerr

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

ParsecT s u m モナドの >>= 演算子の本体。parserBind 関数については動作が複雑なのと以前の記事でも調べたので読解を省略するが、全て継続のプログラムのみで記述されている。

Prelude Text.Parsec> parseTest (parserBind (string "hello") (\x -> return (x ++ ", world"))) "hello"
"hello, world"

parserFail コンビネータ

parserFail :: String -> ParsecT s u m a
parserFail msg
.... = ParsecT $ \s _ _ _ eerr ->
...... eerr $ newErrorMessage (Message msg) (statePos s)

unexpected コンビネータと同じくエラー終了するパーサを作る。err 継続のみが使われている。eerrr 継続に渡されるエラーは Message 型である。

Prelude Text.Parsec> parseTest (parserFail "hello, world") "foo"
parse error at (line 1, column 1):
hello, world

parserZero コンビネータ

parserZero :: ParsecT s u m a
parserZero
.... = ParsecT $ \s _ _ _ eerr ->
...... eerr $ unknownError s

unexpected コンビネータと同じくエラー終了するパーサを作る。eerr 継続のみが使われている。eerr 継続に渡されるエラーは unknown エラーである。

Prelude Text.Parsec> parseTest (parserZero) "hello"
parse error at (line 1, column 1):unknown parse error

parserPlus コンビネータ

parserPlus m n

.... = ParsecT $ \s cok cerr eok eerr ->
...... let

.......... meerr err =
.............. let
.................. neok y s' err' = eok y s' (mergeError err err')
.................. neerr err' = eerr $ mergeError err err'
.............. in unParser n s cok cerr neok neerrs
...... in unParser m s cok cerr eok meerr

ParsecT s u m モナドの MonadPlus クラスの演算子 <|> の本体。m パーサのパターンマッチが失敗したときだけ n パーサのパターンマッチが行われる。

unParser m s cok cerr eok merr でパターンマッチが行われ。eerr 以外の継続ではそのまま終了するが、eerr が発生したときは、パラメータが meerr に渡される。

merr では unParser n s cok cerr neok neerr でパーサ n のパターンマッチが行われ、eok と eerr 継続が利用される場合に merr と meerr へパラメータが渡される。渡されるパラメータは m パーサと n パーサのパターマッチエラーを合成したものだ。

Prelude Text.Parsec> parseTest (parserPlus (string "foo") (string "bar")) "foo"
"foo"
Prelude Text.Parsec> parseTest (parserPlus (string "foo") (string "bar")) "bar"
"bar"
Prelude Text.Parsec> parseTest (parserPlus (string "foo") (string "bar")) "quux"
parse error at (line 1, column 1):
unexpected "q"
expecting "foo" or "bar"

Text.Parsec.Prim の継続渡しスタイルで記述されたコンビネータはまだまだ続くが今回はここまでにする。

継続渡しスタイルプログラミングの考え方

ParsecT s u m a 型モナド p の構造は次のようになっている。

p = ParsecT { unParser = \s cok cerr eok eerr -> some body function }

このとき、モナド p のフィールドのデータは unParser アクセサで呼び出すことができるので、

unParser p = \s cok cerr eok eerr -> some body function

だ。したがって、パーサ p の働きは上の右辺の無名関数が担っていることになる。この関数がどのような働きをするのかを理解すれば Text.Parsec.Prim モジュールのいろいろなプログラムの意味が分かる。関数の性質を調べるには、引数の性質を調べるのがよい。この関数の引数はパーサ状態 s と継続 cok eerr eok eerr の５つからなっている。まず、パーサ状態 s についてだが、そのデータ構造は次のようになっている。

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

stateInpu フィールドのデータはユーザが与える入力の文字列だ。また、statePos はパーサがパターンマッチを行う位置の情報だ。更に stateUser はユーザ用の状態だ。したがって、パーサ p はこのパーサ状態に対しパターンマッチのテストを行い、その結果によって処理した情報、新しいパーサ位置、ユーザ状態などのデータを返すことになる。

また、この関数の残り４つの引数の値は関数だ。したがってパーサの無名関数は高階関数である。これらの関数はパーサの関数によってパラメータを与えられて呼び出される。パターンマッチの処理の条件分岐によってその後の処理のためにこれらの関数が呼び出されるため、これらの関数は分岐後の処理を担当する「継続」関数である。どの関数が使われるかはパーサの条件分岐にの結果によってパーサ関数の中でプログラムされている。このような形式のプログラムを、継続渡しスタイルプログミングという。

したがって、パーサ関数は、パーサ状態に対してパターンマッチのテストを行い、その条件分岐の結果によって継続の関数に処理を委嘱するという抽象的な動作をする。言い換えると、パーサ関数とは条件のテストと分岐という抽象的な動作のみを行う関数だ。

このようなプログラムの設計のため、パーサ関数のパターンマッチが具体的な値を返すためには、cok cerr eok eerr という継続の変数に外部のプログラムから実引数である関数を渡さなければならない。その継続の実体の関数を渡す働きをしているのが runParsecT 関数で、次のように定義されている。

runParsecT p s = unParser p s cok cerr eok eerr
....where cok a s' err = return . Consumed . return $ Ok a s' err
..........cerr err = return . Consumed . return $ Error err
..........eok a s' err = return . Empty . return $ Ok a s' err
..........eerr err = return . Empty . return $ Error err

この定義で注目すべきは、cok などの継続がどのような引数をとっているかということだ。そこだけを抜き出すと次のようになる。

cok a s' err

cerr err

eok a s' err

eerr err

これらの関数の引数のうち a はリターン値だ。たとえば string "hello" というパターンマッチが成功すれば a = "hello" だ。s’ はパターンマッチの結果として変化したパーサ状態だ。パーサプログラムではパターンマッチが成功した場合に入力文字の先頭からマッチした文字列を消去して次のパターンマッチに備える動作をすることがあり、これを「消費」という。パターンマッチの際にこの消費が行われた場合パターン状態が変化するのでその変化後のパーサ状態が s' だ。err はここでは詳しくは述べないが、パーサ関数で作成する ParseError 型のマッチエラー情報だ。

上の関数の引数をよく見ると、cok と eok は a s' err を受け取るが、cerr と eerr は err のみだ。これはパターンマッチエラーが発生したらそこで処理が中断するので、cerr と eerr は err 情報のみが必要なのである。

パーサ関数の継続は、このように外部から与えられるので、外部から与える継続のプログラムを変えることで、パーサ p には全く手を入れることなくパターンマッチ後の動作をプログラムすることができる。継続渡しスタイルのプログラムは、したがって、引数に渡す継続をプログラムするという形式になるものが多い。

例えば parserRetun 関数は引数の値を ParsecT s u m モナドにラッピングして返すだけの関数だが、次のように定義されている。

parserReturn x = ParsecT $ \s _ _ eok _ -> eok x s (unknownError s)

継続の引数は eok だけしか受け取らずあとは無視するが、それは parserRetun 関数では文字列の消費もなく、また、パターンマッチエラーも発生しないからだ。したがって、この場合のパーサ関数の戻り値は eok x s (unknownError s) になる。parserReturn 関数は ParsecT s u m モナドの return 関数の実体である。

parserBind 関数は ParsecT s u m モナドの >>= 演算子の実体だが次のように、継続のプログラムのみで定義されている。

parserBind m k
..= ParsecT $ \s cok cerr eok eerr ->
....let
........ mcok x s err =
............let
................ pcok = cok
................ pcerr = cerr
................ peok x s err' = cok x s (mergeError err err')
................ peerr err' = cerr (mergeError err err')
............in..unParser (k x) s pcok pcerr peok peerr
........meok x s err =
............let
................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
........mcerr = cerr
........meerr = eerr
....in unParser m s mcok mcerr meok meerr

parserBind については、このブログの以前の記事で詳しく調べたのでここでは述べないが大体の処理の流れを概観すると次のようになる。

1. m >>= k に対し最初に unParser m s mcok mcerr meok meer が実行される。これはパーサ m のパターンマッチが行われその結果が mcok mcerr meok meer のどれかに引き継がれることを示している。

２．例えばパターンマッチが成功し、文字列の消費がおこり、状態が変化した場合のことを考える。このときは mcok に a s' u が渡されるが、mcok = unParser (k x) s pcok pcerr peok peerr であるから、パーサ (k x) のパターンマッチが行われる。(k x) はモナド m のリターン値 x がモナド関数 k に渡され、(k x) というモナドが得られることを示している。モナド (k x) のパターンマッチの結果はその条件分岐によって pcok pcerr peok peerr のどれかに渡され、m >>= k の最終結果が計算されることになる。

３．m パーサと (k x) パーサの起こり得るマッチングの結果は 4 × 4 = 16 通りになるが、上のプログラムはその全ての場合について継続のプログラムのみで対応している。したがって、このプログラムは m と k がどのような値であっても動作する汎用のプログラムである。

継続渡しスタイルのプログラムは、条件分岐のみをプログラムした抽象的プログラムであることが分かれば、その他のパーサコンビネータのソースコードの解読が楽になる。次回からは、Text.Parsec.Prim モジュールに現れたそのような継続渡しプログラムの解読を個々の例についてやってみる。

Text.Parsec.Prim: <?> のソースコード

Text.Parsec.Prim の <?> コンビネータのソースコードは次のようになる。

(<?>) :: (ParsecT s u m a) -> String -> (ParsecT s u m a)
p <?> msg = label p msg

-- | A synonym for @\<?>@, but as a function instead of an operator.
label :: ParsecT s u m a -> String -> ParsecT s u m a
label p msg
.. = labels p [msg]

labels :: ParsecT s u m a -> [String] -> ParsecT s u m a
labels p msgs =
.... ParsecT $ \s cok cerr eok eerr ->
.... let eok' x s' error = eok x s' $ if errorIsUnknown error
.................. then error
.................. else setExpectErrors error msgs
........ eerr' err = eerr $ setExpectErrors err msgs

.... in unParser p s cok cerr eok' eerr'

. where
.. setExpectErrors err [] = setErrorMessage (Expect "") err
.. setExpectErrors err [msg] = setErrorMessage (Expect msg) err
.. setExpectErrors err (msg:msgs)
...... = foldr (\msg' err' -> addErrorMessage (Expect msg') err')
........ (setErrorMessage (Expect msg) err) msgs

<?> コンビネータが label 関数の中置記法であることがつぎのコードから分かる。

p <?> msg = label p msg

また、label 関数は labels 関数を利用している。labels 関数の第２引数に [msg] シングルトンリストを与えるだけだ。

label p msg = labels p [msg]

labels 関数のソースコードをトップダウンで見ると次のようになる。

labels p msgs = ParsecT $ \s cok cerr eok eerr -> unParser p s cok cerr eok' eerr'

ParsecT のフィールドの無名関数の body の部分を抜き出すと、

unParser p s cok cerr eok' eerr'

unPerser p はパーサ p のフィールドの無名関数だから、上の関数はそれにパーサ状態 s と継続 cok cerr eok' eerr' が与えられる。eok', eerr' が let 句で定義されているので、パーサ p のマッチングの結果が Empty Ok のときと、Empty Error のときだけ継続の処理が変わるのが分かる。cok cerr はそのままなので、パーサ p のマッチングの結果が Consumed OK と Consumed Error のときはパーサ p の結果がそのまま返されることが分かる。

eok' のコードは次のようになる。パーサ p のマッチの結果は x s' error が eok' に返される。error がエラーメッセージのない Unkown エラーの場合はそのまま error をかえし、そうでないときは setExpectError error msgs で error のエラーメッセージをエラーメッセージリストの msg で置き換える。x と s' はそのまま eok に渡される。

eok' x s' error = eok x s' $ if errorIsUnknown error
............. then error
............. else setExpectErrors error msgs

eerr' のコードは次のようになる。eerr に setExpectErrors err msgs でエラーメッセージを書き換えた ParseError を渡す。

eerr' err = eerr $ setExpectErrors err msgs

ParseError 型の error のメッセージを書き換える setExpectErrors 関数は次のようになる。パターンを使った定義で、第２引数のメッセージリストが空リスト [] の場合とシングルトンリスト [msg] と要素が２つ以上のリスト (msg:msgs) の３つの場合について定義されている。複数の要素の処理には foldr 畳み込みが使われている。

.. setExpectErrors err [] = setErrorMessage (Expect "") err
.. setExpectErrors err [msg] = setErrorMessage (Expect msg) err
.. setExpectErrors err (msg:msgs)
...... = foldr (\msg' err' -> addErrorMessage (Expect msg') err')
........ (setErrorMessage (Expect msg) err) msgs

ParsecT 関連のプログラムは、トップダウンに調べて、また、継続の変化に注意して読むと分かりやすい。

Text.Parsec.Prim: <?> コンビネータ

Text.Parsec.Prim モジュールの <?> コンビネータはエラーメッセージを差し替える働きがある。digit パーサを普通に使って "foo" とマッチエラーを起こさせると次のようになる。

Prelude Text.Parsec> parseTest digit "foo"
parse error at (line 1, column 1):
unexpected "f"
expecting digit

ところが digit パーサの後に <$> "hello" を続けると、エラーメッセージの expecting digit が expecting hello になってしまう。

Prelude Text.Parsec> parseTest (digit <?> "hello") "foo"
parse error at (line 1, column 1):
unexpected "f"
expecting hello

<?> のソースコードを見ると label コンビネータで定義されている。したがって、上の動作は label p "hello" でも実現できる。

Prelude Text.Parsec> parseTest (label digit "hello") "foo"
parse error at (line 1, column 1):
unexpected "f"
expecting hello

さらに labels コンビネータを使うと、メッセージのリストを使うことができる。

Prelude Text.Parsec> parseTest (labels digit ["hello","world"]) "foo"
parse error at (line 1, column 1):
unexpected "f"
expecting world or hello

Text.Parsec モジュールの概要

Text.Parsec モジュールのソースを手あたり次第に解読していったが、大まかな概要が分かってきたような気がするのでまとめてみる。これを読んでも、ソースをきちんと読まないと動作を理解できるわけではないが、ソース解読を効率的におこなうためのガイドマップになれるかもしれない。

Text.Parsec モジュールを構成する要素で重要なのは ParsecT s u m a モナドと、パーサのパターンマッチを実行する runParsecT 関数、基本的なパースを行うパーサ、それらのパーサを組み合わせて新しいパーサを作るコンビネータの４つの要素だ。これらについて順に概要を述べていく。

ParsecT s u m a モナド

ParsecT モナドの実体は次のようになっている。代数的データ型で、唯一つの unParser という名前のついたフィールドをもち、そのフィールドの中には \s cok cerr eok eerr -> some function という無名関数が収められている。

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

このデータ型は unParser アクセサを使って中の関数を取り出すことができるから、m = ParsecT { unParser = \s cok cerr eok eerr -> some function } で定義サれたパーサ m については、

unParser m s cok cerr eok eerr

という関数と同じものと考えることができる。パーサ m とは unParser m という関数と同じものと考えてもいい。パーサ m とはモナドクラスのインスタンスにできる関数型のデータと考えることができる。ParsecT データコンストラクタにラッピングされているのはこの関数にモナドの演算 rturn と >>= を利用することができるようにする工夫だ。

unParser m 関数の引数 s は State 型のパーサ状態 parser state で、パーサへの入力文字列 parserInpt と パーサ状態の位置 statePos とユーザが使用するユーザ状態 steteUser の３つのデータを保持している。

unParser m の残りの引数 cok cerr eok eerr は関数を受け取る引数で、cok はパーサのマッチが成功してマッチした文字列が入力文字列から生じされた場合の処理をおこなう関数を受け取る。同様に cerr はパーサマッチで文字列が消費されるがパターンマッチは失敗した場合。eok はパーサマッチで入力文字列の消費は行われないがパターンマッチが成功した場合、eerr はパターンマッチで消費も行われるパターンマッチも失敗した場合の処理をおこなう。

このように、関数の処理の結果の処理を、引数としてうけとった（外部の）関数に委嘱するやりかたを、継続渡しスタイルのプログラミングという。関数がファーストオーダーデータとして扱える関数型言語の特徴を利用したプログラムスタイルだ。これはまた、unParser m 関数がパターンマッチの結果を判定するという抽象的な作業しかしていない抽象的プログラムであることを意味している。

ParsecT s u m a 型データは Monad クラスのインスタンスである。したがって、これをモナドとして扱えるので、パーサ m とパーサ関数 k :: a -> ParsecT s u m b からそれらの合成を >>= 演算で作ることができる。すなわち、m >>= k で新しいモナドを合成できる。したがって Monad クラスの return 関数と >>= 演算子がどのように定義されているのかを知ることは重要だ。

runParsecT 関数

unParser m 関数は抽象的関数なので、パーサ状態 s 意外に、継続（関数）cok cerr eok eerr を与えなければ実際のパースを行うことができない。これらの引数を与えるのが runParsecT 関数である。runnParsec 関数は parser (StateT モナド) と state (State) を引数にとり、また、内部で cok cerr eok eerr の４つの継続を作り parser に渡す。

runParsecT parser state = unParser state cok eerr eok eerr

runParsecT 関数の戻り地は上で述べたパターンマッチの４つの可能な結果で異なっており次のようになる。

cok -> m (Consumed (m (Ok x s' err)))

cerr -> m (Consumed (m (Error err)))

eok -> m (Empty (m (Ok x s' err)))

eerr -> m (Empty (m (Error err)))

ここで x は ParsecT モナドのリターン値、s' は新しい State 値、err はパーサで作成されたエラーメッセージだ。

runParsecT は単一のパーサにしか作用しない。パーサが do {many letter; digit} などのような複合的なパーサの場合は、do 記法でプログラムされた複合パーサの最終的なパーサに作用する。つまり、runParsecT 関数は１個のパーサに必要な引数を渡すというような単純な作業しかしていない。

runParsecT はプリミティブなパターンマッチ関数なので、実際には runP (runParser), runPT (runParserT), parse, parseTest などの関数が使われる。これらではいずれも runParserT 関数が内部的に使われている。

基本的なパーサ

Parsec に用意されているパーサは char 'c', letter, digit などの１文字に関するものと、唯一つ文字列にマッチする string "foo" 関数だけだ。また、１文字に関するパーサは全て satisfy 関数を利用することによって定義されている。複雑なパーサはモナドの >>= 演算子を利用するか、後述するパーサコンビネータを利用する。

パーサコンビネータ

基本的なパーサからは、パーサコンビネータを使うことによって、複雑なパーサを作ることができる。たとえば、meny letter で作られたパーサは複数のアルファベットにマッチすることができる。コンビネータとはラムダ計算では自由変数が出現しない式のことを言うが、ここでは複雑なパーサを作る関数という意味合いで使われているようだ。

コンビネータやモナドのバインド演算子によって複雑な動作をするパーサが作られるが、それは複雑な動作をする単一のパーサとして合成される。runParserT 関数にはその単一のパーサが渡されるのである。

以上が、Parsec モジュールのプログラム構造の概略だ。たどり着くまでが大変だったが、まとめてみたのでこれからのソース解読の方向性が見えてきたに思う。Parsec モジュールは大きなモジュールなので簡単には攻略できないし、そのなかに、Haskell のプログラミングを行う上での手本になるようなテクニックがたくさん含まれているので教育的だが、なかなか終わりが見えない。

Text.Parsec.Prim: token

Text.Parsec.Prim には、字句解析の終わったトークンのリスト [(SourcePos, Token)] をパースするパーサを作る token コンビネータが定義されている。解読できないことはないが、Parsec の構文解析は字句解析も含まれているのであまり使う機会がないかもしれないので、用例のプログラムを紹介するだけにする（説明する気力がない）。ソースコードは次のようになる。

ファイル名：token.hs

{-# LANGUAGE FlexibleContexts #-}

module Main where

import Text.Parsec
import Text.Parsec.Prim
import Text.Parsec.Pos
import Data.Functor.Identity

mytoken :: (Stream [(SourcePos,String)] Identity (SourcePos,String)) => String -> Parsec [(SourcePos,String)] u String
mytoken x
..= token showTok posFromTok testTok
..where
....showTok (pos,t) = show t
....posFromTok (pos,t) = pos
....testTok (pos,t) = if x == t then Just t else Nothing

pos0 = initialPos "SourceName"
pos1 = incSourceColumn pos0 1
pos2 = incSourceColumn pos1 1

input = [(pos0,"foo"),(pos1,"bar"),(pos2,"baz")]

foo = mytoken "foo"

main = parseTest foo input

Text.Parsec.Prim: 抽象的プログラム

ParsecT s u m a パーサのフィールドのデータは次のように状態 s と継続 cok cerr eok eerr を引数とする無名関数だ。

\s cok eerr eok eerr -> some function

実のところ、この関数はパターンマッチのテストとその結果の要素的データを返すことしかしていない。それ以後の処理は皆 cok cerr eok eerr のどれかの継続に委嘱してしまう。したがって、実体的な処理は外部からコントロールすることになる。この関数はパターンマッチを行ってその結果を返すという抽象的な処理しかやっていない。

このような抽象的なプログラムは、プログラムの書き直しをせずに色々な用途に利用できるという特徴がある。そこで、簡単な抽象的プログラムを作って実験してみた。次のプログラム foo は値 x と関数 test ok error を引数とする高階関数だ。値 x に関する test を行い test x が真なら ok x を実行し、偽なら err x を実行する。foo はテストと分岐だけを行う抽象的動作しかしない。

Prelude> foo x test ok err = if test x then ok x else err x

foo に何か実体的な動作を行わせるためには、ユーザが foo と ok と err に適当な関数を与える必要がある。

Prelude> foo 3 odd (\x -> "odd") (\x -> "even")
"odd"

戻り値を Maybe 型にすることも可能だ。foo には全く手を入れていない。

Prelude> foo 3 odd (\x -> Just x) (\x -> Nothing)
Just 3

パターンマッチも同じ foo 関数でできる。

Prelude> foo "bar" (=="bar") (\x -> Just x) (\x -> Nothing)
Just "bar"

foo を使った再帰関数も定義できる。

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

foo 関数には何かをテストしてその値に応じて分岐するという抽象的な機能しかないので、逆に、そのパターンにマッチする多種多様なプログラムを記述できる。foo のような抽象関数が記述できるのは、Haskell では引数として関数を与えることができるからだ。

Text.Parsec.Prim: <|> 演算子

Text.Parsec.Prim で <|> 演算子の定義は次のようになっている。

(<|>) :: (ParsecT s u m a) -> (ParsecT s u m a) -> (ParsecT s u m a)
p1 <|> p2 = mplus p1 p2

右辺の mplus は MonadPlus クラスの関数である。Parsec の mplus の定義は次のようになっている。

instance MonadPlus (ParsecT s u m) where
....mzero = parserZero
....mplus p1 p2 = parserPlus p1 p2

-- | @parserZero@ always fails without consuming any input. @parserZero@ is defined
-- equal to the 'mzero' member of the 'MonadPlus' class and to the 'Control.Applicative.empty' member
-- of the 'Control.Applicative.Alternative' class.

parserZero :: ParsecT s u m a
parserZero
....= ParsecT $ \s _ _ _ eerr ->
......eerr $ unknownError s

parserPlus :: ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
{-# INLINE parserPlus #-}
parserPlus m n
....= ParsecT $ \s cok cerr eok eerr ->
......let
..........meerr err =
..............let
..................neok y s' err' = eok y s' (mergeError err err')
..................neerr err' = eerr $ mergeError err err'
..............in unParser n s cok cerr neok neerr
......in unParser m s cok cerr eok meerr

次の MonadPlus クラスのインスタンス宣言を見ると mplus 演算子の本体が parserZero と parserPlus であることが分かる。

instance MonadPlus (ParsecT s u m) where
....mzero = parserZero
....mplus p1 p2 = parserPlus p1 p2

parserZero の定義は次のようになっている。eerr で unkownError を返すだけの関数だ。

parserZero :: ParsecT s u m a
parserZero
....= ParsecT $ \s _ _ _ eerr ->
......eerr $ unknownError s

parserPlus の定義は次のようになる。

parserPlus :: ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
{-# INLINE parserPlus #-}
parserPlus m n
....= ParsecT $ \s cok cerr eok eerr ->
......let
..........meerr err =
..............let
..................neok y s' err' = eok y s' (mergeError err err')
..................neerr err' = eerr $ mergeError err err'
..............in unParser n s cok cerr neok neerr

......in unParser m s cok cerr eok meerr

本体は in .. のところだから、m パーサ（の関数に）s, cok, cerr, eok, merr を渡す。runParsecT からもらうのは s, cok, cerr, eok, eerr だから eerr 継続のところだけが meerr に変わっている。つまり、消費が起きなくてエラーになったとき継続 meerr にerr が渡される。

unParser m s cok cerr eok meerr

merr の in .. の部分は次のようになっている。

unParser n s cok cerr neok neerr

unParser n だから、m がエラーになった場合 merr にのみ次のパーサ n のパターンマッチが行われる。パーサ n でのパターンマッチが成功するが消費が起きない場合 neok 継続が実行される。neok は次のようになっている。runParsecT の eok との違いはパーサ２つ分のエラーメッセージが作成されるところだ。

neok y s' err' = eok y s' (mergeError err err')

パーサ n のパターンマッチも失敗した場合、neerr 継続が実行される。neerr 継続は次のようになっている。

neerr err' = eerr $ mergeError err err'

これも eerr 継続にパーサ m とパーサ n のエラーメッセージをマージしたものを渡すだけだ。

まとめると m <|> n の動作はパーサ m のパターンマッチで消費の発生しない (Empty) エラーが起きた場合のみ次のパーサ n のパターンマッチが行われる。しかし、注意が必要なのはパーサ m のパターンマッチが Empty エラーのときのみ次のパーサ n のパターンマッチが実行されるということだ。"foo" と "baz" のいずれかにマッチさせようと思って次のようにすると成功する。

Prelude Text.Parsec> parseTest (string "foo" <|> string "bar") "bar"
"bar"

しかし、"foo" と "faz" にマッチさせようとするプログラムはエラーになる。

Prelude Text.Parsec> parseTest (string "foo" <|> string "faz") "faz"
parse error at (line 1, column 1):
unexpected "a"
expecting "foo"

これは string "foo" と "faz" のマッチングで cerr 継続が発生してしまうためだ。このようなときは try コンビネータを使って次のようにするとうまくいく。

Prelude Text.Parsec> parseTest (try (string "foo") <|> string "faz") "faz"
"faz"

これも eerr にだけ反応するという <|> の性質を知っていれば戸惑わない。

string "foo" の "faz" に対するパターンマッチが Consumed エラーを返すかどうかは確かめにくいが、次のように parse 関数を利用して parser state を取り出すと確かめることができる。

Prelude Text.Parsec> Right s = parse getParserState "SourceName" "faz"
Prelude Text.Parsec> res = runParsecT (string "foo") s
Prelude Text.Parsec> :t res
res :: Monad m => m (Consumed (m (Reply [Char] () String)))
Prelude Text.Parsec> do {Consumed x <- res; return x}
Prelude Text.Parsec> do {Empty x <- res; return x}
*** Exception: user error (Pattern match failure in do expression at <interactive>:13:5-11)

Text.Parsec.Prim: MonadPlus クラス

Parsec の <|> 演算子は MonadPlus クラスの演算子だ。タイプクラスの演算子はそれぞれ演算法則を満たさなければならない。たとえばモナドの >>= 演算子は次のモナド則を満たしている。

return は >>= に対して、ほとんど単位元である。
....(return x) >>= f ≡ f x
....m >>= return ≡ m
ふたつの関数を続けて bind するのは、これらの関数から決まるひとつの関数を bind することに等しい。
....(m >>= f) >>= g ≡ m >>= ( \x -> (f x >>= g) )

しかし、Monad則を意識してモナドのプログラミングはしない。モナドのプログラムは >>= 演算子が左辺のモナド値のリターン値を右辺のモナド関数の引数に渡すということが分かれば自由にモナドのプログラムができるからだ。つまり、m a がモナド値であったとき >>= はフィールドの a を 右辺の x -> m b 型の関数の変数 x に渡すということを知っていれば十分だ。

<|> 演算子が MonadPlus クラスの演算子であるということは、モナド則のような演算規則が MonadPlus にあるということだ。MonadPlus クラスのインスタンスは、mzero という値と mplus という演算を使うことができる。また、この２つの要素は次のように結合率と左右からの単位元率を満たす。

(a `mplus` b) `mplus` c = a `mplus` (b `mplus` c)
m `mplus` mzero ≡ mzero `mplus` m ≡ m

わかりにくいので Maybe 型が MonadPlus のインスタンスだから実験してみる。Maybe 型の mplus 演算子は左辺の値を残すだけの動作しかしていない。ただし Nothing が左辺にあれば右辺の値を戻す。Maybe 型では mzero == Nothing である。

Prelude Control.Monad> Just 2 `mplus` Just 3
Just 2
Prelude Control.Monad> Nothing `mplus` Just 2
Just 2

Prelude Control.Monad> mzero == Nothing
True

たったこれだけの動作だが次のように結合率と左右からの単位元率を満たす。

Prelude Control.Monad> (Just 2 `mplus` Just 3) `mplus` Just 4
Just 2
Prelude Control.Monad> Just 2 `mplus` (Just 3 `mplus` Just 4)
Just 2
Prelude Control.Monad> mzero `mplus` Just 2
Just 2
Prelude Control.Monad> Just 2 `mplus` mzero

Just 2

この演算法則をどのように利用するのかよくわからない。しかし、Maybe 型は計算が失敗しするかもしれない場合に使われることがあるので、そのような使い方を考えてみる。つまり、次の演算は、mplus の左辺の値が Nothing の場合右辺の値が採用されるので、モナドにおける or 演算子（ショートカットする）であると考えると便利だ。

Prelude Control.Monad> Nothing `mplus` Just 2 `mplus` Just 3
Just 2

Parsec の MonadPlus 演算子の <|> についても Parsec パーサの or 演算子として設計されているようだ。

Prelude Text.Parsec> parseTest (char 'a' <|> char 'b') "baz"
'b'

結論として言えるのは MonadPlus の演算法則には関係なく <|> 演算子は Parsec パーサの or 演算子として使えるのを知っていれば十分ど言うことだ。