parserBind 関数のソース

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

parserBind 関数の型

ソースコードはちょっと長いがトップダウンで見てみる。まず、関数の型だ。

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

これは第１引数が ParsecT モナド値で、第２引数が a -> ParsecT モナド関数だ。戻り値は ParsecT モナド値になる。したがって、関数定義部分の parserBind m k は、m がモナド値で k がモナド関数だ。

モナド関数 k は引数を１個とり、モナド値を返す関数だから、値 x に k を関数適用した k x はモナド値になる。

parserBind の戻り値

parserBind の let 構文は長いが、最終的には次の構文に収束している。

in unParser m s mcok mcerr meok meerr

unParser m というのは ParsecT モナド m の unParser フィールドの無名関数を取り出すという操作を表しているが、これを (unParser m) という関数だと考えると、コードが読みやすい。例えば上の in 構文は (unParser m) s mok mcerr meok meerr という関数が実行されたと考えることができる。

したがって、parserBind 関数の戻り値 p は、次のような ParsecT 型のデータだ。

p = ParsecT { unParer = \s cok cerr eok eerr -> unParser m s mcok
 mcerr meok meerr }

になる。したがって、

(unParser p) s cok cerr eok eerr

を実行するということは、

(unParser m) s mcok mcerr meok meer

を実行することであるということになる。一体 k はどこへ行ってしまったのだろうか。それは let 構文の中を探す必要がある。

(unParser m) 関数の動作

parserBind 関数の動作を考える前に (unParser m) 関数の動作を考えてみる。(unParser m) 関数に s, cok, cerr, eok, eerr を引数として与えたときにどのようなことが起きるのだろうか。

(unParser m) s cok cerr eok eerr

data State s u
  = State {stateInput :: s, statePos :: !SourcePos, stateUser :: !u}
  	-- Defined in ‘Text.Parsec.Prim’

ということは、(unparser m) 関数はこれらの情報を利用できるということだ。

この関数はこれらの情報を利用してパターンマッチを行った後、その処理の結果を４つの場合に分ける。すなわち、パターンマッチ成功と文字列消費あり、パターンマッチ失敗と文字列消費あり、パターンマッチ成功と文字列消費なし、パターンマッチ失敗と文字列消費なしだ。

そうして、それぞれの場合に cok, cerr, eok, eerr のどれかの関数を使って処理を完了する。関数の引数は (unparser m) 関数内で用意する。

例えば parserRetun のコードは次のようになる。

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

これを使って "foo" を返すパーサ p を作る。

Parsec> p = parserReturn "foo"
Parsec> parseTest p "bar"
"foo"

このときモナド値 p の構造は次のようになる。

p = {unParser = \s _ _ eok _ -> eok "foo" s (unkownError s) }

これは、

(unParser p) s cok cerr eok eerr

を実行したときに、

eok "foo" s (unknownError s)

が実行されることを意味する。したがって、(unParser m) 関数の振る舞いは、cok, cerr, eok, eerr のどの関数（継続）が利用されるかを見ると分かる。

(unParser m) s mcok mcerr meok meerr の動作

合成されたモナド p = parserBind m k の振る舞いは、結局次の関数の性質を見ることと同じになる。

(unParser m) s mcok mcerr meok meerr

パターンマッチエラーの場合

まず、エラー処理についてみる。エラー処理は (unParser m) が状態 s に対してエラーを発生させた場合だ。これはモナド m と状態 s との組み合わせではエラーになる場合だ。このときは (unParser m) は mcerr または、merr を呼ぶはずだが、これは (unparser p) のエラー処理と (unParser m) のエラー処理とが同じ結果になることを示している。したがって、mcerr = cerr, meerr = eerr になる。

パターンマッチの最初でエラーが起きるのでそのエラー処理は (unParser m) のエラー処理と同じものになる。したがって、cerr と eerr で良いことになる。

パターンマッチが成功して文字列が消費されない場合

パターンマッチが成功した場合の処理についても考える。これはモナド m と 状態 s でパターンマッチが成功した場合だ。

パターンマッチはパーサ状態 s のフィールドの入力文字列が消費される場合 consumed-ok case と入力文字列が消費されない場合 empty-ok case がある。consumed-ok case と empty-ok case を比べると後者のほうがパーサ状態 s の入力文字列が消費されない分、処理が簡単になる。そこで、empty-ok case のコードを再掲する。

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

