Parsec のパーサの値は ParsecT s u m a モナド値

Prelude Text.Parsec> :t string
string :: Stream s m Char => String -> ParsecT s u m String

すなわち、パーサは ParsecT モナドを値として返す。IO モナドに代表されるようにモナドは return 関数と bind 演算子 >>= を使うことができるのが特徴だ。ParsecT モナドも同様に return と >>= が使える。

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

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

したがって,　return 関数と >>= 演算子が Text.Parsec.Prim でどのように定義されているかを理解すればパーサの動作を理解することができる。今回はそのうちの return 関数について調べてみる。

return 関数

return 関数の定義については、Text.Parsec.Prim では return 関数を直接に定義せず、parserReturn 関数を用いて定義している。ParsecT モナドの return はこの parserRetern で定義される。したがって、return = parserReturn である。

parserRetrun 関数の定義は次のようになっている。

parserReturn :: a -> ParsecT s u m a
parserReturn x
   = ParsecT $ \s _ _ eok _ ->
     eok x s (unknownError s)

あっけないほど簡単だ。ParsecT 型のデータの unParser フィールドの中に次の関数を収めるだけだ。

\s _ _ eok _ -> eok x s (unknownError s)

このラムダ記法の関数本体では、eok 関数に parserReturn の引数 x とパーサ状態 s と ParserError (= unknwonError s) の３つのパラメータを渡す。eok 関数はラムダ記法の関数の第４引数に渡された関数型の実引数が使われる。継続渡しスタイルプログラミングの手法だ。

継続渡しスタイルのプログラミングでは、関数を呼び出す側で、呼び出した関数の戻り値の処理を引数として指定できる。

ここで、少々実験をしてみる。parserRturn 関数に "foo" を引数として与え、値を変数 p に束縛してみる。

Parsec> p = parserReturn "foo"
Parsec> :t p
p :: ParsecT s u m [Char]

p が確かに ParsecT s u m [Char] 型のモナド値であることが分かる。このモナド値と入力文字列 "bar" を parseTest 関数にあたえて、パースを実行してみると、parserRetern の引数の "foo" が返されていることが分かる。

Parsec> parseTest p "bar"
"foo"

StateT モナド値 p を用いたパースを直接的に実行するのは runParsecT 関数である。runParsecT 関数はパーサ p とパーサ状態 st を引数として、パースの結果をモナド値で返す。上の p と parsec.ghci に記述されているパーサ状態 st を利用すると、runParsecT 関数をテストできる。

Parsec> :t runParsecT p st
runParsecT p st
  :: Monad m => m (Consumed (m (Reply [Char] () [Char])))

runParsecT がどのようにしてパーサ p の処理をしているかを見るために、ソースコードを示す。

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

runParsecT 関数の処理も非常に単純で、unParser p でパーサ p のフィールドの無名関数を取り出し、そこにパーサ状態 s と runParsecT 関数内で定義した、cok, cerr, eok, eerr を unParser p 関数に渡すだけだ。

パーサ p の unParser フィールドの無名関数は次のようになっているから、

\s _ _ eok _ -> eok x s (unknownError s)

これは、eok 関数を用いて parserRetun x 関数の引数の x とパーサ状態の s それに ParseError の (unknownError s) を戻り値として返している。

eok 関数の実体は次のような関数だ。これは runParsecT の内部で定義されている。

eok a s' err = return . Empty . return $ Ok a s' err

この関数では引数の a (parserRetrun x の引数), s' (パーサ状態 st), err (unknownError s) が Ok データコンストラクタでラッピングされて

Ok a s' err

となる。これは Text.Parsec.Prim モジュールでは Reply s u a 型として定義されている。

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

この Reply s u a 型のデータは、return 関数で内部モナド m にラッピングされ、それは更に Empty コンストラクタによって、Consumed 型にラッピングされる。Consumed 型の定義は次のようになっている。

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

この Consumed 型のデータは更に return 関数で内部モナド m にラッピングされる。parserReturn の unParser フィールドの無名関数では、この eok を用いてこれらの情報を m(Empty(m (OK a s err)) 型のモナド m に変換して戻り値としている。

話がややこしくなったが、もう一度整理してみる parserRetrun 関数に "foo" を与えると、unParser フィールドに無名関数が収められた次のような ParsecT s u m a 型のデータが戻り値として戻される。

ParsecT { unParser = \s _ _ eok _ -> eok "foo" s (unknownError s)}

このモナド値を parseTest 関数に与えると unParser アクセサで取り出された関数 unParser p に状態 s と関数 eok が渡され、m(Empty(m (OK "foo" s err)) が戻り値として返される。parseTest ではそれは更に parseTest 内部で処理され、最終的な parseTest (return "foo") "bar" 関数の戻り値である IO "foo" が戻される。

Prelude Text.Parsec> parseTest (return "foo") "bar"
"foo"

parserRetun "foo" による ParsecT モナドのフィールドの中身が、たった１個の無名関数であるということを理解するとパーサモナドの動作の理解ができるようになる。

フィールドの内容が関数であるデータ型

フィールドのデータが関数になっているデータ型というのはどういう感じなのかが気になったので実験してみた。

Prelude Text.Parsec> data Foo a b = Foo {unPack :: a -> b}
Prelude Text.Parsec> foo = Foo (\x -> x*x)
Prelude Text.Parsec> unPack foo 2
4
Prelude Text.Parsec> bar = Foo ((+10) . (unPack foo))
Prelude Text.Parsec> unPack bar 2
14

引数が関数の場合もやってみた。

Prelude Text.Parsec> data Bar a = Bar {unpack :: a->(a->a)->(a->a)->a}
Prelude Text.Parsec> baz = Bar (\x f g -> f x)
Prelude Text.Parsec> foobar = Bar (\x f g -> g x)
Prelude Text.Parsec> unpack baz 2 (+1) (*2)
3
Prelude Text.Parsec> unpack foobar 2 (+1) (*2)
4

なんか面白い。

複数のモナドを >>= 演算子で繋ぐ操作では、次々にモナド値が作り出されていく。最終的なモナド値のフィールドの無名関数に対し、parseTest 関数が、s, cok, cerr, eok, eerr の実引数をモナド値のunParser フィールドの無名関数に渡し、最終的な値が得られることになる。次回は、モナドとモナドをつなぐ >>= 演算子の仕組みを調べてみる。