人気ブログランキング | 話題のタグを見る

Text.Parsec.Prim: parserBind その4

paserBind 関数は ParsecT s u m a モナドの >>= 演算子のプログラムだが、次のように、継続の定義が並んでいるだけで、全く、if 文や case 分が見当たらない。

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

訳が分からなかったので、データの流れを図解してみた。m が ParsecT s u m a モナド値、k が k :: a -> ParsecT s u m b 型のモナド関数、s は State s u 型のパーサ状態 parser state であるとする。目的は、runParsec p s が実行されるときのデータの流れを追うことだ。runParsecT p s の戻り値は m のパターンマッチの結果と、(k x) のパターンマッチの結果の種類で変わってくる。x は m と s によるパターンマッチの際に return x で返される値である。

また、以下のデータの流れを解析する場合は 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
............ }


まず最初に runPasecT が p と s に関数適用される。この時、受け取った p と s と runParsecT 関数の内部で作成された cok, cerr, eok, eerr 継続(関数)が unParser p 関数に渡され、unParser p s cok cerr eok eerr が実行される。

runParsecT -> (p, s, cok, cerr, eok, eerr) -> unParser p s cok cerr eok eerr

parserBind の定義から、unParser p cok cerr eok eerr は次の式と同じだ。

-> unParser m s mcok mcerr meok meerr

この式の値は m と s のパターンマッチの成功の状態で次の4つの場合に分けられる。

1.パターンマッチが成功し、入力文字列が消費される場合。mcok に x s' err が渡される。
2.パターンマッチが失敗するが、入力文字列の消費がある場合。mcerr に err が渡される。
3.パターンマッチが成功するが、入力文字列の消費は起こらない場合。meok に x s' err が渡される。
4.パターンマッチが失敗し、入力文字列の消費も怒らない場合。meerr に err が渡される。

x, s, err のデータ型はそれぞれ a, State s u, ParseError である。

まず1.の m のパターンマッチが成功し、入力文字列の消費が起きた場合につい見てみる。

unParser m s mcok mcerr meok meerr -> (x, s', err) -> mcok

この場合は次の式が評価される。

mcok x s' err -> unParser (k x) s' pcok peer peok peerr

unParser (k x) s' pcok peer peok peer の値は (k x) パーサのマッチが成功し文字列の消費が起きる場合、マッチが失敗し文字列が失敗する場合、マッチが成功するが消費が置きない場合、マッチが失敗し消費も置きない場合の4つに場合分けできる。それぞれ次の関数が評価される。

--> pcok x' s'' err' -> cok x' s'' err'
--> pcerr err' -> cerr err'
--> pecok x' s' err' -> eok x s' (mergeError err err')
--> peerr err' -> eerr (mergeError err err')

2.の m のパターンマッチが失敗し、消費は起きた場合次のような図式ができる。

runParsecT p s
--> unParser m s mcok mcerr meok meerr
----> mcerr err -> cerr err

3.m のパターンマッチが成功し、消費は起きなかった場合の図式は次のようになる。

runParsecT p s
--> unParser m s mcok mcerr meok meerr
----> meok x s err -> unParser (k x) s pcok pcerr peok peerr
--------> pcok x' s' err' -> cok x' s err'.......... (k x) のパタンマッチが成功し消費が起きた場合。
--------> pcerr err' -> cerr err' ................... (k x) のパターンマッチが失敗し、消費は置きた場合。
--------> peok x' s err' -> peok x s err' = eok x s (mergeError err err') ... (k x) のパターンマッチが成功し消費が起きない場合。
--------> peerr err' -> eerr (mergeError err err')...... (k x) のパターンマッチが失敗し、消費も起きない場合。

4.m のパターンマッチが失敗し、消費も起きなかった場合。

runParsecT p s
--> unParser m s mcok mcerr meok meerr
-----> meerr err -> eerr err

こうしてみると parserBind のプログラムは m >>= k のパターンマッチのジェネリック・プログラムになっていることが分かる。どのような m と k の組み合わせについても parserBind 関数のテーブルで処理できる。parserBind のプログラムが処理手順のテーブルになっているのが分かると、この形式のプログラムは可読性も高い。たとえば m のパーサマッチが失敗した場合、>>= k の部分の処理はショートカットされることも parserBind のプログラムを見るだけで分かる。mcerr = cerr と定義されているので、処理が最終的な処理 cerr に引き渡されるからだ。

継続渡しプログラムは抽象的でわかりづらい感じがするが、継続を利用することで parserBind 関数のようなジェネリックプログラムをコンパクトに、可読性も高く作ることができるようだ。


by tnomura9 | 2019-08-03 20:30 | Haskell | Comments(0)
<< Text.Parsec.Pri... Text.Parsec.Pri... >>