meok x s err の x s err はモナド m と状態 s のパターンマッチが成功して入力文字列の消費が起きなかった場合に、(unParser m) 関数から供給される。x はモナド m の return 値、s はパーサ状態、err は ParseError だ。

meok x s err の値は in 構文の

unParser (k x) s pcok pcerr peok peerr

だ。(k x) はこれはリターン値 x にモナド関数 k を関数適用してできるモナド値だ。すなわち、(unParser (k x)) 関数に s pcok pcerr peok peer の引数を与える。これはモナド m の次のモナド (k x) におけるパターンマッチの操作の実体だ。

モナド (k x) と状態 s のパターンマッチの結果は４通りになる。pcok は (k x) と s のパターンマッチが成功し消費が行われたときに呼び出される。m モナドでは消費は起きていないが、(k x) モナドでは消費が起きているので pcok = cok だ。暗にモナド m で発生した ParseError である err はそのまま継承される。(k x) のパターンマッチでは消費が行われ、ParseError は発生しないからだ。

peok が呼ばれるのは (k x) モナドでパターンマッチが成功し、消費が起きない場合だ。(k x) のパターンマッチで新しい ParseError の err' が発生するので、(mergeError err err') でエラーメッセージの結合を行う。pok x s err' は、実際は、eok x s (mergeError err err') が実行される。

pcerr が呼ばれるのは (k x) モナドでパターンマッチが失敗し、消費が起きた場合だ。この場合はエラーメッセージは発生しないので、pcerr = cerr になる。

peerr が呼ばれるのは、(k x) モナドでのパターンマッチが失敗し、消費が起きなかった場合だ。このときは新しいエラーメッセージ err' が発生するので　(mergeError err err') でエラーメッセージの結合をおこなう。eerr (mergeError err err') でマージした ParseError が返される。

パターンマッチが成功して入力文字列が消費される場合

最後にパーサ状態の s の入力文字が m モナドとのパターンマッチで消費される場合だが、コードは次のようになる。

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

mcok x s err の引数 x s err はモナド m でのパターンマッチの際に生成される。

パターンマッチの際に消費が起きた場合は、エラーメッセージの生成は起きないようなので、pcok = pok と pcerr = cerr と処理が単純になる。

peok x s err' の場合は、パターンマッチが成功し、消費が起きない場合だ。このときは、新しいエラーメッセージ err' が発生するので、これをモナド m とのパターンマッチで発生したエラーメッセージとマージするため、cok x s (mergeError err err') が実行される。

peerr err' は (k x) でのパターンマッチが失敗し、消費も起きない場合だ。このときもエラーメッセージをマージし、cerr (mergeError err err') が実行される。

parserBind 関数のデータの流れ

パーサモナドによるパターンマッチの結果とデータの流れをすべての可能性について調べると焦点がわかりにくくなるので、ひとつのデータの流れだけを追跡してみる。

ひとつのデータの流れとは、状態 s と モナド m のパターンマッチが consumed-ok で、このパターンマッチで変化した状態 s' とモナド (k x) とのパターンマッチが consumed-ok の場合である。

また、parserBind 関数で合成されたモナド p を次のように定義する。

p = parserBind m k

このとき、モナド m, (k x), p のパターンマッチは次のように進行していく。

runParsecT p s
= (unParser p) s cok cerr eok eerr 
= (unParser m) s mcok mcerr meok meerr
= mcok x s' err
= (unParser (k x)) s pcok pcerr peok peerr
= pcok x s'' err
= cok x s'' err

データ流れを見ると次のようになる。

まず、runParsecT 関数によって合成モナド p と状態 s のパターンマッチが行われる。

これは、モナド m と状態 s のパターンマッチを行うことと同じで、その時リターン値 x と新しい状態 s' とエラーメッセージ err を発生する。

それらのデータは mcok 継続関数に渡されるが、mcok 関数はモナド (k x) と s' のパターンマッチを遂行し、新しいリターン値 x' と新しい状態 s'' とエラーメッセージ err を発生させる（err メッセージはその前のものをそのまま使う）。

これらは pcok 継続関数に渡すが、pcok = cok であるから、最終的には cok x s'' err がモナド p と状態 s のパターンマッチの結果としてモナドにラッピングされて戻される。

モナド m と モナド (k x) のパターンマッチに従って、３つのデータ x s err が mcok -> pcok -> cok と３つの継続を流れていくのが分かる。